Random projections for manifold learning

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

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

    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 - 2009
    Event21st Annual Conference on Neural Information Processing Systems, NIPS 2007 - Vancouver, BC, Canada
    Duration: Dec 3 2007Dec 6 2007

    Publication series

    NameAdvances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference

    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

    Hegde, C., Wakin, M. B., & Baraniuk, R. G. (2009). Random projections for manifold learning. In Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference (Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference).