Denoising Distances in Metric Measure Spaces

Abstract

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 error \(r\), suggesting a statistical-computational gap for high-accuracy denoising beyond the Riemannian setting.

Update the lower bound to close the gap of log(n)