Convergence of graph Laplacian with kNN self-tuned kernels
Convergence of graph Laplacian with kNN self-tuned kernels
复制标题
图拉普拉斯算子与 kNN 自调整核的收敛
DOI：
10.1093/imaiai/iaab019
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wu, Hau-Tieng
中科院分区：
文献类型：
--
作者：
Cheng, Xiuyuan;Wu, Hau-Tieng
由数据点构造的核化Gram矩阵被广泛应用于基于图的几何数据分析和无监督学习中。一个重要的问题是如何选择核的带宽，而一种被称为自调优核的常见做法是根据最近邻(KNN)距离自适应地在每个点上设置AA值。与固定带宽核不同，当样本来自嵌入可能高维空间的维流形时，具有自调谐核的图的拉普拉斯收敛的理论结果是不完整的。本文证明了一类新的KNN自调谐核的图拉普拉斯算子到流形(加权-)拉普拉斯算子的收敛，其中KNN估计的带宽函数和极限算子也被参数化为。如果是，则极限算子是加权流形拉普拉斯算子。具体地说，我们证明了Dirichlet图的逐点收敛和带速率的Dirichlet图的收敛。我们的分析是建立在首先建立以高概率一致界相对估计误差的一致性的基础上的，其中是数据密度函数。我们的理论结果表明，在低密度区域，自调谐核比固定带宽核具有更小的方差误差。该算法不需要数据密度的先验知识。在模拟数据和手写数字图像数据上的数值实验支持了理论结果。
Kernelized Gram matrixconstructed from data pointsasis widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth, and a common practice called self-tuned kernel adaptively sets aat each pointby the-nearest neighbor (kNN) distance. Whens are sampled from a-dimensional manifold embedded in a possibly high-dimensional space, unlike with fixed-bandwidth kernels, theoretical results of graph Laplacian convergence with self-tuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operatorto manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels, whereis the estimated bandwidth function by kNN and the limiting operator is also parametrized by. When, the limiting operator is the weighted manifold Laplacian. Specifically, we prove the point-wise convergence ofand convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing aconsistency forwhich bounds the relative estimation erroruniformly with high probability, whereandis the data density function. Our theoretical results reveal the advantage of the self-tuned kernel over the fixed-bandwidth kernel via smaller variance error in low-density regions. In the algorithm, no prior knowledge ofor data density is needed. The theoretical results are supported by numerical experiments on simulated data and hand-written digit image data.