Random Projections for Manifold Learning

Part of Advances in Neural Information Processing Systems 20 (NIPS 2007)

Bibtex Metadata Paper Supplemental

Authors

Chinmay Hegde, Michael Wakin, Richard Baraniuk

Abstract

We propose a novel method for {\em linear} dimensionality reduction of manifold modeled data. First, we show that with a small number $M$ of {\em random projections} of sample points in $\reals^N$ belonging to an unknown $K$-dimensional Euclidean manifold, the intrinsic dimension (ID) of the sample set can be estimated to high accuracy. Second, we rigorously prove that using only this set of random projections, we can estimate the structure of the underlying manifold. In both cases, the number random projections required is linear in $K$ and logarithmic in $N$, meaning that $K