Isomap - Wikipedia

Abstraction: Nonlinear dimensionality reduction using geodesic distances on manifold neighborhood graph

Key points:

• Extends metric MDS by using geodesic distance (sum of edge weights along shortest path) rather than straight-line Euclidean distance
• Algorithm: (1) find k-nearest neighbors, (2) build neighborhood graph, (3) compute all-pairs shortest paths via Dijkstra, (4) apply MDS on geodesic distance matrix
• Top n eigenvectors of the geodesic distance matrix give coordinates in n-dimensional Euclidean space
• Landmark Isomap (L-ISOMAP): uses n << N landmark points for faster computation, slight accuracy tradeoff
• Vulnerability: "short-circuit errors" if k is too large; neighborhood graph too sparse if k too small
• Geodesic distance matrix can be viewed as a kernel matrix, linking Isomap to kernel PCA

Connections: Dimensionality Reduction · Manifold Learning · Geodesic Distance · Multidimensional Scaling

Source: http://en.wikipedia.org/wiki/Isomap