Nonlinear Dimensionality Reduction by Locally Linear Embedding

Title : Nonlinear Dimensionality Reduction by Locally Linear Embedding
Author : S. T. Roweis and L. K. Saul
Year of Publication: 2000

The paper introduces an unsupervised learning algorithm, locally linear embedding(LLE). The following is the steps of locally linear embedding.

1.Find the neighbors of each point which close to a locally linear patch the manifold. (kNN in this paper)
2.Reconstruct each data point from its neighbors with the constrained least-square error.
3.Compute the low-dimensional embedding vector by minimizing the embedded cost function.

In summary, unlike PCA or MDS, LLE succeeds in mapping nearby data points in the low dimensional system. LLE avoids solving large dynamic programming problems and accumulate sparse matrices; consequently, LLE saves a lot of time and space in the computation.

In my opinion, LLE is easy to figure out because of three simple steps. However, the first time I read the paper, I have no idea about what LLE is. That is, the paper seems to organize many research results together and hide the details, so it may expect the readers to have relative background knowledge or survey the references when reading.