  We provide the first coreset for clustering points in $\mathbb{R}^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
$\epsilon$-coreset of a large dataset is a small proxy, usually a reweighted
subset of points, that $(1+\epsilon)$-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))} (\epsilon^{-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.
