# Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

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

- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Denoising: A Powerful Building-Block for Imaging, Inverse Problems, and Machine Learning](https://mlsanity.com/paper/2409.06219/) (2024)
- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [Discovering Conservation Laws using Optimal Transport and Manifold Learning](https://mlsanity.com/paper/2208.14995/) (2022)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach](https://mlsanity.com/paper/2203.00126/) (2022)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling](https://mlsanity.com/paper/2209.08004/) (2022)
- [Doubly Stochastic Graph-based Non-autoregressive Reaction Prediction](https://mlsanity.com/paper/2306.06119/) (2023)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [Stable generative modeling using Schr"odinger bridges](https://mlsanity.com/paper/2401.04372/) (2024)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [Localized Schr"odinger Bridge Sampler](https://mlsanity.com/paper/2409.07968/) (2024)
- [Spectral Neural Networks: Approximation Theory and Optimization Landscape](https://mlsanity.com/paper/2310.00729/) (2023)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)
- [Conditional expectation using compactification operators](https://mlsanity.com/paper/2306.10592/) (2023)
- [Nonparametric regression on random geometric graphs sampled from submanifolds](https://mlsanity.com/paper/2405.20909/) (2024)
- [Spectral Self-supervised Feature Selection](https://mlsanity.com/paper/2407.09061/) (2024)
- [Diffusion Processes on Implicit Manifolds](https://mlsanity.com/paper/2604.07213/) (2026)
- [Boundary Detection Algorithm Inspired by Locally Linear Embedding](https://mlsanity.com/paper/2406.18456/) (2024)
- [Image denoising as a conditional expectation](https://mlsanity.com/paper/2505.21546/) (2025)
- [Sinkhorn Normalization of Diffusion Kernels](https://mlsanity.com/paper/2507.06161/) (2025)
- [Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise](https://mlsanity.com/paper/2507.18520/) (2025)
- [Digital Twins: McKean-Pontryagin Control for Partially Observed Physical Twins](https://mlsanity.com/paper/2510.00937/) (2025)
- [K-means with learned metrics](https://mlsanity.com/paper/2603.14601/) (2026)

## Abstract (arXiv)

Diffusion maps is a manifold learning algorithm widely used for dimensionality reduction. Using a sample from a distribution, it approximates the eigenvalues and eigenfunctions of associated Laplace-Beltrami operators. Theoretical bounds on the approximation error are however generally much weaker than the rates that are seen in practice. This paper uses new approaches to improve the error bounds in the model case where the distribution is supported on a hypertorus. For the data sampling (variance) component of the error we make spatially localised compact embedding estimates on certain Hardy spaces; we study the deterministic (bias) component as a perturbation of the Laplace-Beltrami operator's associated PDE, and apply relevant spectral stability results. Using these approaches, we match long-standing pointwise error bounds for both the spectral data and the norm convergence of the operator discretisation. We also introduce an alternative normalisation for diffusion maps based on Sinkhorn weights. This normalisation approximates a Langevin diffusion on the sample and yields a symmetric operator approximation. We prove that it has better convergence compared with the standard normalisation on flat domains, and present a highly efficient algorithm to compute the Sinkhorn weights.