CASNMF: A Converged Algorithm for symmetrical nonnegative matrix factorization

Nonnegative matrix factorization (NMF) is a very popular unsupervised or semi-supervised learning method useful in various applications including data clustering, image processing, and semantic analysis of documents. This study focuses on Symmetric NMF (SNMF), which is a special case of NMF and can be useful in network analysis. Although there exist several algorithms for SNMF in literature, their convergence and initialization have not been well addressed. In this paper, we first discuss the convergence and initialization of existing algorithms for SNMF. We then propose a Converged Algorithm for SNMF (called CASNMF) which minimizes the Euclidean distance between a symmetrical matrix and its approximation of SNMF. Based on the optimization principle and the local auxiliary function method, we prove that our presented CASNMF does not only converge to a stationary point, but also could be applied to the wider range of SNMF problems. In addition, CASNMF does not require that the initial values are nonzero. To verify our theoretical results, experiments on three data sets are conducted by comparing our proposed CASNMF with other existing methods.