Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling

Tyler Chen, Archan Ray, Akshay Seshadri +6

The $k$-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the $k$-means algorithm is that each iteration requires time…