Scalable Methods for Nonnegative Matrix Factorizations of Near-separable Tall-and-skinny Matrices

Numerous algorithms are used for nonnegative matrix factorization under the as-sumption that the matrix is nearly separable. In this paper, we show how to make these algorithms scalable for data matrices that have many more rows than columns, so-called “tall-and-skinny matrices. ” One key component to these im-proved methods is an orthogonal matrix transformation that preserves the separa-bility of the NMF problem. Our final methods need to read the data matrix only once and are suitable for streaming, multi-core, and MapReduce architectures. We demonstrate the efficacy of these algorithms on terabyte-sized matrices from scientific computing and bioinformatics. 1 Nonnegative matrix factorizations at scale A nonnegative matrix factorization (NMF) for an m × n matrix X with real-valued, nonnegative entries is X = WH (1) where W is m × r, H is r × n, r < min(m, n), and both factors have nonnegative entries. Whil