Random projections for manifold learning

Chinmay Hegde, Michael B. Wakin, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations

Abstract

We propose a novel method for linear dimensionality reduction of manifold modeled data. First, we show that with a small number M of random projections of sample points in ℝ 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 of random projections required is linear in K and logarithmic in N, meaning that K < M ≪ N. To handle practical situations, we develop a greedy algorithm to estimate the smallest size of the projection space required to perform manifold learning. Our method is particularly relevant in distributed sensing systems and leads to significant potential savings in data acquisition, storage and transmission costs.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference
StatePublished - Dec 1 2009
Event21st Annual Conference on Neural Information Processing Systems, NIPS 2007 - Vancouver, BC, Canada
Duration: Dec 3 2007Dec 6 2007

Other

Other21st Annual Conference on Neural Information Processing Systems, NIPS 2007
CountryCanada
CityVancouver, BC
Period12/3/0712/6/07

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Random projections for manifold learning'. Together they form a unique fingerprint.

Cite this