Search papers, labs, and topics across Lattice.
This paper introduces Orthogonal Ring Distance Estimation Routine (ORDER), a novel algorithm for reconstructing the latent geometry of Riemannian manifolds from random geometric graphs with noisy distance estimates. ORDER achieves a pointwise distance estimation precision of $n^{-2/(d+5)}$, surpassing the volumetric barrier of $n^{-1/d}$ for dimensions $d>5$. As a result, the Gromov-Wasserstein distance between the reconstructed and true manifolds converges at a rate of $n^{-1/d}$, matching the optimal Wasserstein convergence rate.
Breaking the volumetric barrier in manifold reconstruction unlocks asymptotically optimal recovery of latent geometry from noisy distance data.
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.
