Shannon-theoretic limits on noisy compressive sampling

Mehmet Akçakaya, Vahid Tarokh

Research output: Contribution to journalArticlepeer-review

118 Scopus citations


In this paper, we study the number of measurements required to recover a sparse signal in ℤ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 L) measurements are necessary and sufficient for signal recovery, whenever 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. 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.

Original languageEnglish (US)
Article number5361481
Pages (from-to)492-504
Number of pages13
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 2010


  • Compressed sensing
  • Compressive sampling
  • Estimation error
  • Fano's inequality
  • Joint typicality
  • Linear regime
  • Shannon theory
  • Sublinear regime
  • Support recovery


Dive into the research topics of 'Shannon-theoretic limits on noisy compressive sampling'. Together they form a unique fingerprint.

Cite this