Non-negative matrix factorisation

October 14, 2019 β€” October 26, 2023

Figure 1

An intersting special matrix factorisation, where the goal is to decode an element-wise non-negative matrix into a product of two smaller matrices, which looks a lot like adaptive sparse coding if you squint at it.

David Austin simple intro to Non-negative matrix factorization for the American Mathematical Society is a good inroads to the classic problem.

1 Loss functions


2 Optimisation matters


3 Connection to optimal transport

Optimal transport turns out to have a connection to NNMF (Huynh, Zhao, and Phung 2020; Qian et al. 2016; Scetbon, Cuturi, and PeyrΓ© 2021; Schmitz et al. 2018; S. Y. Zhang 2021; Zhao et al. 2020).

4 Tools

NMF (R) πŸ—

Matlab: Chih-Jen Lin’s nmf.m - β€œThis tool solves NMF by alternative non-negative least squares using projected gradients. It converges faster than the popular multiplicative update approach.”

Distributed NMF:

In this repository, we offer both MPI and OPENMP implementation for MU, HALS and ANLS/BPP based NMF algorithms. This can run off the shelf as well easy to integrate in other source code. These are very highly tuned NMF algorithms to work on super computers. We have tested this software in NERSC as well OLCF cluster. The openmp implementation is tested on many different Linux variants with intel processors. The library works well for both sparse and dense matrix. (Fairbanks et al. 2015; Kannan, Ballard, and Park 2016; Kannan 2016)

5 References

