Spectral convergence of diffusion maps
- 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 aDiffusion 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.…
Verfasserangaben: | Caroline L. WormellORCiD, Sebastian ReichORCiDGND |
---|---|
DOI: | https://doi.org/10.1137/20M1344093 |
ISSN: | 0036-1429 |
ISSN: | 1095-7170 |
Titel des übergeordneten Werks (Englisch): | SIAM journal on numerical analysis / Society for Industrial and Applied Mathematics |
Untertitel (Englisch): | Improved error bounds and an alternative normalization |
Verlag: | Society for Industrial and Applied Mathematics |
Verlagsort: | Philadelphia |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Jahr der Erstveröffentlichung: | 2021 |
Erscheinungsjahr: | 2021 |
Datum der Freischaltung: | 24.05.2024 |
Freies Schlagwort / Tag: | Sinkhorn problem; diffusion maps; graph Laplacian; kernel methods |
Band: | 59 |
Ausgabe: | 3 |
Seitenanzahl: | 48 |
Erste Seite: | 1687 |
Letzte Seite: | 1734 |
Fördernde Institution: | Deutsche Forschungsgemeinschaft (DFG, German Science Foundation)German Research Foundation (DFG) [SFB 1294/1-318763901]; European Research Council (ERC) under European Union's Horizon 2020 Research and Innovation ProgrammeEuropean Research Council (ERC) [787304] |
Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Mathematik |
DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Peer Review: | Referiert |