{"id":"arxiv/2606.18301","url":"https://arxiv.org/abs/2606.18301","tags":["cs.CG","math.PR"],"score":0,"title":"Denoising Distances in Metric Measure Spaces","domain":"cs.CG","source":"arxiv","authors":["Han Huang","Pakawut Jiradilok","Elchanan Mossel"],"reviews":0,"subject":"cs.CG","summary":"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\\infty\\), we identify the sharp information-theoretic scale for achieving distance…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-16","reactions":{}}