Instance-optimality in probability with an -minimization decoder

Let Φ(ω), ωΩ, be a family of n×N random matrices whose entries _i,j are independent realizations of a symmetric, real random variable η with expectation and variance . Such matrices are used in compressed sensing to encode a vector by y=Φx. The information y holds about x is extracted by using a decoder . The most prominent decoder is the ℓ₁-minimization decoder Δ which gives for a given the element which has minimal ℓ₁-norm among all with Φz=y. This paper is interested in properties of the random family Φ(ω) which guarantee that the vector will with high probability approximate x in to an accuracy comparable with the best k-term error of approximation in for the range kan/log₂(N/n). This means that for the above range of k, for each signal , the vector satisfies

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 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].