Compressive Sensing With Prior Information: Requirements and Probabilities of Reconstruction in 𝓁₁- Minimization

Abstract

In compressive sensing, prior information about the sparse representation's support reduces the theoretical minimum number of measurements that allows perfect reconstruction. This theoretical lower bound corresponds to the ideal reconstruction procedure based on <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\ell_0}$</tex> </formula> -minimization, which is not practical for most real-life signals. In this paper, we show that this type of prior information also improves the probability of reconstruction from limited linear measurements when using the more practical <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\ell_1}$</tex> </formula> -minimization procedure, for the same considered stochastic signal. In order to prove this result, we present the necessary and sufficient conditions for signal reconstruction by <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\ell_1}$</tex> </formula> -minimization when using prior information. We then prove that the lower bound for the probability of attaining these conditions increases with the number of support locations in the prior information set, and obtain the expression for the final probability of reconstruction under specific conditions. Our theoretical results are then compared to empirical probabilities obtained by Monte Carlo simulations. Finally, we present numerical reconstructions with and without prior information, as well as a simulation to illustrate how prior information can be used to improve reconstruction, for example, in the context of dynamic magnetic resonance imaging.