Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in $L^{\infty }$ from Random Samples

Abstract

In the manifold setting, we provide a series of spectral convergence results quantifying how the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator in the $L^{\infty }$ sense. The convergence rate is also provided. Based on these results, convergence of the proposed heat kernel approximation algorithm, as well as the convergence rate, to the exact heat kernel is guaranteed. To our knowledge, this is the first work exploring the spectral convergence in the $L^{\infty }$ sense and providing a numerical heat kernel reconstruction from the point cloud with theoretical guarantees.

53 Pages

References in corpus (6)

• Consistency of spectral clustering
• Unperturbed: spectral analysis beyond Davis-Kahan
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Geodesic Distance Estimation with Spherelets
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Impact of signal-to-noise ratio and bandwidth on graph Laplacian spectrum from high-dimensional noisy point cloud

Cited by in corpus (7)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Solving PDEs on Unknown Manifolds with Machine Learning
• Impact of signal-to-noise ratio and bandwidth on graph Laplacian spectrum from high-dimensional noisy point cloud
• Unlabeled Data Help in Graph-Based Semi-Supervised Learning: A Bayesian Nonparametrics Perspective
• A continuum limit for the PageRank algorithm
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs