Distributional Convergence of the Empirical Laplacians with Integral Kernels on Domains with Boundaries

Abstract

Motivated by the problem of understanding theoretical bounds for the performance of the Belkin-Niyogi Laplacian eigencoordinate approach to dimension reduction in machine learning problems, we consider the convergence of random graph Laplacian operators to a Laplacian-type operator on a manifold. For $\{X_j\}$ i.i.d.\ random variables taking values in ${\mathbb{R}}^d$ and $K$ a kernel with suitable integrability we define random graph Laplacians \begin{equation*} D_{ε,n}f(p)=\frac{1}{nε^{d+2}}\sum_{j=1}^nK\left(\frac{p-X_j}ε\right)(f(X_j)-f(p)) \end{equation*} and study their convergence as $\epsilon ={\epsilon }_n\to 0$ and $n\to \infty$ to a second order elliptic operator of the form \begin{align*} Δ_K f(p) &= \sum_{i,j=1}^d\frac{\partial f}{\partial x_i}(p)\frac{\partial g}{\partial x_j}(p)\int_{\mathbb{R}^d}K(-t)t_it_jdλ(t)\\ &\quad +\frac{g(p)}{2}\sum_{i,j=1}^d\frac{\partial^2f}{\partial x_i\partial x_j}(p)\int_{\mathbb{R}^d}K(-t)t_it_jdλ(t). \end{align*} Our results provide conditions that guarantee that $D_{{\epsilon }_n,n}f(p)-{\Delta }_{K}f(p)$ converges to zero in probability as $n\to \infty$ and can be rescaled by $\sqrt{n{\epsilon }_n^{d+2}}$ to satisfy a central limit theorem. They generalize the work of Giné--Koltchinskii~\cite{gine2006empirical} and Belkin--Niyogi~\cite{belkin2008towards} to allow manifolds with boundary and a wider choice of kernels $K$, and to prove convergence under weaker smoothness assumptions and a correspondingly more precise choice of conditions on the asymptotics of ${\epsilon }_n$ as $n\to \infty$.