On the tightness of an SDP relaxation of k-means

Abstract

Recently, Awasthi et al. introduced an SDP relaxation of the $k$-means problem in ${\mathbb{R}}^m$. In this work, we consider a random model for the data points in which $k$ balls of unit radius are deterministically distributed throughout ${\mathbb{R}}^m$, and then in each ball, $n$ points are drawn according to a common rotationally invariant probability distribution. For any fixed ball configuration and probability distribution, we prove that the SDP relaxation of the $k$-means problem exactly recovers these planted clusters with probability $1-e^{-\Omega (n)}$ provided the distance between any two of the ball centers is $>2+\epsilon$, where $\epsilon$ is an explicit function of the configuration of the ball centers, and can be arbitrarily small when $m$ is large.

References in corpus (1)

• Relax, no need to round: integrality of clustering formulations

Cited by in corpus (10)

• Sparse Regression: Scalable algorithms and empirical performance
• Convex Relaxation Methods for Community Detection
• Weighted total variation based convex clustering
• On the minimum of the mean-squared error in 2-means clustering
• Cutoff for exact recovery of Gaussian mixture models
• When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming
• Partial recovery bounds for clustering with the relaxed $K$means
• Improved Conic Reformulations for K-means Clustering
• Efficient, Certifiably Optimal Clustering with Applications to Latent Variable Graphical Models
• Distribution free optimality intervals for clustering