Denoising Distances in Metric Measure Spaces

Recent work studied the problem of finding clusters and denoising pairwise distances from points sampled on a manifold. We study the same problems in more general metric measure spaces and provide efficient algorithm to partition the points to clusters of a fixed radii and denoise distances to any fixed accuracy. We also show how to achieve much higher accuracy with a non-efficient algorithm. This suggests that unlike the Riemannian case, denoising to higher accuracy in more general metric spaces has a statistical-computational gap.