Kernelized Diffusion Maps

Loucas Pillaud-Vivien, Francis Bach
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5236-5259, 2023.

Abstract

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 spaces 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öm subsampling, Fourier features) that enable to reduce the computational cost of the estimator while not degrading its overall performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-pillaud-vivien23a, title = {Kernelized Diffusion Maps}, author = {Pillaud-Vivien, Loucas and Bach, Francis}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {5236--5259}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/pillaud-vivien23a/pillaud-vivien23a.pdf}, url = {https://proceedings.mlr.press/v195/pillaud-vivien23a.html}, abstract = {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 spaces 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öm subsampling, Fourier features) that enable to reduce the computational cost of the estimator while not degrading its overall performance.} }
Endnote
%0 Conference Paper %T Kernelized Diffusion Maps %A Loucas Pillaud-Vivien %A Francis Bach %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-pillaud-vivien23a %I PMLR %P 5236--5259 %U https://proceedings.mlr.press/v195/pillaud-vivien23a.html %V 195 %X 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 spaces 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öm subsampling, Fourier features) that enable to reduce the computational cost of the estimator while not degrading its overall performance.
APA
Pillaud-Vivien, L. & Bach, F.. (2023). Kernelized Diffusion Maps. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:5236-5259 Available from https://proceedings.mlr.press/v195/pillaud-vivien23a.html.

Related Material