Optimal phase transitions in compressed sensing with noisy measurements

Yihong Wu, Sergio Verdu

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

Abstract

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. random process. Three classes of encoders are considered, namely, optimal nonlinear, optimal linear and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by the noise sensitivity. The optimal phase-transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase-transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.

Original languageEnglish (US)
Title of host publication2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
Pages1638-1642
Number of pages5
DOIs
StatePublished - Oct 22 2012
Event2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States
Duration: Jul 1 2012Jul 6 2012

Publication series

NameIEEE International Symposium on Information Theory - Proceedings

Other

Other2012 IEEE International Symposium on Information Theory, ISIT 2012
CountryUnited States
CityCambridge, MA
Period7/1/127/6/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Optimal phase transitions in compressed sensing with noisy measurements'. Together they form a unique fingerprint.

  • Cite this

    Wu, Y., & Verdu, S. (2012). Optimal phase transitions in compressed sensing with noisy measurements. In 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012 (pp. 1638-1642). [6283553] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2012.6283553