The Noise-Sensitivity Phase Transition in Compressed Sensing

David L. Donoho, Arian Maleki, Andrea Montanari

Consider the noisy underdetermined system of linear equations: y=Ax0 + z0, with n x N measurement matrix A, n < N, and Gaussian white noise z0 ~ N(0,σ^2 I). Both y and A are known,…