  We present a study on how to effectively reduce the dimensions of the
$k$-means clustering problem, so that provably accurate approximations are
obtained. Four algorithms are presented, two \textit{feature selection} and two
\textit{feature extraction} based algorithms, all of which are randomized.
