TY - GEN

T1 - Random projections for manifold learning

AU - Hegde, Chinmay

AU - Wakin, Michael B.

AU - Baraniuk, Richard G.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85138473721&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85138473721&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85138473721

SN - 160560352X

SN - 9781605603520

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

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

T2 - 21st Annual Conference on Neural Information Processing Systems, NIPS 2007

Y2 - 3 December 2007 through 6 December 2007

ER -