# Landmark Diffusion Maps (L-dMaps): Accelerated manifold learning out-of-sample extension

arXiv: https://arxiv.org/abs/1706.09396 · HTML: https://mlsanity.com/paper/1706.09396/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2017.

## Built on by (most cited first, 10 of 10)

- [Discovering Conservation Laws using Optimal Transport and Manifold Learning](https://mlsanity.com/paper/2208.14995/) (2022)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Geometry-Aware Edge Pooling for Graph Neural Networks](https://mlsanity.com/paper/2506.11700/) (2025)
- [On the Correspondence between Gaussian Processes and Geometric Harmonics](https://mlsanity.com/paper/2110.02296/) (2021)
- [Sampling-enabled scalable manifold learning unveils the discriminative cluster structure of high-dimensional data](https://mlsanity.com/paper/2401.01100/) (2024)
- [Machine Learning of Slow Collective Variables and Enhanced Sampling via Spatial Techniques](https://mlsanity.com/paper/2412.20868/) (2024)
- [Neumann eigenmaps for landmark embedding](https://mlsanity.com/paper/2502.06689/) (2025)
- [Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction](https://mlsanity.com/paper/2505.06756/) (2025)
- [Learning manifold diffusion semigroups from graph transition matrices](https://mlsanity.com/paper/2605.25383/) (2026)
- [FlashDiffusion: Fused Tiled Kernel Spectral Decomposition](https://mlsanity.com/paper/2609.38198/) (2026)

## Abstract (arXiv)

Diffusion maps are a nonlinear manifold learning technique based on harmonic analysis of a diffusion process over the data. Out-of-sample extensions with computational complexity O(N), where N is the number of points comprising the manifold, frustrate applications to online learning applications requiring rapid embedding of high-dimensional data streams. We propose landmark diffusion maps (L-dMaps) to reduce the complexity to O(M), where M ll N is the number of landmark points selected using pruned spanning trees or k-medoids. Offering (N/M) speedups in out-of-sample extension, L-dMaps enables the application of diffusion maps to high-volume and/or high-velocity streaming data. We illustrate our approach on three datasets: the Swiss roll, molecular simulations of a C24H50 polymer chain, and biomolecular simulations of alanine dipeptide. We demonstrate up to 50-fold speedups in out-of-sample extension for the molecular systems with less than 4% errors in manifold reconstruction fidelity relative to calculations over the full dataset.