Non-negative matrix factorisation

October 14, 2019 — October 26, 2023

feature construction
functional analysis
linear algebra
networks
probability
signal processing
sparser than thou
statistics
Figure 1

An interesting 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’s simple intro to Non-negative matrix factorization for the American Mathematical Society is a good inroad to the classic problem.

1 Loss functions

TBD

2 Optimisation matters

TBD.

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.