Randomized Algorithms for Symmetric Nonnegative Matrix Factorization

We propose the first randomized algorithms for Symmetric Nonnegative Matrix Factorization (SymNMF). Nonnegative Matrix Factorization (NMF) is an important method in data analysis with applications to data visualization, text mining, feature learning, information fusion and more [28, 25, 46, 22, 11]. SymNMF is a variant of NMF where the input matrix is symmetric and the output low-rank approximation is also constrained to be symmetric [25, 49]. Applications of SymNMF include (hyper)graph clustering, image segmentation, and information fusion [44, 10, 19, 5, 6]. Several randomized algorithms for nonsymmetric NMF have been previously proposed and shown to be effective for dense and small sparse problems [43, 41, 13], but as far as we are aware there is no prior work on randomized algorithms for SymNMF. Our contributions in this work include a randomized algorithm for SymNMF we call "Low-rank Approximated Input SymNMF" (LAI-SymNMF), a randomized algorithm based on leverage score sampling for least squares problems we call LvS-SymNMF, novel theoretical analysis of leverage score sampling for the Nonnegative Least Squares problem and theoretical analysis of a hybrid sampling scheme for leverage score sampling. The rest of the paper is organized as follows. Section 2, which discusses background material including non-randomized SymNMF algorithms, reviews existing randomized NMF methods and other related work such as randomized methods for other low-rank matrix decompositions and tensor decompositions.