Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices

Wei Wang, Martin J. Wainwright, Kannan Ramchandran

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 analy…