# Optimal terminal dimensionality reduction in Euclidean space

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2018.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN](https://mlsanity.com/paper/2206.03376/) (2022)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)

## Abstract (arXiv)

Let varepsilon∈(0,1) and Xsubsetmathbb Rd be arbitrary with |X| having size n>1. The Johnson-Lindenstrauss lemma states there exists f:Xrightarrowmathbb Rm with m = O(varepsilon-2log n) such that  forall x∈ X forall y∈ X, |x-y|2 ≤ |f(x)-f(y)|2 ≤ (1+varepsilon)|x-y|2 .  We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: "forall y∈ X" in the above statement may be replaced with "forall y∈mathbb Rd", so that f not only preserves distances within X, but also distances to X from the rest of space. Previously this stronger version was only known with the worse bound m = O(varepsilon-4log n). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].