Sketch-and-solve approaches to k-means clustering by semidefinite programming

Charles Clum, Dustin G. Mixon, Soledad Villar +1

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 op…