# Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

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

## Key facts

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

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

- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [FedCore: Straggler-Free Federated Learning with Distributed Coresets](https://mlsanity.com/paper/2402.00219/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Advancing Complex Wide-Area Scene Understanding with Hierarchical Coresets Selection](https://mlsanity.com/paper/2507.13061/) (2025)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Universal Weak Coreset](https://mlsanity.com/paper/2305.16890/) (2023)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation](https://mlsanity.com/paper/2507.14631/) (2025)
- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## Abstract (arXiv)

We obtain the first strong coresets for the k-median and subspace approximation problems with sum of distances objective function, on n points in d dimensions, with a number of weighted points that is independent of both n and d; namely, our coresets have size poly(k/ε). A strong coreset (1+ε)-approximates the cost function for all possible sets of centers simultaneously. We also give efficient nnz(A) + (n+d)poly(k/ε) + exp(poly(k/ε)) time algorithms for computing these coresets. We obtain the result by introducing a new dimensionality reduction technique for coresets that significantly generalizes an earlier result of Feldman, Sohler and Schmidt citeFSS13 for squared Euclidean distances to sums of p-th powers of Euclidean distances for constant p≥1.