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 can be projected into dimensions, for any in time, such that with constant probability the optimal k-partition of the point set is preserved within a factor of The projection is done by post-multiplying A with a d × t random matrix R having entries 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.