  In this paper, we present a linear-time approximation scheme for $k$-means
clustering of \emph{incomplete} data points in $d$-dimensional Euclidean space.
An \emph{incomplete} data point with $\Delta>0$ unspecified entries is
represented as an axis-parallel affine subspaces of dimension $\Delta$. The
distance between two incomplete data points is defined as the Euclidean
distance between two closest points in the axis-parallel affine subspaces
corresponding to the data points. We present an algorithm for $k$-means
clustering of axis-parallel affine subspaces of dimension $\Delta$ that yields
an $(1+\epsilon)$-approximate solution in $O(nd)$ time. The constants hidden
behind $O(\cdot)$ depend only on $\Delta, \epsilon$ and $k$. This improves the
$O(n^2 d)$-time algorithm by Eiben et al.[SODA'21] by a factor of $n$.
