Fetching the paper…

Reading the bibliography…

2015

On the tightness of an SDP relaxation of k-means

Iguchi, Takayuki, Mixon, Dustin G., Peterson, Jesse et al.

Original
PDF
Post on X

Understand

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.

On the tightness of an SDP relaxation of k-means · Around

Built on

Least squares quantization in pcm
S. Lloyd · 1982
Earlier work this paper cites.
A new greedy approach for facility location problems
K. Jain, M. Mahdian, and A. Saberi · 2002
Earlier work this paper cites.
A local search approximation algorithm for k-means clustering
T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu · 2002
Earlier work this paper cites.
A new theoretical framework for k k -means-type clustering
J. Peng and Y. Xia · 2005
Earlier work this paper cites.
The effectiveness of lloyd-type methods for the k-means problem
R. Ostrovsky, Y. Rabani, L. Schulman, and C. Swamy · 2006
Earlier work this paper cites.

Similar

k-means++: the advantages of careful seeding
D. Arthur and S. Vassilvitskii · 2007
Cited alongside, same era.
Approximating k-means-type clustering via semidefinite programming
J. Peng and Y. Wei · 2007
Cited alongside, same era.
NP-hardness of euclidean sum-of-squares clustering
D. Aloise, A. Deshpande, P. Hansen, and P. Popat · 2009
Cited alongside, same era.
User-friendly tail bounds for sums of random matrices
J. A. Tropp · 2010
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
Original
R. Vershynin · 2011
Cited alongside, same era.

Then

Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery
E. Elhamifar, G. Sapiro, and R. Vidal · 2012
Later among the works it cites.
Recovery guarantees for exemplar-based clustering
Original
A. Nellore and R. Ward · 2013
Later among the works it cites.
Relax, no need to round: Integrality of clustering formulations
Original
P. Awasthi, A. Bandeira, M. Charikar, K. Ravishankar, S. Villar, and R. Ward · 2014
Later among the works it cites.
Cone programming cheat sheet
D. G. Mixon · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…