Consider an instance of Euclidean $k$-means or $k$-medians clustering. We
show that the cost of the optimal solution is preserved up to a factor of
$(1+\varepsilon)$ under a projection onto a random $O(\log(k / \varepsilon) /
\varepsilon^2)$-dimensional subspace. Further, the cost of every clustering is
preserved within $(1+\varepsilon)$. More generally, our result applies to any
dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our
bound on the dimension is nearly optimal. Additionally, our result applies to
Euclidean $k$-clustering with the distances raised to the $p$-th power for any
constant $p$.
For $k$-means, our result resolves an open problem posed by Cohen, Elder,
Musco, Musco, and Persu (STOC 2015); for $k$-medians, it answers a question
raised by Kannan.

通过投影到随机的 O (log (k/ ε) / ε²) 维子空间上，可以近似保持欧几里得 k-means 或 k-medians 聚类的最优解成本，并且适用于任何满足温和的子高斯尾条件的维度缩减映射，其维数几乎是最优的。此外，该结果适用于所有权重的欧几里得 k - 聚类。