NMFLibrary: Non-negative Matrix Factorization Library

Authors: Hiroyuki Kasai

Last page update: July 22, 2022

Latest library version: 2.1 (see Release notes for more info)

Announcement

• NMF solvers written by MATLAB,
• appplication MATLAB flies using NMF solvers, and
• your comments and suggestions.

Introduction

Bibliograph

@misc{kasaiNMFLibrary2017,
    Author = {Kasai, Hiroyuki},
     Title = {{NMFLibrary}: MATLAB library for non-negative matrix factorization (NMF)},
     Year  = {2017},
     Howpublished = {\url{https://github.com/hiroyuki-kasai/NMFLibrary}}
}

List of solver algorithms available in NMFLibrary

• Frobenius-norm

- PGD (projected gradient descent) - PGD - Direct PGD - C.-J. Lin, "Projected gradient methods for nonnegative matrix factorization," Neural Computation, vol.19, no.10, pp.2756-2779, 2007.

- ALS (alternative least squares) - ALS - Hierarchical ALS (HALS) - A. Cichocki and P. Anh-Huy, "Fast local algorithms for large scale nonnegative matrix and tensor factorizations," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.92, no.3, pp.708-721, 2009. - Accelerated Hierarchical ALS - N. Gillis and F. Glineur, "Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization," Neural Computation, vol.24, no.4, pp.1085-1105, 2012.

- ANLS (alternative non-negative least squares) - ASGROUP (ANLS with Active Set Method and Column Grouping) - ASGIVENS (ANLS with Active Set Method and Givens Updating) - BPP (ANLS with Block Principal Pivoting Method) - J. Kim, Y. He, and H. Park, "Algorithms for nonnegative matrix and tensor factorizations: A unified view based on block coordinate descent framework," Journal of Global Optimization, vol.58, no.2, pp.285-319, 2014. - J. Kim and H. Park, "Fast nonnegative matrix factorization: An active-set-like method and comparisons," SIAM Journal on Scientific Computing (SISC), vol.33, no.6, pp.3261-3281, 2011.

• Divergence-based

- Div-ADMM - D.L. Sun and C. Fvotte, "Alternating direction method of multipliers for non-negative matrix factorization with the beta divergence," IEEE ICASSP, 2014.

- KL-FPA (First-order primal-dual algorithm)

- F. Yanez, and F. Bach, "Primal-dual algorithms for non-negative matrix factorization with the Kullback-Leibler divergence," IEEE ICASSP, 2017.

- KL-BMD - Block mirror descent method for KL-based non-negative matrix factorization

• Semi

- Semi-BCD - N. Gillis and A. Kumar, "Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization," SIAM Journal on Matrix Analysis and Applications 36 (4), pp. 1404-1424, 2015.

• Variant

- NeNMF (NMF with Nesterov's gradient acceleration) - N. Guan, D. Tao, Z. Luo, and B. Yuan, "NeNMF: An Optimal Gradient Method for Non-negative Matrix Factorization," IEEE Transactions on Signal Processing, Vol.60, No.6, pp. 2882-2898, 2012.

- SDNMF (NMF with Sinkhorn Distance) - W. Qian, B. Hong, D. Cai, X. He, and X. Li, "Non-negative matrix factorization with sinkhorn distance," IJCAI, pp.1960-1966, 2016.

• Robust

- N. Guan, D. Tao, Z. Luo, and B. Yuan, "Online nonnegative matrix factorization with robust stochastic approximation," IEEE Transactions on Neural Networks and Learning Systems, 2012.

• Sparse

- Sparse-MU-V - T. Virtanen, "Monaural sound source separation by non-negative factorization with temporal continuity and sparseness criteria," IEEE Transactions on Audio, Speech, and Language Processing, vol.15, no.3, 2007.

- sparseNMF (Sparse NMF)

- SC-NMF (NMF with sparseness constraints) - Patrik O. Hoyer, "Non-negative matrix factorization with sparseness constraints," Journal of Machine Learning Research (JMLR), vol.5, pp.1457-1469, 2004.

- Nonsmooth-NMF - A. Pascual-Montano, J. M. Carazo, K. Kochi, D. Lehmann, and R. D. Pascual-Marqui, "Nonsmooth Nonnegative Matrix Factorization (nsNMF)," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, no.3, pp.403-415, 2006.

- NS-NMF (Fast nonsmooth NMF) - Z. Yang, Y. Zhang, W. Yan, Y. Xiang, and S. Xie, "A fast non-smooth nonnegative matrix factorization for learning sparse representation," IEEE Access, vol.4, pp.5161-5168, 2016.

- Proj-Sparse - P. O. Hoyer, "Non-negative matrix factorization with sparseness constraints," Journal of Machine Learning Research (JMLR), vol.5, pp.1457-1469, 2004. - R. Ohib, N. Gillis, Niccolò Dalmasso, S. Shah, V. K. Potluru, S. Plis, "Explicit Group Sparse Projection with Applications to Deep Learning and NMF," arXiv preprint:1912.03896, 2019.

- PALM-Sparse-Smooth-NMF - PALM framework with smoothness and sparsity constraints for non-negative matrix factorization.

• Orthogonal

- Orth-MU (Orthogonal multiplicative upates (MU)) - S. Choi, "Algorithms for orthogonal nonnegative matrix factorization." IEEE IJCNN, 2008.

- ALT-ONMF - F. Pompilia, N. Gillis, P.-A. Absil, and F. Glineur, "Two algorithms for orthogonal nonnegative matrix factorization with application to clustering," Neurocomputing, vol.141, no.2, pp.15-25, 2014.

- HALS-SO (Hierarchical ALS with soft orthogonal constraint) - M. Shiga, K. Tatsumi, S. Muto, K. Tsuda, Y. Yamamoto, T. Mori, and T. Tanji, "Sparse modeling of EELS and EDX spectral imaging data by nonnegative matrix factorization," Ultramicroscopy, Vol.170, p.43-59, 2016.

• Symmetric

- D. Kuang, S. Yun, H. Park, "SymNMF Nonnegative low-rank approximation of a similarity matrix for graph clustering," Journal of Global Optimization, vol.62, no.3, pp.545-574, 2015.

- Z. Zhu, X. Li, K. Liu, Q. Li, "Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization," NIPS, 2018.

- SymmHALS (Symmetric HALS) - Z. Zhu, X. Li, K. Liu, Q. Li, "Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization," NIPS, 2018.

- SymmNewton (Symmetric Newton)

• Online/stochastic

- SPG (Stochastic projected gradient descent)

- Robust-Online-MU (Robust online NMF) - R. Zhao and Y. F. Tan, "Online nonnegative matrix factorization with outliers," IEEE ICASSP2016, 2016. - N. Guan, D. Tao, Z. Luo, and B. Yuan, "Online nonnegative matrix factorization with robust stochastic approximation," IEEE Transactions on Newral Network Learninig Systems, 2012.

- ASAG-MU-NMF (Asymmetric stochastic averaging gradient multiplicative updates) - R. Serizel, S. Essid and G.Richard, "Mini-batch stochastic approaches for accelerated multiplicative updates in nonnegative matrix factorisation with beta-divergence," IEEE MLSP, 2016.

- SVRMU-NMF (Stochastic multiplicative updates) and SVRMU (Stochastic variance reduced multiplicative updates) - H. Kasai, "Stochastic variance reduced multiplicative update for nonnegative matrix factorization," IEEE ICASSP, 2018.

- SAGMU-NMF (Stochastic averaging gradient multiplicative multiplicative updates) - H. Kasai, "Accelerated stochastic multiplicative update with gradient averaging for nonnegative matrix factorizations," EUSIPCO, 2018.

• Probabilistic

- T. Brouwer, P. Lio, "Bayesian Hybrid Matrix Factorisation for Data Integration," AISTATS, 2017. - PNMF-VB (Variational Bayesian inference for non-negative matrix factorisation, with ARD) - T. Brouwer, J. Frellsen. P. Lio, "Comparative Study of Inference Methods for Bayesian Nonnegative Matrix Factorisation," ECML PKDD, 2017.

- Prob-NMF

• Deep

- G. Trigeorgis, K. Bousmalis, S. Zafeiriou and B. Schuller, "A deep semi-NMF model for learning hidden representations," ICML, 2014.

- G. Trigeorgis, K. Bousmalis, S. Zafeiriou and B. Schuller, "A deep matrix factorization method for learning attribute representations," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.39, no.3, pp.417-429, 2017.

- Deep-nsNMF

- Deep-Multiview-Semi

- H. Zhao, Z. Ding, and Y. Fu, "Multi-view clustering via deep matrix factorization," AAAI, 2017.

• Convex

- C. Ding, T. Li, and M.I. Jordan, "Convex and semi-nonnegative matrix factorizations," IEEE Transations on Pattern Analysis and Machine Intelligence, vol. 32, no. 1, pp. 45-55, 2010. - T. Li and C. Ding, "The relationships among various nonnegative matrix factorization methods for clustering," ICDM, 2006.

- Y. Li and A. Ngom, "A new kernel non-Negative matrix factorization and its application in microarray data analysis," CIBCB, 2012.

• Separable

- SNPA - N. Gillis, "Successive nonnegative projection algorithm for robust nonnegative blind source separation," SIAM Journal on Imaging Sciences, vol.7, no.2, pp.1420-1450, 2014.

• Convolutive

- Heur-MU-Conv - Heuristic multiplicative update (MU) based convolutive non-negative matrix factorization

- ADMM-Y-Conv - ADMM based convolutive non-negative matrix factorization

- ADMM-Seq-Conv - ADMM based convolutive non-negative matrix factorization

• Projective

• Rank2

• Nonnegative matrix tri-factorization

• Nonnegative under-approximation

• Minimum-volume

• Weighted Low-Rank matrix approximation

Algorithm configurations

|Category|Name in example codes| function | options.alg | other options | |---|---|---|---|---| |Frobenius-norm|Fro-MU|fromunmf|mu|metric='euc'| ||Modified Fro-MU|fromunmf|mod_mu|| ||Accelerated Fro-MU|fromunmf|acc_mu|| ||PGD|pgd_nmf|pgd|| ||Direct PGD|pgdnmf|directpgd|| ||Adaptive-step PGD|pgdnmf|adpstep_pgd|| ||ALS|als_nmf|als|| ||Hierarchical ALS|alsnmf|halsmu|| ||Accelerated Hierarchical ALS|alsnmf|acchals_mu|| ||ASGROUP|anlsnmf|anlsasgroup|| ||ASGIVENS|anlsnmf|anlsasgivens|| ||BPP|anlsnmf|anlsbpp|| |Divergence|Div-MU-KL|divmunmf||metric='kl-div'| ||Div-MU-ALPHA|divmunmf||metric='alpha-div'| ||Div-MU-BETA|divmunmf||metric='beta-div'| ||Div-MU-IS|divmunmf||metric='beta-div' d_beta=0| ||Div-MU-KL|divmunmf||metric='beta-div' d_beta=1| ||Div-ADMM-IS|divadmmnmf||metric='beta-div' d_beta=0 | ||Div-ADMM-KL|divadmmnmf||metric='beta-div' d_beta=1 | ||KL-FPA|klfpanmf||| ||KL-BMD|klbmdnmf||| |Semi|Semi-MU|semimunmf||| ||Semi-BCD|semibcdnmf||| |Variant|NeNMF|nenmf||| ||GNMF|GNMF||| ||SDNMF|SDNMF||| |Robust|Robust-MU|robustmunmf||| |Sparse|Sparse-MU-EUC|sparsemunmf||metric='euc'| ||Sparse-MU-KL|sparsemunmf||metric='kl-div'| ||sparseNMF|sparse_nmf||| ||SC-NMF|sc_nmf||| ||Nonsmooth-NMF|nsnmf||metric='euc', updatealg='apg'| ||Proj-Sparse|projsparsenmf||| ||PALM-Sparse-Smooth|palmsparsesmooth_nmf||| |Orthogonal|DTPP|dtpp_nmf||| ||Orth-MU|orthmunmf||| ||NMF-HALS-SO|halssonmf||| ||ALT-ONMF|alternating_onmf||| |Symmetric|SymmANLS|symm_anls||| ||SymmHALS|symm_halsacc||| ||SymmNewton|symm_newton||| |Online|Incremental-NMF|incrementalmunmf||| ||Online-MU|onlinemunmf||| ||Accelerated Online-MU|acconlinemu_nmf||| ||SPG|spg_nmf||| ||Robust-Online-MU|robustonlinemu_nmf||| ||ASAG-MU-NMF|asagmunmf||| ||Stochastic-MU|smu_nmf||| ||SVRMU|svrmu_nmf||| ||R-SVRMU|svrmu_nmf||robust=true| ||SAGMU|sagmu_nmf||| |Probabilistic|PNMF-VB|vbpronmf||| ||PNMF-VB-ARD|vbpronmf||ard=true| ||Prob-NM|prob_nmf||| |Deep|Deep-Semi|deepseminmf||| ||Deep-Bidir-Semi|deepbidirectionalnmf||| ||Deep-nsNMF|deepnsnmf||| ||Deep-Multiview-Semi|deepmultiviewsemi_nmf||| |Convex|Convex-MU|convexmunmf||sub_mode='std'| ||Kernel-Convex-MU|convexmunmf||sub_mode='kernel'| |Separable|SPA|spa||| ||SNPA|snpa||| |Convolutive|MU-Conv|muconvnmf||| ||Heur-MU-Conv|heuristicmuconv_nmf||| ||ADMM-Y-Conv|admmyconv_nmf||| ||ADMM-Seq-Conv|admmseqconv_nmf||| |Rank2|Rank2-NMF|rank2nmf||| |Nonnegative matrix tri-factorization|Sep-Symm-NMTF|sepsymmnmtf||| |Nonnegative under-approximation|recursivenmu|recursivenmu||| |Minimum-volume|minvol-NMF|minvol_nmf|| |Weighted Low-Rank matrix approximation|WLRA|wlra|||

Folders and files

 ./                              - Top directory. ./README.md                     - This readme file. ./runmefirst.m                - The scipt that you need to run first. ./demo.m                        - Demonstration script to check and understand this package easily.  ./demo_face.m                   - Demonstration script to check and understand this package easily.  ./demo.py                       - Demonstration script to use this package easily from python.  |plotter/                       - Contains plotting tools to show convergence results and various plots. |auxiliary/                     - Some auxiliary tools for this project. |solver/                        - Contains various optimization algorithms.     |--- frobenius_norm/        - NMF solvers with Frobenius norm metric.     |--- divergence/            - NMF solvers with various divertence metrics (KL, beta, alpha, IS).     |--- online/                - Online/stochstic NMF solvers.     |--- sparse/                - Sparse NMF solvers.     |--- robust/                - Robust NMF solvers.     |--- orthogonal/            - Orthogonal NMF solvers.     |--- symmetric/             - Symmetric NMF solvers.     |--- semi/                  - Semi NMF solvers.     |--- deep/                  - Deep NMF solvers.     |--- probabilistic/         - Probabilistic NMF solvers.     |--- convex/                - Convex NMF solver.     |--- convolutive/           - Convolutive NMF solvers.     |--- minvol/                - Minimum-volume rank-deficient NMF.     |--- nmunderapprox/       - Recursive non-negative matrix underapproximation.     |--- nmtf/                  - Separable symmetric nonnegative matrix tri-factorization.     |--- projective_nmf/        - Projective NMF solver.     |--- rank2/                 - rank-two NMF solver.     |--- weightlowrankaprox/  - Weighted Low-Rank matrix Approximation algorithm.     |--- nenmf/                 - Nesterov's accelerated NMF solver.     |--- nnls/                  - Solvers for nonnegativity-constrained least squares.     |--- 3rdparty/             - Solvers provided by 3rdparty.     |--- solverhealthcheck.m  - Health check scripts for solvers. |applications/                  - Some appplications using NMF. 

First to do

%% First run the setup script runmefirst;

Simplest usage example: 4 steps!

Just execute demo for the simplest demonstration of this package. .

%% Execute the demonstration script
demo;

The "demo.m" file contains below.

%% generate synthetic data non-negative matrix V size of (mxn) m = 500; n = 100; V = rand(m,n);      %% Initialize rank to be factorized rank = 5;

%% perform factroization % Fro-MU options.alg = 'mu'; [wmu, infosmu] = fromunmf(V, rank, options); % Hierarchical ALS options.alg = 'hals'; [whals, infoshals] = als_nmf(V, rank, options);              %% plot displaygraph('epoch','cost', {'MU', 'HALS'}, {wmu, whals}, {infosmu, infos_hals});

Let's take a closer look at the code above bit by bit. The procedure has only 4 steps!

Step 1: Generate data

First, we generate synthetic data of V of size (mxn).

m = 500; n = 100; V = rand(m,n);

Step 2: Define rank

We set the rank value.

rank = 5;

Step 3: Perform solver

Now, you can perform nmf solvers, e.g., Frobenius-norm MU and Hierarchical ALS (HALS), calling solver functions, i.e., fromunmf() function and alsnmf() function after setting some optimization options.

% Fro-MU options.alg = 'mu'; [wmu, infosmu] = fromunmf(V, rank, options); % Hierarchical ALS options.alg = 'hals'; [whals, infoshals] = als_nmf(V, rank, options);

Step 4: Show result

Finally, display_graph() provides output results of decreasing behavior of the cost values in terms of the number of iterrations (epochs) and time [sec].

displaygraph('epoch','cost', {'Fro-MU', 'HALS'}, {wmu, whals}, {infosmu, infos_hals}); displaygraph('time','cost', {'Fro-MU', 'HALS'}, {wmu, whals}, {infosmu, infos_hals});

That's it!

More plots

"demoface.m" illustrates the learned basis (dictrionary) in case of CBCL face datasets.

V = importdata('./data/CBCL_face.mat');

plotdictionnary(wmu.W, [], [7 7]); 
plotdictionnary(whals.W, [], [7 7]);

matlabroot;

cd "c:\Program Files\MATLAB\R2022a\extern\engines\python"
python setup.py install

cd "/usr/local/MATLAB/R2022a/bin/matlab/extern/engines/python"
python setup.py install

cd "/Applications/MATLAB_R2022a.app/extern/engines/python"
python setup.py install

python demo.py