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

Abstract

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.

arXiv commentElectronic copy of the final peer-reviewed manuscript accepted for publication

References in corpus (9)

• Consistency of spectral clustering
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
• Nonparametric forecasting of low-dimensional dynamical systems
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Manifold learning with bi-stochastic kernels
• Convergence of Laplacian spectra from random samples
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator
• Kernel Scaling for Manifold Learning and Classification

Cited by in corpus (6)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in $L^{\infty }$ from Random Samples
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions
• Scaling positive random matrices: concentration and asymptotic convergence
• Analysis of the feedback particle filter with diffusion map based approximation of the gain