Roweis, Saul, 2000

Summary

ISOMAP and MDS require estimates of pairwise distances between data points. LLE gets around this by “thinking” globally but fitting locally. Essentially, each data point should hypothetically be representable by a locally linear patch. Therefore, LLE seeks $W$ such that

\[E(W) = \sum_i \| X_i - \sum_j W_{ij} X_j \|^{2}\]

is minimized. Hence, a data point should be reconstructed by its neighbors; the problem is solved via least squares. Note that the weights are invariant to affine transformations and translations. Assuming that $W$ should be preserved in a lower dimensional representation of the data, LLE seeks to solve

\[\Phi (Y) = \sum_i \| Y_i - \sum_j W_{ij} Y_j \|^{2}\]

The optimal coordinates $Y$ can be found by solving a sparse $n \times n$ eigenvalue problem.

  • Because of the simple construction and use of simple linear algebra, LLE has better theoretical properties than other algorithms like autoencoders
  • It also has less hyperparameters
  • Doesn’t need to be rerun when new dimensions are added to the embedding space (old ones do not change)
  • Does LLE work on spheres? It seems like it would run into the same problem if the sphere didn’t have a hole taken out of it