Recovering Geodesic Distances from Noisy Observations

Abstract

Let $(M,d,\mu )$ be a nice geodesic probability space (such as a manifold) and $X=\{x_i{\}}_{i\in [N]}\subset M$ a finite $\mu$-i.i.d. sample. Suppose we observe noisy distance random variables $d^{\prime }(x_i,x_j)$. When can the true distances be recovered to small additive error? This question has attracted interest in two disparate fields: latent-space graph models and boundary-value inverse problems. We first show that, taking $N\asymp {\epsilon }^{-2d-2}|\log \epsilon |$ and using runtime $O(N^{2.5+o_d(1)})$, we can recover all distances in $X$ to additive error $O(\epsilon |\log \epsilon |)$ with high probability, assuming $\mathbb{E}{d}^{\prime }(x_i,x_j)=F(d(x_i,x_j))$ for an unknown, increasing bilipschitz $F$ and with the $d^{\prime }(x_i,x_j)$ allowed to be arbitrarily heterogeneous in their distribution as long as they are bounded in subgaussian norm. This generalizes existing work, which required $F$ to be known and made strict assumptions on the distribution of $d^{\prime }(x_i,x_j)$. Achieving this generalization required a novel ``ruler-building'' procedure to learn $F$. We extend our results to a missing data case where we randomly lose access to noisy distances. Our second result uses ideas from the first to tackle a partial observability case: $X=Y\cup Z$ with $Z$ sampled from $M$ and $Y$ sampled from an observer subset satisfying visibility conditions that model the assumptions made on the boundary in boundary-value inverse problems. In this setting, we recover all pairwise distances in $Z$ to additive error $O(\epsilon )$ with $|Z|\asymp {\epsilon }^{-2d-2}|\log \epsilon |$, $|Y|\asymp {\epsilon }^{-\max \{d_{\nu },4\}}$ with $d_{\nu }$ determined by the volume-growth properties of the probability measure on the observer set, and runtime $O(|Z{|}^3)$. This is, to our knowledge, the first quantitative guarantee for this observer/observed split under noise, which complements existing stability results for boundary data.

arXiv comment36 pages; a few added and modified results. Submitted to STOC 2027