The Isomaps work by approximating the geodesic distances between all pairs of points embedded in a non-linear manifold. Such an approximation is summarized in the following steps:
- Compute the Euclidean distances between points that are neighbors in the manifold for all data points(the k-Nearest Neighbors algorithm can be used to find the neighbors). The result of this step is a connected graph with all the neighboring vertices connected to each other. Each edge is labeled with the Euclidean distance between the two points corresponding to the pair of vertices.
- Compute the matrix of distances between points for all points by approximating the true geodesic distances by the sum of distances of the shortest path between two points.
- Use the classic metric MDS_OldKiwi approach to diagonalize the distance matrix and find a lower dimensional projection of the data
Bibliography
- "A Global Geometric Framework for Nonlinear Dimensionality Reduction", J. Tenenbaum, V. de Silva and, J. Langford, Science, Vol 290, Dec 22, 2000.
