Lipschitz regularity of graph Laplacians on random data clouds
Lipschitz regularity of graph Laplacians on random data clouds
复制标题
DOI：
10.1137/20m1356610
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
J. Calder;N. G. Trillos;M. Lewicka
中科院分区：
文献类型：
--
作者：
J. Calder;N. G. Trillos;M. Lewicka
本文研究了几何图上由随机数据点构造的椭圆型偏微分方程的Lipschitz正则性。数据点从光滑流形上支持的分布中采样。我们研究的方程族出现在基于图的学习背景下的数据分析中，并且包含图拉普拉斯特征向量所满足的方程作为重要示例。特别是，我们证明了高概率内部和整体Lipschitz估计的解决方案的图泊松方程。我们的结果可以用来表明，图拉普拉斯特征向量，具有很高的概率，基本上Lipschitz正则常数显式依赖于其相应的特征值。我们的分析依赖于合适的随机游走在连续水平上的概率耦合参数，以及将随机点云上的函数扩展到连续流形的插值方法。作为我们的一般正则性结果的副产品，我们获得了高概率$L^\infty$和近似$\mathcal{C}^{0，1}$收敛速度的图拉普拉斯特征向量对相应的加权Laplace-Beltrami算子的特征函数的收敛。我们得到的收敛速度类似于两位作者在以前的工作中建立的L^2 $-收敛速度。
In this paper we study Lipschitz regularity of elliptic PDEs on geometric graphs, constructed from random data points. The data points are sampled from a distribution supported on a smooth manifold. The family of equations that we study arises in data analysis in the context of graph-based learning and contains, as important examples, the equations satisfied by graph Laplacian eigenvectors. In particular, we prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues. Our analysis relies on a probabilistic coupling argument of suitable random walks at the continuum level, and an interpolation method for extending functions on random point clouds to the continuum manifold. As a byproduct of our general regularity results, we obtain high probability $L^\infty$ and approximate $\mathcal{C}^{0,1}$ convergence rates for the convergence of graph Laplacian eigenvectors towards eigenfunctions of the corresponding weighted Laplace-Beltrami operators. The convergence rates we obtain scale like the $L^2$-convergence rates established by two of the authors in previous work.