Improving Ultrametrics Embeddings Through Coresets

To tackle the curse of dimensionality in data analysis and unsupervised learning, it is critical to be able to efficiently compute "simple" faithful representations of the data that helps extract information, improves understanding and visualization of the structure. When the dataset consists of ddimensional vectors, simple representations of the data may consist in trees or ultrametrics, and the goal is to best preserve the distances (i.e.: dissimilarity values) between data elements. To circumvent the quadratic running times of the most popular methods for fitting ultrametrics, such as average, single, or complete linkage, Cohen-Addad et al. ( 2020 ) recently presented a new algorithm that for any c ≥ 1, outputs in time n 1+O(1/c 2 ) an ultrametric ∆ such that for any two points u, v, ∆(u, v) is within a multiplicative factor of 5c to the distance between u and v in the "best" ultrametric representation. We improve the above result and show how to improve the above guarantee from 5c to √ 2c + ε while achieving the same asymptotic running time. To complement the improved theoretical bound, we additionally show that the performances of our algorithm are significantly better for various real-world datasets.