Recovering Geodesic Distances from Noisy Observations
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
- Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks
- Diffusion Models Observe Only Gradients: A Geometric Perspective on Score Matching Errors
- Quantifying Error Propagation and Model Collapse in Diffusion Models
- Behavior of prediction performance metrics with rare events
- Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
- Control Variate Design for Score-Function Gradient Estimators in Importance-Weighted Variational Inference