Nonlinear dimensionality reduction & manifold learning

A dataset of thousand-dimensional vectors rarely fills that space — it usually lies on a thin, curved surface inside it (the manifold hypothesis). Linear methods like PCA can only slice that surface with a flat plane; where the surface bends, they fold far-apart points on top of each other. Manifold learning unrolls the surface instead — and the honest surprise is that every method here is the same move as everything else on this site: eigenvectors of a matrix built from the data.

Chapter 16 — Nonlinear Dimensionality Reduction & Manifold Learning — of Izenman's Modern Multivariate Statistical Techniques (on the Bookshelf), made playable — and the far end of the manifold-and-TDA thread the research program keeps circling back to. The lab below runs each method on the same swiss roll, colouring every point by its true position on the sheet.

method

neighbours k = 8

the data — a 2-D sheet rolled into 3-D (coloured by the true coordinate)

Isomap embedding geodesic — unrolls · computing…

Isomap. Replace straight-line distance with GEODESIC (shortest-path-along-the-graph) distance, then run classical MDS. Distances along the sheet are preserved, so the roll opens into a clean rectangle. If the colours stay a smooth gradient, the method recovered the sheet; if they scramble, it didn't. All three are eigenvectors of a matrix built from the data — the spectral thread.

Where linear stops

PCA keeps the directions of greatest variance — the top eigenvectors of the covariance $Σ = \frac{1}{n} \sum_{i} (x_{i} - \overset{x}{ˉ}) (x_{i} - \overset{x}{ˉ})^{⊤}$ (the same eigen move as the Eigenbook and the L² deep dive). But its axes are straight. On a rolled-up sheet, the two ends of the roll are close in the ambient 3-D space and far along the sheet — and PCA, seeing only straight-line distance, crushes them together. It can rotate the roll; it cannot open it.

Isomap — straighten the ruler

The fix is to change what “distance” means. Build a k-nearest-neighbour graph and measure distance as the shortest path along the graph — the geodesic along the sheet, not the chord through space. Then classical multidimensional scaling (chapter 13) turns that geodesic distance matrix back into coordinates by an eigendecomposition of the double-centered matrix:

B = - \frac{1}{2} J D_{geo}^{2} J, embedding = top eigenvectors of B

With the ruler bent to follow the surface, the roll opens into a clean rectangle — the same pipeline that runs on Compute. There is a catch worth seeing: too large a $k$ lets the graph short-circuit. An edge jumps between two layers of the roll, the shortest path takes that shortcut instead of travelling along the sheet, and the recovered geometry collapses back toward the flat PCA answer — the neighbours slider above makes the failure appear.

Laplacian Eigenmaps — the graph is the point

The same kNN graph carries a Laplacian $L = D - W$ (degree minus adjacency). Its eigenvectors are the standing waves — the low-frequency modes — of a diffusion on the graph, and the smallest nonzero ones give an embedding that keeps neighbours near:

L_{sym} = I - D^{- 1/2} W D^{- 1/2}, embedding = smallest nonzero eigenvectors of L_{sym}

This is spectral graph analytics — the same graph Laplacian behind spectral clustering, the connectivity of a network, and the Fiedler vector. On a long, thin roll its two lowest modes are both harmonics of the long axis, so it yields the characteristic spectral horseshoe rather than a rectangle — correct, and a different lens than Isomap's. Kernel PCA, LLE, and Hessian/Laplacian eigenmaps (Izenman 16) are all cousins: pick a matrix from the data, take its eigenvectors.

The spectral thread: PCA (covariance), Isomap (geodesic MDS), Laplacian Eigenmaps (graph Laplacian), spectral clustering, and the random-matrix lab are one idea — the eigenvectors of a data-built matrix. It runs straight into persistent homology and the topology of data (P1).