Denoising Distances in Metric Measure Spaces
For researchers working on metric learning and clustering in non-smooth spaces, this work identifies a fundamental trade-off between accuracy and computational efficiency.
The paper extends denoising of pairwise distances from Riemannian manifolds to general metric measure spaces under lower regularity, providing an efficient algorithm for fixed-accuracy denoising and showing a statistical-computational gap for higher accuracy.
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 \lowerphiregularity{}. We give an algorithm that extracts large localized clusters around every sampled point and uses them to denoise distances to any fixed accuracy, with near-linear running time in the dense fixed-accuracy regime. 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.