Convergence of a Fast Hierarchical Alternating Least Squares Algorithm for Nonnegative Matrix Factorization

Liangshao Hou, Delin Chu*, Li Zhi Liao

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)77-89
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume36
Issue number1
Early online date24 May 2023
DOIs
Publication statusPublished - Jan 2024

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Kurdyka-Łojasiewicz property
  • nonnegative matrix factorization
  • the fast hierarchical alternating least squares algorithm
  • Kurdyka-Aojasiewicz property

Fingerprint

Dive into the research topics of 'Convergence of a Fast Hierarchical Alternating Least Squares Algorithm for Nonnegative Matrix Factorization'. Together they form a unique fingerprint.

Cite this