  We introduce a sketch-and-solve approach to speed up the Peng-Wei
semidefinite relaxation of k-means clustering. When the data is appropriately
separated we identify the k-means optimal clustering. Otherwise, our approach
provides a high-confidence lower bound on the optimal k-means value. This lower
bound is data-driven; it does not make any assumption on the data nor how it is
generated. We provide code and an extensive set of numerical experiments where
we use this approach to certify approximate optimality of clustering solutions
obtained by k-means++.
