A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization
This work addresses a computational bottleneck in NMF, a widely used tool in unsupervised learning, by providing faster convergence, though it is incremental as it builds on existing majorization-minimization techniques.
The paper tackled the problem of slow convergence in Nonnegative Matrix Factorization (NMF) by introducing a second-order optimization framework called Second-Order Majorant (SOM), which includes a new algorithm mSOM that consistently outperforms state-of-the-art methods on synthetic and real datasets.
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.