Hien, Le Thi Khanh; Acapela Group, Rue du Crossage 2a, 7012 Mons, Belgium.
Leplat, Valentin; Institute of Data Sciences, Faculty of Engineering, Innopolis Univerity, Innopolis, Russia.
GILLIS, Nicolas ; Université de Mons - UMONS > Faculté Polytechnique > Service de Mathématique et Recherche opérationnelle
Language :
English
Title :
Block Majorization Minimization with Extrapolation and Application to beta-NMF
Publication date :
13 August 2025
Journal title :
SIAM Journal on Mathematics of Data Science
eISSN :
2577-0187
Publisher :
Society for Industrial & Applied Mathematics (SIAM)
Volume :
7
Issue :
3
Pages :
1292-1314
Peer reviewed :
Peer Reviewed verified by ORBi
Research unit :
F151 - Mathématique et Recherche opérationnelle
Research institute :
R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique R450 - Institut NUMEDIART pour les Technologies des Arts Numériques
European Projects :
HE - 101085607 - eLinoR - Beyond Low-Rank Factorizations
A. M. S. Ang and N. Gillis, Accelerating nonnegative matrix factorization algorithms using extrapolation, Neural Comput., 31 (2019), pp. 417-439, https://doi.org/10.1162/neco a 01157.
H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116 (2009), pp. 5-16, https://doi.org/10.1007/s10107-007-0133-5.
H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-\ Lojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438-457, https://doi.org/10.1287/moor.1100.0449.
A. Beck and L. Tetruashvili, On the convergence of block coordinate descent type methods, SIAM J. Optim., 23 (2013), pp. 2037-2060, https://doi.org/10.1137/120887679.
D. Bertsekas, Nonlinear Programming, Athena Scientific, 2016.
J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), pp. 459-494, https://doi.org/10.1007/s10107-013-0701-9.
P. Carbonetto, K. Luo, A. Sarkar, A. Hung, K. Tayeb, S. Pott, and M. Stephens, GoM DE: Interpreting structure in sequence count data with differential expression analysis allowing for grades of membership, Genome Biol., 24 (2023), 236, https://doi.org/10.1186/s13059-023-03067-9.
A. P. Dempster, N. M. Laird, and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. R. Stat. Soc. Ser. B Stat. Methodol., 39 (1977), pp. 1-22, https://doi.org/10.1111/j.25176161.1977.tb01600.x.
C. Fevotte \' and N. Dobigeon, Nonlinear Hyperspectral Unmixing with Robust Nonnegative Matrix Factorization, preprint, arXiv:1401.5649, 2014.
C. Fevotte \' and J. Idier, Algorithms for nonnegative matrix factorization with the \beta-divergence, Neural Comput., 23 (2011), pp. 2421-2456, https://doi.org/10.1162/NECO a 00168.
X. Fu, W.-K. Ma, K. Huang, and N. D. Sidiropoulos, Blind separation of quasi-stationary sources: Exploiting convex geometry in covariance domain, IEEE Trans. Signal Process., 63 (2015), pp. 2306-2320, https://doi.org/10.1109/TSP.2015.2404577.
L. Grippo and M. Sciandrone, On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26 (2000), pp. 127-136, https://doi.org/10.1016/S0167-6377(99)00074-7.
L. Hien, D. Phan, and N. Gillis, Inertial alternating direction method of multipliers for non-convex nonsmooth optimization, Comput. Optim. Appl., 83 (2022), pp. 247-285, https://doi.org/10.1007/s10589-022-00394-8.
L. T. K. Hien and N. Gillis, Algorithms for nonnegative matrix factorization with the Kullback-Leibler divergence, J. Sci. Comput., 87 (2021), 93, https://doi.org/10.1007/s10915-021-01504-0.
L. T. K. Hien, N. Gillis, and P. Patrinos, Inertial block proximal method for non-convex non-smooth optimization, in Thirty-Seventh International Conference on Machine Learning (ICML), 2020.
L. T. K. Hien, D. N. Phan, and N. Gillis, An inertial block majorization minimization framework for nonsmooth nonconvex optimization, J. Mach. Learn. Res., 24 (2023), pp. 1-41, https://www.jmlr.org/papers/v24/21-0571.html.
C. J. Hsieh and I. S. Dhillon, Fast coordinate descent methods with variable selection for non-negative matrix factorization, in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011.
D. R. Hunter and K. Lange, A tutorial on MM algorithms, Amer. Statist., 58 (2004), pp. 30-37, https://doi.org/10.1198/0003130042836.
K. Lange, D. R. Hunter, and I. Yang, Optimization transfer using surrogate objective functions, J. Comput. Graph. Stat., 9 (2000), pp. 1-20, https://doi.org/10.1080/10618600.2000.10474858.
D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), pp. 788-791, https://doi.org/10.1038/44565.
V. Leplat, N. Gillis, and A. M. Ang, Blind audio source separation with minimum-volume beta-divergence NMF, IEEE Trans. Signal Process., 68 (2020), pp. 3400-3410, https://doi.org/10.1109/TSP.2020.2991801.
V. Leplat, N. Gillis, and J. Idier, Multiplicative updates for NMF with \beta-divergences under disjoint equality constraints, SIAM J. Matrix Anal. Appl., 42 (2021), pp. 730-752, https://doi.org/10.1137/ 20M1377278.
C. H. Lin, W.-K. Ma, W.-C. Li, C.-Y. Chi, and A. Ambikapathi, Identifiability of the simplex volume minimization criterion for blind hyperspectral unmixing: The no-pure-pixel case, IEEE Trans. Geosci. Remote Sens., 53 (2015), pp. 5530-5546, https://doi.org/10.1109/TGRS.2015.2424719.
H. Lyu and Y. Li, Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization, SIAM J. Optim., 35 (2025), pp. 842-871, https://doi.org/10.1137/23M1604515.
J. Mairal, Optimization with first-order surrogate functions, in 30th International Conference on Machine Learning, Vol. 28, 2013, pp. 783-791.
A. Marmin, J. H. de Morais Goulart, and C. Fevotte \', Joint majorization-minimization for nonnegative matrix factorization with the \beta-divergence, Signal Process., 209 (2023), 109048, https://doi.org/10.1016/j.sigpro.2023.109048.
A. Marmin, J. H. de Morais Goulart, and C. Fevotte \', Majorization-minimization for sparse nonnegative matrix factorization with the \beta-divergence, IEEE Trans. Signal Process., 71 (2023), pp. 1435-1447, https://doi.org/10.1109/TSP.2023.3266939.
J. G. Melo and R. D. C. Monteiro, Iteration-Complexity of a Jacobi-Type Non-Euclidean ADMM for Multi-block Linearly Constrained Nonconvex Programs, https://arxiv.org/abs/1705.07229, 2017.
L. Miao and H. Qi, Endmember extraction from highly mixed data using minimum volume constrained nonnegative matrix factorization, IEEE Trans. Geosci. Remote Sens., 45 (2007), pp. 765-777, https://doi.org/10.1109/TGRS.2006.888466.
R. M. Neal and G. E. Hinton, A View of the EM Algorithm that Justifies Incremental, Sparse, and other Variants, Springer, Dordrecht, The Netherlands, 1998, pp. 355-368.
Y. Nesterov, Lectures on Convex Optimization, Springer, 2018.
P. Ochs, Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano, SIAM J. Optim., 29 (2019), pp. 541-570, https://doi.org/10.1137/17M1124085.
P. Ochs, Y. Chen, T. Brox, and T. Pock, iPiano: Inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci., 7 (2014), pp. 1388-1419, https://doi.org/10.1137/130942954.
M. Q. Pham, J. Cohen, and T. Chonavel, A Fast Multiplicative Updates Algorithm for Nonnegative Matrix Factorization, preprint, arXiv:2303.17992, 2023.
T. Pock and S. Sabach, Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems, SIAM J. Imaging Sci., 9 (2016), pp. 1756-1787, https://doi.org/10.1137/ 16M1064064.
M. Razaviyayn, M. Hong, and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optim., 23 (2013), pp. 1126-1153, https://doi.org/10.1137/120891009.
W. H. Richardson, Bayesian-based iterative method of image restoration, J. Optical Soc. Amer., 62 (1972), pp. 55-59, https://doi.org/10.1364/JOSA.62.000055.
Y. Sun, P. Babu, and D. Palomar, Majorization-minimization algorithms in signal processing, communications, and machine learning, IEEE Trans. Signal Process., 65 (2017), pp. 794-816, https://doi.org/10.1109/TSP.2016.2601299.
P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl., 109 (2001), pp. 475-494, https://doi.org/10.1023/A:1017501703105.
P. Tseng, On Accelerated Proximal Gradient Methods for Convex-Concave Optimization, Technical report, 2008.
P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117 (2009), pp. 387-423, https://doi.org/10.1007/s10107-007-0170-0.
O. Vu Thanh, A. Ang, N. Gillis, and L. T. K. Hien, Inertial majorization-minimization algorithm for minimum-volume NMF, in European Signal Processing Conference (EUSIPCO), 2021.
Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6 (2013), pp. 1758-1789, https://doi.org/10.1137/120887795.
