Improved spectral convergence rates for graph Laplacians on ε-graphs and k-NN graphs
Improved spectral convergence rates for graph Laplacians on ε-graphs and k-NN graphs
复制标题
DOI：
10.1016/j.acha.2022.02.004
复制
发表时间：
2022-03
影响因子：
2.5
通讯作者：
J. Calder;Nicolás García Trillos
中科院分区：
文献类型：
--
作者：
J. Calder;Nicolás García Trillos
在本文中，我们提高了由随机数据构造的加权 Laplace-Beltrami 算子的基于图的近似的谱收敛率。我们利用连续本征函数的正则性和强点一致性结果来证明谱收敛率与图拉普拉斯算子的点一致性率相同。特别是，对于图连通性 ε 的最佳选择，我们的结果表明，图拉普拉斯算子的特征值和特征向量以 O (n− 1/(m+ 4)) 的速率收敛到加权 Laplace-Beltrami 算子的特征值和特征向量，直至对数因子，其中 m 是流形维数，n 是图中顶点的数量。我们的方法是通用的，使我们能够分析多种图结构，包括 ε 图和 k-NN 图。我们还提出了分析二维球上收敛速度的数值实验结果。
In this paper we improve the spectral convergence rates for graph-based approximations of weighted Laplace-Beltrami operators constructed from random data. We utilize regularity of the continuum eigenfunctions and strong pointwise consistency results to prove that spectral convergence rates are the same as the pointwise consistency rates for graph Laplacians. In particular, for an optimal choice of the graph connectivity ε, our results show that the eigenvalues and eigenvectors of the graph Laplacian converge to those of a weighted Laplace-Beltrami operator at a rate of O (n− 1/(m+ 4)), up to log factors, where m is the manifold dimension and n is the number of vertices in the graph. Our approach is general and allows us to analyze a large variety of graph constructions that include ε-graphs and k-NN graphs. We also present the results of numerical experiments analyzing convergence rates on the two dimensional sphere.