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 vector x = [x(1), ... , x(N)](T) has a randomly generated sparsity pattern, where the i-th entry is non-zero with probability p(i). Given knowledge of these probabilities, the decoder attempts to recover x based on M random noisy projections. Information-theoretic limits on the number of measurements needed to recover the support set of x perfectly 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.