Isomap: Isometric Feature Mapping

Imagine you're standing on the surface of the Earth and want to measure the distance between two cities—say, New York and Tokyo. You could draw a straight line through the Earth (the Euclidean distance), but that line passes through molten rock and is completely irrelevant for any practical purpose. What matters is the shortest path along the surface—the geodesic distance.

This seemingly simple observation has profound implications for machine learning. When data lies on a curved manifold embedded in high-dimensional space, Euclidean distances can be catastrophically misleading. Two points that appear close in ambient space might actually be far apart when measured along the manifold's surface. Isomap (Isometric Feature Mapping) was designed to solve precisely this problem by using geodesic distances instead of Euclidean distances.

Euclidean distance is the workhorse of classical machine learning. For two points $\mathbf{x}, \mathbf{y} \in \mathbb{R}^D$, it's defined as:

$$d_E(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|2 = \sqrt{\sum{i=1}^{D}(x_i - y_i)^2}$$

This metric assumes a flat, Euclidean geometry where the shortest path between two points is always a straight line. While this assumption works well for many datasets, it can be fundamentally wrong when data lies on a curved manifold.

The Swiss Roll Example

Consider the classic Swiss Roll dataset—a 2D manifold embedded in 3D space. Imagine a flat sheet of paper that has been rolled up. Two points that are close in straight-line Euclidean distance might actually be far apart along the surface of the roll. Conversely, points on opposite "layers" of the roll might be close in Euclidean distance but distant along the surface.

This creates a fundamental problem: if we apply PCA or any method based on Euclidean distances, we will:

1. Conflate points that should be separated — points from different "layers" of the roll appear close
2. Separate points that should be together — nearby points along the manifold appear distant
3. Destroy the true structure — the unrolled 2D structure is completely lost

The Euclidean distance is measuring the extrinsic geometry (the embedding in 3D), not the intrinsic geometry (the true structure of the manifold itself).

A geodesic is a curve on a manifold that represents the shortest path between two points along the manifold's surface. The length of this curve is the geodesic distance. Let's build this concept rigorously.

Formal Definition

Let $\mathcal{M}$ be a smooth manifold embedded in $\mathbb{R}^D$. For two points $\mathbf{x}, \mathbf{y} \in \mathcal{M}$, the geodesic distance is:

$$d_G(\mathbf{x}, \mathbf{y}) = \inf_{\gamma} \int_0^1 \left\| \frac{d\gamma(t)}{dt} \right\| dt$$

where the infimum is taken over all smooth curves $\gamma: [0, 1] \to \mathcal{M}$ with $\gamma(0) = \mathbf{x}$ and $\gamma(1) = \mathbf{y}$. This integral computes the arc length of the curve, and the geodesic minimizes this length.

Riemannian Perspective

In the language of Riemannian geometry, a manifold $\mathcal{M}$ is equipped with a metric tensor $g$ that defines inner products on tangent spaces at each point. The geodesic distance between points is then:

$$d_G(\mathbf{x}, \mathbf{y}) = \inf_{\gamma} \int_0^1 \sqrt{g_{\gamma(t)}\left(\dot{\gamma}(t), \dot{\gamma}(t)\right)} \, dt$$

where $\dot{\gamma}(t) = \frac{d\gamma(t)}{dt}$ is the velocity vector along the curve, and $g_{\gamma(t)}(\cdot, \cdot)$ is the inner product defined by the metric tensor at point $\gamma(t)$.

For a manifold embedded in Euclidean space with the induced metric (the restriction of the Euclidean metric to the tangent spaces of the manifold), this reduces to the arc-length integral above.

Properties of Geodesic Distances

Geodesic distance satisfies the axioms of a metric:

1. Non-negativity: $d_G(\mathbf{x}, \mathbf{y}) \geq 0$, with equality iff $\mathbf{x} = \mathbf{y}$
2. Symmetry: $d_G(\mathbf{x}, \mathbf{y}) = d_G(\mathbf{y}, \mathbf{x})$
3. Triangle inequality: $d_G(\mathbf{x}, \mathbf{z}) \leq d_G(\mathbf{x}, \mathbf{y}) + d_G(\mathbf{y}, \mathbf{z})$

Importantly, geodesic distance provides an upper bound on Euclidean distance:

$$d_E(\mathbf{x}, \mathbf{y}) \leq d_G(\mathbf{x}, \mathbf{y})$$

The equality holds only when the geodesic between $\mathbf{x}$ and $\mathbf{y}$ is a straight line in the ambient space—which happens only on flat regions of the manifold. On curved regions, the geodesic must bend to stay on the manifold, making it longer than the straight-line distance.

To develop intuition for geodesics, let's examine them on several familiar manifolds. These examples illuminate how curvature affects the relationship between Euclidean and geodesic distances.

The Sphere Example in Detail

On a sphere of radius $r$, the geodesic between any two points is an arc of a great circle—a circle whose center coincides with the center of the sphere. Familiar examples include the equator and any circle of longitude.

For two points $\mathbf{x}, \mathbf{y}$ on the unit sphere, the geodesic distance is:

$$d_G(\mathbf{x}, \mathbf{y}) = \arccos(\mathbf{x} \cdot \mathbf{y})$$

The Euclidean (chord) distance is:

$$d_E(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\| = \sqrt{2(1 - \mathbf{x} \cdot \mathbf{y})}$$

For antipodal points (diametrically opposite), the geodesic distance is $\pi$ (half the circumference), while the Euclidean distance is 2 (the diameter). The ratio $d_G / d_E = \pi / 2 \approx 1.57$.

The key insight of Isomap is that if we can preserve geodesic distances in a low-dimensional embedding, we capture the intrinsic geometry of the manifold. This idea is grounded in the concept of isometric embeddings.

Definition: Isometric Embedding

An embedding $f: \mathcal{M} \to \mathbb{R}^d$ is isometric if it preserves distances:

$$d_{\mathbb{R}^d}(f(\mathbf{x}), f(\mathbf{y})) = d_G(\mathbf{x}, \mathbf{y}) \quad \text{for all } \mathbf{x}, \mathbf{y} \in \mathcal{M}$$

In words, the Euclidean distance between embedded points equals the geodesic distance between original points. An isometric embedding is a "perfect unfolding" of the manifold—no stretching, no compression, no distortion.

The Isometry Theorem for Manifolds

A fundamental result in differential geometry states that a $d$-dimensional Riemannian manifold with zero curvature (a flat manifold) can be locally isometrically embedded in $\mathbb{R}^d$. Examples include:

• A plane (trivially embeds in $\mathbb{R}^2$)
• A cylinder (unrolls to a plane; same as $\mathbb{R}^2$)
• The Swiss Roll (is intrinsically flat; can be unrolled to $\mathbb{R}^2$)

This is profound: the Swiss Roll, despite being a curved surface in 3D, has the same intrinsic geometry as a flat rectangle. If we measure distances correctly (geodesically), we can discover this hidden flatness and embed it in 2D without distortion.

What About Curved Manifolds?

Manifolds with non-zero intrinsic curvature (like spheres) cannot be isometrically embedded in a Euclidean space of the same dimension. A 2D sphere cannot be flattened into 2D without distortion—this is why all map projections of Earth introduce some distortion.

For such manifolds, Isomap produces an embedding that approximately preserves geodesic distances, minimizing distortion in a least-squares sense. The quality of the approximation depends on the manifold's curvature and the target dimension.

The Isomap Objective

Isomap seeks an embedding $\mathbf{Y} = \{\mathbf{y}_1, \ldots, \mathbf{y}_N\} \subset \mathbb{R}^d$ that minimizes:

$$\min_{\mathbf{Y}} \sum_{i < j} \left( d_G(\mathbf{x}_i, \mathbf{x}_j) - \|\mathbf{y}_i - \mathbf{y}_j\| \right)^2$$

This is exactly the objective of classical Multidimensional Scaling (MDS), but with geodesic distances instead of Euclidean distances. Isomap's innovation is computing geodesic distances from local Euclidean distances via shortest-path algorithms.

We've established that geodesic distances are the right concept for manifold learning. But there's a fundamental practical problem: we don't know the true manifold.

Given only a finite sample $\{\mathbf{x}_1, \ldots, \mathbf{x}_N\}$ of points from an unknown manifold $\mathcal{M}$, how can we estimate geodesic distances?

The key insight is that for nearby points, geodesic distance is well-approximated by Euclidean distance. If two points are close enough that the manifold looks approximately flat between them, the shortest path along the manifold is nearly a straight line.

Local Flatness Assumption

Formally, for a smooth manifold, the geodesic distance satisfies:

$$d_G(\mathbf{x}, \mathbf{y}) = d_E(\mathbf{x}, \mathbf{y}) + O(\|\mathbf{x} - \mathbf{y}\|^3)$$

as $\|\mathbf{x} - \mathbf{y}\| \to 0$. The error term scales with the cube of the distance, so for nearby points, the approximation is excellent.

This leads to Isomap's two-stage strategy:

1. For nearby points: Approximate geodesic distance with Euclidean distance
2. For distant points: Compute geodesic distance as the sum of local approximations along a shortest path

The second step uses the triangle inequality property of distances: the shortest path from $\mathbf{x}$ to $\mathbf{y}$ can be approximated by chaining together shortest paths through intermediate points.

The theoretical foundation of Isomap rests on asymptotic guarantees about when the graph-based approximation converges to true geodesic distances. Understanding these guarantees helps us know when to trust Isomap's results.

Convergence Theorem (Informal)

Under suitable conditions on the manifold and sampling, as the number of sample points $N \to \infty$ and the neighborhood size decreases appropriately, Isomap's estimated geodesic distances converge to true geodesic distances:

$$\hat{d}_G(\mathbf{x}_i, \mathbf{x}_j) \xrightarrow{N \to \infty} d_G(\mathbf{x}_i, \mathbf{x}_j)$$

Required Conditions:

1. Manifold regularity: The manifold $\mathcal{M}$ should be a compact, smooth submanifold without boundary (or with geodesically convex boundary)

2. Sufficient curvature bound: The curvature of $\mathcal{M}$ should be bounded, ensuring local Euclidean approximations are valid

3. Uniform sampling: Points should be sampled uniformly (or nearly uniformly) from $\mathcal{M}$

4. Connectivity: The neighborhood graph must be connected

5. Appropriate neighborhood scaling: The neighborhood radius must decrease slowly enough to maintain connectivity but fast enough to exploit local flatness

The Reach Condition

A key concept in manifold learning theory is the reach of a manifold. Intuitively, the reach is the largest radius $r$ such that any point within distance $r$ of the manifold has a unique nearest point on the manifold. For embeddings:

• A manifold with large reach is "well-separated" from itself—no two non-adjacent parts come too close
• The reach bounds how tightly the manifold can curve
• Isomap's accuracy depends on choosing neighborhoods smaller than the reach

$$\epsilon < \frac{\text{reach}(\mathcal{M})}{2}$$

ensures local Euclidean distances are faithful approximations to geodesics.

To appreciate why geodesic distances are special for manifold learning, let's compare them to other distance metrics used in machine learning.

We've established the mathematical foundation for understanding geodesic distances and their central role in Isomap. Let's consolidate the key insights: