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'(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'(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 \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.