# A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization

arXiv: https://arxiv.org/abs/2303.17992 · HTML: https://mlsanity.com/paper/2303.17992/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 62 references that are in the map.
- First posted on arXiv 31 Mar 2023.

## Builds on (most cited first, 15 of 15)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Hyperspectral Unmixing: Ground Truth Labeling, Datasets, Benchmark Performances and Survey](https://mlsanity.com/paper/1708.05125/) (2017)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2010.01935/) (2020)
- [Nonlinear hyperspectral unmixing with robust nonnegative matrix factorization](https://mlsanity.com/paper/1401.5649/) (2014)
- [Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation](https://mlsanity.com/paper/1805.06604/) (2018)
- [Multiplicative Updates for NMF with β-Divergences under Disjoint Equality Constraints](https://mlsanity.com/paper/2010.16223/) (2020)
- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms](https://mlsanity.com/paper/1905.09050/) (2019)
- [A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization](https://mlsanity.com/paper/1609.00951/) (2016)
- [Alternating Minimization Methods for Strongly Convex Optimization](https://mlsanity.com/paper/1911.08987/) (2019)
- [A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations](https://mlsanity.com/paper/2106.00293/) (2021)
- [Semi-Supervised Convolutive NMF for Automatic Piano Transcription](https://mlsanity.com/paper/2202.04989/) (2022)

## Built on by (most cited first, 2 of 2)

- [Majorization-Minimization Networks for Inverse Problems: An Application to EEG Imaging](https://mlsanity.com/paper/2602.03855/) (2026)
- [An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2607.13919/) (2026)

## Abstract (arXiv)

Nonnegative Matrix Factorization (NMF) is a fundamental tool in unsupervised learning, widely used for tasks such as dimensionality reduction, feature extraction, representation learning, and topic modeling. Many algorithms have been developed for NMF, including the well-known Multiplicative Updates (MU) algorithm, which belongs to a broader class of majorization-minimization techniques. In this work, we introduce a general second-order optimization framework for NMF under both quadratic and β-divergence loss functions. This approach, called Second-Order Majorant (SOM), constructs a local quadratic majorization of the loss function by majorizing its Hessian matrix. It includes MU as a special case, while enabling faster variants. In particular, we propose mSOM, a new algorithm within this class that leverages a tighter local approximation to accelerate convergence. We provide a convergence analysis, showing linear convergence for individual factor updates and global convergence to a stationary point for the alternating version, AmSOM algorithm. Numerical experiments on both synthetic and real data sets demonstrate that mSOM consistently outperforms state-of-the-art algorithms across multiple loss functions.