Sketch-and-solve approaches to k-means clustering by semidefinite programming
- Resource Type
- Working Paper
- Authors
- Clum, Charles; Mixon, Dustin G.; Villar, Soledad; Xie, Kaiying
- Source
- Subject
- Computer Science - Machine Learning
Computer Science - Data Structures and Algorithms
Computer Science - Information Theory
Mathematics - Optimization and Control
Mathematics - Statistics Theory
Statistics - Machine Learning
- Language
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++.