Stability and Instance Optimality for Gaussian Measurements in Compressed Sensing

In compressed sensing, we seek to gain information about a vector xaa"e (N) from d a parts per thousand(a) N nonadaptive linear measurements. Candes, Donoho, Tao et al. (see, e.g., Candes, Proc. Intl. Congress Math., Madrid, 2006; Candes et al., Commun. Pure Appl. Math. 59:1207-1223, 2006; Donoho, IEEE Trans. Inf. Theory 52:1289-1306, 2006) proposed to seek a good approximation to x via a"" (1) minimization. In this paper, we show that in the case of Gaussian measurements, a"" (1) minimization recovers the signal well from inaccurate measurements, thus improving the result from Candes et al. (Commun. Pure Appl. Math. 59:1207-1223, 2006). We also show that this numerically friendly algorithm (see Candes et al., Commun. Pure Appl. Math. 59:1207-1223, 2006) with overwhelming probability recovers the signal with accuracy, comparable to the accuracy of the best k-term approximation in the Euclidean norm when k similar to d/ln N.