We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Global convergence of modified multiplicative updates for nonnegative matrix factorization.
- Authors
Takahashi, Norikazu; Hibi, Ryota
- Abstract
Nonnegative matrix factorization (NMF) is the problem of approximating a given nonnegative matrix by the product of two nonnegative matrices. The multiplicative updates proposed by Lee and Seung are widely used as efficient computational methods for NMF. However, the global convergence of these updates is not formally guaranteed because they are not defined for all pairs of nonnegative matrices. In this paper, we consider slightly modified versions of the original multiplicative updates and study their global convergence properties. The only difference between the modified updates and the original ones is that the former do not allow variables to take values less than a user-specified positive constant. Using Zangwill's global convergence theorem, we prove that any sequence of solutions generated by either of those modified updates has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the corresponding optimization problem. Furthermore, we propose algorithms based on the modified updates that always stop within a finite number of iterations.
- Subjects
NONNEGATIVE matrices; FACTORIZATION; MATHEMATICS; MATHEMATICAL optimization; COMPUTATIONAL complexity; ALGORITHMS
- Publication
Computational Optimization & Applications, 2014, Vol 57, Issue 2, p417
- ISSN
0926-6003
- Publication type
Article
- DOI
10.1007/s10589-013-9593-0