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}.$
Categories: math.PR math.DG