Clustering with Spectral Norm and the k-means Algorithm

Abstract

There has been much progress on efficient algorithms for clustering data points generated by a mixture of $k$ probability distributions under the assumption that the means of the distributions are well-separated, i.e., the distance between the means of any two distributions is at least $\Omega (k)$ standard deviations. These results generally make heavy use of the generative model and particular properties of the distributions. In this paper, we show that a simple clustering algorithm works without assuming any generative (probabilistic) model. Our only assumption is what we call a "proximity condition": the projection of any data point onto the line joining its cluster center to any other cluster center is $\Omega (k)$ standard deviations closer to its own center than the other center. Here the notion of standard deviations is based on the spectral norm of the matrix whose rows represent the difference between a point and the mean of the cluster to which it belongs. We show that in the generative models studied, our proximity condition is satisfied and so we are able to derive most known results for generative models as corollaries of our main result. We also prove some new results for generative models - e.g., we can cluster all but a small fraction of points only assuming a bound on the variance. Our algorithm relies on the well known $k$-means algorithm, and along the way, we prove a result of independent interest -- that the $k$-means algorithm converges to the "true centers" even in the presence of spurious points provided the initial (estimated) centers are close enough to the corresponding actual centers and all but a small fraction of the points satisfy the proximity condition. Finally, we present a new technique for boosting the ratio of inter-center separation to standard deviation.

Cited by in corpus (17)

• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Improved Spectral-Norm Bounds for Clustering
• Impact of regularization on Spectral Clustering
• Principal Component Analysis and Higher Correlations for Distributed Data
• Quantization/clustering: when and why does k-means work?
• Fundamental limits for learning hidden Markov model parameters
• Relax, no need to round: integrality of clustering formulations
• Learning from Untrusted Data
• Convergence Analysis of Gradient EM for Multi-component Gaussian Mixture
• Constant Approximation for $k$-Median and $k$-Means with Outliers via Iterative Rounding
• Learning RUMs: Reducing Mixture to Single Component via PCA
• A Fast Approximation Scheme for Low-Dimensional $k$-Means
• When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming
• Learning a Latent Simplex in Input-Sparsity Time
• Efficient, Certifiably Optimal Clustering with Applications to Latent Variable Graphical Models
• Clustering under Perturbation Resilience
• Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing