Clustering with Spectral Norm and the k-means Algorithm

Amit Kumar, Ravindran Kannan

There has been much progress on efficient algorithms for clustering data points generated by a mixture of $k$ probability distributions under the assumption that the means of the d…