Nonnegative matrix factorization and I-divergence alternating minimization☆

By Lorenzo Finesso, Peter Spreij. 2004

89 citations recorded by the source corpus.

Abstract In this paper we consider the Nonnegative Matrix Factorization (NMF) problem: given an (elementwise) nonnegative matrix V ∈ R + m × n find, for assigned k, nonnegative matrices W ∈ R + m × k and H ∈ R + k × n such that V = WH. Exact, nontrivial, nonnegative factorizations do not always exist, hence it is interesting to pose the approximate NMF problem. The criterion which is commonly employed is I-divergence between nonnegative matrices. The problem becomes that of finding, for assigned k, the factorization WH closest to V in I-divergence. An iterative algorithm, EM like, for the construction of the best pair (W, H) has been proposed in the literature. In this paper we interpret the algorithm as an alternating minimization procedure a la Csiszar–Tusnady and investigate some of its stability properties. NMF is widespreading as a data analysis method in applications for which the positivity constraint is relevant. There are other data analysis methods which impose some form of nonnegativity: we discuss here the connections between NMF and Archetypal Analysis.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Representation & Self-Supervised Learning, Mathematical Optimization, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Electrical and Electronic Engineering

In Representation & Self-Supervised Learning

In Mathematical Optimization

In Signal Processing

Citations in the corpus

Adafactor: Adaptive Learning Rates with Sublinear Memory Cost (2018, methodology): “…this cost function, we aim to minimize the total elementwise divergence subject to componentwise nonnegativity constraints: minimize (1) Solving this problem for general rank-k factors is nontrivial, requiring for instance the use of an alternating minimization procedure (Finesso & Spreij, 2006).”
On Tensors, Sparsity, and Nonnegative Factorizations (2011, unknown): “d Nonnegative Factorizations 3 In terms of convergence, Lin [32] and Gillis and Glienur [18] have shown convergence of two dierent modied versions of the Lee-Seung method for LS. Finesso and Spreij [15] (tensor extension in [51]) have shown convergence of the Lee-Seung method for KL divergence; howe”
Graph Regularized Nonnegative Matrix Factorization for Data Representation (2011, methodology): “For the divergence formulation of NMF, previous studies [16] successfully analyzed the convergence property of the multiplicative algorithm [27] from EM algorithm’s maximum likelihood point of view.”
On the Convergence of Multiplicative Update Algorithms for Nonnegative Matrix Factorization (2007, background): “Section I mentioned that [ 5 ] addressed the convergence of minimizing the KL divergence formula (2).”