A single-letter characterization of optimal noisy compressed sensing

Dongning Guo*, Dror Baron, Shlomo Shamai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

77 Scopus citations

Abstract

Compressed sensing deals with the reconstruction of a high-dimensional signal from far fewer linear measurements, where the signal is known to admit a sparse representation in a certain linear space. The asymptotic scaling of the number of measurements needed for reconstruction as the dimension of the signal increases has been studied extensively. This work takes a fundamental perspective on the problem of inferring about individual elements of the sparse signal given the measurements, where the dimensions of the system become increasingly large. Using the replica method, the outcome of inferring about any fixed collection of signal elements is shown to be asymptotically decoupled, i.e., those elements become independent conditioned on the measurements. Furthermore, the problem of inferring about each signal element admits a single-letter characterization in the sense that the posterior distribution of the element, which is a sufficient statistic, becomes asymptotically identical to the posterior of inferring about the same element in scalar Gaussian noise. The result leads to simple characterization of all other elemental metrics of the compressed sensing problem, such as the mean squared error and the error probability for reconstructing the support set of the sparse signal. Finally, the single-letter characterization is rigorously justified in the special case of sparse measurement matrices where belief propagation becomes asymptotically optimal.

Original languageEnglish (US)
Title of host publication2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009
Pages52-59
Number of pages8
DOIs
StatePublished - Dec 1 2009
Event2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009 - Monticello, IL, United States
Duration: Sep 30 2009Oct 2 2009

Publication series

Name2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009

Other

Other2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009
CountryUnited States
CityMonticello, IL
Period9/30/0910/2/09

ASJC Scopus subject areas

  • Computer Science(all)
  • Control and Systems Engineering
  • Communication

Fingerprint Dive into the research topics of 'A single-letter characterization of optimal noisy compressed sensing'. Together they form a unique fingerprint.

Cite this