On efficient low distortion ultrametric embedding

A classic problem in unsupervised learning and data analysis is to find simpler and easy-to-visualize representations of the data that preserve its essential properties. A widely-used method to preserve the underlying hierarchical structure of the data while reducing its complexity is to find an embedding of the data into a tree or an ultrametric, but computing such an embedding on a data set of n points in Ω(log n) dimensions incurs a quite prohibitive running time of Θ(n²). In this paper, we provide a new algorithm which takes as input a set of points P in R^d, and for every c ≥ 1, runs in time n^{1+ c ρ 2} (for some universal constant ρ > 1) to output an ultrametric ∆ such that for any two points u, v in P, we have ∆(u, v) is within a multiplicative factor of 5c to the distance between u and v in the “best” ultrametric representation of P. Here, the best ultrametric is the ultrametric ∆^e that minimizes the maximum distance distortion with respect to the l₂ distance, namely that minimizes max ^{∆e (u,v})/ku−vk₂. u,v∈P We complement the above result by showing that under popular complexity theoretic assumptions, for every constant ε > 0, no algorithm with running time n^2−ε can distinguish between inputs in l_∞-metric that admit isometric embedding and those that incur a distortion of 3/2. Finally, we present empirical evaluation on classic machine learning datasets and show that the output of our algorithm is comparable to the output of the linkage algorithms while achieving a much faster running time.