Nonlinear Dimensionality Reduction by Locally Linear Embedding

Locally Linear Embedding (LLE) is an unsupervised algorithm that maps data points from the original high dimensional space into a low dimensional space.

Dimension reduction is beneficial in several aspect, for example

1. Compact data representation
2. Data visualization
3. Relationship between data points are better described in some particular low dimensional space

The key of this paper is that: given a nonlinear manifold, a local patch of the manifold can be approximated by a hyperplane. The local structure of the patch on the hyperplane is invariant to the projection from the original space to the manifold.

The main assumption, or requirement of the algorithm, is that data points are dense enough that each data point and its neighbors lies in a small patch that can be well approximated by a hyperplane.

So the algorithm can be summarized as followed:

1. Extract local structure information.
   Because local patch can be approximated by hyperplane, each point can be reconstructed by linear combination of its neighbors. Such reconstruction contains local geometry information that is invariant to the projection form the original space to the low dimensional manifold.
2. Projection to the manifold.
   A mapping that preserves the local structure information is found. Finding such mapping can be transformed to a optimization problem with close form solution. It can be solved using linear algebra method.