Zangwill's Global Convergence Theorem and Its Application to Nonnegative Matrix Factorization Algorithms

DOI

Bibliographic Information

Other Title
  • Zangwillの大域収束定理とその非負値行列因子分解アルゴリズムへの応用

Abstract

Zangwill's global convergence theorem is a fundamental result that has long been known in the field of optimization theory and has been used to prove global convergence of various iterative algorithms. The author and his colleagues have used this theorem to analyze some representative algorithms for Nonnegative Matrix Factorization (NMF), which is the process of decomposing a given nonnegative matrix into two low-rank nonnegative factor matrices. NMF is formulated as an optimization problem of minimizing the difference between the product of the factor matrices and the given nonnegative matrix under the constraint that all entries of the factor matrices are nonnegative. The multiplicative update rule and the hierarchical alternating least squares method are widely used to solve this optimization problem efficiently. However, they are not well-defined and therefore do not guarantee global convergence. The author and his colleagues focused on some algorithms obtained by slightly modifying the original update formulae and proved their global convergence using Zangwill's theory. This paper introduces Zangwill's global convergence theorem and describes the results obtained by the author and his colleagues.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top