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

Abstract

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

Keywords

Affiliated Institutions

• Georgia Institute of Technology US

Related Publications