Probably certifiably correct \(k\)-means clustering (Q1675259)

Clustering is a central problem in unsupervised machine learning. The aim of \(k\)-means clustering is the partitioning of a given finite set \(\{ x_i \}_{i=1}^N\) into \(k\) subsets. A definition of a probably certificably correct algorithm is given. First, it is proven that Peng and Wei's semidefinite relaxation of \(k\)-means [\textit{J. Peng} and \textit{Y. Wei}, SIAM J. Optim. 18, No. 1, 186--205 (2007; Zbl 1146.90046)] is tight. It is shown how to test the optimality of a proposed \(k\)-means solution using this dual certificate in quasilinear time. It typically plants clusters under the stochastic ball method. A version of spectral clusteing is designed to solve \(k\)-means in the case of two clusters.