Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(13)
Approximate Algorithm
Approximation Method
Basis Pursuit
Compressed Sensing
Computer Experiment
Linear Equations
Mean Square Error
Message Passing
Minimax Risk
Noise Measurement
Phase Space
Gaussian White Noise
Phase Transition
Subscribe
Academic
Publications
The NoiseSensitivity Phase Transition in Compressed Sensing
The NoiseSensitivity Phase Transition in Compressed Sensing,10.1109/TIT.2011.2165823,IEEE Transactions on Information Theory,David L. Donoho,Arian Ma
Edit
The NoiseSensitivity Phase Transition in Compressed Sensing
BibTex

RIS

RefWorks
Download
David L. Donoho
,
Arian Maleki
,
Andrea Montanari
Consider the noisy underdetermined system of linear equations: , with an measurement matrix, , and a Gaussian white noise. Both and are known, both and are unknown, and we seek an approx imation to . When has few nonzeros, useful approximations are often obtained by penalized minimization, in which the reconstruction solves . Consider the reconstruction meansquared error , and define the ratio as the noise sensitivity. Consider matrices with i.i.d. Gaussian entries and a largesystem limit in which with and . We develop exact expressions for the asymptotic MSE of , and evaluate its worstcase noise sensitivity over all types of sparse signals. The
phase space
is partitioned by the curve into two regions. Formal noise sensitivity is bounded throughout the region and is unbounded throughout the region . The phase boundary is identical to the previously known
phase transition
curve for equivalence of minimiza tion in the sparse noiseless case. Hence, a single phase boundary describes the fundamental phase transitions both for the noise less and noisy cases. Extensive computational experiments validate thesepredictions,includingtheexistenceofgametheoreticalstruc tures underlying it (saddlepoints in the payoff, leastfavorable sig nals and maximin penalization). Underlying our formalism is an approximate
message passing
soft thresholding algorithm (AMP) introduced earlier by the au thors.Otherpapersbytheauthorsdetailexpressionsfortheformal MSE of AMP and its close connection to penalized reconstruc tion. The focus of the present paper is on computing the minimax formal MSE within the class of sparse signals .
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 10, pp. 69206941, 2011
DOI:
10.1109/TIT.2011.2165823
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
References
(32)
Compressed Sensing: How Sharp Is the Restricted Isometry Property?
(
Citations: 2
)
Jeffrey D. Blanchard
,
Coralia Cartis
,
Jared Tanner
Published in 2011.
The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
(
Citations: 7
)
Mohsen Bayati
,
Andrea Montanari
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 2, pp. 764785, 2011
A Fast Iterative ShrinkageThresholding Algorithm for Linear Inverse Problems
(
Citations: 197
)
Amir Beck
,
Marc Teboulle
Journal:
Siam Journal on Imaging Sciences  SIAM J IMAGING SCI
, vol. 2, no. 1, pp. 183202, 2009
An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
(
Citations: 593
)
Ingrid Daubechies
,
Michel Defrise
,
Christine De Mol
Journal:
Communications on Pure and Applied Mathematics  COMMUN PURE APPL MATH
, vol. 57, no. 11, pp. 14131457, 2004
Atomic Decomposition by Basis Pursuit
(
Citations: 1960
)
Scott Shaobing Chen
,
David L. Donoho
Journal:
Siam Journal on Scientific Computing
, vol. 20, no. 1, 1998