# Metric embedding with outliers

arXiv: https://arxiv.org/abs/1508.03600 · HTML: https://mlsanity.com/paper/1508.03600/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2015.

## Built on by (most cited first, 1 of 1)

- [Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams](https://mlsanity.com/paper/2311.17840/) (2023)

## Abstract (arXiv)

We initiate the study of metric embeddings with outliers. Given some metric space (X,ρ) we wish to find a small set of outlier points K subset X and either an isometric or a low-distortion embedding of (Xsetminus K,ρ) into some target metric space. This is a natural problem that captures scenarios where a small fraction of points in the input corresponds to noise. For the case of isometric embeddings we derive polynomial-time approximation algorithms for minimizing the number of outliers when the target space is an ultrametric, a tree metric, or constant-dimensional Euclidean space. The approximation factors are 3, 4 and 2, respectively. For the case of embedding into an ultrametric or tree metric, we further improve the running time to O(n2) for an n-point input metric space, which is optimal. We complement these upper bounds by showing that outlier embedding into ultrametrics, trees, and d-dimensional Euclidean space for any d≥ 2 are all NP-hard, as well as NP-hard to approximate within a factor better than 2 assuming the Unique Game Conjecture. For the case of non-isometries we consider embeddings with small ℓ∞ distortion. We present polynomial-time bi-criteria approximation algorithms. Specifically, given some ε > 0, let kε denote the minimum number of outliers required to obtain an embedding with distortion ε. For the case of embedding into ultrametrics we obtain a polynomial-time algorithm which computes a set of at most 3kε outliers and an embedding of the remaining points into an ultrametric with distortion O(ε log n). For embedding a metric of unit diameter into constant-dimensional Euclidean space we present a polynomial-time algorithm which computes a set of at most 2kε outliers and an embedding of the remaining points with distortion O(√ε).