Non-Negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition

Kejun Huang, Nicholas D. Sidiropoulos, Ananthram Swami

Research output: Contribution to journalArticlepeer-review

138 Scopus citations

Abstract

Non-negative matrix factorization (NMF) has found numerous applications, due to its ability to provide interpretable decompositions. Perhaps surprisingly, existing results regarding its uniqueness properties are rather limited, and there is much room for improvement in terms of algorithms as well. Uniqueness aspects of NMF are revisited here from a geometrical point of view. Both symmetric and asymmetric NMF are considered, the former being tantamount to element-wise non-negative square-root factorization of positive semidefinite matrices. New uniqueness results are derived, e.g., it is shown that a sufficient condition for uniqueness is that the conic hull of the latent factors is a superset of a particular second-order cone. Checking this condition is shown to be NP-complete; yet this and other results offer insights on the role of latent sparsity in this context. On the computational side, a new algorithm for symmetric NMF is proposed, which is very different from existing ones. It alternates between Procrustes rotation and projection onto the non-negative orthant to find a non-negative matrix close to the span of the dominant subspace. Simulation results show promising performance with respect to the state-of-art. Finally, the new algorithm is applied to a clustering problem for co-authorship data, yielding meaningful and interpretable results.

Original languageEnglish (US)
Article number6630130
Pages (from-to)211-224
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume62
Issue number1
DOIs
StatePublished - Jan 1 2014

Keywords

  • Nonnegative matrix factorization (NMF)
  • Procrustes rotation
  • sparsity
  • symmetric NMF
  • uniqueness

Fingerprint

Dive into the research topics of 'Non-Negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition'. Together they form a unique fingerprint.

Cite this