The Isomap algorithm takes as input the distancesd_{X}(i,j) between all pairs i,j from Ndata points in the high-dimensional input space X, measured either in the standard Euclidean metric (as in Fig. 1A) or in some domain-specific metric (as in Fig. 1B). The algorithm outputs coordinate vectors y_{i} in ad-dimensional Euclidean space Y that (according to Eq. 1) best represent the intrinsic geometry of the data. The only free parameter (ε or K) appears in Step 1.

Step

1

Construct neighborhood graph

Define the graphG over all data points by connecting points i andj if [as measured byd_{X}(i,j)] they are closer than ε (ε-Isomap), or if i is one of theK nearest neighbors of j (K-Isomap). Set edge lengths equal tod_{X}(i,j).

2

Compute shortest paths

Initialized_{G}(i,j) =d_{X}(i,j) ifi,j are linked by an edge;d_{G}(i,j) = ∞ otherwise. Then for each value of k = 1, 2, …,N in turn, replace all entriesd_{G}(i,j) by min{d_{G}(i,j),d_{G}(i,k) +d_{G}(k,j)}. The matrix of final values D_{G} = {d_{G}(i,j)} will contain the shortest path distances between all pairs of points inG (16, 19).

3

Constructd-dimensional embedding

Let λ_{p}be the p-th eigenvalue (in decreasing order) of the matrix τ(D_{G}) (17), andv_{p}^{i} be the i-th component of the p-th eigenvector. Then set the p-th component of the d-dimensional coordinate vectory_{i} equal tov_{p}^{i}.