Abstract: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 $\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 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.
From: Kristin Sheridan [view email]
[v1]
Wed, 21 Jan 2026 21:09:18 UTC (627 KB)
[v2]
Sat, 31 Jan 2026 23:34:48 UTC (76 KB)
[v3]
Tue, 23 Jun 2026 18:10:16 UTC (628 KB)
[v4]
Thu, 16 Jul 2026 20:34:39 UTC (630 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。