Random Projections of Smooth Manifolds

By Richard Baraniuk, Michael B. Wakin. Foundations of Computational Mathematics, 2009

480 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/202b93afcd3f7bc17bfb305e52bd171ea196760b

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

Compressed Sensing (2014, unknown): “Un segundo tipo de generalización de CS consiste en reemplazar la condición de que la señal buscada es k-esparsa, por la hipótesis de que dicha señal pertenece a una variedad de dimension k [5, 70].”
Distance Preserving Embeddings for General n-Dimensional Manifolds (2012, background): “Perhaps the first algorithmic result for embedding a general n-dimensional manifold is due to Baraniuk and Wakin (2007). They show that an orthogonal linear projection of a well-conditioned n-dimensional manifold M ⊂ R into a sufficiently high dimensional random subspace is enough to approximately p”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, unknown): “As a consequence, the JL Lemma has become a valuable tool for dimensionality reduction in a myriad of applications ranging from computer science [26], numerical linear algebra [36, 23, 18], manifold learning [6], and compressed sensing [7], [40], [10].”
Robust Face Recognition via Sparse Representation (2009, methodology): “Random projection has been previously studied as a general dimensionality-reduction method for numerous clustering problems [47], [48], [49], as well as for learning nonlinear manifolds [50], [51].”
Signal Processing With Compressive Measurements (2010, unknown): “This formulation can sometimes be more convenient.”
Learning Sparse Representations for Human Action Recognition (2012, background): “Recently, Random Projection (RP) has emerged as a powerful tool in dimensionality reduction [25].”
Robust Compressed Sensing MRI with Deep Generative Priors (2021, background): “[11] Richard G Baraniuk and Michael B Wakin.”
GAN-Based Projector for Faster Recovery With Convergence Guarantees in Linear Inverse Problems (2019, background): “It has been shown in [2] that a random matrix A with orthonormal rows will satisfy this condition with high probability for m roughly linear in dimension k with log factors dependent on the properties of the manifold, in this case, R(G).”
Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces (2009, background): “The measures on A i are assumed to be such that all subsets of A i of dimension less than i are of measure zero 3 .”
The smashed filter for compressive classification and target recognition (2007, methodology): “Subsequently, the classifier in (3) can be interpreted as a “nearest-manifold” search from y to each of the Mi.”
Compressed Sensing using Generative Models (2017, background): “A related result appears in [5], which studies the measurement complexity of an RIP condition for smooth manifolds.”
Single-pixel imaging via compressive sampling (2008, background): “The smashed filter exploits a recent result that the structure of a smooth K-dimensional manifold in RN is preserved with high probability under a random projection to the lower dimensional space RM as long as M = O(K log N ) [21].”
Spectral compressive sensing (2013, background): “While such classes of signals are well suited for manifold models when the signal consists of a known number of parameterized components [27, 28], they fall short for arbitrary linear combinations of a varying number of components; in this case, we must estimate both the model order (number of compo”
Statistical mechanics of complex neural systems and high dimensional data (2013, background): “[104, 105, 106] show that M > O( δ2 logNC) random projections preserve the geometry of the manifold up to distortion δ.”