TY  - JOUR
A1  - Wormell, Caroline L.
A1  - Reich, Sebastian
T1  - Spectral convergence of diffusion maps
T2  - SIAM journal on numerical analysis / Society for Industrial and Applied Mathematics
N2  - 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 localized 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 discretization. We also introduce an alternative normalization for diffusion maps based on Sinkhorn weights. This normalization approximates a Langevin diffusion on the sample and yields a symmetric operator approximation. We prove that it has better convergence compared with the standard normalization on flat domains, and we present a highly efficient rigorous algorithm to compute the Sinkhorn weights.
KW  - diffusion maps
KW  - graph Laplacian
KW  - Sinkhorn problem
KW  - kernel methods
Y1  - 2021
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/63706
SN  - 0036-1429
SN  - 1095-7170
VL  - 59
IS  - 3
SP  - 1687
EP  - 1734
PB  - Society for Industrial and Applied Mathematics
CY  - Philadelphia
ER  -