# Terminal Embeddings

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2016.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures](https://mlsanity.com/paper/2107.06626/) (2021)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)

## Abstract (arXiv)

In this paper we study em terminal embeddings, in which one is given a finite metric (X,dX) (or a graph G=(V,E)) and a subset K subseteq X of its points are designated as em terminals. The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve ≈|K|· |X| pairs, the distortion depends only on |K|, rather than on |X|. We also strengthen this notion, and consider embeddings that approximately preserve the distances between em all pairs, but provide improved distortion for pairs containing a terminal. Surprisingly, we show that such embeddings exist in many settings, and have optimal distortion bounds both with respect to X × X and with respect to K × X. Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [ALN08] devised an tildeO(√log r)-approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an tildeO(√log |K|)-approximation for sparsest-cut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since |K| ≤ r, our bound generalizes that of [ALN08].