DocumentCode :
3236573
Title :
A single-letter characterization of optimal noisy compressed sensing
Author :
Dongning Guo ; Baron, D. ; Shamai, S.
Author_Institution :
Electr. Eng. & Comput. Sci. Dept., Northwestern Univ., Evanston, IL, USA
fYear :
2009
fDate :
Sept. 30 2009-Oct. 2 2009
Firstpage :
52
Lastpage :
59
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.
Keywords :
error statistics; matrix algebra; mean square error methods; signal denoising; signal representation; belief propagation; error probability; linear measurements; mean squared error; optimal noisy compressed sensing; scalar Gaussian noise; signal reconstruction; single-letter characterization; sparse measurement matrices; sparse representation; Compressed sensing; Computer science; Error probability; Extraterrestrial measurements; Gaussian noise; Lead; Linear systems; Multiaccess communication; Noise measurement; Statistical distributions;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4244-5870-7
Type :
conf
DOI :
10.1109/ALLERTON.2009.5394838
Filename :
5394838
Link To Document :
بازگشت