THEORETICAL ADVANCES IN CLUSTERING WITH APPLICATIONS TO MATRIX FACTORIZATION

Abstract

The main purpose of this thesis is to theoretically analyze the applications of clustering in various unsupervised learning problems, including the learning of mixture models and nonnegative matrix factorization (NMF). The thesis mainly consists of two parts. The first part considers the informativeness of the k-means algorithm, which is perhaps the most popular clustering algorithm, for learning mixture models. In the second part, we propose a geometric assumption on nonnegative data matrices such that under this assumption, we are able to provide upper bounds (both deterministic and probabilistic) on the relative error of nonnegative matrix factorization.