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

Abstract

Let $M$ be a compact Riemannian submanifold of ${\mathbf{R}}^m$ of dimension $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}{n{h}_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}^{-\Vert u{\Vert }^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 }_{M}f$ (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 }_{M}f(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 $\mathcal{F}$ of three times differentiable functions on $M$ with uniformly bounded derivatives $$\underset{p\in M}{\sup }\underset{f\in F}{\sup }|{\Delta }_{h_n,p}f(p)-\frac{1}{|\mu |}{\Delta }_{M}f(p)|=O\left(\sqrt{\frac{\log (1/h_n)}{n{h}_n^{d+2}}}\right)a.s.$$ as soon as $$n{h}_n^{d+2}/\log h_n^{-1}\to \infty andn{h}_n^{d+4}/\log h_n^{-1}\to 0,$$ and also prove asymptotic normality of ${\Delta }_{h_n,p}f(p)-\frac{1}{|\mu |}{\Delta }_{M}f(p)$ (functional CLT) for a fixed $p\in M$ and uniformly in $f.$

Published at http://dx.doi.org/10.1214/074921706000000888 in the IMS Lecture Notes Monograph Series (http://www.imstat.org/publications/lecnotes.htm) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Chernoff's Theorem and Discrete Time Approximations of Brownian Motion on Manifolds

Cited by in corpus (42)

• Discrete Signal Processing on Graphs
• Spectral clustering and the high-dimensional stochastic blockmodel
• A Tutorial on Spectral Clustering
• Continuum limit of total variation on point clouds
• An Analysis of the Convergence of Graph Laplacians
• Sparse Representation on Graphs by Tight Wavelet Frames and Applications
• Generalized density clustering
• Spectral Domain Sampling of Graph Signals
• The geometry of kernelized spectral clustering
• A Spectral Series Approach to High-Dimensional Nonparametric Regression
• On the path density of a gradient field
• Random curves on surfaces induced from the Laplacian determinant
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Spectral Convergence of the connection Laplacian from random samples
• Consistency of Cheeger and Ratio Graph Cuts
• Manifold learning with arbitrary norms
• A review of geometric, topological and graph theory apparatuses for the modeling and analysis of biomolecular data
• The Normalized Graph Cut and Cheeger Constant: from Discrete to Continuous
• On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
• Localized Fourier Analysis for Graph Signal Processing
• Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
• On the convergence of maximum variance unfolding
• Towards Stratification Learning through Homology Inference
• Model-free consistency of graph partitioning
• Fast communication-efficient spectral clustering over distributed data
• Operator norm convergence of spectral clustering on level sets
• Graph Laplacians on Singular Manifolds: Toward understanding complex spaces: graph Laplacians on manifolds with singularities and boundaries
• Bayesian Manifold Regression
• Graph Signal Processing: Overview, Challenges and Applications
• The game theoretic p-Laplacian and semi-supervised learning with few labels
• Hydrodynamic limit of the Symmetric Exclusion Process on a compact Riemannian manifold
• Graph Laplacians and their convergence on random neighborhood graphs
• Diffuse to fuse EEG spectra -- intrinsic geometry of sleep dynamics for classification
• Spectral Connectivity Analysis
• Network Distance Based on Laplacian Flows on Graphs
• Think globally, fit locally under the Manifold Setup: Asymptotic Analysis of Locally Linear Embedding
• Measure estimation on a manifold explored by a diffusion process
• Behavior of Graph Laplacians on Manifolds with Boundary
• PrivateMail: Supervised Manifold Learning of Deep Features With Differential Privacy for Image Retrieval
• Dimension Estimation Using Random Connection Models
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds