Oblivious Dimension Reduction fork-Means:Beyond Subspaces and the Johnson-Lindenstrauss Lemma

We show that fornpoints ind-dimensional Euclidean space, a dataoblivious random projection of the columns ontoO(((logk+log logn)/ε^6)log(1/ε)) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±ε) factor. The previous-bestupper bounds on O(logn/ε^2) given by a direct application of the Johnson-Lindenstrauss Lemma, and O(k/ε^2)given by [Cohen etal.-STOC’15]