The Johnson-Lindenstrauss Lemma Meets Compressed Sensing

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

88 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/592bcf994c925e65d91a652eb10358ea6275eb3e

How researchers see this paper

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

Citations in the corpus

Compressive Sensing (2008, methodology): “For example, we draw the matrix elements φ j,i as independent and identically distributed (iid) random variables from a zero-mean, 1 /N -variance Gaussian density (white noise) [1, 2, 5].”
Deterministic constructions of compressed sensing matrices (2007, methodology): “Matrices of this type can be constructed using random variables such as Gaussian or Bernouli as their entries (see [ 1 ] for example).”
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit (2007, methodology): “We sketch a new approach due to Baraniuk et al. that combines classical arguments in a clever fashion [ BDDW06 ].”
Compressive Sensing [Lecture Notes] (2007, background): “More specifically, an M × N iid Gaussian matrix = I = can be shown to have the RIP with high probability if M ≥ cK log(N/K) , with c a small constant [1], [2], [4].”
Random Projections of Smooth Manifolds (2009, background): “1 of [2] (and recalling that we assume δ ≤ 1/2), we have that for all a ∈ A, the tangent space Tana has compaction isometry 2 := 2 1, where := denotes equality by definition.”
Compressed Sensing and Redundant Dictionaries (2007, methodology): “(or some other distribution showing certain concentration properties, see below) will have small restricted isometry constants δS with ’overwhelming probability’ as long as n= O(Slog(d/S)), (1.3) see [2, 4, 5, 20] for details. The results for OMP in compressed sensing are weaker than for BP. While i”
Sparsity and incoherence in compressive sampling (2006, background): “This work has shown that taking random measurements is in some sense an optimal strategy for acquiring sparse signals; it requires a near-minimal number of measurements [1, 6, 7, 10, 11]—m measurements can recover signals with sparsity S m/ log(n/m), and all of the constants appearing in the analysi”
Robust Face Recognition via Sparse Representation (2009, methodology): “Random projection has been previously studied as a general dimensionality-reduction method for numerous clustering problems [48]–[50], as well as for learning nonlinear manifolds [51], [52].”
Compressive Radar Imaging (2007, background): “It can be shown that many random measurement matrices are universal in the sense that they are incoherent with any fixed basis Ψ (spikes, sinusoids, wavelets, Gabor functions, curvelets, and so on) with high probability [2], [3], [5].”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, background): “We remark that the same lemma and grid construction also appeared in [12, 51]; [45] contains a weaker form.”