Fetching the paper…
Reading the bibliography…
One of the most popular algorithms for clustering in Euclidean space is the $k$-means algorithm; $k$-means is difficult to analyze mathematically, and few theoretical guarantees are known about it, particularly when the data is {\em well-clustered}.
Cluster analysis of multivariate data: Efficiency vs. interpretability of classification
E. Forgey · 1965
Earlier work this paper cites.
Some methods for classification and analysis of multivariate observations
J. B. MacQueen · 1967
Earlier work this paper cites.
Maximum likelihood from incomplete data via the em algorithm (with discussion)
A. P. Dempster, N. M. Laird, and D. B. Rubin · 1977
Earlier work this paper cites.
Strong consistency of k-means clustering
D. Pollard · 1981
Earlier work this paper cites.
Least squares quantization in PCM
S.P. Lloyd · 1982
Earlier work this paper cites.
Mixture densities, maximum likelihood and the em algorithm
R. Redner and H. Walker · 1984
Earlier work this paper cites.
Mixture Models:Theory, Geometry and Applications
B. G. Lindsey · 1996
Earlier work this paper cites.
On convergence properties of the em algorithm for gaussian mixtures
L. Xu and M. I. Jordan · 1996
Earlier work this paper cites.
B. Yu · 1997
Earlier work this paper cites.
Learning mixtures of gaussians
S. Dasgupta · 1999
Cited alongside, same era.
A two-round variant of EM for Gaussian mixtures
S. Dasgupta and L. Schulman · 2000
Cited alongside, same era.
A spectral algorithm for learning mixtures of distributions
V. Vempala and G. Wang · 2002
Cited alongside, same era.
Learning mixtures of separated nonspherical Gaussians
S. Arora and R. Kannan · 2005
Cited alongside, same era.
On spectral learning of mixtures of distributions
D. Achlioptas and F. McSherry · 2005
Cited alongside, same era.
Elements of Information Theory : Second Edition
T. Cover and J. Thomas · 2005
Cited alongside, same era.
The spectral method for general mixture models
An investigation of computational and informational limits in gaussian mixture clustering
N. Srebro, G. Shakhnarovich, and S. T. Roweis · 2006
Later among the works it cites.
Separating populations with wide data: A spectral analysis
A. Blum, A. Coja-Oghlan, A. M. Frieze, and S. Zhou · 2007
Later among the works it cites.
Learning Mixtures of Distributions
K. Chaudhuri · 2007
Later among the works it cites.
A rigorous analysis of population stratification with limited data
K. Chaudhuri, E. Halperin, S. Rao, and S. Zhou · 2007
Later among the works it cites.
Isotropic PCA and affine-invariant clustering
S. C. Brubaker and S. Vempala · 2008
Later among the works it cites.
Learning mixtures of distributions using correlations and independence
K. Chaudhuri and S. Rao · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
R. Kannan, H. Salmasian, and S. Vempala · 2005
Cited alongside, same era.
How slow is the k-means method?
D. Arthur and S. Vassilvitskii · 2006
Cited alongside, same era.
The effectiveness of lloyd-type methods for the k-means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy · 2006
Cited alongside, same era.
k-means has polynomial smoothed complexity
D. Arthur, B. Manthey, and H. Röglin · 2009
Closest in time.
Improved smoothed analysis of the k-means method
B. Manthey and H. Röglin · 2009
Closest in time.
k-means takes exponentially many iterations even in the plane
A. Vattani · 2009
Closest in time.