Aarhus University Seal

A Unifying Framework and Comparison of Algorithms for Non-negative Matrix Factorisation

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review


Non-negative matrix factorisation (NMF) is an increasingly popular unsupervised learning method. However, parameter estimation in the NMF model is a difficult high-dimensional optimisation problem. We consider algorithms of the alternating least squares type. Solutions to the least squares problem fall in two categories. The first category is iterative algorithms, which include algorithms such as the majorise–minimise (MM) algorithm, coordinate descent, gradient descent and the Févotte-Cemgil expectation–maximisation (FC-EM) algorithm. We introduce a new family of iterative updates based on a generalisation of the FC-EM algorithm. The coordinate descent, gradient descent and FC-EM algorithms are special cases of this new EM family of iterative procedures. Curiously, we show that the MM algorithm is never a member of our general EM algorithm. The second category is based on cone projection. We describe and prove a cone projection algorithm tailored to the non-negative least square problem. We compare the algorithms on a test case and on the problem of identifying mutational signatures in human cancer. We generally find that cone projection is an attractive choice. Furthermore, in the cancer application, we find that a mix-and-match strategy performs better than running each algorithm in isolation.

Original languageEnglish
JournalInternational Statistical Review
Pages (from-to)29-53
Publication statusPublished - Apr 2020

    Research areas

  • Cone projection, EM-algorithm, mutational signatures, non-negative least squares (NLS), non-negative matrix factorisation (NMF), SIGNATURES

See relations at Aarhus University Citationformats

ID: 178937402