Enhancing the fundamental limits of sparsity pattern recovery

Detecting the sparsity pattern or support set of a sparse vector from a small number of noisy linear measurements is a challenging problem in compressed sensing. This paper considers the problem of support recovery when statistical side information is available. From the standard linear and noisy measurement model with arbitrary sensing matrix and Gaussian additive noise and by exploiting the side information, a new linear model is derived which benefits from a larger sample size. The common potential benefits of the increase in the number of samples are revealed. The stability guarantees are then analyzed based on the new model. Two decoding schemes are taken for the support recovery task from the new framework, namely, Maximum Likelihood (ML) and Joint-Typicality (JT) decoding. Performance bounds of the support recovery from the new framework are developed and upper bounds are derived on the error probability of these decoders when they are fed with the prior knowledge which is the statistical properties of the new measurement noise. Finally, an extension is provided for when the noise is non-Gaussian. The results show that with the aid of the prior knowledge and using the new framework one can push the performance limits of the sparsity pattern recovery significantly. The approach is supported by extensive simulations including extension of LASSO to the new framework.