nnlm function slower than R's nnls or addreg's nnpois + support for sparse matrices?

[tomwenseleers]

I was doing some tests with the nnlm function hoping it would be faster than the inbuilt nnls R function, but if I try with a 200 x 1000 covariate matrix x and a univariate outcome variable y it turns out to be 10x slower than the inbuilt nnls R function... (This is setting all 3 alphas to zero and rest of the arguments to the defaults and either with or without multithreading; using mkl things becomes even worse) Is there any plans to implement a faster nnls algo, maybe like the ones of http://www.jasoncantarella.com/wordpress/software/tsnnls/ (using method http://www.jasoncantarella.com/downloads/adlers.pdf) or http://suvrit.de/work/soft/nnls.html or https://github.com/MyreResearchGroup/tnt-nn (recoded in Rcpp) or https://github.com/cran/multiway/blob/master/R/fnnls.R for the case where all alphas are set to zero? (This is especially relevant for some designs where nnls has been shown to be equally efficient as LASSO in producing sparse solutions, with about equal prediction error - e.g. when the covariate matrix would be a sparse banded matrix as is common in deconvolution problems, see https://projecteuclid.org/euclid.ejs/1386943911).

The first two algos above also support sparse covariate matrices, which would also be a nice feature to have...

When using Kullback-Leibler divergence I also found the function nnpois in the addreg R package to be faster than nnlm.

[linxihui]

For a small matrix, nnls (actually, implemented in Fortran77) seems faster, but if said for a matrix of 5000 x 5000, nnlm seems a bit faster though not a lot. The NNLM package is designed for NMF, instead of non-negative regression. The nnlm is the engine behind nnmf and supports missing values. In nnlm, the b in problem A x = b can be a matrix, and b is allowed to have missing values. Thus the nnmf hands missing values. Plus, nnls R interface does not allow customized initialization, thus not useful for nnmf.

[zdebruine]

For the record on this issue, on well-conditioned large matrices, the least squares solving steps are not the computational bottleneck, it's the loss calculation (ironically).

FWIW here's a benchmark from factorization of 10,000 single cells across 15,000 features on 4 cores. I am measuring the runtimes of a pair of update steps (update(W) and update(H)) and the mse calculation. No regularizations or maskings were applied.

 #                  test replications elapsed relative user.self sys.self
 # 5              update           10    0.31    1.000      0.75     0.09
 # 2                 mse           10    0.50    1.613      0.41     0.10

I can also confirm what Eric stated about speed. nnls::nnls in Fortran77 may be faster on a one-off solution, but does not receive an initialization. It may be easy enough to add initialization to the Fortran77 code in addition to adding regularizations and constraints, but I have no Fortran experience to speak to that specifically.

[pcarbo]

@zdebruine @tomwenseleers @linxihui We have developed an R package fastTopics that includes methods for Poisson NMF (i.e., NMF with divergence objective). The algorithms are partly based on C++ code from the NNLM package, and this code has been adapted for sparse matrices. We have vignettes illustrating application of the fastTopics package to single-cell data.