Scalable Methods for Nonnegative Matrix Factorizations of Near-separable Tall-and-skinny Matrices
Numerous algorithms are used for nonnegative matrix factorization under the assumption 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 improved methods is an orthogonal matrix transformation that preserves the separability 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.
This paper describes a non-negative matrix factorization for tall and skinny matrices.  This algorithm works in the bigdata scenario because it need only pass over the tall skinny matrix one time.  This linear read of the tall skinny matrix does not fully utilize the distributed mapreduce framework.  I wonder, is it possible to parallelize the reading of the matrix and combine the results from subsets of the data into one final result?  Perhaps this is already being done, but is buried in the details of TQSR and not mentioned.  In figure 1, r=10 is chosen based on the GP curve, and then used to compare all 3 methods.  A fairer approach would be to choose the "elbows" for each method independently.  I'm also unclear on what the right hand subfigure of Figure 1 refers to.  The text says the lines correspond to the rows, but the legend says they correspond to columns.  From a readability perspective, this paper could use some effort towards cohesion.  Each section reads well, but it is harder to put the sections together to make a coherent story.  For example, name your new extension and mention it early.  Perhaps describe the content of the paper (i.e. a roadmap) in the introduction and remind the reader of where you are in each section.If I understand correctly, you are applying your new technique to three existing algorithms.  But there is no comparison (in either reconstruction error or time to compute) of your extension vs without your extension.  For this reason it is unclear to me what the contribution of this paper really amounts to.  You state that these results constitute the largest NMF to date, which is impressive, and so perhaps none of the 3 algorithms could be run on these data sets.  If true, I suggest and exposition of run time on  smaller simulated data sets to really illustrate the advantage your algorithm affords.Minor comments:line 253 simultaneous -> simultaneously