Recovering Geodesic Distances from Noisy Observations

arXiv:2511.13025 · stat.ML, cs.LG, math.DG, math.PR · Submitted 2025-11-17 · Read on arXiv

stat.ML, cs.LG, math.DG, math.PR

Submitted: 2025-11-17

Updated: 2026-11-03

Comments: 36 pages; a few added and modified results. Submitted to STOC 2027

License: http://creativecommons.org/licenses/by-sa/4.0/

The gist: Let (M,d,μ) be a nice geodesic probability space (such as a manifold) and X=x i i in [N] M a finite μ-i.i.d.

Terminology

Abstract

Let (M,d,μ) be a nice geodesic probability space (such as a manifold) and X=x i i in [N] M a finite μ-i.i.d. sample. Suppose we observe noisy distance random variables d'(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 ε-2d-2 ε and using runtime O(N 2.5+o d (1)), we can recover all distances in X to additive error O(ε ε) with high probability, assuming E d'(x i, x j) = F(d(x i,x j)) for an unknown, increasing bilipschitz F and with the d'(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'(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 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(ε) with Z ε-2d-2 ε, Y ε- d ν,4 with d ν 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.

Sources

Related papers