Convergence Analysis of Graph Regularized Non-Negative Matrix Factorization

Graph regularized non-negative matrix factorization (NMF) algorithms can be applied to information retrieval, image processing, and pattern recognition. However, challenge that still remains is to prove the convergence of this class of learning algorithms since the geometrical structure of the data space is considered. This paper presents the convergence properties of the graph regularized NMF learning algorithms. In the analysis, we focus on the study of Euclidian distance based algorithms. The structures of the fixed points are presented. The non-divergence of the learning algorithms is analyzed by constructing invariant sets for update rules. Based on Lyapunov indirect method, the stability of the algorithms is discussed in detail. The analysis shows that this class of NMF algorithms can converge to their fixed points under some given conditions. In the simulations, theoretical results presented in the paper are confirmed. For different initializations and data sets, variations of cost functions and decomposition data in the learning are presented to show the convergence features of the discussed NMF update rules, and the convergence speed of the algorithms is also investigated.