Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4605346 | Applied and Computational Harmonic Analysis | 2009 | 14 Pages |
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].