Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator
This provides theoretical guarantees for manifold learning algorithms, but it is incremental as it builds on existing convergence results with improved rates.
The paper tackles the problem of quantifying the convergence rate of graph Laplacian eigenvalues and eigenvectors on random geometric graphs to those of the Laplace-Beltrami operator on a submanifold, showing a rate of O((log n/n)^(1/(2m))) without requiring prior knowledge of the submanifold.
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.