A Faster $k$-means++ Algorithm

$k$-means++ is an important algorithm for choosing initial cluster centers for the $k$-means clustering algorithm. In this work, we present a new algorithm that can solve the $k$-means++ problem with nearly optimal running time. Given $n$ data points in ${\mathbb{R}}^d$, the current state-of-the-art algorithm runs in $\tilde{O}(k)$ iterations, and each iteration takes $\tilde{O}(ndk)$ time. The overall running time is thus $\tilde{O}(nd{k}^2)$. We propose a new algorithm $\text{textsc}FastKmeans++$ that only takes in $\tilde{O}(nd+n{k}^2)$ time, in total.