Random Projections for $k$-means Clustering

Christos Boutsidis, Anastasios Zouzias, Petros Drineas

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 \in \RR^{n \times d}…