Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
复制标题
DOI：
10.1016/j.acha.2022.06.003
复制
发表时间：
2022-07-08
影响因子：
2.5
通讯作者：
Wu, Nan
中科院分区：
文献类型：
--
作者：
Cheng, Xiuyuan;Wu, Nan
当在环境欧几里得空间中从一个\(d\)维流形上的\(N\)个随机样本构建核化图亲和矩阵时，我们研究图拉普拉斯算子到拉普拉斯 - 贝尔特拉米算子的谱收敛性。通过分析狄氏型收敛，并通过与流形热核卷积构造候选近似特征函数，我们证明了随着\(N\)增加的特征收敛及其速率。最佳特征值收敛速率是\(N^{-\frac{1}{\frac{d}{2}+2}}\)（当核带宽参数\(\epsilon\)类似于\((\frac{\log N}{N})^{\frac{1}{\frac{d}{2}+2}}\)时），最佳特征向量\(2\)-范数收敛速率是\(N^{-\frac{1}{\frac{d}{2}+3}}\)（当\(\epsilon\)类似于\((\frac{\log N}{N})^{\frac{1}{\frac{d}{2}+3}}\)时）。对于未归一化和归一化图拉普拉斯算子的有限多个低阶特征值，这些速率在一个\(\log N\)因子范围内成立。当数据密度不均匀时，我们证明了密度校正图拉普拉斯算子具有相同的速率，并且我们还建立了新的算子逐点收敛速率和狄氏型收敛速率作为中间结果。提供了数值结果以支持该理论。© 2022爱思唯尔公司。保留所有权利。
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 epsilon similar to(log N/N)(1/(d/2+2)) ) and the best eigenvector 2-norm convergence rate is N-1/(d/2+3) (when epsilon similar to (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. (C) 2022 Elsevier Inc. All rights reserved.