  Recently, Bandeira [arXiv:1509.00824] introduced a new type of algorithm (the
so-called probably certifiably correct algorithm) that combines fast solvers
with the optimality certificates provided by convex relaxations. In this paper,
we devise such an algorithm for the problem of k-means clustering. First, we
prove that Peng and Wei's semidefinite relaxation of k-means is tight with high
probability under a distribution of planted clusters called the stochastic ball
model. Our proof follows from a new dual certificate for integral solutions of
this semidefinite program. Next, we show how to test the optimality of a
proposed k-means solution using this dual certificate in quasilinear time.
Finally, we analyze a version of spectral clustering from Peng and Wei that is
designed to solve k-means in the case of two clusters. In particular, we show
that this quasilinear-time method typically recovers planted clusters under the
stochastic ball model.
