ISOMAP: Unfolding the Manifold with Geodesic Distances

ISOMAP (Isometric Mapping) is a sophisticated non-linear dimensionality reduction technique that aims to preserve the intrinsic geometric properties of data lying on a curved manifold. Unlike linear methods such as Principal Component Analysis (PCA), ISOMAP captures complex structures by approximating the manifold on which the data resides. This post delves deeply into ISOMAP’s methodology, mathematical formulation, and practical application.

Overview of ISOMAP

ISOMAP operates under the assumption that data points lie on a low-dimensional manifold embedded in a high-dimensional space. The goal is to map the data from its high-dimensional space to a lower-dimensional space while preserving the geodesic distances—the shortest paths along the manifold—between points. The process involves three main steps:

• Construct the Neighborhood Graph: Build a graph where nodes represent data points and edges denote connections based on similarity or distance.
• Compute Geodesic Distances: Estimate the geodesic distances by calculating the shortest paths in the graph.
• Apply Classical MDS: Perform classical MDS (Multidimensional Scaling) on the distance matrix derived from the graph to achieve a low-dimensional representation.

Mathematical Formulation

Step 1: Construct the Neighborhood Graph

1. Identify Nearest Neighbors:

Let \( \mathbf{X} = \{ \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n \} \) be a set of \( n \) data points in a \( d \)-dimensional space. For each point \( \mathbf{x}_i \), determine its \( k \)-nearest neighbors \( \mathcal{N}_i \) using a similarity measure (e.g., Euclidean distance).

2. Construct the Adjacency Matrix:

Define an adjacency matrix \( W \), where \( W_{ij} \) denotes the similarity between \( \mathbf{x}_i \) and \( \mathbf{x}_j \). If \( \mathbf{x}_j \) is one of the \( k \)-nearest neighbors of \( \mathbf{x}_i \), then:

\[ W_{ij} = \exp \left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma^2}\right) \]

Here, \( \sigma \) is a parameter controlling the width of the Gaussian kernel. If \( \mathbf{x}_j \) is not a neighbor of \( \mathbf{x}_i \), set \( W_{ij} = 0 \).

Step 2: Compute Geodesic Distances

1. Graph Representation:

Treat the adjacency matrix \( W \) as a graph where data points are nodes. An edge between nodes \( i \) and \( j \) exists if \( W_{ij} > 0 \).

2. Shortest Path Calculation:

Compute the shortest path distances \( D_{ij} \) between all pairs of nodes in the graph using algorithms like Dijkstra’s or Floyd-Warshall. These distances approximate the geodesic distances on the manifold.

The distance matrix \( D \) is given by:

\[ D_{ij} = \text{shortest path distance between } \mathbf{x}_i \text{ and } \mathbf{x}_j \]

3. Distance Matrix:

Construct the matrix \( D \), where \( D_{ij} \) represents the geodesic distance between points \( \mathbf{x}_i \) and \( \mathbf{x}_j \).

Step 3: Apply Classical MDS

1. Double-Centering:

To apply classical MDS, compute the matrix \( B \) from the distance matrix \( D \). Double-centering involves the following steps:

\[ B_{ij} = -\frac{1}{2} \left( D_{ij}^2 - \frac{1}{n} \sum_{k=1}^{n} D_{ik}^2 - \frac{1}{n} \sum_{k=1}^{n} D_{kj}^2 + \frac{1}{n^2} \left( \sum_{k=1}^{n} D_{ik} \right)^2 \right) \]

Here, \( n \) is the number of data points.

2. Eigenvalue Decomposition:

Perform eigenvalue decomposition on the matrix \( B \):

\[ B = U \Lambda U^T \]

Where \( \Lambda \) is a diagonal matrix with eigenvalues, and \( U \) contains the corresponding eigenvectors.

3. Low-Dimensional Embedding:

Select the top \( k \) eigenvalues and their corresponding eigenvectors. The low-dimensional coordinates are obtained by:

\[ \mathbf{Y} = U_k \Lambda_k^{1/2} \]

Here, \( U_k \) contains the eigenvectors corresponding to the \( k \) largest eigenvalues, and \( \Lambda_k^{1/2} \) is the diagonal matrix with the square roots of these eigenvalues.

Example: Applying ISOMAP

Step 1: Construct the Neighborhood Graph

Consider a 2D dataset:

\[ \mathbf{X} = \begin{bmatrix} 1 & 2 \\ 2 & 3 \\ 3 & 3 \\ 4 & 2 \\ 5 & 1 \end{bmatrix} \]

For \( k = 2 \) nearest neighbors, we construct the adjacency matrix \( W \). After identifying the nearest neighbors, the matrix might look like:

\[ W = \begin{bmatrix} 0 & \text{exp}(-0.5) & 0 & \text{exp}(-0.5) & 0 \\ \text{exp}(-0.5) & 0 & \text{exp}(-0.5) & 0 & \text{exp}(-0.5) \\ 0 & \text{exp}(-0.5) & 0 & \text{exp}(-0.5) & 0 \\ \text{exp}(-0.5) & 0 & \text{exp}(-0.5) & 0 & \text{exp}(-0.5) \\ 0 & \text{exp}(-0.5) & 0 & \text{exp}(-0.5) & 0 \end{bmatrix} \]

Step 2: Compute Geodesic Distances

Using the adjacency matrix \( W \), apply Dijkstra’s algorithm to compute the shortest paths. Assume the resulting geodesic distance matrix \( D \) is:

\[ D = \begin{bmatrix} 0 & 1 & 2 & 1 & 2 \\ 1 & 0 & 1 & 2 & 1 \\ 2 & 1 & 0 & 1 & 2 \\ 1 & 2 & 1 & 0 & 1 \\ 2 & 1 & 2 & 1 & 0 \end{bmatrix} \]

Step 3: Apply Classical MDS

1. Double-Centering:

Compute the matrix \( B \) using the double-centering formula.

2. Eigenvalue Decomposition:

Perform eigenvalue decomposition on \( B \). Suppose we get eigenvalues \( \Lambda \) and eigenvectors \( U \).

3. Low-Dimensional Embedding:

Select the top 2 eigenvectors corresponding to the largest eigenvalues. The low-dimensional coordinates are obtained by:

\[ \mathbf{Y} = U_k \Lambda_k^{1/2} \]

Resulting 2D embedding matrix \( \mathbf{Y} \):

\[ \mathbf{Y} = \begin{bmatrix} -0.5 & 0.7 \\ -0.4 & -0.1 \\ 0.1 & -0.5 \\ 0.6 & 0.3 \\ -0.3 & -0.4 \end{bmatrix} \]

Summary

ISOMAP effectively captures the intrinsic geometric structure of data lying on a manifold by preserving geodesic distances. The technique involves:

• Constructing a neighborhood graph to approximate the manifold.
• Computing geodesic distances through shortest path calculations.
• Applying classical MDS to obtain a low-dimensional representation.

Applications: ISOMAP is particularly useful for visualizing data with non-linear relationships, such as in image and speech recognition, where the data lies on complex manifolds.

By understanding and applying ISOMAP, you can unlock the underlying structure of high-dimensional data and gain valuable insights into its intrinsic properties.