Claire Alexandra Bräuer:
The Effects of Initialization on the Convergence of Non-negative Matrix Factorization
Non-negative matrix factorization (NMF) refers to a group of algorithms that seek to factorize an input matrix X into a matrix product WH with the additional constraint that all three matrices may only contain non-negative entries. Because of its non-negativity constraint, it is a widely used tool in multivariate data-analysis as it allows for meaningful interpretations of extracted features. In this thesis we first motivate non-negative matrix factorization on two examples. Lee and Seung's multiplicative update rules to compute NMF provide us with an easy-to-implement, iterative algorithm, for which we provide its derivation and proof of convergence. We then address properties of NMF with a main focus on initialization, where we propose a novel initialization technique based on k-means++ clustering. Lastly, we include preliminary experimental results regarding the effects of different initialization techniques on the convergence of NMF.