A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization

Renbo Zhao, Vincent Y. F. Tan

Type: Article

Publication Date: 2017-09-28

Citations: 27

DOI: https://doi.org/10.1109/tsp.2017.2757914

Abstract

The multiplicative update (MU) algorithm has been extensively used to estimate the basis and coefficient matrices in nonnegative matrix factorization (NMF) problems under a wide range of divergences and regularizers. However, theoretical convergence guarantees have only been derived for a few special divergences without regularization. In this work, we provide a conceptually simple, self-contained, and unified proof for the convergence of the MU algorithm applied on NMF with a wide range of divergences and regularizers. Our main result shows the sequence of iterates (i.e., pairs of basis and coefficient matrices) produced by the MU algorithm converges to the set of stationary points of the nonconvex NMF optimization problem. Our proof strategy has the potential to open up new avenues for analyzing similar problems in machine learning and signal processing.

Locations

IEEE Transactions on Signal Processing - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization	2016	Renbo Zhao Vincent Y. F. Tan
+	A Unified Convergence Analysis of the Multiplicative Update Algorithm for Nonnegative Matrix Factorization	2016	Renbo Zhao Vincent Y. F. Tan
+	A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized NMF with General Divergences	2016	Renbo Zhao Vincent Y. F. Tan
+	Unified Development of Multiplicative Algorithms for Linear and Quadratic Nonnegative Matrix Factorization	2011	Zhirong Yang Erkki Oja
+	A fast Multiplicative Updates algorithm for Non-negative Matrix Factorization	2023	Mai Quyen Pham Jérémy Cohen Thierry Chonavel
+	Block Majorization Minimization with Extrapolation and Application to $β$-NMF	2024	Le Thi Khanh Hien Valentin Leplat Nicolas Gillis
+	Global convergence of modified multiplicative updates for nonnegative matrix factorization	2013	Norikazu Takahashi Ryota Hibi
+	A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization	2018	Norikazu Takahashi Jiro Katayama Seki Masato Jun’ichi Takeuchi
+	Stochastic variance reduced multiplicative update for nonnegative matrix factorization	2017	Hiroyuki Kasai
+ PDF Chat	Stochastic Variance Reduced Multiplicative Update for Nonnegative Matrix Factorization	2018	Hiroyuki Kasai
+	Algorithms for nonnegative matrix factorization with the beta-divergence	2010	Cédric Févotte Jérôme Idier
+	DC Programming and DCA for Nonnegative Matrix Factorization	2014	Hoai An Le Thi Tao Pham Dinh Xuan Thanh Vo
+	A Unified Framework for Sparse Non-Negative Least Squares using Multiplicative Updates and the Non-Negative Matrix Factorization Problem	2016	Igor Fedorov Alican Nalci Ritwik Giri Bhaskar D. Rao Truong Q. Nguyen Harinath Garudadri
+	A Unified Framework for Sparse Non-Negative Least Squares using Multiplicative Updates and the Non-Negative Matrix Factorization Problem	2016	I. A. Fedorov Alican Nalci Ritwik Giri Bhaskar D. Rao Truong Q. Nguyen Harinath Garudadri
+	Multiplicative update for a class of constrained optimization problems related to NMF and its global convergence	2016	Norikazu Takahashi Seki Masato
+ PDF Chat	Majorization-Minimization for Sparse Nonnegative Matrix Factorization With the $\beta$-Divergence	2023	Arthur Marmin José Henrique de Morais Goulart Cédric Févotte
+ PDF Chat	A unified framework for sparse non-negative least squares using multiplicative updates and the non-negative matrix factorization problem	2018	Igor Fedorov Alican Nalci Ritwik Giri Bhaskar D. Rao Truong Q. Nguyen Harinath Garudadri
+	Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization	2017	Paris V. Giampouras Athanasios A. Rontogiannis Konstantinos Koutroumbas
+	Efficient Nonnegative Matrix Factorization by DC Programming and DCA	2016	Hoai An Le Thi Xuan Thanh Vo Tao Pham Dinh
+	A Modified Multiplicative Update Algorithm for Euclidean Distance-Based Nonnegative Matrix Factorization and Its Global Convergence	2011	Ryota Hibi Norikazu Takahashi

Works That Cite This (9)

Action	Title	Year	Authors
+	Multimodal Sparse Bayesian Dictionary Learning	2018	Igor Fedorov Bhaskar D. Rao
+ PDF Chat	Dual-Constrained Deep Semi-Supervised Coupled Factorization Network with Enriched Prior	2021	Yan Zhang Zhao Zhang Yang Wang Zheng Zhang Li Zhang Shuicheng Yan Meng Wang
+ PDF Chat	Distributionally Robust and Multi-Objective Nonnegative Matrix Factorization	2021	Nicolas Gillis Le Thi Khanh Hien Valentin Leplat Vincent Y. F. Tan
+	Dual-constrained Deep Semi-Supervised Coupled Factorization Network with Enriched Prior	2020	Yan Zhang Zhao Zhang Yang Wang Zheng Zhang Li Zhang Shuicheng Yan Meng Wang
+ PDF Chat	Joint majorization-Minimization for nonnegative matrix factorization with the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si8.svg"><mml:mi>β</mml:mi></mml:math>-divergence	2023	Arthur Marmin José Henrique de Morais Goulart Cédric Févotte
+ PDF Chat	A Ranking Model Motivated by Nonnegative Matrix Factorization with Applications to Tennis Tournaments	2020	Rui Xia Vincent Y. F. Tan Louis Filstroff Cédric Févotte
+ PDF Chat	Majorization-Minimization for Sparse Nonnegative Matrix Factorization With the $\beta$-Divergence	2023	Arthur Marmin José Henrique de Morais Goulart Cédric Févotte
+	Distributionally Robust and Multi-Objective Nonnegative Matrix Factorization	2019	Nicolas Gillis Le Thi Khanh Hien Valentin Leplat Vincent Y. F. Tan
+ PDF Chat	A convergent algorithm for bi-orthogonal nonnegative matrix tri-factorization	2021	Andri Mirzal

Works Cited by This (23)

Action	Title	Year	Authors
+ PDF Chat	An alternating direction algorithm for matrix completion with nonnegative factors	2012	Yangyang Xu Wotao Yin Zaiwen Wen Yin Zhang
+	A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization	2016	Kejun Huang Nicholas D. Sidiropoulos Athanasios P. Liavas
+	A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion	2013	Yangyang Xu Wotao Yin
+	On concepts of directional differentiability	1990	Alexander Shapiro
+	Nonparametric Tikhonov Regularized NMF and Its Application in Cancer Clustering	2014	Andri Mirzal
+	Global convergence of modified multiplicative updates for nonnegative matrix factorization	2013	Norikazu Takahashi Ryota Hibi
+	Cubic regularization of Newton method and its global performance	2006	Yurii Nesterov B. T. Polyak
+ PDF Chat	On Tensors, Sparsity, and Nonnegative Factorizations	2012	C. Eric Tamara G. Kolda
+ PDF Chat	A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization	2013	Meisam Razaviyayn Mingyi Hong Zhi-Quan Luo
+	Unified Development of Multiplicative Algorithms for Linear and Quadratic Nonnegative Matrix Factorization	2011	Zhirong Yang Erkki Oja