Random Projections for $k$-means Clustering

This paper discusses the topic of dimensionality reduction for k-means clustering. We prove that any set of n points in d dimensions (rows in a matrix A ∈ ℝn x d) can be projected into t = Ω(k/e2) dimensions, for any e ∈ (0, 1/3), in O(nd[e-2k/ log(d)]) time, such that with constant probability the optimal k-partition of the point set is preserved within a factor of 2 + e. The projection is done by post-multiplying A with a d x t random matrix R having entries + 1/√t or -1/√t with equal probability. A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results.