Manifold Learning: The Price of Normalization

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.

Submitted to JMLR

Cited by in corpus (13)

• Schroedinger Eigenmaps for the Analysis of Bio-Medical Data
• Regression on manifolds: Estimation of the exterior derivative
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Manifold Matching using Shortest-Path Distance and Joint Neighborhood Selection
• On the convergence of maximum variance unfolding
• Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
• Selecting the independent coordinates of manifolds with large aspect ratios
• Non-Redundant Spectral Dimensionality Reduction
• A New Method for Performance Analysis in Nonlinear Dimensionality Reduction
• Manifold Learning via Manifold Deflation
• Unsupervised Functional Data Analysis via Nonlinear Dimension Reduction
• An Application of Manifold Learning in Global Shape Descriptors
• LLE with low-dimensional neighborhood representation