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. π

## 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. n.d. βDetect and Track Latent Factors with Online Nonnegative Matrix Factorization.β In.

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. 2009. βFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.β

*arXiv:0909.4061 [Math]*, September.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.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.
## No comments yet. Why not leave one?