Coseparable Nonnegative Matrix Factorization

Nonnegative matrix factorization (NMF) is a popular model in the field of pattern recognition. The aim is to find a low rank approximation for nonnegative matrix M by a product of two nonnegative matrices W and H. In general, NMF is NP-hard to solve while it can be solved efficiently under a separability assumption, which requires that the columns of the factor matrix are some columns of the input matrix M. In this paper, we generalize the separability assumption based on 3-factor NMF (M = P1SP2), and require that S is a submatrix of the input matrix M. We refer to this NMF as a Coseparable NMF (CoS-NMF). In the paper, we discuss and study mathematical properties of CoS-NMF, and present its relationships with other matrix factorizations such as generalized separable NMF, tri-symNMF, biorthogonal trifactorization and CUR decomposition. An optimization method for CoS-NMF is proposed, and an alternating fast gradient method is employed to determine the rows and the columns of M for the submatrix S. Numerical experiments on synthetic data sets, document data sets, and facial data sets are conducted to verify the effectiveness of the proposed CoS-NMF model. By comparison with state-of-the-art methods, the CoS-NMF model performs very well in a coclustering task by finding useful features, and keeps a good approximation to the input data matrix as well.