Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results

By Evarist Gin'e, Vladimir Koltchinskii. 2006

160 citations recorded by the source corpus.

Let ${M}$ be a compact Riemannian submanifold of ${{\bf R}^m}$ of dimension $\scriptstyle{d}$ and let ${X_1,...,X_n}$ be a sample of i.i.d. points in ${M}$ with uniform distribution. We study the random operators $$ \Delta_{h_n,n}f(p):=\frac{1}{nh_n^{d+2}}\sum_{i=1}^n K(\frac{p-X_i}{h_n})(f(X_i)-f(p)), p\in M $$ where ${K(u):={\frac{1}{(4\pi)^{d/2}}}e^{-\|u\|^2/4}}$ is the Gaussian kernel and ${h_n\to 0}$ as ${n\to\infty.}$ Such operators can be viewed as graph laplacians (for a weighted graph with vertices at data points) and they have been used in the machine learning literature to approximate the Laplace-Beltrami operator of ${M,}$ ${\Delta_Mf}$ (divided by the Riemannian volume of the manifold). We prove several results on a.s. and distributional convergence of the deviations ${\Delta_{h_n,n}f(p)-{\frac{1}{|\mu|}}\Delta_Mf(p)}$ for smooth functions ${f}$ both pointwise and uniformly in ${f}$ and ${p}$ (here ${|\mu|=\mu(M)}$ and ${\mu}$ is the Riemannian volume measure). In particular, we show that for any class ${{\cal F}}$ of three times differentiable functions on ${M}$ with uniformly bounded derivatives $$ \sup_{p\in M}\sup_{f\in F}\Big|\Delta_{h_n,p}f(p)-\frac{1}{|\mu|}\Delta_Mf(p)\Big|= O\Big(\sqrt{\frac{\log(1/h_n)}{nh_n^{d+2}}}\Big) a.s. $$ as soon as $$ nh_n^{d+2}/\log h_n^{-1}\to \infty and nh^{d+4}_n/\log h_n^{-1}\to 0, $$ and also prove asymptotic normality of ${\Delta_{h_n,p}f(p)-{\frac{1}{|\mu|}}\Delta_Mf(p)}$ (functional CLT) for a fixed ${p\in M}$ and uniformly in ${f}.$

Subfields: Applied Mathematics, Mathematical Physics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/e3b5acb6eaa58ea9234d02e3f6fe69159dc19de9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Mathematical Physics

In Numerical Analysis

Citations in the corpus

Towards a theoretical foundation for Laplacian-based manifold methods (2005, background): “A more subtle analysis of uniform convergence has recently been made in [15].”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “ this manifold is a good discrete approximation that converges pointwise and uniformly to the elliptic LaplaceBeltrami operator applied to this function as the number of points goes to inﬁnity [194], [195], [196]. References [197], [198], [29] choose discrete approximations to other continuous opera”
Graph Laplacians and their Convergence on Random Neighborhood Graphs (2006, background): “In Singer (2006), see also Gin´e and Koltchinskii (2006), the rate of convergence given by Hein et al. (2005) has been improved in the setting of the uniform measure.”
Metric Learning and Manifolds: Preserving the Intrinsic Geometry (2017, methodology): “These assumptions we made in Proposition 16 and Lemma lem:key allowed us to make use of the key results in (GinØ and Koltchinskii, 2006; Belkin and Niyogi, 2007).”
Convergence of Laplacian Eigenmaps (2006, background): “Recently [8] provided deeper probabilistic analysis in that case.”
A tutorial on spectral clustering (2007, methodology): “In Giné and Koltchinskii (2005), distributional and uniform convergence results are proved on manifolds with uniform distribution.”