Nonlinear Dimensionality Reduction by Locally Linear Embedding

Nonlinear Dimensionality Reduction by Locally Linear Embedding
Sam T. Roweis1 and Lawrence K. Saul2
 Science, 2000
======================================================

Locally linear embedding (LLE), an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs.

The figure below is the toy example which shows the dimension reduction from 3-D to 2-D manifold subspace. The structure(neighborhood distance) of the date was kept through the reduction.

Characterize the local geometry of these patches by linear coefficients that reconstruct each data point from its neighbors. Reconstruction errors are measured by the cost function

 

Below is the illustration of the reconstruction, for a given point, select the neighbors and resconstruct with lineat weught and reserve this property in the embedded coordinates.

An common example of face

==================================================

Sumary and Comment:

The main goal of LLE is neighborhood preserving which based on the fundamental manifold properties, preserved the local geometry of each sample and its neighbors. The advantage is it Ignores the global geometry in large scale which could be more efficient than calculate the all pairs distance.

But like many other manifold learning methods, it must assume that the data must be well-sampled and sufficient, and  each sample and its neighbors lie on or closed to a local
linear patch (sub-plane) of the manifold. The assumption might be too strong and cause the method could not be general used in many problems.