Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.17992 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908411712503808 |
|---|---|
| author | Pham, Mai-Quyen Cohen, Jérémy Chonavel, Thierry |
| author_facet | Pham, Mai-Quyen Cohen, Jérémy Chonavel, Thierry |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_17992 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization Pham, Mai-Quyen Cohen, Jérémy Chonavel, Thierry Optimization and Control Machine Learning 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. |
| title | A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2303.17992 |