Uniqueness of nonnegative matrix factorizations by rigidity theory

Robert Krone, Kaie Kubjas

Research output: Contribution to journalArticleScientificpeer-review

8 Downloads (Pure)


Nonnegative matrix factorizations are often encountered in data mining applications where they are used to explain datasets by a small number of parts. For many of these applications it is desirable that there exists a unique nonnegative matrix factorization up to trivial modifications given by scalings and permutations. This means that model parameters are uniquely identifiable from the data. Rigidity theory of bar and joint frameworks is a field that studies uniqueness of point configurations given some of the pairwise distances. The goal of this paper is to use ideas from rigidity theory to study uniqueness of nonnegative matrix factorizations in the case when nonnegative rank of a matrix is equal to its rank. We characterize infinitesimally rigid nonnegative factorizations, prove that a nonnegative factorization is infinitesimally rigid if and only if it is locally rigid and a certain matrix achieves its maximal possible Kruskal rank, and show that locally rigid nonnegative factorizations can be extended to globally rigid nonnegative factorizations. These results give so far the strongest necessary condition for the uniqueness of a nonnegative factorization. We also explore connections between rigidity of nonnegative factorizations and boundaries of the set of matrices of fixed nonnegative rank. Finally we extend these results from nonnegative factorizations to completely positive factorizations.

Original languageEnglish
Pages (from-to)134-164
Number of pages31
JournalSIAM Journal on Matrix Analysis and Applications
Issue number1
Publication statusPublished - Feb 2021
MoE publication typeA1 Journal article-refereed


  • Completely positive factorizations
  • Nonnegative matrix factorizations
  • Rigidity theory
  • Semialgebraic sets

Fingerprint Dive into the research topics of 'Uniqueness of nonnegative matrix factorizations by rigidity theory'. Together they form a unique fingerprint.

Cite this