On Efficient Low Distortion Ultrametric Embedding

Authors Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde

Publication date 15 August 2020

Abstract: 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. The most popular algorithms for this task are the classic linkage algorithms (single, average, or complete). However, these methods on a data set of

n

points in

O m e g a (l o g n)

dimensions exhibit a quite prohibitive running time of

T h e t a (n^{2})

. In this paper, we provide a new algorithm which takes as input a set of points

P

in

m a t h b b R^{d}

, and for every

c g e 1

, runs in time

n^{1 + f r a c h o c^{2}}

(for some universal constant

h o > 1

) to output an ultrametric

D e l t a

such that for any two points

u, v

in

P

, we have

D e l t a (u, v)

is within a multiplicative factor of

5 c

to the distance between

u

and

v

in the "best" ultrametric representation of

P

. Here, the best ultrametric is the ultrametric

i l d e D e l t a

that minimizes the maximum distance distortion with respect to the

e l l_{2}

distance, namely that minimizes

u n d e r s e t u, v i n P m a x f r a c i l d e D e l t a (u, v) | u - v |_{2}

. We complement the above result by showing that under popular complexity theoretic assumptions, for every constant

v a r e p s i l o n > 0

, no algorithm with running time

n^{2 - v a r e p s i l o n}

can distinguish between inputs in

e l l_{i} n f t y

-metric that admit isometric embedding and those that incur a distortion of

f r a c 32

. 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.

This page was built for publication: On Efficient Low Distortion Ultrametric Embedding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347128)