An error analysis on locally linear embedding

Locally linear embedding (LLE) has been proved to an efficient tool for nonlinear dimensionality reduction. It is an unsupervised learning method with various attractive properties, such as few parameters to select and non prone to local minima. However, few works have been done on analyzing learning errors for LLE. In this paper, we conduct an error analysis on the LLE method and show that under what conditions LLE would be able to correctly discover the underlying manifold structure. Besides, we also present reconstruction errors between the local weights in the embedding and the ambient space, which is crucial to the success of LLE.