# 2009 Research Summary

## Information-Theoretic Limits on Sparse Signal Recovery: Dense Versus Sparse Measurement Matrices

View Current Project Information

Wei Wang, Martin Wainwright and Kannan Ramchandran

National Science Foundation CCF-0635114, National Science Foundation CAREER-CCF-0545862 and National Science Foundation DMS-0605165

We study the information-theoretic limits of exactly recovering the support of a sparse signal using noisy projections defined by various classes of measurement matrices. Our analysis is high-dimensional in nature, in which the number of observations *n*, the ambient signal dimension *p*, and the signal sparsity *k* are all allowed to tend to infinity in a general manner. This project makes two novel contributions. First, we provide sharper necessary conditions for exact support recovery using general (non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields sharp characterizations of when the optimal decoder can recover a signal for various scalings of the sparsity *k* and sample size *n*, including the important special case of linear sparsity (*k* = θ(*p*) using a linear scaling of observations (*n* = θ(*p*)). Our second contribution is to prove necessary conditions on the number of observations *n* required for asymptotically reliable recovery using a class of γ-sparsified measurement matrices, where the measurement sparsity γ(*n*, *p*, *k*) ∈ (0,1] corresponds to the fraction of non-zero entries per row. Our analysis allows general scaling of the quadruplet (*n*, *p*, *k*, γ), and reveals three different regimes, corresponding to whether measurement sparsity has no effect, a minor effect, or a dramatic effect on the information-theoretic limits of the subset recovery problem.

- [1]
- W. Wang, M. J. Wainwright, and K. Ramchandran, "Information-Theoretic Limits on Sparse Support Recovery: Dense Versus Sparse Measurements,"
*IEEE International Symposium on Information Theory*, Toronto, Canada, July 2008.