Random projections for manifold learning

A powerful data model for many applications is the geometric notion of a low-dimensional manifold.

Data that possess merely K “intrinsic” degrees of freedom can be assumed to lie on a K-dimensional manifold in the N-dimensional ambient space, where K<<N. Once the manifold model is identified, any point on it can be represented using essentially K pieces of information. Thus, algorithms in this vein of dimensionality reduction attempt to learn the structure of the manifold given high dimensional training data. However, in situations where N is large, this requires a good deal of processing power.

On the other hand, the theory of Compressive Sensing enables us to acquire data using the technique of random projections. These random projections are obtained by linear operations on the data, and thus are cheaply computed. Clearly, in many situations it will be less expensive to store, transmit, and process such randomly projected versions
of the sensed data. Interestingly, it can be shown that a small number of such random projections effectively captures the underlying manifold structure of the data. This property can be exploited in many inference tasks such as intrinsic dimension estimation and classification.

Authors: Chinmay Hegde, Mark Davenport, Richard Baraniuk

Publications: Random Projections for Manifold Learning, Random Projections for Manifold Learning: Proofs and Analysis

Related research at Rice