CMU Campus
Center for                           Nonlinear Analysis
CNA Home People Seminars Publications Workshops and Conferences CNA Working Groups CNA Comments Form Summer Schools Summer Undergraduate Institute PIRE Cooperation Graduate Topics Courses SIAM Chapter Seminar Positions Contact
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