TY - GEN

T1 - A single-letter characterization of optimal noisy compressed sensing

AU - Guo, Dongning

AU - Baron, Dror

AU - Shamai, Shlomo

PY - 2009/12/1

Y1 - 2009/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77949635021&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77949635021&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2009.5394838

DO - 10.1109/ALLERTON.2009.5394838

M3 - Conference contribution

AN - SCOPUS:77949635021

SN - 9781424458714

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

SP - 52

EP - 59

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

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

Y2 - 30 September 2009 through 2 October 2009

ER -