Online Program

Isomap Revisited (308520)

Keywords: Manifold learning, nonlinear dimension reduction, convergence analysis.

The Isomap procedure for manifold learning (1) uses points on a compact Riemannian manifold M to construct a graph G, (2) approximates geodesic distance on M with shortest path distance (SPD) on G, and (3) approximates SPD with Euclidean distance. Isomap has been criticized on the grounds that it only succeeds for manifolds that possess “geodesic convexity”. This criticism originated in the convergence analysis that accompanied its introduction, and in several examples of its use. However, careful examination of the analysis suggests that geodesic convexity is not needed to show that SPD converges to geodesic distance as M is more densely sampled. Moreover, examples of Isomap distorting non-convex regions are better understood as interpretable Euclidean representations of non-Euclidean geometries. We present a new convergence analysis and several examples to support our contention that Isomap is a reasonable procedure under more general conditions than previously believed.