Consider the k-means queries in \(\mathbb {R}^d\) , i.e., the cost is the sum of squared distances \(\sum _{p\in P}D(p,C)\)  over every point in \(P\)  to its nearest center in a given set \(C\)  of \(k\)  points in \(\mathbb {R}^d\) . It was proven that projecting \(P\)  onto an \(O(k/\varepsilon )\) -dimensional subspace that minimizes its sum of squared distances, known as the low-rank approximation of \(P\) , would preserve this sum, to any set of \(k\)  centers, up to a factor of \(1\pm \varepsilon \) . This is in some sense an \(\varepsilon \) -coreset for \(P\)  of size \(n\)  and that is not subset of the input, but of low-dimensionality. In particular, this result implies that there is a set of centers (known as centroid set [1]}) that is contained in a \(O(k/\varepsilon )\) -dimensional space, such that every set of \(k\)  centers in \(\mathbb {R}^d\)  can be replaced by a set of \(k\)  centers in the centroid set, that would yield the same cost up to a factor of \(1\pm \varepsilon \) . In particular, this implies that the dimension of the \(k\) -means problem can be reduced to \(O(k/\varepsilon )\)  instead of \(dk\) , i.e., independent of \(d\) . Combining this result with our paper yields the first coreset for \(k\) -means of size independent of \(d\)  that is subset of the input (in particular, preserve the sparsity of the input points) that also supports streaming.
