We develop low distortion embeddings with outliers from arbitrary metrics into hierarchically separated trees (HSTs). In particular, we propose an efficient algorithm that, for any $\epsilon > 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}{\epsilon}\log k)$ points into HSTs that achieves distortion at most $(32+\epsilon)c$.
Our results are based on two key technical components. First, we extend an algorithm by 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.
Blogger's Review: This study makes significant advancements in low distortion embeddings handling outliers, particularly in tree structures. The new onion partitioning method presents fresh insights for further optimizing embeddings and is worth exploring and applying.