Table 1

The Isomap algorithm takes as input the distancesdX (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
1Construct neighborhood graphDefine the graphG over all data points by connecting points i andj if [as measured bydX (i,j)] they are closer than ε (ε-Isomap), or if i is one of theK nearest neighbors of j (K-Isomap). Set edge lengths equal todX (i,j).
2Compute shortest pathsInitializedG (i,j) =dX (i,j) ifi,j are linked by an edge;dG (i,j) = ∞ otherwise. Then for each value of k = 1, 2, …,N in turn, replace all entriesdG (i,j) by min{dG (i,j),dG (i,k) +dG (k,j)}. The matrix of final values DG = {dG (i,j)} will contain the shortest path distances between all pairs of points inG (16, 19).
3Constructd-dimensional embeddingLet λpbe the p-th eigenvalue (in decreasing order) of the matrix τ(DG ) (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 to v p i.