The Noise-Sensitivity Phase Transition in Compressed Sensing

The Noise-Sensitivity Phase Transition in Compressed Sensing,10.1109/TIT.2011.2165823,IEEE Transactions on Information Theory,David L. Donoho,Arian Ma

The Noise-Sensitivity Phase Transition in Compressed Sensing  
BibTex | RIS | RefWorks Download
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 mean-squared error , and define the ratio as the noise sensitivity. Consider matrices with i.i.d. Gaussian entries and a large-system limit in which with and . We develop exact expressions for the asymptotic MSE of , and evaluate its worst-case 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,includingtheexistenceofgame-theoreticalstruc- tures underlying it (saddlepoints in the payoff, least-favorable 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. 6920-6941, 2011
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.