jmlr jmlr2013 jmlr2013-77 jmlr2013-77-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ery Arias-Castro, Bruno Pelletier
Abstract: Maximum Variance Unfolding is one of the main methods for (nonlinear) dimensionality reduction. We study its large sample limit, providing specific rates of convergence under standard assumptions. We find that it is consistent when the underlying submanifold is isometric to a convex subset, and we provide some simple examples where it fails to be consistent. Keywords: maximum variance unfolding, isometric embedding, U-processes, empirical processes, proximity graphs.
M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(16):1373–1396, 2003. M. Belkin and P. Niyogi. Towards a theoretical foundation for laplacian-based manifold methods. In Peter Auer and Ron Meir, editors, Learning Theory, volume 3559 of Lecture Notes in Computer Science, pages 835–851. Springer Berlin / Heidelberg, 2005. ISBN 978-3-540-26556-6. 1767 A RIAS -C ASTRO AND P ELLETIER M. Bernstein, V. De Silva, J.C. Langford, and J.B. Tenenbaum. Graph approximations to geodesics on embedded manifolds. Technical report, Technical report, Department of Psychology, Stanford University, 2000. M. Brand. Charting a manifold. Advances In Neural Information Processing Systems, pages 985– 992, 2003. A. Brudnyi and Y. Brudnyi. Methods Of Geometric Analysis In Extension And Trace Problems. Volume 1, volume 102 of Monographs in Mathematics. Birkh¨ user/Springer Basel AG, Basel, a 2012. ISBN 978-3-0348-0208-6. D. Burago, Y. Burago, and S. Ivanov. A Course In Metric Geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001. ISBN 0-8218-2129-6. R.R. Coifman and S. Lafon. Diffusion maps. Applied And Computational Harmonic Analysis, 21 (1):5–30, 2006. V. H. de la Pe˜ a and E. Gin´ . Decoupling. Probability and its Applications (New York). Springern e Verlag, New York, 1999. ISBN 0-387-98616-2. From dependence to independence, Randomly stopped processes. U-statistics and processes. Martingales and beyond. D.L. Donoho and C. Grimes. Hessian eigenmaps: Locally linear embedding techniques for highdimensional data. P. Natl. Acad. Sci. USA, 100(10):5591–5596, 2003. H. Federer. Curvature measures. Trans. Amer. Math. Soc., 93:418–491, 1959. ISSN 0002-9947. E. Gin´ and V. Koltchinskii. Empirical graph Laplacian approximation of Laplace-Beltrami e operators: large sample results. In High Dimensional Probability, volume 51 of IMS Lecture Notes Monogr. Ser., pages 238–259. Inst. Math. Statist., Beachwood, OH, 2006. doi: 10.1214/074921706000000888. URL http://dx.doi.org/10.1214/074921706000000888. Y. Goldberg, A. Zakai, D. Kushnir, and Y. Ritov. Manifold learning: the price of normalization. J. Mach. Learn. Res., 9:1909–1939, 2008. ISSN 1532-4435. M. Hein, J.-Y. Audibert, and U. von Luxburg. From graphs to manifolds – weak and strong pointwise consistency of graph laplacians. In Peter Auer and Ron Meir, editors, Learning Theory, volume 3559 of Lecture Notes in Computer Science, pages 470–485. Springer Berlin / Heidelberg, 2005. ISBN 978-3-540-26556-6. W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13–30, 1963. ISSN 0162-1459. A. N. Kolmogorov and V. M. Tikhomirov. ε-entropy and ε-capacity of sets in functional space. Amer. Math. Soc. Transl. (2), 17:277–364, 1961. ISSN 0065-9290. U. Lang and V. Schroeder. Kirszbraun’s theorem and metric spaces of bounded curvature. Geom. Funct. Anal., 7(3):535–560, 1997. ISSN 1016-443X. doi: 10.1007/s000390050018. URL http://dx.doi.org/10.1007/s000390050018. 1768 O N THE C ONVERGENCE OF M AXIMUM VARIANCE U NFOLDING P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39(1):419–441, 2008. ISSN 0179-5376. doi: http://dx.doi.org/10.1007/s00454-008-9053-2. A. Paprotny and J. Garcke. On a connection between maximum variance unfolding, shortest path problems and isomap. In Fifteenth International Conference on Artificial Intelligence and Statistics, 2012. D. Perrault-Joncas and M. Meila. Metric learning and manifolds: Preserving the intrinsic geometry. Technical report, Department of Statistics, University of Washington, 2012. S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000. L.K. Saul, K.Q. Weinberger, J.H. Ham, F. Sha, and D.D. Lee. Semisupervised learning. In B. Schoelkopf, O. Chapelle, and A. Zien, editors, Spectral Methods For Dimensionality Reduction, pages 293–308. MIT Press, 2006. A. Singer. From graph to manifold laplacian: The convergence rate. Applied and Computational Harmonic Analysis, 21(1):128–134, 2006. A.K. Smith, X. Huo, and H. Zha. Convergence and rate of convergence of a manifold-based dimension reduction algorithm. In Proceedings of Neural Information Processing Systems, pages 1529–1536. Citeseer, 2008. J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000. L.J.P. Van der Maaten, E.O. Postma, and H.J. Van den Herik. Dimensionality reduction: A comparative review. Technical report, Tilburg University, 2008. U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. The Annals of Statistics, 36(2):555–586, 2008. K. Q. Weinberger and Lawrence K. Saul. An introduction to nonlinear dimensionality reduction by maximum variance unfolding. In National Conference on Artificial Intelligence (AAAI), volume 2, pages 1683–1686, 2006. K.Q. Weinberger, F. Sha, and L.K. Saul. Learning a kernel matrix for nonlinear dimensionality reduction. In International Confernence on Machine Learning (ICML), page 106, 2004. K.Q. Weinberger, B.D. Packer, and L.K. Saul. Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization. In International Workshop on Artificial Intelligence and Statistics, pages 381–388, 2005. H. Weyl. On the volume of tubes. Amer. J. Math., 61(2):461–472, 1939. ISSN 0002-9327. Q. Ye and W. Zhi. Discrete hessian eigenmaps method for dimensionality reduction. Technical report, Department of Mathematics, University of Kentucky, 2012. 1769 A RIAS -C ASTRO AND P ELLETIER H. Zha and Z. Zhang. Continuum isomap for manifold learnings. Computational Statistics & Data Analysis, 52(1):184–200, 2007. H.Z. Zha and Z. Zhang. Isometric embedding and continuum isomap. In In Proceedings of the Twentieth International Conference on Machine Learning. Citeseer, 2003. Z. Zhang and H. Zha. Principal manifolds and nonlinear dimension reduction via tangent space alignment. SIAM J. Sci. Comput., 26(1):313–338, 2004. 1770