Minimum description length as an objective function for non-negative matrix factorization

Non-negativematrix factorization (NMF) is a dimensionality reduction technique whichtends to produce a sparse representation of data. Commonly, the error between the actual and recreated matrices is used as an objective function, butthis method may not produce the type of representation we desire as it allows for the complexity of the model to grow, constrained only by the size of the subspace and the non-negativity requirement. If additional constraints, such as sparsity, are imposed the question of parameter selection becomes critical. Insteadof adding sparsity constraints in an ad-hoc manner we propose a novel objective function created by using the principle of minimum description length (MDL). Our formulation, MDL-NMF, automatically trades off between the complexity and accuracy of the model using a principled approach with little parameter selection or the need for domain expertise. We demonstrate our model works effectively on three heterogeneous data-sets and on a range of semisynthetic data showing the broad applicability of our method. Keywords: nonnegative matrix factorisation, minimum description length, model selection 1. Introduction Nonnegative matrix factorisation (NMF) is a popular linear dimensionality reduction technique. Its ability to produce a sparse and parts based representation, incontrast to principal component analysis (PCA) which is variance preserving, has been exploited in a range of applications [1, 2, 3].