Nonlinear dimensionality reduction by locally linear embedding

Locally linear embedding (LLE) is an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs.
Unlike clustering methods for local dimensionality reduction, LLE maps its inputs into a single
global coordinate system of lower dimensionality, and its optimizations do not involve local minima.

The problem of nonlinear dimensionality reduction

Black outlines in (B) and (C) show the neighborhood of a single point. 

PCA Map faraway data points to nearby points in the plane, failing to identify the underlying structure of the manifold. 

 Steps of locally linear embedding:
(1) Assign neighbors to each data point Xi  (for example byusing the K nearest neighbors).
(2) Compute the weights Wij that best linearly reconstruct Xi from its neighbors, solving the
constrained least-squares problem

(3) Compute the low-dimensional embedding vectors Yi

For implementations of LLE, the algorithm has only one free parameter: the number of neighbors, K.

Images of faces  mapped into the embedding space described by the first two coordinates of LLE.