## 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.