Publication 17-CNA-024
Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace-Beltrami operator
Nicolas García Trillos
Brown University
Applied Mathematics
Providence, RI
nicolas_garcia_trillos@brown.edu
Moritz Gerlach
Department of Mathematics and Computer Science
Saarland University
gerlach@cs.uni-saarland.de
Matthias Hein
Department of Mathematics and Computer Science
Saarland University
hein@cs.uni-saarland.de
Dejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
slepcev@andrew.cmu.edu
Abstract: 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
${\cal M}$ in $\mathbb{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 ${\cal M}$.
No information on the submanifold ${\cal 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 $\mathbb{R}^d$ in infinity transportation distance.
Get the paper in its entirety as 17-CNA-024.pdf
« Back to CNA Publications