Publications [#368016] of Xiuyuan Cheng

Papers Published

1. Cheng, X; Wu, N, Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation, Applied and Computational Harmonic Analysis, vol. 61 (November, 2022), pp. 132-190 [doi]
   (last updated on 2024/10/18)

   Abstract:
   We study the spectral convergence of graph Laplacians to the Laplace-Beltrami operator when the kernelized graph affinity matrix is constructed from N random samples on a d-dimensional manifold in an ambient Euclidean space. By analyzing Dirichlet form convergence and constructing candidate approximate eigenfunctions via convolution with manifold heat kernel, we prove eigen-convergence with rates as N increases. The best eigenvalue convergence rate is N−1/(d/2+2) (when the kernel bandwidth parameter ϵ∼(log⁡N/N)1/(d/2+2)) and the best eigenvector 2-norm convergence rate is N−1/(d/2+3) (when ϵ∼(log⁡N/N)1/(d/2+3)). These rates hold up to a log⁡N-factor for finitely many low-lying eigenvalues of both un-normalized and normalized graph Laplacians. When data density is non-uniform, we prove the same rates for the density-corrected graph Laplacian, and we also establish new operator point-wise convergence rate and Dirichlet form convergence rate as intermediate results. Numerical results are provided to support the theory.