Scalable Manifold Learning for High Dimensional Data

This direction is merged into another direction: manifold learning scalability. Its last version stays readable and citable here.

Version 1 of 193 papers99 conceptsfrozen 2026-10-04

Modern datasets often contain millions of samples, each described by thousands of features. However, these points rarely fill their high-dimensional space uniformly. Instead, they typically cluster around a low-dimensional "manifold"—a curved surface like a crumpled sheet of paper embedded in a 3D room.

Manifold learning aims to "unwrap" this sheet to reveal the data's true structure. While techniques like Locally Linear Embedding (LLE) and Isomap are mathematically elegant, they face a significant "computational wall." As Ali Ghodsi and Benyamin Ghojogh note in their surveys of LLE and Isomap, these algorithms often scale quadratically ($O(N^2)$) or even cubically ($O(N^3)$) with the number of data points $N$. This makes them impractical for the millions of observations common in genomics, computer vision, and natural language processing.

To bridge this gap, researchers have developed strategies to approximate these manifolds without comparing every point to every other point.

The Landmark Skeleton

The most intuitive way to scale manifold learning is to realize that you don't need every single data point to understand the overall shape of the manifold. If you have a million points on a sphere, a few thousand well-chosen "landmarks" can define the sphere's curvature just as well.

Jorge G. Silva and colleagues proposed Selecting Landmark Points for Sparse Manifold Learning, which treats landmark selection as a sparse regression problem. By using the LARS algorithm to track changes in local geometry, they can represent complex manifolds using only a tiny fraction of the original data. Similarly, Gautam Pai introduced DIMAL, which uses sparse geodesic sampling to train Siamese neural networks, allowing the model to learn a global mapping from just a few anchor points.

Algorithmic Approximations and Hashing

Another approach involves speeding up the underlying math of neighbor discovery. Traditional t-SNE is notoriously slow because it calculates interactions between all pairs of points. JH Krijthe popularized the Barnes-Hut implementation of t-SNE, which uses a tree-based structure to group distant points together, reducing complexity from $O(N^2)$ to $O(N \log N)$.

For even larger scales, Fumin Shen and Chunhua Shen developed Inductive Hashing on Manifolds. Instead of embedding the entire dataset at once, they learn the manifold structure on a small subset and then "inductively" map the remaining millions of points into compact binary hash codes. This allows for near-instantaneous retrieval in massive databases.

Hybrid and Deep Manifold Learning

Recent work has moved toward hybridizing fast linear methods with slow non-linear ones. Long Cheng and Yani Guan demonstrated that using Random Projections as a pre-processing step can drastically reduce the dimensionality of the data before it ever hits a manifold algorithm, saving massive amounts of memory and time.

Furthermore, researchers are increasingly replacing non-parametric algorithms with neural networks that "distill" the manifold. Sixue Gong and Vishnu Boddeti introduced DeepMDS, which uses a neural network to learn the Multidimensional Scaling mapping. Once trained, this network can embed new points in constant time, bypassing the $O(N^2)$ bottleneck entirely.

Practical Tools for Big Data

The shift toward scalability has culminated in high-performance software libraries. The megaman library is a prime example, combining fast approximate nearest-neighbor searches with optimized sparse eigensolvers. It enables the analysis of millions of data points—such as galaxy spectra or word embeddings—on a single desktop, a task that would have previously required a supercomputer.

By moving from exact, global optimizations to sparse, approximate, and inductive frameworks, the field has transformed manifold learning from a theoretical curiosity into a robust tool for the era of big data.

Papers in this version

Showing 60 of 93 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scalable_manifold_learning_for_high_dime_5efbcfb2,
  title = {Scalable Manifold Learning for High Dimensional Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-manifold-learning-for-high-dimensional-data/rdr_5efbcfb2972d4f449a0eae07647aa8ca},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_manifold_learning_for_high_dime_5efbcfb2_v1,
  title = {Scalable Manifold Learning for High Dimensional Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-manifold-learning-for-high-dimensional-data/rdr_5efbcfb2972d4f449a0eae07647aa8ca/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}