Random projections of smooth manifolds

Richard G. Baraniuk, Michael B. Wakin

Research output: Contribution to journalArticlepeer-review

243 Scopus citations

Abstract

We propose a new approach for nonadaptive dimensionality reduction of manifold-modeled data, demonstrating that a small number of random linear projections can preserve key information about a manifold-modeled signal. We center our analysis on the effect of a random linear projection operator Φ: NM , M<N, on a smooth well-conditioned K-dimensional submanifold N . As our main theoretical contribution, we establish a sufficient number M of random projections to guarantee that, with high probability, all pairwise Euclidean and geodesic distances between points on are well preserved under the mapping Φ. Our results bear strong resemblance to the emerging theory of Compressed Sensing (CS), in which sparse signals can be recovered from small numbers of random linear measurements. As in CS, the random measurements we propose can be used to recover the original data in N . Moreover, like the fundamental bound in CS, our requisite M is linear in the "information level" K and logarithmic in the ambient dimension N; we also identify a logarithmic dependence on the volume and conditioning of the manifold. In addition to recovering faithful approximations to manifold-modeled signals, however, the random projections we propose can also be used to discern key properties about the manifold. We discuss connections and contrasts with existing techniques in manifold learning, a setting where dimensionality reducing mappings are typically nonlinear and constructed adaptively from a set of sampled training data.

Original languageEnglish (US)
Pages (from-to)51-77
Number of pages27
JournalFoundations of Computational Mathematics
Volume9
Issue number1
DOIs
StatePublished - Feb 2009

Keywords

  • Compressed sensing
  • Dimensionality reduction
  • Johnson-Lindenstrauss lemma
  • Manifold learning
  • Manifolds
  • Random projections
  • Sparsity

ASJC Scopus subject areas

  • Analysis
  • Applied Mathematics
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Random projections of smooth manifolds'. Together they form a unique fingerprint.

Cite this