Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator

Autoren: Nicolas Garcia Trillos, Moritz Gerlach, Matthias Hein, Dejan Slepcev (2019)

We study the convergence of the graph Laplacian of a random geometric graph generated by an i.i.d. sample from a m-dimensional submanifold M in R^d as the sample size n increases and the neighborhood size h tends to zero. We show that eigenvalues and eigenvectors of the graph Laplacian converge with a rate of O\Big(\big(\frac{\log n}{n}\big)^\frac{1}{2m}\Big) to the eigenvalues and eigenfunctions of the weighted Laplace-Beltrami operator of M.
No information on the submanifold M is needed in the construction of the graph or the "out-of-sample extension" of the eigenvectors. Of independent interest is a generalization of the rate of convergence of empirical measures on submanifolds in R^d in infinity transportation distance.

Foundations of Computational Mathematics

zur Übersicht der Publikationen