Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

DOI10.1016/J.ACHA.2022.06.003zbMATH Open1496.65203arXiv2101.09875OpenAlexW3123464492WikidataQ114214251 ScholiaQ114214251MaRDI QIDQ2168682FDOQ2168682

Nan Wu, Xiuyuan Cheng

Publication date: 26 August 2022

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: This work studies the spectral convergence of graph Laplacian to the Laplace-Beltrami operator when the graph affinity matrix is constructed from $N$ random samples on a $d$-dimensional manifold embedded in a possibly high dimensional space. By analyzing Dirichlet form convergence and constructing candidate approximate eigenfunctions via convolution with manifold heat kernel, we prove that, with Gaussian kernel, one can set the kernel bandwidth parameter $epsilonsim(logN/N{)}^{1/(d/2+2)}$ such that the eigenvalue convergence rate is $N^{-1/(d/2+2)}$ and the eigenvector convergence in 2-norm has rate $N^{-1/(d+4)}$; When $epsilonsim(logN/N{)}^{1/(d/2+3)}$, both eigenvalue and eigenvector rates are $N^{-1/(d/2+3)}$. These rates are up to a $logN$ factor and proved for finitely many low-lying eigenvalues. The result holds for un-normalized and random-walk graph Laplacians when data are uniformly sampled on the manifold, as well as the density-corrected graph Laplacian (where the affinity matrix is normalized by the degree matrix from both sides) with non-uniformly sampled data. As an intermediate result, we prove new point-wise and Dirichlet form convergence rates for the density-corrected graph Laplacian. Numerical results are provided to verify the theory.

Full work available at URL: https://arxiv.org/abs/2101.09875

Recommendations

• Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• From graph to manifold Laplacian: the convergence rate
• Convergence of graph Laplacian with kNN self-tuned kernels
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results

zbMATH Keywords

manifold learningLaplace-Beltrami operatorheat kernelGaussian kernelgraph Laplacianspectral convergence

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) PDEs on manifolds (35R01) Relations of PDEs with special manifold structures (Riemannian, Finsler, etc.) (58J60) Numerical methods for eigenvalue problems for boundary value problems involving PDEs (65N25)

Cites Work

• Diffusion maps
• Consistency of spectral clustering
• On the parabolic kernel of the Schrödinger operator
• Heat kernel and analysis on manifolds
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• From graph to manifold Laplacian: the convergence rate
• The Laplacian on a Riemannian manifold. An introduction to analysis on manifolds
• Learning Theory
• Bounds for the fundamental solution of a parabolic equation
• Gaussian upper bounds for the heat kernel on arbitrary Riemannian manifolds
• Variable bandwidth diffusion kernels
• Graph connection Laplacian methods can be made robust to noise
• A graph discretization of the Laplace-Beltrami operator
• Uniform Convergence of Adaptive Graph-Based Regularization
• Analysis of $p$-Laplacian Regularization in Semisupervised Learning
• Spectral convergence of the connection Laplacian from random samples
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Think globally, fit locally under the manifold setup: asymptotic analysis of locally linear embedding
• Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
• Convergence of Laplacian Spectra from Random Samples
• Spectral Convergence of Diffusion Maps: Improved Error Bounds and an Alternative Normalization
• Doubly Stochastic Normalization of the Gaussian Kernel Is Robust to Heteroskedastic Noise
• Manifold learning with bi-stochastic kernels
• Title not available (Why is that?)
• Lipschitz Regularity of Graph Laplacians on Random Data Clouds

Cited In (9)

• Data-driven efficient solvers for Langevin dynamics on manifold in high dimensions
• Kernel two-sample tests for manifold data
• Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling
• From graph to manifold Laplacian: the convergence rate
• Title not available (Why is that?)
• The \(G\)-invariant graph Laplacian. II: Diffusion maps
• The \(G\)-invariant graph Laplacian. I: Convergence rate and eigendecomposition.
• Geometric scattering on measure spaces
• Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples

This page was built for publication: Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168682)