Optimal phase transitions in compressed sensing

Yihong Wu, Sergio Verdu

Research output: Contribution to journalArticlepeer-review

88 Scopus citations


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. process with known distribution. 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 error probability and noise sensitivity in the absence and presence of measurement noise, respectively. 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)
Article number6228534
Pages (from-to)6241-6263
Number of pages23
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - 2012

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Compressed sensing
  • Rényi information dimension
  • Shannon theory
  • joint source-channel coding
  • minimum mean-square error (MMSE) dimension
  • phase transition
  • random matrix


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

Cite this