Random projections of smooth manifolds
type: Item
instance of: scholarly article
title: Random projections of smooth manifolds
zbMATH Open document ID: 1172.53005
author: Richard G. Baraniuk
author: Michael B. Wakin
published in: Foundations of Computational Mathematics
publication date: 2009-07-13T00:00:00Z
full work available at URL: http://hdl.handle.net/1911/19724
review text: Consider a compact \(K\)-dimensional Riemannian submanifold \({\mathcal M} \subset\mathbb R^N\) and denote by \(\Phi\) a random orthoprojection operator from \(\mathbb R^N\) onto \(\mathbb R^M\). The main theorem of this article states that with probability at least \(1-\rho\) the distance (or geodesic distance) between any two points \(x\), \(y\in{\mathcal M}\) is roughly preserved by \(\Phi\) provided \[ M = O\biggl(\frac{K \log(NVR\tau^{-1}\varepsilon^{-1})\log(1/\rho)}{\varepsilon^2}\biggr) \leq N. \] In this formula \(V\) is the volume of \({\mathcal M}\), \(R\) its geodesic covering regularity, and \(1/\tau\) its condition number. The positive real \(\varepsilon\) determines the desired accuracy of length preservation. An explicit bound (not just the order of magnitude) for \(M\) can be extracted from the proof. This result is similar to a theorem by Johnson and Lindenstrauss on distance preservation under random orthoprojections of a finite point cloud. The article also contains an introduction to applications of ``dimension reduction techniques'' in general and a discussion of ideas for the application of the above result in the context of compressed sensing and manifold learning.
reviewed by: Hans-Peter Schröcker
Mathematics Subject Classification ID: 53A07
Mathematics Subject Classification ID: 62H99
Mathematics Subject Classification ID: 65C99
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 94A12
Mathematics Subject Classification ID: 94A29
zbMATH DE Number: 5577664
zbMATH Keywords: manifolds
zbMATH Keywords: dimensionality reduction
zbMATH Keywords: random projection
zbMATH Keywords: compressed sensing
zbMATH Keywords: sparsity
zbMATH Keywords: manifold learning
zbMATH Keywords: Johnson-Lindenstrauss lemma
MaRDI profile type: Publication
OpenAlex ID: W1986736933
Wikidata QID: Q125259994
cites work: A simple proof of the restricted isometry property for random matrices
cites work: Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
cites work: A New Approach to Dimensionality Reduction: Theory and Algorithms
cites work: The Whitney reduction network: A method for computing autoassociative graphs
cites work: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
cites work: Stable signal recovery from incomplete and inaccurate measurements
cites work: Decoding by Linear Programming
cites work: The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
cites work: Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
cites work: Diffusion wavelets
cites work: Geodesic Entropic Graphs for Dimension and Entropy Estimation in Manifold Learning
cites work: An elementary proof of a theorem of Johnson and Lindenstrauss
cites work: Compressed sensing
cites work: For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
cites work: High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
cites work: Neighborliness of randomly projected simplices in high dimensions
cites work: On the stability of the basis pursuit in the presence of noise
cites work: Image manifolds which are isometric to Euclidean space
cites work: Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
cites work: Counting faces of randomly projected polytopes when the projection radically lowers dimension
cites work: Signal Reconstruction From Noisy Random Projections
cites work: Nearest-neighbor-preserving embeddings
cites work: Q4320142
cites work: Q4488070
cites work: Finding the homology of submanifolds with high confidence from random samples
cites work: Multiscale Representations for Manifold-Valued Data
cites work: Q5471272
cites work: Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment
DOI: 10.1007/S10208-007-9011-Z
description: scientific article; zbMATH DE number 5577664