TY - JOUR
T1 - Convergence of a Fast Hierarchical Alternating Least Squares Algorithm for Nonnegative Matrix Factorization
AU - Hou, Liangshao
AU - Chu, Delin
AU - Liao, Li Zhi
N1 - Funding information:
The work of Li-Zhi Liao was supported in part by General Research Fund (GRF) of Hong Kong under Grants HKBU12302019 and HKBU12300920. The work of Delin Chu was supported by NUS Research under Grants A-0004252-00-00 and A-8000430-00-00. Recommended for acceptance by P. Tsaparas. (Corresponding author: Delin Chu.)
Publisher Copyright:
© 2023 IEEE.
PY - 2024/1
Y1 - 2024/1
N2 - The hierarchical alternating least squares (HALS) algorithms are powerful tools for nonnegative matrix factorization (NMF), among which the Fast-HALS, proposed in [A. Cichocki and A.-H. Phan, 2009], is one of the most efficient. This paper investigates the convergence of Fast-HALS. First, a more general weak convergence (converged subsequences exist and converge to the stationary point set) is established without any assumption, while most existing results assume all the columns of iterates are strictly away from the origin. Then, a simplified strong convergence (the entire sequence converges to a stationary point) proof is provided. The existing strong convergence is attributed to the block prox-linear (BPL) method, which is a more general framework including Fast-HALS as a special case. So, the convergence proof under BPL is quite complex. Our simplified proof explores the structure of Fast-HALS and can be regarded as a complement to the results under BPL. In addition, some numerical verifications are presented.
AB - The hierarchical alternating least squares (HALS) algorithms are powerful tools for nonnegative matrix factorization (NMF), among which the Fast-HALS, proposed in [A. Cichocki and A.-H. Phan, 2009], is one of the most efficient. This paper investigates the convergence of Fast-HALS. First, a more general weak convergence (converged subsequences exist and converge to the stationary point set) is established without any assumption, while most existing results assume all the columns of iterates are strictly away from the origin. Then, a simplified strong convergence (the entire sequence converges to a stationary point) proof is provided. The existing strong convergence is attributed to the block prox-linear (BPL) method, which is a more general framework including Fast-HALS as a special case. So, the convergence proof under BPL is quite complex. Our simplified proof explores the structure of Fast-HALS and can be regarded as a complement to the results under BPL. In addition, some numerical verifications are presented.
KW - Kurdyka-Łojasiewicz property
KW - nonnegative matrix factorization
KW - the fast hierarchical alternating least squares algorithm
KW - Kurdyka-Aojasiewicz property
UR - http://www.scopus.com/inward/record.url?scp=85161086702&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2023.3279369
DO - 10.1109/TKDE.2023.3279369
M3 - Journal article
SN - 1041-4347
VL - 36
SP - 77
EP - 89
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 1
ER -