Skip to main content

Shannon-theoretic limits on noisy compressive sampling

Publication ,  Journal Article
Akçakaya, M; Tarokh, V
Published in: IEEE Transactions on Information Theory
January 1, 2010

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. © 2009 IEEE.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

January 1, 2010

Volume

56

Issue

1

Start / End Page

492 / 504

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Akçakaya, M., & Tarokh, V. (2010). Shannon-theoretic limits on noisy compressive sampling. IEEE Transactions on Information Theory, 56(1), 492–504. https://doi.org/10.1109/TIT.2009.2034796
Akçakaya, M., and V. Tarokh. “Shannon-theoretic limits on noisy compressive sampling.” IEEE Transactions on Information Theory 56, no. 1 (January 1, 2010): 492–504. https://doi.org/10.1109/TIT.2009.2034796.
Akçakaya M, Tarokh V. Shannon-theoretic limits on noisy compressive sampling. IEEE Transactions on Information Theory. 2010 Jan 1;56(1):492–504.
Akçakaya, M., and V. Tarokh. “Shannon-theoretic limits on noisy compressive sampling.” IEEE Transactions on Information Theory, vol. 56, no. 1, Jan. 2010, pp. 492–504. Scopus, doi:10.1109/TIT.2009.2034796.
Akçakaya M, Tarokh V. Shannon-theoretic limits on noisy compressive sampling. IEEE Transactions on Information Theory. 2010 Jan 1;56(1):492–504.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

January 1, 2010

Volume

56

Issue

1

Start / End Page

492 / 504

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing