Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method

Hyunsoo Kim, Haesun Park

Research output: Contribution to journalArticlepeer-review

448 Scopus citations

Abstract

Nonnegative matrix factorization (NMF) determines a lower rank approximation of a matrix A ∈ ℝ mxn ≈ WH where an integer k << min(m, n) is given and nonnegativity is imposed on all components of the factors W ∈ ℝ mxk and H ∈ ℝ k x n. NMF has attracted much attention for over a decade and has been successfully applied to numerous data analysis problems. In applications where the components of the data are necessarily nonnegative, such as chemical concentrations in experimental results or pixels in digital images, NMF provides a more relevant interpretation of the results since it gives nonsubtractive combinations of nonnegative basis vectors. In this paper, we introduce an algorithm for NMF based on alternating nonnegativity constrained least squares (NMF/ANLS) and the active set-based fast algorithm for nonnegativity constrained least squares with multiple right-hand side vectors, and we discuss its convergence properties and a rigorous convergence criterion based on the Karush-Kuhn-Tucker (KKT) conditions. In addition, we also describe algorithms for sparse NMFs and regularized NMF. We show how we impose a sparsity constraint on one of the factors by L 1-norm minimization and discuss its convergence properties. Our algorithms are compared to other commonly used NMF algorithms in the literature on several test data sets in terms of their convergence behavior.

Original languageEnglish (US)
Pages (from-to)713-730
Number of pages18
JournalSIAM Journal on Matrix Analysis and Applications
Volume30
Issue number2
DOIs
StatePublished - 2008
Externally publishedYes

Keywords

  • Active set method
  • Karush-Kuhn-Tucker (KKT) conditions
  • Lower rank approximation
  • Nonnegative Matrix factorization
  • Nonnegativity constrained least squares
  • Two-block coordinate descent method

Fingerprint

Dive into the research topics of 'Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method'. Together they form a unique fingerprint.

Cite this