Distributional Convergence of the Empirical Laplacians with integral Kernels on domains with boundaries
Bernard Akwei, Luke G. Rogers, Alexander Teplyaev · 2025
Read Distributional Convergence of the Empirical Laplacians with integral Kernels on domains with boundaries by Bernard Akwei, Luke G. Rogers, Alexander Teplyaev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05633.txt.
Introduction
Bernard Akwei, Luke Rogers, and Alexander Teplyaev study how random graph operators settle onto a smooth limit as data grows, in a paper published in two thousand twenty-five. The work is motivated by a popular dimension reduction method that builds coordinates from the eigenvectors of a graph Laplacian.
In that method, points sampled from a surface are linked by a kernel that weights nearby pairs. The authors define the matching random graph Laplacians and ask what operator they approach as the sample size grows and the kernel width shrinks. They prove convergence, in the distributional sense, to a second-order elliptic operator on the domain. Crucially, they handle domains with boundaries, where edge effects can distort the limit. Understanding this convergence underpins theoretical bounds for the Belkin-Niyogi approach used in machine learning. The result tells practitioners what their discrete construction is really approximating.
Catalog record
| CREATOR | Bernard Akwei, Luke G. Rogers, Alexander Teplyaev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05633
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distributional Convergence of the Empirical Laplacians with integral Kernels on domains with boundaries Bernard Akwei, Luke G. Rogers, Alexander Teplyaev 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 } \{X_{j}\} i.i.d. random variables taking values in ℝ d \mathbb{R}^{d} and K K a kernel with suitable integrability we define random graph Laplacians D ϵ , n f ( p ) = 1 n ϵ d + 2 ∑ j = 1 n K ( p − X j ϵ ) ( f ( X j ) − f ( p ) ) D_{\epsilon,n}f(p)=\frac{1}{n\epsilon^{d+2}}\sum_{j=1}^{n}K\left(\frac{p-X_{j}}{\epsilon}\right)(f(X_{j})-f(p)) and study their convergence as ϵ = ϵ n → 0 \epsilon=\epsilon_{n}\to 0 and n → ∞ n\to\infty to a second order elliptic operator of the form Δ K f ( p ) \displaystyle\Delta_{K}f(p) = ∑ i , j = 1 d ∂ f ∂ x i ( p ) ∂ g ∂ x j ( p ) ∫ ℝ d K ( − t ) t i t j 𝑑 λ ( t ) \displaystyle=\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_{i}t_{j}d\lambda(t) + g ( p ) 2 ∑ i , j = 1 d ∂ 2 f ∂ x i ∂ x j ( p ) ∫ ℝ d K ( − t ) t i t j d λ ( t ) . \displaystyle\quad+\frac{g(p)}{2}\sum_{i,j=1}^{d}\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}(p)\int_{\mathbb{R}^{d}}K(-t)t_{i}t_{j}d\lambda(t). Our results provide conditions that guarantee that D ϵ n , n f ( p ) − Δ K f ( p ) D_{\epsilon_{n},n}f(p)-\Delta_{K}f(p) converges to zero in probability as n → ∞ n\to\infty and can be rescaled by n ϵ n d + 2 \sqrt{n\epsilon_{n}^{d+2}} to satisfy a central limit theorem. They generalize the work of Giné–Koltchinskii [ GK06 ] and Belkin–Niyogi [ BN08 ] to allow manifolds with boundary and a wider choice of kernels K K , and to prove convergence under weaker smoothness assumptions and a correspondingly more precise choice of conditions on the asymptotics of ϵ n \epsilon_{n} as n → ∞ n\to\infty . 1. Introduction The Laplacian eigenmap method introduced by Belkin–Niyogi [ BN03 ] for dimension reduction in machine learning problems may be thought of as follows: given sample points X_{1},\dotsc,X_{n} in a high dimensional space, one forms a graph Laplacian by introducing edge weights between pairs X_{i},X_{j} . Computing the eigenfunctions \{\zeta_{k}\}_{k=1}^{N} of this Laplacian that have the smallest non-zero eigenvalues provides a map (\zeta_{1},\dotsc,\zeta_{N})\mathrel{\mathop{\mathchar 58\relax}}\{X_{j}\}\to\mathbb{R}^{N} called the Laplacian eigenmap to \mathbb{R}^{N} . It was proposed in [ BN03 ] that this map preserves the large-scale geometry of the sample data while reducing the dimension to a prescribed value N because the graph Laplacians approximate the Laplace-Beltrami operator of the manifold and the latter encodes suitable geometric information. If the data lies on a d -dimensional manifold then, following [ BN08 ] , one usually has N>d because the number of eigenfunctions needs to be larger than the dimension of the manifold for an accurate representation of this manifold. For instance, one needs at least three eigenfunctions to construct a three-dimensional representation of a two-dimensional torus, as shown in [ AAB+24 , Figure 2] . Our motivation is to explore eigenmaps in more general, less smooth settings, offering a broader perspective compared to previous work. The preceding sketch of the eigenmap method leaves several significant details open. One is how to choose the edge weights. Belkin–Niyogi suggest several possibilities, including connecting points x_{i},x_{j} with an edge of weight e^{-|x_{i}-x_{j}|^{2}/\epsilon} (Gaussian weights) or choosing a threshold \epsilon and connecting points that satisfy |x_{i}-x_{j}|<\epsilon . The highest generality would allow weights K(x,y) , but it is typical to only consider functions K(x-y) or, in order to fix a length scale \epsilon , K\bigl(\frac{x-y}{\epsilon}\bigr) for some integrable K . Another natural question is in what sense and under what assumptions the graph Laplacians approximate a Laplacian operator on the manifold. One approach to this problem is to take points \{X_{j}\}_{j=1}^{n} randomly on a manifold and ask whether the graph Laplacians converge to the classical Laplace-Beltrami operator as the length scale \epsilon\to 0 and the number of points n\to\infty . Significant early results of this type are due to Giné–Koltchinskii [ GK06 ] , who write their random graph Laplacian in the form (1.1) D_{\epsilon,n}f(p)=\frac{1}{n\epsilon^{d+2}}\sum_{j=1}^{n}K\Bigl(\frac{p-X_{j}}{\epsilon_{n}}\Bigr)(f(X_{j})-f(p)), with K the Gaussian kernel and the points X_{i} taken to be i.i.d. with uniform distribution on a compact manifold of dimension d without boundary. Normalizing the measure to be unity they denote the Laplace-Beltrami operator by \Delta and for a function f that is C^{3} in a neighborhood of p they prove a law of large numbers (LLN) [ GK06 , Proposition 4.1] and a central limit theorem (CLT) [ GK06 , Proposition 4.1] as follows: (1.2) \displaystyle\text{\mbox{\qquad If }}\epsilon_{n}\to 0\text{ and }n\epsilon_{n}^{d+2}\to\infty\text{ then }D_{\epsilon_{n},n}f(p)-\Delta f(p)\overset{\text{prob}}{\longrightarrow}0, (1.3) \displaystyle\text{\mbox{\qquad If }}n\epsilon_{n}^{d+4}\to 0\text{ and }n\epsilon_{n}^{d}\to\infty\text{ then }\sqrt{n\epsilon_{n}^{d+2}}\bigl(D_{\epsilon_{n},n}f(p)-\Delta f(p)\bigr)\overset{\text{dist}}{\longrightarrow}sZ. where Z is a standard normal random variable. A formula for the variance s^{2} similar to ( 2.3 ) below is also given in [ GK06 , Proposition 4.1] . This convergence may be taken to be uniform over a family of functions with uniformly bounded C^{3} norm with the same proof. Moreover, using a more difficult analysis and with extra factors of the form |\log\epsilon_{n}|^{-1} in the hypotheses, the above convergences may be taken to be uniform over points p in the manifold and the weak law of large numbers may be upgraded to a strong law (i.e. with almost sure convergence). A contemporaneous LLN result of Belkin–Niyogi [ BN08 ] is formulated for f\in C^{\infty} and with \epsilon_{n}=n^{-\frac{1}{d+2+\nu}} for some \nu>0 and may be stated in the form (1.4) D_{\epsilon_{n},n}f(p)-\Delta f(p)\overset{\text{prob}}{\longrightarrow}0\text{ as }n\to\infty. It, too, may be taken to be uniform for f in a family of functions with uniformly bounded C^{3} norm. Belkin–Niyogi in [ BN08 , Section 5] also consider the question of taking a non-uniform probability distribution on the X_{i} and describe the limit in this case. Other significant results at around the same time as the works [ GK06 , BN08 , Sin06 ] are that of Coifman–Lafon [ CL06 ] , who point out that various kernel eigenmap techniques are equivalent to (heat) diffusion maps and study of the effect of non-uniform probability distributions for sample points in this setting, and Jones–Maggioni–Schul [ JMS08 ] , who prove that a diffusion map yields a bi-Lipschitz parametrization of a Hölder manifold on a (quantitatively) small neighborhood of a point. During the nearly 20 years since the preceding papers were written, the question of convergence of graph Laplacians to Laplace-Beltrami operators has been explored by several authors in a number of different contexts, particularly with respect to convergence of spectral data. We note, in particular, the works [ BIK15 , BIK19 , GTGHS20 ] which study operators like ( 1.1 ) and ( 1.5 ) in non-probabilistic settings. Other applications of graph Laplacians like ( 1.1