Page "Nonlinear dimensionality reduction" Paragraph 34

Isomap is a combination of the Floyd – Warshall algorithm with classic Multidimensional Scaling.

Classic Multidimensional Scaling ( MDS ) takes a matrix of pair-wise distances between all points, and computes a position for each point.

With NLDR algorithms like Isomap, however, the pair-wise distances are only known between neighboring points.

So Isomap uses the Floyd – Warshall algorithm to compute the pair-wise distances between all of the other points.

This effectively estimates the full matrix of pair-wise geodesic distances between all of the points.

Isomap then uses classic MDS to compute the reduced-dimensional positions of all the points.