Stability Analysis of Multiplicative Update Algorithms and Application to Nonnegative Matrix Factorization

Abstract

Multiplicative update algorithms have proved to be a great success in solving optimization problems with nonnegativity constraints, such as the famous nonnegative matrix factorization (NMF) and its many variants. However, despite several years of research on the topic, the understanding of their convergence properties is still to be improved. In this paper, we show that Lyapunov's stability theory provides a very enlightening viewpoint on the problem. We prove the exponential or asymptotic stability of the solutions to general optimization problems with nonnegative constraints, including the particular case of supervised NMF, and finally study the more difficult case of unsupervised NMF. The theoretical results presented in this paper are confirmed by numerical simulations involving both supervised and unsupervised NMF, and the convergence speed of NMF multiplicative updates is investigated.