search

mljs / nmf

Non-negative Matrix Factorization (NMF)
MIT License
3 stars 2 forks source link

Non-Negative Least Squares #2

Open jeremyweymann opened 5 years ago

jeremyweymann commented 5 years ago

A particular case of the NMF is to find a vector x such that Ax=b where x is non-negative (and A is known), which is actually a least square problem with constraint x >= 0. The best-known algorithm to solve this problem is the one provided by Lawson and Hanson, available in the book Solving least squares problems ((Lawson, C. L., & Hanson, R. J. (1995). Solving least squares problems (Vol. 15). Siam.)), with a Fortran code available. An extension to this problem is the following: finding a matrix K of non-negative coefficient such that AK=B, where A and B are known matrixes, which is called by Van Benthem and Keenan, "Least Square problem with multiple right hand side". They developed an algorithm called Fast Combinatorial Non-Negative Least Square in their paper (Van Benthem, M. H., & Keenan, M. R. (2004). Fast algorithm for the solution of large‐scale non‐negativity‐constrained least squares problems. Journal of Chemometrics: A Journal of the Chemometrics Society, 18(10), 441-450.) which is based on the Lawson-Hanson algorithm and significantly reduces the computation burden when the observation matrix B is big (compared to classical NNLS algorithm). A code in Matlab is also provided at the end of the paper.

Here is an example with A = matrix.txt and b = target.txt and the three results, the first one obtained using SVD, the second one using the Lawson-Hanson algorithm and the last one using the algorithm from Van Benthem and Keenan (which give the same result since when b is a vector the latter simply applies the Lawson-Hanson algorithm) (all three computed in R): x_svd.txt x_nnls.txt x_fcnnls.txt

matrix.txt target.txt

I will try in the following week to provide a JavaScript code for at least one of them. This is a work I do with Luc Patiny as a summer internship.

When this issue is solved, we will then be able to use this FC-NNLS algorithm to implement Alternating Least Square Method for Non-Negative Matrix Factorization from Park and Kim (Kim, H., & Park, H. (2008). Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM journal on matrix analysis and applications, 30(2), 713-730.).

jobo322 commented 4 years ago

Hello @jeremyweymann, I wonder to know if I can help you to complete the work started in your fork

jeremyweymann commented 4 years ago

Hey @jobo322, thanks a lot for your message. The fcnnls algorithm is here: https://github.com/mljs/fcnnls, but it has some one computational issue. For the nmf, I started to organized the files in term of methods and algorithms. There are indeed many different ways to compute the nmf. My aim was to be able to use any of the available methods to compute the nmf. The idea comes from the work done in https://github.com/hiroyuki-kasai/NMFLibrary (but my goal was much more humble, with fewer options, only the most used algorithms).