#### Compressed nonnegative matrix factorization is fast and accurate

Mariano Tepper, Guillermo Sapiro

Nonnegative matrix factorization (NMF) has an established reputation as a useful data analysis technique in numerous applications. However, its usage in practical situations is undergoing challenges in recent years. The fundamental factor to this is the increasingly growing size of the datasets available and needed in the information sciences. To address this, in this work we propose to use structured random compression, that is, random projections that exploit the data structure, for two NMF variants: classical and separable. In separable NMF (SNMF) the left factors are a subset of the columns of the input matrix. We present suitable formulations for each problem, dealing with different representative algorithms within each one. We show that the resulting compressed techniques are faster than their uncompressed variants, vastly reduce memory demands, and do not encompass any significant deterioration in performance. The proposed structured random projections for SNMF allow to deal with arbitrarily shaped large matrices, beyond the standard limit of tall-and-skinny matrices, granting access to very efficient computations in this general setting. We accompany the algorithmic presentation with theoretical foundations and numerous and diverse examples, showing the suitability of the proposed approaches.

Separable NMF (SNMF) code now integrated into Nimfa!

• Biclustering a bipartite graph: The Marvel social network

The network links Marvel characters and the Marvel comic books in which they appear, and exhibits most characteristics of “real-life” collaboration networks [1]. It can be represented as an $m \times n$ matrix, where $m = 6445$ and $n = 12850$ are the number of characters and comics, respectively. We bicluster this matrix using NMF with $r = 10$, aiming at obtaining 10 very representative groups of characters appearing jointly in different comic books. The ith bicluster ($i = 1...10$) is formed by the $i$th column of $\mathbf{X}$ and the ith row of $\mathbf{Y}$ (small entries were set to zero, as explained in the manuscript). The radar plots represent the coefficients of these vectors.