Isomap is one of the “oldest” tools for dimensionality reduction. It aims at reproducing geodesic distances (geodesic distances are a property of Riemanian manifolds) on the manifold in an Euclidiean space.

To compute the approximated geodesic distances, a graph is created, an edge linking two close points (K-neighboors or Parzen windows can be used to choose the closest points) with its weight being the Euclidean distance between them. Then, a square matrix is computed with the shortest path between two points with a Dijkstra or Floyd-Warshall algorithm. This follows some distance and Riemanian manifolds properties. The number of points is generally chosen based on the estimated distance on the manifold.

Finally, an classical MDS procedure is performed to get a set of coordinates.

Some results for the SwissRoll :

I reduce this data set with the 8 nearest neighboors (so much more than the 4 that is the least for a 2D reduction) and got this :

The standard deviation for the error of the reduction between the original coordinates and the computed ones (up to an affine transformation) is 4.8% for 2000 points (the norm of the difference between the original coordinates and the reduced set is 3.01).

This is not much, but I will show you in the near future that we can do far better than 4.8%.