Latent Distance Denoising in Metric Measure Spaces

Pairwise observations often encode a noisy monotone transform of an unobserved distance. We study how to denoise all latent pairwise distances when the underlying points are sampled from a metric measure space governed only by lower volume-growth bounds, without assuming coordinates, curvature, or a fixed dimension. Our observable neighborhood construction converts internal similarity into controlled-radius clusters and then denoises distances by independent cluster-to-cluster averaging. At any fixed target accuracy, the resulting algorithm produces uniform latent-distance estimates in near-linear time up to polylogarithmic factors. With 1,200 sampled points, controlled simulations reduce normalized mean absolute error from 0.107 to 0.022 on an interval and from 0.112 to 0.047 on a branching metric tree. We also give an exhaustive procedure that reaches finer resolution, together with an indistinguishability lower bound showing that lower volume growth alone cannot guarantee arbitrarily accurate denoising. The results expose a statistical-computational tension: fixed-accuracy denoising is efficient in general metric measure spaces, while the finer resolutions certified by our assumptions require substantially more computation.