Aarabi, and Peeters. 2018. β€œMusic Retiler: Using NMF2D Source Separation for Audio Mosaicing.” In Proceedings of the Audio Mostly 2018 on Sound in Immersion and Emotion. AM’18.
Abdallah, and Plumbley. 2004. β€œPolyphonic Music Transcription by Non-Negative Sparse Coding of Power Spectra.” In.
Afshar, Yin, Yan, et al. 2021. β€œSWIFT: Scalable Wasserstein Factorization for Sparse Nonnegative Tensors.” Proceedings of the AAAI Conference on Artificial Intelligence.
Arora, Ge, Halpern, et al. 2012. β€œA Practical Algorithm for Topic Modeling with Provable Guarantees.” arXiv:1212.4777 [Cs, Stat].
Baladi. 2000. Positive Transfer Operators and Decay of Correlations. Advanced Series in Nonlinear Dynamics, v. 16.
Berman, and Plemmons. 1987. Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics 1.0.
Berry, Browne, Langville, et al. 2007. β€œAlgorithms and Applications for Approximate Nonnegative Matrix Factorization.” Computational Statistics & Data Analysis.
Bertin, Badeau, and Vincent. 2010. β€œEnforcing Harmonicity and Smoothness in Bayesian Non-Negative Matrix Factorization Applied to Polyphonic Music Transcription.” IEEE Transactions on Audio, Speech, and Language Processing.
Bruckstein, Elad, and Zibulevsky. 2008. β€œSparse Non-Negative Solution of a Linear System of Equations Is Unique.” In 3rd International Symposium on Communications, Control and Signal Processing, 2008. ISCCSP 2008.
Buch, Quinton, and Sturm. 2017. β€œNichtnegativeMatrixFaktorisierungnutzendesKlangsynthesenSystem (NiMFKS): Extensions of NMF-Based Concatenative Sound Synthesis.” In Proceedings of the 20th International Conference on Digital Audio Effects.
Cao, Shen, Sun, et al. 2007. β€œDetect and Track Latent Factors with Online Nonnegative Matrix Factorization.” In Proceedings of the 20th International Joint Conference on Artifical Intelligence. IJCAI’07.
Carabias-Orti, Virtanen, Vera-Candeas, et al. 2011. β€œMusical Instrument Sound Multi-Excitation Model for Non-Negative Spectrogram Factorization.” IEEE Journal of Selected Topics in Signal Processing.
Cemgil. 2009. β€œBayesian Inference for Nonnegative Matrix Factorisation Models.” Computational Intelligence and Neuroscience.
Cichocki, Zdunek, and Amari. 2006. β€œNew Algorithms for Non-Negative Matrix Factorization in Applications to Blind Source Separation.” In 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings.
Damle, and Sun. 2014. β€œA Geometric Approach to Archetypal Analysis and Non-Negative Matrix Factorization.” arXiv:1405.4275 [Stat].
Devarajan. 2008. β€œNonnegative Matrix Factorization: An Analytical and Interpretive Tool in Computational Biology.” PLoS Comput Biol.
Ding, C., He, and Simon. 2005. β€œOn the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering.” In Proceedings of the 2005 SIAM International Conference on Data Mining. Proceedings.
Ding, C., Li, and Jordan. 2010. β€œConvex and Semi-Nonnegative Matrix Factorizations.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
Ding, Chris, Li, and Peng. 2008. β€œOn the Equivalence Between Non-Negative Matrix Factorization and Probabilistic Latent Semantic Indexing.” Computational Statistics & Data Analysis.
Ding, Jiu, and Zhou. 2009. β€œElementary Properties of Non-Negative Matrices.” In Nonnegative Matrices, Positive Operators, and Applications.
Driedger, and Pratzlich. 2015. β€œLet It Bee – Towards NMF-Inspired Audio Mosaicing.” In Proceedings of ISMIR.
Drineas, and Mahoney. 2005. β€œOn the NystrΓΆm Method for Approximating a Gram Matrix for Improved Kernel-Based Learning.” Journal of Machine Learning Research.
Dueck, Morris, and Frey. 2005. β€œMulti-Way Clustering of Microarray Data Using Probabilistic Sparse Matrix Factorization.” Bioinformatics.
Eggert, and Korner. 2004. β€œSparse Coding and NMF.” In 2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541).
Fairbanks, Kannan, Park, et al. 2015. β€œBehavioral Clusters in Dynamic Graphs.” Parallel Computing, Graph analysis for scientific discovery,.
FΓ©votte, Bertin, and Durrieu. 2008. β€œNonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis.” Neural Computation.
FΓ©votte, and Idier. 2011. β€œAlgorithms for Nonnegative Matrix Factorization with the Ξ²-Divergence.” Neural Computation.
Gemulla, Nijkamp, Haas, et al. 2011. β€œLarge-Scale Matrix Factorization with Distributed Stochastic Gradient Descent.” In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’11.
Guan, Naiyang, Tao, Luo, et al. 2012. β€œNeNMF: An Optimal Gradient Method for Nonnegative Matrix Factorization.” IEEE Transactions on Signal Processing.
Guan, N., Tao, Luo, et al. 2012. β€œOnline Nonnegative Matrix Factorization With Robust Stochastic Approximation.” IEEE Transactions on Neural Networks and Learning Systems.
Halko, Martinsson, and Tropp. 2010. β€œFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.”
Hoffman, Blei, and Cook. 2010. β€œBayesian Nonparametric Matrix Factorization for Recorded Music.” In International Conference on Machine Learning.
Hoyer, Patrik O. n.d. β€œNon-Negative Matrix Factorization with Sparseness Constraints.” Journal of Machine Learning Research.
Hoyer, P.O. 2002. β€œNon-Negative Sparse Coding.” In Proceedings of the 2002 12th IEEE Workshop on Neural Networks for Signal Processing, 2002.
Hsieh, and Dhillon. 2011. β€œFast Coordinate Descent Methods with Variable Selection for Non-Negative Matrix Factorization.” In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’11.
Hu, Pehlevan, and Chklovskii. 2014. β€œA Hebbian/Anti-Hebbian Network for Online Sparse Dictionary Learning Derived from Symmetric Matrix Factorization.” In 2014 48th Asilomar Conference on Signals, Systems and Computers.
Huynh, Zhao, and Phung. 2020. β€œOTLDA: A Geometry-Aware Optimal Transport Approach for Topic Modeling.” In Advances in Neural Information Processing Systems.
Kannan. 2016. β€œScalable and Distributed Constrained Low Rank Approximations.”
Kannan, Ballard, and Park. 2016. β€œA High-Performance Parallel Algorithm for Nonnegative Matrix Factorization.” In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP ’16.
Kim, and Park. 2008. β€œNonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method.” SIAM Journal on Matrix Analysis and Applications.
Koren, Bell, and Volinsky. 2009. β€œMatrix Factorization Techniques for Recommender Systems.” Computer.
Lee, and Seung. 1999. β€œLearning the Parts of Objects by Non-Negative Matrix Factorization.” Nature.
β€”β€”β€”. 2001. β€œAlgorithms for Non-Negative Matrix Factorization.” In Advances in Neural Information Processing Systems 13.
Liberty, Woolfe, Martinsson, et al. 2007. β€œRandomized Algorithms for the Low-Rank Approximation of Matrices.” Proceedings of the National Academy of Sciences.
Li, S.Z., Hou, Zhang, et al. 2001. β€œLearning Spatially Localized, Parts-Based Representation.” In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001. CVPR 2001.
Li, Yuanzhi, Liang, and Risteski. 2016. β€œRecovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates.” In Advances in Neural Information Processing Systems 29.
Lin. 2007. β€œProjected Gradient Methods for Nonnegative Matrix Factorization.” Neural Computation.
Liu, and Tao. 2015. β€œOn the Performance of Manhattan Nonnegative Matrix Factorization.” IEEE Transactions on Neural Networks and Learning Systems.
Martinsson. 2016. β€œRandomized Methods for Matrix Computations and Analysis of High Dimensional Data.” arXiv:1607.01649 [Math].
Martinsson, Rockhlin, and Tygert. 2006. β€œA Randomized Algorithm for the Approximation of Matrices.”
Masood, and Doshi-Velez. 2016. β€œRapid Posterior Exploration in Bayesian Non-Negative Matrix Factorization.” arXiv:1610.08928 [Stat].
Paatero, and Tapper. 1994. β€œPositive Matrix Factorization: A Non-Negative Factor Model with Optimal Utilization of Error Estimates of Data Values.” Environmetrics.
Qian, Hong, Cai, et al. 2016. β€œNon-Negative Matrix Factorization with Sinkhorn Distance.” In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI’16.
Rokhlin, Szlam, and Tygert. 2009. β€œA Randomized Algorithm for Principal Component Analysis.” SIAM J. Matrix Anal. Appl.
Rokhlin, and Tygert. 2008. β€œA Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression.” Proceedings of the National Academy of Sciences.
Salakhutdinov, and Mnih. 2008. β€œBayesian Probabilistic Matrix Factorization Using Markov Chain Monte Carlo.” In Proceedings of the 25th International Conference on Machine Learning. ICML ’08.
Saul. 2023. β€œA Geometrical Connection Between Sparse and Low-Rank Matrices and Its Application to Manifold Learning.” Transactions on Machine Learning Research.
Scetbon, Cuturi, and PeyrΓ©. 2021. β€œLow-Rank Sinkhorn Factorization.” In Proceedings of the 38th International Conference on Machine Learning.
Schmidt, Larsen, and Hsiao. 2007. β€œWind Noise Reduction Using Non-Negative Sparse Coding.” In 2007 IEEE Workshop on Machine Learning for Signal Processing.
Schmitz, Heitz, Bonneel, et al. 2018. β€œWasserstein Dictionary Learning: Optimal Transport-Based Unsupervised Nonlinear Dictionary Learning.” SIAM Journal on Imaging Sciences.
Sra, and Dhillon. 2006. β€œGeneralized Nonnegative Matrix Approximations with Bregman Divergences.” In Advances in Neural Information Processing Systems 18.
Tepper, and Sapiro. 2016. β€œCompressed Nonnegative Matrix Factorization Is Fast and Accurate.” IEEE Transactions on Signal Processing.
TΓΌrkmen. 2015. β€œA Review of Nonnegative Matrix Factorization Methods for Clustering.” arXiv:1507.03194 [Cs, Stat].
Turner, and Sahani. 2014. β€œTime-Frequency Analysis as Probabilistic Inference.” IEEE Transactions on Signal Processing.
Vaz, Toutios, and Narayanan. 2016. β€œConvex Hull Convolutive Non-Negative Matrix Factorization for Uncovering Temporal Patterns in Multivariate Time-Series Data.” In.
Vincent, Bertin, and Badeau. 2008. β€œHarmonic and Inharmonic Nonnegative Matrix Factorization for Polyphonic Pitch Transcription.” In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing.
Virtanen. 2007. β€œMonaural Sound Source Separation by Nonnegative Matrix Factorization With Temporal Continuity and Sparseness Criteria.” IEEE Transactions on Audio, Speech, and Language Processing.
Virtanen, Cemgil, and Godsill. 2008. β€œBayesian Extensions to Non-Negative Matrix Factorisation for Audio Signal Modelling.” In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing.
Wang, Yuan, and Jia. 2004. β€œFisher Non-Negative Matrix Factorization for Learning Local Features.” In In Proc. Asian Conf. On Comp. Vision.
Wang, Fei, and Li. 2010. β€œEfficient Nonnegative Matrix Factorization with Random Projections.” In SDM.
Wang, Y. X., and Zhang. 2013. β€œNonnegative Matrix Factorization: A Comprehensive Review.” IEEE Transactions on Knowledge and Data Engineering.
Wenwu Wang. 2011. β€œInstantaneous Versus Convolutive Non-Negative Matrix Factorization: Models, Algorithms and Applications to Audio Pattern Separation.” In Machine Audition: Principles, Algorithms and Systems.
Witten, and CandΓ¨s. 2015. β€œRandomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds.” Algorithmica.
Woolfe, Liberty, Rokhlin, et al. 2008. β€œA Fast Randomized Algorithm for the Approximation of Matrices.” Applied and Computational Harmonic Analysis.
Yu, Hsieh, Si, et al. 2012. β€œScalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems.” In IEEE International Conference of Data Mining.
β€”β€”β€”, et al. 2014. β€œParallel Matrix Factorization for Recommender Systems.” Knowledge and Information Systems.
Zass, and Shashua. 2005. β€œA Unifying Approach to Hard and Probabilistic Clustering.” In Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1 - Volume 01. ICCV ’05.
Zhang, Stephen Y. 2021. β€œA Unified Framework for Non-Negative Matrix and Tensor Factorisations with a Smoothed Wasserstein Loss.”
Zhang, Zhongyuan, Ding, Li, et al. 2007. β€œBinary Matrix Factorization with Applications.” In Seventh IEEE International Conference on Data Mining, 2007. ICDM 2007.
Zhao, Phung, Huynh, et al. 2020. β€œNeural Topic Model via Optimal Transport.” In.