arXiv:2604.00432stat.MLcs.LG2026-04被引 1

突破几何重构的体积瓶颈,实现更精确的距离估计。

Denoising distances beyond the volumetric barrier

  • 提出ORDER方法,通过正交环结构提升距离估计精度。
  • 精度达n^{-2/(d+5)},在d>5时超越传统体积极限。
  • 适用于噪声距离、稀疏图等复杂场景,适合几何学习研究者。

我们研究从随机几何图中重构d维黎曼流形的潜在几何结构问题。尽管近期工作在从随机几何图或噪声距离中恢复流形方面取得进展,但成对距离估计的精度长期受限于体积屏障,即由样本间距尺度n^{-1/d}决定的自然限制。本文提出一种新方法——正交环距离估计流程(ORDER),可在多项式时间内实现点对点距离估计精度为n^{-2/(d+5)}(忽略对数因子),严格优于体积屏障(当d > 5时)。由此证明,重构度量测度空间与真实流形之间的Gromov–Wasserstein距离为n^{-1/d},达到经验测度的最优Wasserstein收敛速率,表明重构图度量在渐近意义上等价于拥有全部点对距离矩阵。结果在广泛设定下成立,涵盖一般噪声距离模型、稀疏随机几何图及未知连接概率函数。

原文摘要 · Abstract (English)

We study the problem of reconstructing the latent geometry of a $d$-dimensional Riemannian manifold from a random geometric graph. While recent works have made significant progress in manifold recovery from random geometric graphs, and more generally from noisy distances, the precision of pairwise distance estimation has been fundamentally constrained by the volumetric barrier, namely the natural sample-spacing scale $n^{-1/d}$ coming from the fact that a generic point of the manifold typically lies at distance of order $n^{-1/d}$ from the nearest sampled point. In this paper, we introduce a novel approach, Orthogonal Ring Distance Estimation Routine (ORDER), which achieves a pointwise distance estimation precision of order $n^{-2/(d+5)}$ up to polylogarithmic factors in $n$ in polynomial time. This strictly beats the volumetric barrier for dimensions $d > 5$. As a consequence of obtaining pointwise precision better than $n^{-1/d}$, we prove that the Gromov--Wasserstein distance between the reconstructed metric measure space and the true latent manifold is of order $n^{-1/d}$. This matches the Wasserstein convergence rate of empirical measures, demonstrating that our reconstructed graph metric is asymptotically as good as having access to the full pairwise distance matrix of the sampled points. Our results are proven in a very general setting which includes general models of noisy pairwise distances, sparse random geometric graphs, and unknown connection probability functions.

几何学习距离估计流形重建

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。