Instance-optimality in probability with an l1-minimization decoder

Let Phi(omega), omega is an element of Omega, be a family of n x N random matrices whose entries Phi(i,j) are independent realizations of a symmetric, real random variable eta with expectation E eta = 0 and variance E eta(2) = 1/n. Such matrices are used in compressed sensing to encode a vector x is an element of R-N by y = Phi x. The information y holds about x is extracted by using a decoder Delta : R-n -> R-N. The most prominent decoder is the l(1)-minimization decoder Delta which gives for a given y is an element of R-n the element Delta(y) is an element of R-N which has minimal l(1)nrm among all Z is an element of R-N with Phi z = y. This paper is interested in properties of the random family Phi(omega) which guarantee that the vector (x) over bar := Delta(Phi x) will with high probability approximate x in l(2)(N) to an accuracy comparable with the best k-term error of approximation in l(2)(N) for the range k <= an/log(2)(N/n). This means that for the above range of k, for each signal x is an element of R-N, the vector (x) over bar:= Delta(Phi x) satisfies parallel to x - (x) over bar parallel to(l2n) <= C inf(z is an element of Sigma k) parallel to x - z parallel to(l2N) with high probability on the draw of Phi. Here, Sigma(k) consists of all vectors with at most k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [R Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math.. in press] who showed this property when eta is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where eta is the Bernoulli random variable which takes the values +/- 1/root n with equal probability. The proofs of our results use geometric mapping properties of such random matrices some of which were recently obtained in [A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005) 491-523]. (C) 2009 Elsevier Inc. All rights reserved.