[Summary] Nonlinear Dimensionality Reduction by Locally Linear Embedding

Topic: Nonlinear Dimensionality Reduction by Locally Linear Embedding

Author: Roweis & Saul

Summary:

The need to analyze large amounts of multivariate data raises the fundamental problem of dimensionality reduction: how to discover compact representations of high-dimensional data. The paper introduce locally linear embedding (LLE), an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of  high-dimensional inputs.

The problem of mapping high-dimensional inputs into a low-dimensional space with as many coordinates as observed modes of variability.


Locally Linear Embedding (LLE)
Suppose the data consist of N real-valued vectors Xi, each of dimensionality D, sampled from some underlying manifold.
1. Select neighbors

2. Reconstruct with linear weights

Minimizing the cost function subject to two constraints:
Each data point Xi is reconstructed only from its neighbors(Wij=0 if Xj does not belong to the set of neighbors of X).
The rows of the weight matrix sum to one: Sumj(Wij)=1.

3. Map to embedded coordinates
Each high-dimensional observation Xi is mapped to a low-dimensional vector Yi representing global internal coordinates on the manifold. This is done by choosing
d-dimensional coordinates Yi to minimize the embedding cost function



LLE scales well with the intrinsic manifold dimensionality, d, and does not require a
discretized gridding of the embedding space. As more dimensions are added to the embedding space, the existing ones do not change, so that LLE does not have to be rerun to compute higher dimensional embeddings.

Comments:
The proposed method is cool. However, it didn't mention about how to handle the upcoming new data to the system. How can it renew the neighbor relationship of each point and how to choose from the new point's neighborhood(shortest distance?!).