LLE -- Related Work
Nonlinear Dimensionality Reduction
Here are some important algorithms in the history of manifold learning
and nonlinear dimensionality reduction.
- Pairwise distance methods.
Multidimensional scaling (MDS), non-metric MDS, Sammon mapping, etc.
- Linear methods.
Principal component analysis (PCA) or Karhunen Loeve transform (KLT),
singular value decomposition (SVD)
- Topographic maps.
Elastic net, self-organizing maps (SOM), generative topographic
mapping (GTM).
- Principal curves and surfaces.
- Neural network methods.
Nonlinear autoencoders, kernel PCA.
- Isomap.
- Locally Linear Embedding (LLE).
Related groups and research
Notes:
- LLE and other dimensionality reduction/embedding algorithms go
beyond density modeling techniques such as local PCA or mixtures of
factor analyzers. Density models do not provide a consistent set of
global coordinates which embed the observations across the entire manifold;
thus they cannot be used, for example, to visualize low
dimensional projections of the original dataset.
- LLE is doing something very different than finding an embedding which
preserves distances from each point to its nearest neighbours.
Imagine 3 dimensional (or higher) data distributed on a 2 dimensional
square lattice with unit spacing. Colour
the points red/black according to a checkerboard patter. An
embedding which places all the red points at the origin and all the
black points one unit away exactly preserves the distance from each
point to its 4 nearest neighbours but completely destroys the
essential structure of the manifold.
- However, as a follow up to the point above, notice that if, for
each point, you know the distance from the point to its nearest
neighbors AND you also know the pairwise distances between those
neighbors then you can apply LLE. In fact, the weights can be computed
directly from the local distance matrix using a calculation similar to
the one involving the local covariance matrix. For the curious, the
trick is simply to convert the local distance matrix into the local covariance
matrix and then apply the algorithm as usual. The formula is 2Cij =
(Di + Dj - Dij -D0) where Dk is the average of the kth row (or colum)
of D and D0 is the average of all elements in D.
Sam T. Roweis............
roweis at cs dot toronto dot edu ......
www.cs.toronto.edu/~roweis/
Lawrence K. Saul.........
lsaul@research.att.com..........
www.research.att.com/~lsaul/