用图转移矩阵直接逼近流形扩散半群，适用于非均匀采样。
Learning manifold diffusion semigroups from graph transition matrices
- 通过迭代图转移矩阵逼近流形热半群，无需高光滑性假设。
- 在样本量N下达到误差率O(N^{-2/(d+6)})，支持样本内与外推广。
- 可处理非均匀采样，适合流形学习与数据降维任务。
我们研究从嵌入欧氏空间的未知流形中独立同分布采样得到的图扩散过程，其中图相似度由环境空间高斯核矩阵定义。在仅对测试函数f有低正则性要求（包括f ∈ L∞）的前提下，证明图转移矩阵P的迭代可直接逼近流形热半群Q_t = e^{tΔ}。在∞-范数下给出∥P^n f - Q_t f∥的界，当扩散时间t ≤ O(1)时，恢复经典图拉普拉斯点态收敛率O(N^{-2/(d+6)})，仅含对数因子。该结果同时适用于样本内误差与样本外泛化，新点处的Q_t f估计通过核卷积定义。为处理流形上非均匀采样密度，引入图转移矩阵的右归一化；在采样密度p为C^3且远离零的假设下，仍保持相同收敛速率。数值实验验证了所提估计器在模拟数据上的性能。
原文摘要 · Abstract (English)
We consider graph diffusion processes constructed from finite i.i.d. samples drawn from an unknown manifold embedded in ambient Euclidean space, where the graph affinity is defined by an ambient Gaussian kernel matrix. We show that the manifold heat semigroup $Q_t = e^{tΔ}$ can be approximated directly by iterating the graph transition matrix $P$, under only low regularity assumptions on the test function $f$, including the case $f \in L^\infty$. We bound $\| P^n f - Q_t f \|$ in $\infty$-norm, with the operator application to $f$ properly defined, and we recover the classical graph-Laplacian pointwise rate $O(N^{-2/(d+6)})$ up to logarithmic factors, for diffusion times $t $ up to $O(1)$ and longer. The rate holds for in-sample error as well as out-of-sample generalization, where the estimator of $Q_t f$ at a new point is defined via kernel convolution. To handle non-uniform sampling densities on the manifold, we introduce a right-normalization of the graph transition matrix; under the assumption that the sampling density $p$ is $C^3$ and bounded away from zero, the same convergence rates hold. We numerically demonstrate the performance of the proposed estimator on simulated data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。