Instance-optimality in probability with an ℓ1ℓ1-minimization decoder

Let Φ(ω)Φ(ω), ω∈Ωω∈Ω, be a family of n×Nn×N random matrices whose entries ϕi,jϕi,j are independent realizations of a symmetric, real random variable η   with expectation Eη=0Eη=0 and variance Eη2=1/nEη2=1/n. Such matrices are used in compressed sensing to encode a vector x∈RNx∈RN by y=Φxy=Φx. The information y holds about x   is extracted by using a decoder Δ:Rn→RNΔ:Rn→RN. The most prominent decoder is the ℓ1ℓ1-minimization decoder Δ   which gives for a given y∈Rny∈Rn the element Δ(y)∈RNΔ(y)∈RN which has minimal ℓ1ℓ1-norm among all z∈RNz∈RN with Φz=yΦz=y. This paper is interested in properties of the random family Φ(ω)Φ(ω) which guarantee that the vector x¯:=Δ(Φx) will with high probability approximate x   in ℓ2N to an accuracy comparable with the best k  -term error of approximation in ℓ2N for the range k⩽an/log2(N/n)k⩽an/log2(N/n). This means that for the above range of k  , for each signal x∈RNx∈RN, the vector x¯:=Δ(Φx) satisfies‖x−x¯‖ℓ2N⩽Cinfz∈Σk‖x−z‖ℓ2N with high probability on the draw of Φ  . Here, ΣkΣ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/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].