Bi-Lipschitz extensions and outlier embeddings into trees
This work provides a theoretical advance in metric embeddings with outliers, relevant to algorithm designers working on data analysis and approximation algorithms.
The paper develops an algorithm for embedding metrics into hierarchically separated trees (HSTs) while handling outliers, achieving distortion (32+ε)c for all but O(k/ε log k) points, improving on previous work by extending embeddings to outliers with only O(log k) additional distortion.
We develop low distortion embeddings with outliers from arbitrary metrics into hierarchically separated trees (HSTs). In particular, we develop an efficient algorithm that for any $ε>0$, given an input metric $(X,d)$, and a probabilistic embedding of all but $k$ points from $X$ into HSTs with distortion $c$, samples from a probabilistic embedding of all but $O(\frac{k}ε\log k)$ points into HSTs that achieves distortion at most $(32+ε)c$. Our results are based on two key technical components. First, we extend an algorithm of Munagala et al. [2023] for minimizing the distortion of embeddings without outliers into HSTs to the setting with outliers. We combine this with new results on bi-Lipschitz extensions into trees and $\ell_1$ space. In particular, we show that any probabilistic embedding into HSTs can be extended to $k$ additional points with only a factor $O(\log k)$ of additional distortion. This bi-Lipschitz extension result utilizes a new probabilistic partitioning scheme that we call onion partitioning.