Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 56, Issue 1, Pages 492-504Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2009.2034796
Keywords
Compressed sensing; compressive sampling; estimation error; Fano's inequality; joint typicality; linear regime; Shannon theory; sublinear regime; support recovery
Ask authors/readers for more resources
In this paper, we study the number of measurements required to recover a sparse signal in C-M with L nonzero coefficients from compressed samples in the presence of noise. We consider a number of different recovery criteria, including the exact recovery of the support of the signal, which was previously considered in the literature, as well as new criteria for the recovery of a large fraction of the support of the signal, and the recovery of a large fraction of the energy of the signal. For these recovery criteria, we prove that O(L) ( an asymptotically linear multiple of) measurements are necessary and sufficient for signal recovery, whenever 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. In contrast, the implementation of our proof method would have a higher complexity. We also show that O(L log(M - L)) measurements are required in the sublinear regime (L = o(M)). For our sufficiency proofs, we introduce a Shannon-theoretic decoder based on joint typicality, which allows error events to be defined in terms of a single random variable in contrast to previous information-theoretic work, where comparison of random variables are required. We also prove concentration results for our error bounds implying that a randomly selected Gaussian matrix will suffice with high probability. For our necessity proofs, we rely on results from channel coding and rate-distortion theory.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available