Reconstruction of Manifold Distances from Noisy Observations

Abstract: This talk is an overview of a recent ArXiv preprint, which is joint work with Kevin Ren and Charles Fefferman (https://arxiv.org/abs/2511.13025). Thererin, we consider the problem of reconstructing the intrinsic geometry of a manifold from noisy pairwise distance observations. Specifically, let M denote a diameter 1 d-dimensional manifold and mu a probability measure on M that is mutually absolutely continuous with the volume measure. Suppose X_1, ..., X_N are i.i.d. samples of mu and we observe noisy-distance random variables d'(X_j, X_k) that are related to the true geodesic distances d(X_j,X_k). Specifically, we assume that Ed'(X_j, X_k) = F(d(X_j, X_k)) with F an unknown increasing bilipschitz function, along with mild assumptions on the concentration of the d'(X_j, X_k) and their independence. Under these conditions, we develop a new algorithm that recovers all distances between points in an ε-net of M up to additive error O(ε log(1/ε)), with sample complexity N ≍ ε^{-2d-2}\log(1/ε) and runtime o(N^3).

 

In this talk, I will introduce the result and provide intuition for a few of the techniques utilized in the paper. These techniques include a method for estimating L_2-inner products of certain expectation-functions f_x(y) = Ed'(x,y), which allows us to build robust clusters centered at points of our sample, as well as a novel "ruler-building" approach that uses these clusters to approximate the expected-noisy-distance function F, admitting recovery of the true distances.