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

Apr 1, 2026

Denoising distances beyond the volumetric barrier

We study the problem of reconstructing the latent geometry of a dd-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/dn^{-1/d} coming from the fact that a generic point of the manifold typically lies at distance of order n−1/dn^{-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)n^{-2/(d+5)} up to polylogarithmic factors in nn in polynomial time. This strictly beats the volumetric barrier for dimensions d>5d > 5. As a consequence of obtaining pointwise precision better than n−1/dn^{-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/dn^{-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.
Jul 24, 2025

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

Pairwise Euclidean distances provide a simple geometric representation of high-dimensional data and underlie many data analysis methods, including clustering, visualization, and manifold learning. However, in real-world applications, these distances can be severely corrupted by heterogeneous noise, where different data points are subject to different, and potentially large, noise levels. Such noise distorts the distances inhomogeneously, leading to a misrepresentation of the underlying data geometry. In this work, we ask whether the underlying clean Euclidean geometry can nevertheless be recovered from the corrupted pairwise distances. We answer this question affirmatively, showing that, perhaps surprisingly, such recovery is possible across a broad class of high-dimensional settings with underlying low-dimensional geometry, even when the noise magnitudes vary substantially across observations. We develop a principled approach for recovering the clean pairwise distances, without prior knowledge of either the clean data structure or the noise distribution, and establish probabilistic recovery guarantees. In particular, the recovery error converges to zero at polynomial rates as the feature dimension and dataset size increase simultaneously. Experiments on synthetic datasets demonstrate accurate recovery of the Euclidean geometry in challenging regimes and improved robustness of downstream methods that rely on pairwise distances. When applied to real single-cell RNA sequencing data, our method reliably recovers local neighborhood structure, enabling accurate nearest-neighbor identification used in many downstream analyses.
May 11, 2026

The Observable Wasserstein Distance

We introduce the observable Wasserstein distance, a framework for deriving lower bounds on the Wasserstein distance between probability measures on Polish metric spaces, designed to bypass the computational intractability of exact optimal transport in large-scale, non-Euclidean datasets. Analogous to the sliced Wasserstein distance in Rd\mathbb{R}^d, our approach projects measures onto the real line via 1-Lipschitz observables and computes the Wasserstein distances between the resulting pushforward distributions. We define a hierarchy of pseudo-metrics by restricting observables to a nested chain of subspaces. A central theoretical contribution is an injectivity result linking the metric covering dimension of the support of a measure to the specific order in the hierarchy that guarantees unique recovery. This serves as a metric-space analogue to the Cramér-Wold Device for Euclidean distributions. We demonstrate that this hierarchy offers a tunable trade-off between sharpness as a lower bound on the Wasserstein distance and computational efficiency. We also present a discrete computational model for finite grids and numerical experiments validating the efficacy and utility of these approximations.