Randomized Dimensionality Reduction for k-means

Clustering

This paper makes further progress towards a better understanding of dimensionality reduction for kmeans

clustering. Namely, we present the first provably accurate feature selection method for k-means

clustering and, in addition, we present two feature extractionmethods. The first feature extractionmethod

is based on random projections and it improves upon the existing results in terms of time complexity and

number of features needed to be extracted. The second feature extraction method is based on fast approximate

SVD factorizations and it also improves upon the existing results in terms of time complexity. The

proposed algorithms are randomized and provide constant-factor approximation guarantees with respect

to the optimal k-means objective value.