jmlr jmlr2013 jmlr2013-34 jmlr2013-34-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nakul Verma
Abstract: Low dimensional embeddings of manifold data have gained popularity in the last decade. However, a systematic finite sample analysis of manifold embedding algorithms largely eludes researchers. Here we present two algorithms that embed a general n-dimensional manifold into Rd (where d only depends on some key manifold properties such as its intrinsic dimension, volume and curvature) that guarantee to approximately preserve all interpoint geodesic distances. Keywords: manifold learning, isometric embeddings, non-linear dimensionality reduction, Nash’s embedding theorem
R. Baraniuk and M. Wakin. Random projections of smooth manifolds. Foundations of Computational Mathematics (FoCM), 9(1):51–77, 2009. M. Bernstein, V. de Silva, J. Langford, and J. Tenebaum. Graph approximations to geodesics on embedded manifolds. Techical Report, 2000. K. Clarkson. Tighter bounds for random projections of manifolds. Symposium on Computational Geometry (SoCG), 24:39–49, 2008. S. Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. ACM Symposium on Theory of Computing (STOC), pages 537–546, 2008. T. Dey, J. Giesen, S. Goswami, and W. Zhao. Shape dimension and approximation from samples. Symposium on Discrete Algorithms (SODA), pages 772–780, 2002. H. Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418– 491, 1959. J. Giesen and U. Wagner. Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. Symposium on Computational Geometry (SoCG), pages 329–337, 2003. J. Milnor. Topology from the Differential Viewpoint. University of Virginia Press, 1972. J. Nash. C1 isometric imbeddings. Annals of Mathematics, 60(3):383–396, 1954. P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Computational Geometry, 39(1):419–441, 2008. J. Tenebaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000. 2447 V ERMA N. Verma. A note on random projections for preserving paths on a manifold. UC San Diego, Tech. Report CS2011-0971, 2011. R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, Theory and Applications. 2010. H. Whitney. Differentiable manifolds. Annals of Mathematics, 37:645–680, 1936. 2448