Denoising Distances in Metric Measure Spaces

Recent work studied the problem of finding clusters and denoising pairwise distances from noisy distances of points sampled on a manifold. We study the same problems in more general metric measure spaces under a lower mass condition. We give an algorithm that extracts large localized clusters around every sampled point, which can be used to denoise distances, with near-linear running time in the dense regime for fixed target distance error $r$. When the target distance error $r$ is allowed to vanish as $n\to \mathrm{\infty }$, we identify the sharp information-theoretic scale for achieving distance error $r$, suggesting a statistical-computational gap for high-accuracy denoising beyond the Riemannian setting.