Fast NMF algorithm for dense and sparse data

[mblondel]

Here's an algorithm which I think would be a good candidate for inclusion in scikit-learn:

http://www.cs.utexas.edu/~cjhsieh/nmf/

[ogrisel]

I would rather like an algorithm that scales with n_samples rather than n_features. Maybe an Averaged SGD optimization of the NMF cost function + positive projections?

[mblondel]

Their algorithm didn't gave me the impression that it doesn't scale wrt n_samples (the datasets they use for their experiments are pretty large). And variable selection seems to help accelerate convergence a lot.

BTW, the tricks necessary for efficient implementation of averaging in the sparse case may not be applicable if there's a projection step (to be verified).

[ogrisel]

Ok interesting. The code seems simple enough to implement too.

[mblondel]

I added a preliminary implementation of this method here:
https://gist.github.com/mblondel/09648344984565f9477a

A difference is that my implementation uses cyclic coordinate selection instead of greedy.

CC @vene @larsmans

[mblondel]

I obtained a 20x speed up by numba-ing the most computationally expensive part. Now computing the NMF on the full News20 dataset takes 10 seconds.

https://gist.github.com/mblondel/09648344984565f9477a

[amueller]

should we close this in favor of #4811?

[mblondel]

Let's close it when #4852 is merged :)

[amueller]

#4852 is merged now :)