Clustering subgaussian mixtures by semidefinite programming. (17th March 2017)

• Record Type: Journal Article
• Authors: Mixon, Dustin G; Villar, Soledad; Ward, Rachel
• Is Part Of: Information and inference. Volume 6:Number 4(2017)
• Page Start: 389
• Page End: 415
• Publication Date: 2017-03-17
• Subjects: clustering -- machine learning -- semidefinite programming -- approximation algorithm; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iax001
• Languages: English
• ISSNs: 2049-8764

Abstract

Abstract: We introduce a model-free relax-and-round algorithm for k -means clustering based on a semidefinite relaxation due to Peng and Wei (2007, SIAM J. Optim ., 18, 186–205). The algorithm interprets the output of the semidefinite program as a denoised version of the original data and then rounds this output to a hard clustering. We provide a generic method for proving performance guarantees for this algorithm, and we analyse the algorithm in the context of subgaussian mixture models. We also study the fundamental limits of estimating Gaussian centers by k -means clustering to compare our approximation guarantee to the theoretically optimal k -means clustering solution.