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

Citation data:

Applied and Computational Harmonic Analysis, ISSN: 1063-5203, Vol: 27, Issue: 3, Page: 275-288

Publication Year:
Usage 286
Abstract Views 285
Link-outs 1
Captures 42
Readers 40
Exports-Saves 2
Citations 35
Citation Indexes 35
Repository URL:;
DeVore, Ronald; Petrova, Guergana; Wojtaszczyk, Przemyslaw
Elsevier BV
Mathematics; ℓ1-minimization decoder; Compressed sensing; Instance-optimality in probability
article description
Let Φ(ω), ω∈Ω, be a family of n×N random matrices whose entries ϕ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 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). This means that for the above range of k, for each signal x∈RN, the vector x¯:=Δ(Φx) satisfies ‖x−x¯‖ℓ2N⩽Cinfz∈Σk‖x−z‖ℓ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/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].