Instance-optimality in probability with an

Ronald DeVore, Guergana Petrova, Przemyslaw Wojtaszczyk

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


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.
Original languageEnglish (US)
Pages (from-to)275-288
Number of pages14
JournalApplied and Computational Harmonic Analysis
Issue number3
StatePublished - Nov 2009
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUS-C1-016-04
Acknowledgements: This research was supported by the Office of Naval Research Contracts N00014-03-1-0051, N00014-08-1-1113, N00014-03-1-0675, and N00014-05-1-0715; the ARO/DoD Contracts W911NF-05-1-0227 and W911NF-07-1-0185; the NSF Grant DMS-0810869; the Award #KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST); the Polish MNiSW Grant N201 269335; and the Institute for Mathematics and Its Applications.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'Instance-optimality in probability with an'. Together they form a unique fingerprint.

Cite this