Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace-Beltrami Operator

Nicolás García Trillos, Moritz Gerlach, Matthias Hein, Dejan SlepcevFound. Comput. Math 2020 · OpenReview

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 $${\mathcal {M}}$$ M in $$\mathbb {R}^d$$ 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 )$$ O ( ( log n n ) 1 2 m ) to the eigenvalues and eigenfunctions of the weighted Laplace–Beltrami operator of $${\mathcal {M}}$$ M . No information on the submanifold $${\mathcal {M}}$$ 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$$ R d in infinity transportation distance.
BibTeX
@inproceedings{trillos2020error,
  author = {Nicolás García Trillos and Moritz Gerlach and Matthias Hein and Dejan Slepcev},
  title = {{Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace-Beltrami Operator}},
  booktitle = {Found. Comput. Math},
  year = {2020},
  url = {https://openreview.net/forum?id=aPQsNsinQWP},
}
Figure