Journal
JOURNAL OF GLOBAL OPTIMIZATION
Volume 84, Issue 3, Pages 755-781Publisher
SPRINGER
DOI: 10.1007/s10898-022-01167-7
Keywords
Nonnegative matrix factorization; Hierarchical alternating least squares algorithm; Global convergence
Funding
- JSPS KAKENHI [JP21H03510]
Ask authors/readers for more resources
In this paper, a novel update rule for the HALS algorithm is proposed, which is well-defined and guarantees global convergence. The proposed rule allows sparse factor matrices by allowing variables to take the value of zero. Two stopping conditions are also presented to ensure the finite termination of the algorithm.
Nonnegative Matrix Factorization (NMF) has attracted a great deal of attention as an effective technique for dimensionality reduction of large-scale nonnegative data. Given a nonnegative matrix, NMF aims to obtain two low-rank nonnegative factor matrices by solving a constrained optimization problem. The Hierarchical Alternating Least Squares (HALS) algorithm is a well-known and widely-used iterative method for solving such optimization problems. However, the original update rule used in the HALS algorithm is not well defined. In this paper, we propose a novel well-defined update rule of the HALS algorithm, and prove its global convergence in the sense of Zangwill. Unlike conventional globally-convergent update rules, the proposed one allows variables to take the value of zero and hence can obtain sparse factor matrices. We also present two stopping conditions that guarantee the finite termination of the HALS algorithm. The practical usefulness of the proposed update rule is shown through experiments using real-world datasets.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available