[Reading] Nonlinear Dimensionality Reduction by Locally Linear Embedding

This paper introduce locally linear embedding (LLE), an unsupervised learning algorithm that
computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs.
LLE recovers global nonlinear structure from locally linear fits by exploiting the local symmetries of linear reconstructions, thus LLE is able to learn the global structure of nonlinear manifolds.

LLE maps high-dimensional data into a single global coordinate system of lower dimensionality. It constructs a neighborhood-preserving mapping based on reconstructing the constrained weights. By minimize the reconstruction errors, these weights reflect intrinsic geometric properties of the data that are invariant to rotations, rescalings, and translations.

This approach eliminates the need to estimate pairwise distances between widely separated data points. It also avoids the need to solve large dynamic programming problems.