Manifold learning: the price of normalization. (English) Zbl 1225.68181

Summary: 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.


68T05 Learning and adaptive systems in artificial intelligence
68Q32 Computational learning theory
Full Text: arXiv Link