Non-negative matrix factorisation

2019-10-14
Maybe related 🀷:

A cute hack in the world of sparse 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 sparse coding if you squint at it.

David Austin gives a simple introduction, to the classic Non-negative matrix factorization for the American Mathematical Society.

This method is famous for decomposing things into parts in a sparse way using \(l_2\) loss. It can be made even sparser by exploring other losses. πŸ—

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)

References

Aarabi, Hadrien Foroughmand, and Geoffroy Peeters. 2018. β€œMusic Retiler: Using NMF2D Source Separation for Audio Mosaicing.” In Proceedings of the Audio Mostly 2018 on Sound in Immersion and Emotion, 27:1–7. AM’18. New York, NY, USA: ACM.
Abdallah, Samer A., and Mark D. Plumbley. 2004. β€œPolyphonic Music Transcription by Non-Negative Sparse Coding of Power Spectra.” In.
Arora, Sanjeev, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. 2012. β€œA Practical Algorithm for Topic Modeling with Provable Guarantees.” arXiv:1212.4777 [Cs, Stat], December.
Baladi, Viviane. 2000. Positive Transfer Operators and Decay of Correlations. Advanced Series in Nonlinear Dynamics, v. 16. Singapore ; River Edge, NJ: World Scientific Pub. Co.
Berman, Abraham, and Robert J. Plemmons. 1987. Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics 1.0. Society for Industrial and Applied Mathematics.
Berry, Michael W., Murray Browne, Amy N. Langville, V. Paul Pauca, and Robert J. Plemmons. 2007. β€œAlgorithms and Applications for Approximate Nonnegative Matrix Factorization.” Computational Statistics & Data Analysis 52 (1): 155–73.
Bertin, N., R. Badeau, and E. 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 18 (3): 538–49.
Bruckstein, A. M., Michael Elad, and M. 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, 762–67.
Buch, Michael, Elio Quinton, and Bob L Sturm. 2017. β€œNichtnegativeMatrixFaktorisierungnutzendesKlangsynthesenSystem (NiMFKS): Extensions of NMF-Based Concatenative Sound Synthesis.” In Proceedings of the 20th International Conference on Digital Audio Effects, 7. Edinburgh.
Cao, Bin, Dou Shen, Jian-Tao Sun, Xuanhui Wang, Qiang Yang, and Zheng Chen. 2007. β€œDetect and Track Latent Factors with Online Nonnegative Matrix Factorization.” In Proceedings of the 20th International Joint Conference on Artifical Intelligence, 2689–94. IJCAI’07. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
Carabias-Orti, J. J., T. Virtanen, P. Vera-Candeas, N. Ruiz-Reyes, and F. J. Canadas-Quesada. 2011. β€œMusical Instrument Sound Multi-Excitation Model for Non-Negative Spectrogram Factorization.” IEEE Journal of Selected Topics in Signal Processing 5 (6): 1144–58.
Cemgil, Ali Taylan. 2009. β€œBayesian Inference for Nonnegative Matrix Factorisation Models.” Computational Intelligence and Neuroscience.
Cichocki, A., R. Zdunek, and S. 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, 5:V–.
Damle, Anil, and Yuekai Sun. 2014. β€œA Geometric Approach to Archetypal Analysis and Non-Negative Matrix Factorization.” arXiv:1405.4275 [Stat], May.
Devarajan, Karthik. 2008. β€œNonnegative Matrix Factorization: An Analytical and Interpretive Tool in Computational Biology.” PLoS Comput Biol 4 (7): e1000029.
Ding, C., X. He, and H. Simon. 2005. β€œOn the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering.” In Proceedings of the 2005 SIAM International Conference on Data Mining, 606–10. Proceedings. Society for Industrial and Applied Mathematics.
Ding, Chris, Tao Li, and Wei Peng. 2008. β€œOn the Equivalence Between Non-Negative Matrix Factorization and Probabilistic Latent Semantic Indexing.” Computational Statistics & Data Analysis 52 (8): 3913–27.
Ding, C., Tao Li, and M.I. Jordan. 2010. β€œConvex and Semi-Nonnegative Matrix Factorizations.” IEEE Transactions on Pattern Analysis and Machine Intelligence 32 (1): 45–55.
Ding, Jiu, and Aihui Zhou. 2009. β€œElementary Properties of Non-Negative Matrices.” In Nonnegative Matrices, Positive Operators, and Applications. Hackensack, N.J: World Scientific.
Driedger, Jonathan, and Thomas Pratzlich. 2015. β€œLet It Bee – Towards NMF-Inspired Audio Mosaicing.” In Proceedings of ISMIR, 7. Malaga.
Drineas, Petros, and Michael W. Mahoney. 2005. β€œOn the NystrΓΆm Method for Approximating a Gram Matrix for Improved Kernel-Based Learning.” Journal of Machine Learning Research 6 (December): 2153–75.
Dueck, Delbert, Quaid D. Morris, and Brendan J. Frey. 2005. β€œMulti-Way Clustering of Microarray Data Using Probabilistic Sparse Matrix Factorization.” Bioinformatics 21 (suppl 1): i144–51.
Eggert, J., and E. Korner. 2004. β€œSparse Coding and NMF.” In 2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541), 4:2529–2533 vol.4.
Fairbanks, James P., Ramakrishnan Kannan, Haesun Park, and David A. Bader. 2015. β€œBehavioral Clusters in Dynamic Graphs.” Parallel Computing, Graph analysis for scientific discovery, 47 (August): 38–50.
FΓ©votte, CΓ©dric, Nancy Bertin, and Jean-Louis Durrieu. 2008. β€œNonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis.” Neural Computation 21 (3): 793–830.
FΓ©votte, CΓ©dric, and JΓ©rΓ΄me Idier. 2011. β€œAlgorithms for Nonnegative Matrix Factorization with the Ξ²-Divergence.” Neural Computation 23 (9): 2421–56.
Gemulla, Rainer, Erik Nijkamp, Peter J. Haas, and Yannis Sismanis. 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, 69–77. KDD ’11. New York, NY, USA: ACM.
Guan, Naiyang, Dacheng Tao, Zhigang Luo, and Bo Yuan. 2012. β€œNeNMF: An Optimal Gradient Method for Nonnegative Matrix Factorization.” IEEE Transactions on Signal Processing 60 (6): 2882–98.
Guan, N., D. Tao, Z. Luo, and B. Yuan. 2012. β€œOnline Nonnegative Matrix Factorization With Robust Stochastic Approximation.” IEEE Transactions on Neural Networks and Learning Systems 23 (7): 1087–99.
Halko, Nathan, Per-Gunnar Martinsson, and Joel A. Tropp. 2010. β€œFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.” arXiv.
Hoffman, Matthew D, David M Blei, and Perry R Cook. 2010. β€œBayesian Nonparametric Matrix Factorization for Recorded Music.” In International Conference on Machine Learning, 8.
Hoyer, Patrik O. n.d. β€œNon-Negative Matrix Factorization with Sparseness Constraints.” Journal of Machine Learning Research 5 (9): 1457–69.
Hoyer, P.O. 2002. β€œNon-Negative Sparse Coding.” In Proceedings of the 2002 12th IEEE Workshop on Neural Networks for Signal Processing, 2002, 557–65.
Hsieh, Cho-Jui, and Inderjit S. 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, 1064–72. KDD ’11. New York, NY, USA: ACM.
Hu, Tao, Cengiz Pehlevan, and Dmitri B. 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.
Kannan, Ramakrishnan. 2016. β€œScalable and Distributed Constrained Low Rank Approximations,” April.
Kannan, Ramakrishnan, Grey Ballard, and Haesun 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, 9:1–11. PPoPP ’16. New York, NY, USA: ACM.
Kim, H., and H. Park. 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–30.
Koren, Yehuda, Robert Bell, and Chris Volinsky. 2009. β€œMatrix Factorization Techniques for Recommender Systems.” Computer 42 (8): 30–37.
Lee, Daniel D., and H. Sebastian Seung. 1999. β€œLearning the Parts of Objects by Non-Negative Matrix Factorization.” Nature 401 (6755): 788–91.
β€”β€”β€”. 2001. β€œAlgorithms for Non-Negative Matrix Factorization.” In Advances in Neural Information Processing Systems 13, edited by T. K. Leen, T. G. Dietterich, and V. Tresp, 556–62. MIT Press.
Li, S.Z., XinWen Hou, HongJiang Zhang, and Qiansheng Cheng. 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, 1:I-207-I-212 vol.1.
Li, Yuanzhi, Yingyu Liang, and Andrej Risteski. 2016. β€œRecovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates.” In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 4988–96. Curran Associates, Inc.
Liberty, Edo, Franco Woolfe, Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert. 2007. β€œRandomized Algorithms for the Low-Rank Approximation of Matrices.” Proceedings of the National Academy of Sciences 104 (51): 20167–72.
Lin, Chih-Jen. 2007. β€œProjected Gradient Methods for Nonnegative Matrix Factorization.” Neural Computation 19 (10): 2756–79.
Liu, T., and D. Tao. 2015. β€œOn the Performance of Manhattan Nonnegative Matrix Factorization.” IEEE Transactions on Neural Networks and Learning Systems PP (99): 1–1.
Martinsson, Per-Gunnar. 2016. β€œRandomized Methods for Matrix Computations and Analysis of High Dimensional Data.” arXiv:1607.01649 [Math], July.
Martinsson, Per-Gunnar, Vladimir Rockhlin, and Mark Tygert. 2006. β€œA Randomized Algorithm for the Approximation of Matrices.” DTIC Document.
Masood, M. Arjumand, and Finale Doshi-Velez. 2016. β€œRapid Posterior Exploration in Bayesian Non-Negative Matrix Factorization.” arXiv:1610.08928 [Stat], October.
Paatero, Pentti, and Unto Tapper. 1994. β€œPositive Matrix Factorization: A Non-Negative Factor Model with Optimal Utilization of Error Estimates of Data Values.” Environmetrics 5 (2): 111–26.
Rokhlin, Vladimir, Arthur Szlam, and Mark Tygert. 2009. β€œA Randomized Algorithm for Principal Component Analysis.” SIAM J. Matrix Anal. Appl. 31 (3): 1100–1124.
Rokhlin, Vladimir, and Mark Tygert. 2008. β€œA Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression.” Proceedings of the National Academy of Sciences 105 (36): 13212–17.
Salakhutdinov, Ruslan, and Andriy Mnih. 2008. β€œBayesian Probabilistic Matrix Factorization Using Markov Chain Monte Carlo.” In Proceedings of the 25th International Conference on Machine Learning, 880–87. ICML ’08. New York, NY, USA: ACM.
Saul, Lawrence K. 2023. β€œA Geometrical Connection Between Sparse and Low-Rank Matrices and Its Application to Manifold Learning.” Transactions on Machine Learning Research, January.
Schmidt, M.N., J. Larsen, and Fu-Tien Hsiao. 2007. β€œWind Noise Reduction Using Non-Negative Sparse Coding.” In 2007 IEEE Workshop on Machine Learning for Signal Processing, 431–36.
Sra, Suvrit, and Inderjit S. Dhillon. 2006. β€œGeneralized Nonnegative Matrix Approximations with Bregman Divergences.” In Advances in Neural Information Processing Systems 18, edited by Y. Weiss, B. SchΓΆlkopf, and J. C. Platt, 283–90. MIT Press.
Tepper, Mariano, and Guillermo Sapiro. 2016. β€œCompressed Nonnegative Matrix Factorization Is Fast and Accurate.” IEEE Transactions on Signal Processing 64 (9): 2269–83.
TΓΌrkmen, Ali Caner. 2015. β€œA Review of Nonnegative Matrix Factorization Methods for Clustering.” arXiv:1507.03194 [Cs, Stat], July.
Turner, Richard E., and Maneesh Sahani. 2014. β€œTime-Frequency Analysis as Probabilistic Inference.” IEEE Transactions on Signal Processing 62 (23): 6171–83.
Vaz, Colin, Asterios Toutios, and Shrikanth S. Narayanan. 2016. β€œConvex Hull Convolutive Non-Negative Matrix Factorization for Uncovering Temporal Patterns in Multivariate Time-Series Data.” In, 963–67.
Vincent, E., N. Bertin, and R. Badeau. 2008. β€œHarmonic and Inharmonic Nonnegative Matrix Factorization for Polyphonic Pitch Transcription.” In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, 109–12.
Virtanen, T. 2007. β€œMonaural Sound Source Separation by Nonnegative Matrix Factorization With Temporal Continuity and Sparseness Criteria.” IEEE Transactions on Audio, Speech, and Language Processing 15 (3): 1066–74.
Virtanen, T., A. Taylan Cemgil, and S. Godsill. 2008. β€œBayesian Extensions to Non-Negative Matrix Factorisation for Audio Signal Modelling.” In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, 1825–28.
Wang, Fei, and Ping Li. 2010. β€œEfficient Nonnegative Matrix Factorization with Random Projections.” In SDM, 281–92. SIAM.
Wang, Y. X., and Y. J. Zhang. 2013. β€œNonnegative Matrix Factorization: A Comprehensive Review.” IEEE Transactions on Knowledge and Data Engineering 25 (6): 1336–53.
Wang, Yuan, and Yunde Jia. 2004. β€œFisher Non-Negative Matrix Factorization for Learning Local Features.” In In Proc. Asian Conf. On Comp. Vision, 27–30.
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, 353–70. Hershey, PA, USA: IGI Global.
Witten, Rafi, and Emmanuel CandΓ¨s. 2015. β€œRandomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds.” Algorithmica 72 (1): 264–81.
Woolfe, Franco, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. 2008. β€œA Fast Randomized Algorithm for the Approximation of Matrices.” Applied and Computational Harmonic Analysis 25 (3): 335–66.
Yu, Hsiang-Fu, Cho-Jui Hsieh, Si Si, and Inderjit S. Dhillon. 2012. β€œScalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems.” In IEEE International Conference of Data Mining, 765–74.
β€”β€”β€”. 2014. β€œParallel Matrix Factorization for Recommender Systems.” Knowledge and Information Systems 41 (3): 793–819.
Zass, Ron, and Amnon 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, 294–301. ICCV ’05. Washington, DC, USA: IEEE Computer Society.
Zhang, Zhongyuan, Chris Ding, Tao Li, and Xiangsun Zhang. 2007. β€œBinary Matrix Factorization with Applications.” In Seventh IEEE International Conference on Data Mining, 2007. ICDM 2007, 391–400. IEEE.

Download bibliography

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.