Title: The Informativeness of $k$-Means and Dimensionality Reduction for Learning Mixture Models,
Abstract: The learning of mixture models can be viewed as a clustering problem. Indeed,
given data samples independently generated from a mixture of distributions, we
often would like to find the correct target clustering of the samples according
to which component distribution they were generated from. For a clustering
problem, practitioners often choose to use the simple k-means algorithm.
k-means attempts to find an optimal clustering which minimizes the
sum-of-squared distance between each point and its cluster center. In this
paper, we provide sufficient conditions for the closeness of any optimal
clustering and the correct target clustering assuming that the data samples are
generated from a mixture of log-concave distributions. Moreover, we show that
under similar or even weaker conditions on the mixture model, any optimal
clustering for the samples with reduced dimensionality is also close to the
correct target clustering. These results provide intuition for the
informativeness of k-means (with and without dimensionality reduction) as an
algorithm for learning mixture models. We verify the correctness of our
theorems using numerical experiments and demonstrate using datasets with
reduced dimensionality significant speed ups for the time required to perform
clustering.