Back to Search
Start Over
Probably certifiably correct k-means clustering.
- Source :
- Mathematical Programming; Oct2017, Vol. 165 Issue 2, p605-642, 38p
- Publication Year :
- 2017
-
Abstract
- Recently, Bandeira (C R Math, 2015) 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 Peng and Wei (SIAM J Optim 18(1):186-205, 2007) 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 (SIAM J Optim 18(1):186-205, 2007) 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 165
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 125431194
- Full Text :
- https://doi.org/10.1007/s10107-016-1097-0