A hybrid iterative algorithm for Nonnegative Matrix Factorization

The aim of Non-negative Matrix Factorization (NMF) is to decompose a non-negative matrix into a product of two (or multiple) non-negative matrices with reduced ranks. Several iterative methods have been developed for this purpose, e.g. the Alternating Least Squares (ALS) or Lee-Seung (LS) multiplicative methods. Despite its fast convergence, the ALS algorithm suffers from its instability, and may diverge in practice. The LS method, although reasonably stable, is known to converge slowly. In this paper, we develop a hybrid algorithm using mixed iterations based on these two methods. We show theoretically that the hybrid algorithm outperforms both methods by achieving a better tradeoff between the convergence speed and stability without increasing computational complexity. We also provide numerical examples in which we compare our hybrid algorithm with the LS and ALS algorithms.