# Kernelized Diffusion maps

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 43 references that are in the map.
- First posted on arXiv 13 Feb 2023.

## Builds on (most cited first, 11 of 11)

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Data-driven approximation of the Koopman generator: Model reduction, system identification, and control](https://mlsanity.com/paper/1909.10638/) (2019)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/2009.04324/) (2020)
- [On minimal variations for unsupervised representation learning](https://mlsanity.com/paper/2211.03782/) (2022)
- [Statistical Estimation of the Poincar'e constant and Application to Sampling Multimodal Distributions](https://mlsanity.com/paper/1910.14564/) (2019)

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

- [Learning the Infinitesimal Generator of Stochastic Diffusion Processes](https://mlsanity.com/paper/2405.12940/) (2024)
- [Laplace Transform Based Low-Complexity Learning of Continuous Markov Semigroups](https://mlsanity.com/paper/2410.14477/) (2024)
- [The Galerkin method beats Graph-Based Approaches for Spectral Algorithms](https://mlsanity.com/paper/2306.00742/) (2023)
- [From Biased to Unbiased Dynamics: An Infinitesimal Generator Approach](https://mlsanity.com/paper/2406.09028/) (2024)
- [Adaptive Kernel Selection for Kernelized Diffusion Maps](https://mlsanity.com/paper/2604.18402/) (2026)

## Abstract (arXiv)

Spectral clustering and diffusion maps are celebrated dimensionality reduction algorithms built on eigen-elements related to the diffusive structure of the data. The core of these procedures is the approximation of a Laplacian through a graph kernel approach, however this local average construction is known to be cursed by the high-dimension d. In this article, we build a different estimator of the Laplacian, via a reproducing kernel Hilbert space method, which adapts naturally to the regularity of the problem. We provide non-asymptotic statistical rates proving that the kernel estimator we build can circumvent the curse of dimensionality. Finally we discuss techniques (Nystr"om subsampling, Fourier features) that enable to reduce the computational cost of the estimator while not degrading its overall performance.