Compressed Sensing With Prior Information: Information-Theoretic Limits and Practical Decoders

This paper considers the problem of sparse signal recovery when the decoder has prior information on the sparsity pattern of the data. The data vectorx=[x1,...,xN]Thas a randomly generated sparsity pattern, where thei-th entry is non-zero with probabilitypi. Given knowledge of these probabilities, the decoder attempts to recoverxbased onMrandom noisy projections. Information-theoretic limits on the number of measurements needed to recover the support set ofxperfectly are given, and it is shown that significantly fewer measurements can be used if the prior distribution is sufficiently non-uniform. Furthermore, extensions of Basis Pursuit, LASSO, and Orthogonal Matching Pursuit which exploit the prior information are presented. The improved performance of these methods over their standard counterparts is demonstrated using simulations.