# Coresets for Clustering with Missing Values

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2021.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [Representative Subset Selection for Efficient Fine-Tuning in Self-Supervised Speech Recognition](https://mlsanity.com/paper/2203.09829/) (2022)
- [Efficient NTK using Dimensionality Reduction](https://mlsanity.com/paper/2210.04807/) (2022)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)

## Abstract (arXiv)

We provide the first coreset for clustering points in ℝd that have multiple missing values (coordinates). Previous coreset constructions only allow one missing coordinate. The challenge in this setting is that objective functions, like k-Means, are evaluated only on the set of available (non-missing) coordinates, which varies across points. Recall that an ε-coreset of a large dataset is a small proxy, usually a reweighted subset of points, that (1+ε)-approximates the clustering objective for every possible center set. Our coresets for k-Means and k-Median clustering have size (jk)O(min(j,k)) (ε-1 d log n)2, where n is the number of data points, d is the dimension and j is the maximum number of missing coordinates for each data point. We further design an algorithm to construct these coresets in near-linear time, and consequently improve a recent quadratic-time PTAS for k-Means with missing values [Eiben et al., SODA 2021] to near-linear time. We validate our coreset construction, which is based on importance sampling and is easy to implement, on various real data sets. Our coreset exhibits a flexible tradeoff between coreset size and accuracy, and generally outperforms the uniform-sampling baseline. Furthermore, it significantly speeds up a Lloyd's-style heuristic for k-Means with missing values.