Instance-optimality in probability with an

Let Φ (ω), ω ∈ Ω, be a family of n × N random matrices whose entries φ{symbol}i, j are independent realizations of a symmetric, real random variable η with expectation E η = 0 and variance E η2 = 1 / n. Such matrices are used in compressed sensing to encode a vector x ∈ RN by y = Φ x. The information y holds about x is extracted by using a decoder Δ : Rn → RN. The most prominent decoder is the ℓ1-minimization decoder Δ which gives for a given y ∈ Rn the element Δ (y) ∈ RN which has minimal ℓ1-norm among all z ∈ RN with Φ z = y. This paper is interested in properties of the random family Φ (ω) which guarantee that the vector over(x, ̄) : = Δ (Φ x) will with high probability approximate x in ℓ2 N to an accuracy comparable with the best k-term error of approximation in ℓ2 N for the range k ≤ a n / log2 (N / n). This means that for the above range of k, for each signal x ∈ RN, the vector over(x, ̄) : = Δ (Φ x) satisfies{norm of matrix} x - over(x, ̄) {norm of matrix}ℓ2N ≤ C under(inf, z ∈ Σk) {norm of matrix} x - z {norm of matrix}ℓ2N with high probability on the draw of Φ. Here, Σk consists of all vectors with at most k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math., in press] who showed this property when η is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where η is the Bernoulli random variable which takes the values ± 1 / sqrt(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]. © 2009 Elsevier Inc. All rights reserved.