Aarhus University Seal

A Sampling Algorithm to Compute the Set of Feasible Solutions for NonNegative Matrix Factorization with an Arbitrary Rank

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


Nonnegative matrix factorization (NMF) is a useful method to extract features from multivariate data, but an important and sometimes neglected concern is that NMF can result in nonunique solutions. Often, there exist a set of feasible solutions (SFS), which makes it more difficult to interpret the factorization. This problem is especially ignored in cancer genomics, where NMF is used to infer information about the mutational processes present in the evolution of cancer. In this paper the extent of nonuniqueness is investigated for two mutational counts data, and a new sampling algorithm that can find the SFS is introduced. Our sampling algorithm is easy to implement and applies to an arbitrary rank of NMF. This is in contrast to state of the art, where the NMF rank must be smaller than or equal to four. For lower ranks we show that our algorithm performs similar to the polygon inflation algorithm that is developed in relation to chemometrics. Furthermore, we show how the size of the SFS can have a high influence on the appearing variability of a solution. Our sampling algorithm is implemented in the R package SFS (https://github.com/ragnhildlaursen/SFS).

Original languageEnglish
JournalSIAM Journal on Matrix Analysis and Applications
Pages (from-to)257-273
Number of pages17
Publication statusPublished - 2022

    Research areas

  • identifiability, mutational processes, nonnegative matrix factorization (NMF), sampling, uniqueness

See relations at Aarhus University Citationformats

ID: 281259589