Shannon Theoretic Limits on Noisy Compressive Sampling

Abstract

In this paper, we study the number of measurements required to recover a sparse signal in ${\mathbb{C}}^M$ with $L$ non-zero coefficients from compressed samples in the presence of noise. For a number of different recovery criteria, we prove that $O(L)$ (an asymptotically linear multiple of $L$) measurements are necessary and sufficient if $L$ grows linearly as a function of $M$. This improves on the existing literature that is mostly focused on variants of a specific recovery algorithm based on convex programming, for which $O(L\log (M-L))$ measurements are required. We also show that $O(L\log (M-L))$ measurements are required in the sublinear regime ($L=o(M)$).

21 pages, submitted

References in corpus (1)

• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting

Cited by in corpus (1)

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