stat.MLNov 17, 2025

Recovering Geodesic Distances from Noisy Observations

Authors: Charles Fefferman, Jonathan Marty, Kevin Ren

Organizations: Department of Mathematics, Princeton University, Princeton, NJ 08544 USA. · Program in Applied and Computational Mathematics (PACM), Princeton University, Princeton, NJ 08544, USA.

Abstract

Let (M,d,μ)(M,d,μ) be a nice geodesic probability space (such as a manifold) and X={xi}i∈[N]⊂MX=\{x_i\}_{i\in [N]} \subset M a finite μμ-i.i.d. sample. Suppose we observe noisy distance random variables d′(xi,xj)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∣log⁡ε∣N \asymp ε^{-2d-2}|\logε| and using runtime O(N2.5+od(1))O(N^{2.5+o_d (1)}), we can recover all distances in XX to additive error O(ε∣log⁡ε∣)O(ε|\logε|) with high probability, assuming Ed′(xi,xj)=F(d(xi,xj))\mathbb{E} d'(x_i, x_j) = F(d(x_i,x_j)) for an unknown, increasing bilipschitz FF and with the d′(xi,xj)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 FF to be known and made strict assumptions on the distribution of d′(xi,xj)d'(x_i, x_j). Achieving this generalization required a novel ``ruler-building'' procedure to learn FF. 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∪ZX = Y \cup Z with ZZ sampled from MM and YY 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 ZZ to additive error O(ε)O(ε) with ∣Z∣≍ε−2d−2∣log⁡ε∣|Z| \asymp ε^{-2d-2}|\logε|, ∣Y∣≍ε−max⁡{dν,4}|Y| \asymp ε^{-\max\{d_ν,4\}} with dνd_ν determined by the volume-growth properties of the probability measure on the observer set, and runtime O(∣Z∣3)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.

Figures & tables

Explore similar work

CardsList
  1. Denoising distances beyond the volumetric barrier

    Apr 1, 2026Han Huang, Pakawut Jiradilok, Elchanan MosselManifold LearningLatent Space Geometry

  2. Recovering the Euclidean Geometry of High-Dimensional Data Under Heterogeneous Noise

    Jul 24, 2025Keyi Li, Yuval Kluger, Boris LandaLatent Space Geometry

  3. The Observable Wasserstein Distance

    May 11, 2026Edivaldo Lopes dos Santos, Leandro Vicente Mauri, Washington Mio +1Sliced Wasserstein DistanceOptimal Transport