Optimal Phase Transitions in Compressed Sensing

DOI10.1109/TIT.2012.2205894MaRDI QIDQ2989726zbMATH OpenFDO

Authors Yihong Wu, Sergio Verdú

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.6822

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Sampling theory in information and communication theory (94A20)

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

Recommendations

• On the Error in Phase Transition Computations for Compressed Sensing
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• Phase transitions in error correcting and compressed sensing by \(\ell _{1}\) linear programming
• The quest for optimal sampling: computationally efficient, structure-exploiting measurements for compressed sensing
• Near-Optimal Adaptive Compressed Sensing
• Phase Transitions in Recovery of Structured Signals From Corrupted Measurements
• From compression to compressed sensing
• Compressed sensing

Cited in

(5)

• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• Analysis of sparse recovery algorithms via the replica method
• Phase Transitions in Recovery of Structured Signals From Corrupted Measurements
• Large dimensional analysis of general margin based classification methods
• From compression to compressed sensing

This page was built for publication: Optimal Phase Transitions in Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989726)