# Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering

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

## Key facts

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

## Built on by (most cited first, 30 of 53)

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [Feature Affinity Assisted Knowledge Distillation and Quantization of Deep Neural Networks on Label-Free Data](https://mlsanity.com/paper/2302.10899/) (2023)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [Fast and Simple Spectral Clustering in Theory and Practice](https://mlsanity.com/paper/2310.10939/) (2023)
- [Probabilistic methods for approximate archetypal analysis](https://mlsanity.com/paper/2108.05767/) (2021)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)

## Abstract (arXiv)

Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+varepsilon) under a projection onto a random O(log(k / varepsilon) / varepsilon2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+varepsilon). More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p. For k-means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan.