EPTAS for $k$-means Clustering of Affine Subspaces

Abstract

We consider a generalization of the fundamental $k$-means clustering for data with incomplete or corrupted entries. When data objects are represented by points in ${\mathbb{R}}^d$, a data point is said to be incomplete when some of its entries are missing or unspecified. An incomplete data point with at most $\hat{I}”$ unspecified entries corresponds to an axis-parallel affine subspace of dimension at most $\hat{I}”$, called a $\hat{I}”$-point. Thus we seek a partition of $n$ input $\hat{I}”$-points into $k$ clusters minimizing the $k$-means objective. For $\hat{I}”=0$, when all coordinates of each point are specified, this is the usual $k$-means clustering. We give an algorithm that finds an $(1+\hat{I}\mu )$-approximate solution in time $f(k,\hat{I}\mu ,\hat{I}”)\cdot n^2\cdot d$ for some function $f$ of $k,\hat{I}\mu$, and $\hat{I}”$ only.

To be published in Symposium on Discrete Algorithms (SODA) 2021