Theoretical Analysis of LLE Based on Its Weighting Step

Abstract

The local linear embedding algorithm (LLE) is a widely used nonlinear dimension-reducing algorithm. However, its large sample properties are still not well understood. In this article, we present new theoretical results for LLE based on the way that LLE computes its weight vectors. We show that LLE’s weight vectors are computed from the high-dimensional neighborhoods and are thus highly sensitive to noise. We also demonstrate that in some cases LLE’s output converges to a linear projection of the high-dimensional input. We prove that for a version of LLE that uses the low-dimensional neighborhood representation (LDR-LLE), the weights are robust against noise. We also prove that for conformally embedded manifold, the preimage of the input points achieves a low value of the LDR-LLE objective function, and that close-by points in the input are mapped to close-by points in the output. Finally, we prove that asymptotically LDR-LLE preserves the order of the points of a one-dimensional manifold. The Matlab code and all datasets in the presented examples are available as online supplements.

Key Words:

• Dimension reduction
• LDR-LLE
• Locally linear embedding
• Manifold learning

Notes

http://www.cs.toronto.edu/roweis/lle/. The changes in the Matlab function eigs were taken into account.