mlsanityData to 14 Oct 2026

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

arXiv 1811.03195 ↗First posted 8 Nov 2018cs.DS cs.LGcited by 53

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 14; 2022: 11; 2023: 14; 2024: 9; 2025: 5.

53 papers.

Sort:

By area:

  1. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  2. 2021Learning-Augmented k-means Clusteringcited by 26
  3. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  4. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  5. 2021Locally Private k-Means in One Roundcited by 19
  6. 2023Replicable Clusteringcited by 19
  7. 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15
  8. 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
  9. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  10. 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
  11. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  12. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 11
38 more
  1. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  2. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  3. 2024Efficiently Computing Similarities to Private Datasetscited by 9
  4. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  5. 2022An Empirical Evaluation of k-Means Coresetscited by 7
  6. 2021Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clusteringcited by 6
  7. 2023Feature Affinity Assisted Knowledge Distillation and Quantization of Deep Neural Networks on Label-Free Datacited by 5
  8. 2023Multi-Swap k-Means++cited by 5
  9. 2023Fast and Simple Spectral Clustering in Theory and Practicecited by 5
  10. 2021Probabilistic methods for approximate archetypal analysiscited by 4
  11. 2022k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacycited by 4
  12. 2023Adversarially robust clustering with optimality guaranteescited by 4
  13. 2023On Generalization Bounds for Projective Clusteringcited by 4
  14. 2024Settling Time vs. Accuracy Tradeoffs for Clustering Big Datacited by 4
  15. 2025A Tight VC-Dimension Analysis of Clustering Coresets with Applicationscited by 4
  16. 2022Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvaluescited by 3
  17. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  18. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2
  19. 2023Differential Privacy for Clustering Under Continual Observationcited by 2
  20. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  21. 2025Differentially Private Wasserstein Barycenterscited by 2
  22. 2021Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Errorcited by 1
  23. 2022Robust and Provable Guarantees for Sparse Random Embeddingscited by 1
  24. 2022Socially Fair Center-based and Linear Subspace Clusteringcited by 1
  25. 2023Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guaranteescited by 1
  26. 2023On Robust Wasserstein Barycenter: The Model and Algorithmcited by 1
  27. 2024Contrastive Explainable Clustering with Differential Privacycited by 1
  28. 2024Making Old Things New: A Unified Algorithm for Differentially Private Clusteringcited by 1
  29. 2021Communication-efficient k-Means for Edge-based Machine Learningcited by 0
  30. 2021Confidence-Optimal Random Embeddingscited by 0
  31. 2022Hashing Learning with Hyper-Class Representationcited by 0
  32. 2022Improved Coresets for Euclidean k-Meanscited by 0
  33. 2023Exact Non-Oblivious Performance of Rademacher Random Embeddingscited by 0
  34. 2023Learning the Positions in CountSketchcited by 0
  35. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  36. 2024Node Similarities under Random Projections: Limits and Pathological Casescited by 0
  37. 2024Coresets for Multiple ℓp Regressioncited by 0
  38. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0

50 most cited of 53 All 53 (JSON)