# Tight Sensitivity Bounds For Smaller Coresets

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

## Key facts

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

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

- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [On the Size and Approximation Error of Distilled Sets](https://mlsanity.com/paper/2305.14113/) (2023)
- [Provable Pruning for Efficient 3D Gaussian Splatting via Coresets](https://mlsanity.com/paper/2607.02721/) (2026)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation](https://mlsanity.com/paper/2507.14631/) (2025)
- [Linear time small coresets for k-mean clustering of segments with applications](https://mlsanity.com/paper/2511.12564/) (2025)

## Abstract (arXiv)

An varepsilon-coreset for Least-Mean-Squares (LMS) of a matrix A∈ℝn× d is a small weighted subset of its rows that approximates the sum of squared distances from its rows to every affine k-dimensional subspace of ℝd, up to a factor of 1±varepsilon. Such coresets are useful for hyper-parameter tuning and solving many least-mean-squares problems such as low-rank approximation (k-SVD), k-PCA, Lassso/Ridge/Linear regression and many more. Coresets are also useful for handling streaming, dynamic and distributed big data in parallel. With high probability, non-uniform sampling based on upper bounds on what is known as importance or sensitivity of each row in A yields a coreset. The size of the (sampled) coreset is then near-linear in the total sum of these sensitivity bounds. We provide algorithms that compute provably tight bounds for the sensitivity of each input row. It is based on two ingredients: (i) iterative algorithm that computes the exact sensitivity of each point up to arbitrary small precision for (non-affine) k-subspaces, and (ii) a general reduction of independent interest from computing sensitivity for the family of affine k-subspaces in ℝd to (non-affine) (k+1)- subspaces in ℝd+1. Experimental results on real-world datasets, including the English Wikipedia documents-term matrix, show that our bounds provide significantly smaller and data-dependent coresets also in practice. Full open source is also provided.