Non-linear manifold learning algorithms excel at uncovering the low-dimensional structure hidden within high-dimensional data. For example, Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, introduced by Mikhail Belkin et al., constructs a neighborhood graph to preserve local geometric relationships and "unfold" complex data manifolds into a lower-dimensional space.
However, a fundamental limitation plagues these non-linear techniques: they are inherently transductive. When optimizing an embedding, these algorithms compute coordinates directly for a fixed, static training set. Unlike linear methods like Principal Component Analysis (PCA), they do not inherently construct a continuous mathematical function $f: \mathbb{R}^D \to \mathbb{R}^d$ that maps any arbitrary point from the high-dimensional space to the latent space.
As identified by Jakob Verbeek et al. in Fast nonlinear dimensionality reduction with topology representing networks and Kerstin Bunte et al. in Nonlinear Discriminative Data Visualization, this creates the out-of-sample extension problem. If a new data point arrives after the initial training phase, there is no direct formula to determine its position in the embedding. The naive solution requires adding the new point to the dataset and re-running the entire optimization process from scratch. Because these optimizations scale quadratically or cubically with the number of samples, re-computation is completely impractical for large-scale datasets or real-time applications (Piotr Dollár et al. in Learning to Traverse Image Manifolds; Heeyoul Choi et al. in Manifold Integration with Markov Random Walks).
Non-Parametric Geometric Interpolation
To place an out-of-sample point without re-running the global optimization, one major paradigm leverages the local geometric properties of the already established manifold. The core intuition is that if the underlying manifold is smooth, a new point's position in the low-dimensional space should be determined by its closest neighbors in the high-dimensional space.
In Supervised Local Tangent Space Alignment for Classification, Hongyu Li 0001 et al. utilize a nearest-neighbor interpolation strategy. When a new point is introduced, the system identifies its nearest neighbors within the existing training set and uses their pre-computed low-dimensional coordinates to interpolate the new point's position. This approach preserves the local geometric relationships established during training while avoiding global recalculations.
To make this geometric intuition universally applicable, Harry Strange et al. proposed a generalized framework called GOoSE in A Generalised Solution to the Out-of-Sample Extension Problem in Manifold Learning. Instead of relying on algorithm-specific mathematical formulations, GOoSE uses local geometric alignment to map new data points into any existing manifold embedding. This decouples the out-of-sample extension from the specific choice of dimensionality reduction algorithm, providing a flexible, plug-and-play solution for dynamic environments.
Inductive Manifold Learning and Functional Mappings
An alternative paradigm avoids on-the-fly interpolation by forcing the manifold learning process to learn an explicit, reusable functional mapping from the outset. This shifts the framework from transductive to inductive learning.
One approach is to constrain the embedding function to a specific mathematical family. In Learning a Locality Preserving Subspace for Visual Recognition, Xiaofei He et al. introduced Locality Preserving Projections (LPP). LPP solves an optimization problem structurally similar to Laplacian Eigenmaps but enforces a linear transformation constraint. Because the result is an explicit projection matrix, mapping a new out-of-sample point reduces to a simple, instantaneous matrix multiplication.
When linear transformations are insufficient to capture highly non-linear, twisting manifolds, researchers employ non-linear functional representations. For instance, Andrew Lensen et al. in Genetic Programming for Manifold Learning: Preserving Local Topology used genetic programming to evolve explicit, interpretable symbolic equations that map high-dimensional inputs directly to their manifold coordinates.
In a similar vein, Ruobing Wu et al. developed SCaLE in SCaLE: Supervised and Cascaded Laplacian Eigenmaps for Visual Object Recognition Based on Nearest Neighbors, which stacks layers of non-linear mappings to parameterize the projection. By embedding the manifold structure directly into a functional or deep architecture, these methods ensure that out-of-sample data can be processed instantly during inference.
Enabling Real-Time and Streaming Applications
Resolving the out-of-sample extension problem is the key mechanism that enables manifold learning to operate in real-world, streaming data pipelines.
In time-series analysis, data arrives continuously, and systems must adapt without retraining. In Manifold Learning with Contracting Observers for Data-driven Time-series Analysis, Tal Shnitzer et al. demonstrated that an efficient out-of-sample extension allows static Diffusion Maps to be combined with control-theoretic contracting observers. This combination enables real-time tracking and noise filtering of continuous signals.
Similarly, Markus Breitenbach et al. showed in Clustering through ranking on manifolds that a fixed projection formula allows manifold-based clustering models to seamlessly ingest streaming data, making non-linear geometric analysis viable for real-time inference systems.
Key Foundational Work
Fast nonlinear dimensionality reduction with topology representing networks (2002) — contributed 1 concept elements to this direction.
Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering (2001) — contributed 1 concept elements to this direction.