Isomap

Isomap is a nonlinear dimensionality reduction technique that aims to uncover the intrinsic geometry of a data set assumed to lie on a low-dimensional manifold embedded in a higher-dimensional space. It was introduced by Joshua B. Tenenbaum, Vin de Silva, and John C. Langford in 2000 as an extension of classical multidimensional scaling (MDS) to non-Euclidean structures. Isomap seeks to preserve the geodesic distances between data points, rather than straight-line Euclidean distances, in the low-dimensional embedding.

The method consists of several steps. First, a neighborhood graph is constructed by connecting each data point to its k nearest neighbors (or to points within an epsilon radius). Edge weights are the Euclidean distances between connected points. Second, the geodesic distance between any pair of points is approximated by the shortest path distance on this graph, typically computed with algorithms such as Floyd–Warshall or Dijkstra. Third, classical MDS is applied to the matrix of these geodesic distances to produce a low-dimensional embedding that preserves the estimated geodesic distances as closely as possible.

Out-of-sample extensions are nontrivial, but various approaches exist, including using the Nyström method or other approximation schemes to embed new points based on their distances to the training set. Isomap is commonly used for data visualization and as a preprocessing step for learning tasks where the data lie on nonlinear manifolds.

Limitations include sensitivity to the choice of neighborhood size, potential “short-circuit” errors when the graph connects points that are not on the same manifold region, noise sensitivity, and high computational cost for large data sets.