A Simple Proof of the Restricted Isometry Property for Random Matrices

By Richard Baraniuk, Mark A. Davenport, Ronald A. DeVore, Michael B. Wakin. 2008

2,582 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/8b9b060985fe05362cd350752489213a0d1e3dbd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Learning Sparse Additive Models with Interactions in High Dimensions (2016, background): “While the ﬁrst part is standard (see for example [37]), the second result was stated in [8] as a specialization of Theorem 1.2 from [20] to the case of Bernoulli measurement matrices.”
Kronecker Compressive Sensing (2012, background): “For example, each image frame in a video sequence is often sparse or compressible in a wavelet basis, since it corresponds to an image obtained at a particular time instant.”
Compressive Sensing by Random Convolution (2009, background): “Notice that to have the same result (1.3) as the random waveform case, µ will have to be on the order of 1; we call such Φ′ and Ψ incoherent.”
Compressed Sensing with Coherent and Redundant Dictionaries (2010, neutral): “[38,6]), this would yield an m × n fast transform with optimal number of measurements, m = O(s log n), obeying the D-RIP.”
Texture Classification from Random Features (2012, methodology): “, whose entries are randomly drawn from certain probability distributions [37], specifically including the Gaussian distribution [27], [37], [42].”
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation (2009, background): “1 in [1]), we have‖ASAS − I‖2 ≥ δ with probability at most2(1 + 12/δ) exp(−c0/9nδ(2)) with c0 = 7/18.”
From BoW to CNN: Two Decades of Texture Representation for Texture Classification (2018, background): “The random projection is a fixed, distance-preserving embedding capable of alleviating the curse of dimensionality [11, 69].”
Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, background): “It is an active area of research in random matrix theory to quantify RIP constants e.g. see (Baraniuk et al., 2008).”
Signal representations with minimum ℓ∞-norm (2012, neutral): “, [15]–[17]).”
High-dimensional regression with unknown variance (2011, background): “In an ultra-high-dimensional setting, the form of the minimax risk (nσ 2) is related to the fact that no designs can satisfy Φ2k,−(X)/Φ2k,+(X) ≈ 1; see, for example, [10].”
Signal Processing With Compressive Measurements (2010, background): “2The constants in [29] differ from those in Lemma 2, but the proof is substantially the same, so we provide only a sketch.”
Sparse subspace clustering (2009, methodology): “This is because the rank of the data matrix W is bounded above by 4n. As we want a projection that preserves the sparsity of the data, we use a random projection matrix " . [8, 1 ] show that if we form " by sampling i.i.d entries from a Normal distribution with zero mean and variance 1/m or from i.”