A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization

• Published in: Computational optimization and applications 2018-09, Vol.71 (1), p.221-250
• Main Authors: Takahashi, Norikazu, Katayama, Jiro, Seki, Masato, Takeuchi, Jun’ichi
• Format: Article
• Language: English
• Subjects: Convergence; Convex and Discrete Geometry; Error analysis; Factorization; Management Science; Mathematics; Mathematics and Statistics; Operations Research; Operations Research/Decision Theory; Optimization; Statistics
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-018-9997-y

Multiplicative update rules are a well-known computational method for nonnegative matrix factorization. Depending on the error measure between two matrices, various types of multiplicative update rules have been proposed so far. However, their convergence properties are not fully understood. This paper provides a sufficient condition for a general multiplicative update rule to have the global convergence property in the sense that any sequence of solutions has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the optimization problem. Using this condition, it is proved that many of the existing multiplicative update rules have the global convergence property if they are modified slightly so that all variables take positive values. This paper also proposes new multiplicative update rules based on Kullback–Leibler, Gamma, and Rényi divergences. It is shown that these three rules have the global convergence property if the same modification as above is made.