Manifold Learning: The Price of Normalization Export

@article{citeulike:5972584, abstract = {We analyze the performance of a class of manifold-learning algorithms that find their output by minimizing a quadratic form under some normalization constraints. This class consists of Locally Linear Embedding (LLE), Laplacian Eigenmap, Local Tangent Space Alignment (LTSA), Hessian Eigenmaps (HLLE), and Diffusion maps. We present and prove conditions on the manifold that are necessary for the success of the algorithms. Both the finite sample case and the limit case are analyzed. We show that there are simple manifolds in which the necessary conditions are violated, and hence the algorithms cannot recover the underlying manifolds. Finally, we present numerical results that demonstrate our claims.}, author = {Goldberg, Yair and Zakai, Alon and Kushnir, Dan and Ritov, Ya'acov}, citeulike-article-id = {5972584}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1390681.1442796}, issn = {1532-4435}, journal = {J. Mach. Learn. Res.}, keywords = {manifold}, pages = {1909--1939}, posted-at = {2009-10-19 21:58:26}, priority = {2}, publisher = {JMLR.org}, title = {Manifold Learning: The Price of Normalization}, url = {http://portal.acm.org/citation.cfm?id=1390681.1442796}, volume = {9}, year = {2008} }

TY - JOUR ID - citeulike:5972584 L3 - citeulike-article-id:5972584 N2 - We analyze the performance of a class of manifold-learning algorithms that find their output by minimizing a quadratic form under some normalization constraints. This class consists of Locally Linear Embedding (LLE), Laplacian Eigenmap, Local Tangent Space Alignment (LTSA), Hessian Eigenmaps (HLLE), and Diffusion maps. We present and prove conditions on the manifold that are necessary for the success of the algorithms. Both the finite sample case and the limit case are analyzed. We show that there are simple manifolds in which the necessary conditions are violated, and hence the algorithms cannot recover the underlying manifolds. Finally, we present numerical results that demonstrate our claims. JF - J. Mach. Learn. Res. SN - 1532-4435 EP - 1939 TI - Manifold Learning: The Price of Normalization PB - JMLR.org VL - 9 SP - 1909 KW - manifold AU - Goldberg, Yair AU - Zakai, Alon AU - Kushnir, Dan AU - Ritov, Ya'acov PY - 2008/// UR - http://portal.acm.org/citation.cfm?id=1390681.1442796 ER -