# Reconstruction of Manifold Distances from Noisy Observations

arXiv: https://arxiv.org/abs/2511.13025 · HTML: https://mlsanity.com/paper/2511.13025/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 24 references that are in the map.
- First posted on arXiv 17 Nov 2025.

## Builds on (most cited first, 1 of 1)

- [Non-linear dimensionality reduction: Riemannian metric estimation and the problem of geometric discovery](https://mlsanity.com/paper/1305.7255/) (2013)

## Built on by (most cited first, 1 of 1)

- [Denoising distances beyond the volumetric barrier](https://mlsanity.com/paper/2604.00432/) (2026)

## Abstract (arXiv)

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 μ a probability measure on M that is mutually absolutely continuous with the volume measure. Suppose X1,dots,XN are i.i.d. samples of μ and we observe noisy-distance random variables d'(Xj, Xk) that are related to the true geodesic distances d(Xj,Xk). With mild assumptions on the distributions and independence of the noisy distances, we develop a new framework for recovering all distances between points in a sufficiently dense subsample of M. Our framework improves on previous work which assumed i.i.d. additive noise with known moments. Our method is based on a new way to estimate L2-norms of certain expectation-functions fx(y)=mathbbEd'(x,y) and use them to build robust clusters centered at points of our sample. Using a new geometric argument, we establish that, under mild geometric assumptions--bounded curvature and positive injectivity radius--these clusters allow one to recover the true distances between points in the sample up to an additive error of O(varepsilon log varepsilon-1). We develop two distinct algorithms for producing these clusters. The first achieves a sample complexity N asymp varepsilon-2d-2log(1/varepsilon) and runtime o(N3). The second introduces novel geometric ideas that warrant further investigation. In the presence of missing observations, we show that a quantitative lower bound on sampling probabilities suffices to modify the cluster construction in the first algorithm and extend all recovery guarantees. Our main technical result also elucidates which properties of a manifold are necessary for the distance recovery, which suggests further extension of our techniques to a broader class of metric probability spaces.