high-dim
Unroll the swiss roll
It is 2000, and dimensionality reduction is stuck at linear: PCA finds the best flat subspace, but the data of interest — faces under varying pose, handwritten digits, speech spectra — live on curved low-dimensional manifolds embedded in thousands of dimensions, where Euclidean shortcuts tunnel through the ambient space and lie about proximity. Recover the manifold's own geometry from samples alone: distances measured along the surface rather than through it, embeddings computed from neighborhood graphs by spectral machinery, and honest conditions — sampling density, noise, curvature — under which the recovered coordinates mean anything. Get it wrong and visualization becomes hallucination: clusters and trajectories that are artifacts of a shortcut through empty space, published as structure in biology and neuroscience for a decade.
Who this problem belongs to
The two figures whose methods fit it best, out of 58 in contention.
Tenenbaum's 2000 Science paper introducing Isomap is, quite literally, this problem: recovering a nonlinear manifold's intrinsic geometry by estimating geodesic distances along the data surface through a neighborhood graph, then applying classical multidimensional scaling to those graph distances to produce a low-dimensional embedding, exactly the 'distances measured along the surface rather than through it' this problem specifies. His paper used the swiss roll as its own illustrative example alongside face-pose and digit datasets, the precise scenario this problem describes, and he supplied honest theoretical conditions on sampling density and manifold properties under which the recovered coordinates are meaningful. His score is not 100 only because the companion technique, locally linear embedding, was developed independently and simultaneously by Roweis and Saul, making this a shared rather than solitary breakthrough moment.
Niyogi, with Mikhail Belkin, developed Laplacian eigenmaps (2003), the spectral-embedding half of this problem's requirement: computing low-dimensional coordinates from the eigenvectors of a graph Laplacian built on a neighborhood graph, with rigorous convergence theory tying the discrete graph Laplacian to the continuous Laplace-Beltrami operator on the underlying manifold as sample density grows. That convergence analysis is precisely the 'honest conditions under which the recovered coordinates mean anything' this problem demands, addressing exactly the overclaiming risk of treating manifold-learning output as ground truth without such guarantees. His broader learning-theory work on when geometric structure inferred from finite samples is statistically trustworthy directly engages the identifiability concerns this problem raises. His score falls just behind Tenenbaum's only because Isomap predates Laplacian eigenmaps by three years as this problem's opening breakthrough.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
58 figures are scored on this problem. Draw it in a battle to see where you land.