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 TrillosBrown University Applied Mathematics Providence, RInicolas_garcia_trillos@brown.edu Moritz GerlachDepartment of Mathematics and Computer Science Saarland Universitygerlach@cs.uni-saarland.de Matthias HeinDepartment of Mathematics and Computer Science Saarland Universityhein@cs.uni-saarland.de Dejan SlepčevDepartment of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213slepcev@andrew.cmu.eduAbstract: 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