Conic optimization-based algorithms for nonnegative matrix factorization

Abstract

Nonnegative matrix factorization is the following problem: given a nonnegative input matrix V and a factorization rank K, compute two nonnegative matrices, W with K columns and H with K rows, such that WH approximates V as well as possible. In this paper, we propose two new approaches for computing high-quality NMF solutions using conic optimization. These approaches rely on the same two steps. First, we reformulate NMF as minimizing a concave function over a product of convex cones – one approach is based on the exponential cone and the other on the second-order cone. Then, we solve these reformulations iteratively: at each step, we minimize exactly, over the feasible set, a majorization of the objective functions obtained via linearization at the current iterate. Hence these subproblems are convex conic programs and can be solved efficiently using dedicated algorithms. We prove that our approaches reach a stationary point with an accuracy decreasing as $\mathcal{O}\left(\frac{1}{i}\right)$, where i denotes the iteration number. To the best of our knowledge, our analysis is the first to provide a convergence rate to stationary points for NMF. Furthermore, in the particular cases of rank-1 factorizations (i.e. K = 1), we show that one of our formulations can be expressed as a convex optimization problem, implying that optimal rank-1 approximations can be computed efficiently. Finally, we show on several numerical examples that our approaches are able to frequently compute exact NMFs (i.e. with V = WH) and compete favourably with the state of the art.

Keywords:

• Nonnegative matrix factorization
• nonnegative rank
• exponential cone
• second-order cone
• concave minimization
• conic optimization
• Frank–Wolfe gap
• convergence to stationary points

Acknowledgments

We thank the two reviewers for their careful reading and insightful feedback that helped us improve the paper significantly.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 3-SAT, or 3-satisfiability, is an instrumental problem in computational complexity to prove NP-completeness results. 3-SAT is the problem of deciding whether a set of disjunctions containing 3 Boolean variables or their negation can be satisfied.

Additional information

Funding

VL acknowledges the support by the European Research Council (ERC Advanced Grant no 788368) and the support by Ministry of Science and Higher Education grant no. 075-10-2021-068. NG acknowledges the support by the Fonds de la Recherche Scientifique - FNRS and the Fonds Wetenschappelijk Onderzoek - Vlanderen (FWO) under EOS Project no O005318F-RG47, by the European Research Council (ERC Starting Grant no 679515), and by the Francqui Foundation. YN and FG acknowledge support from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement no. 788368). FG also acknowledges support from EOS project no. O005318F-RG47.

Notes on contributors

Valentin Leplat

Valentin Leplat received engineering degrees in mechanical engineering from Gramme Institute, Liège, Belgium, in 2012 and in computer sciences and applied mathematics engineering from University of Mons, Belgium in 2017. He completed his Ph.D. in applied mathematics in January 2021 on the topic of Nonnegative Matrix Factorizations (NMF), associated with the Department of Mathematics and operations research at the University of Mons, Belgium. In 2021, he was a postdoctoral research associate in applied mathematics at Université Catholique de Louvain (Belgium). Since October 2021, he is working at Skoltech (Moscow) as a senior research scientist on the topics of machine learning, stochastic optimization and tensors decompositions.

Yurii Nesterov

Yurii Nesterov is a professor at Center for Operations Research and Econometrics (CORE) in Catholic University of Louvain (UCL), Belgium. He received Ph.D. degree (Applied Mathematics) in 1984 at Institute of Control Sciences, Moscow. Starting from 1993 he works at Center of Operations Research and Econometrics (Catholic University of Louvain, Belgium). His research interests are related to complexity issues and efficient methods for solving various optimization problems. The main results are obtained in Convex Optimization (optimal methods for smooth problems, polynomial-time interior-point methods, smoothing technique for structural optimization, complexity theory for secondorder methods, optimization methods for huge-scale problems). He is an author of 6 monographs and more than 150 refereed papers in the leading optimization journals. He got several international prizes and recognitions, among them there are Dantzig Prize from SIAM and Mathematical Programming society (2000), von Neumann Theory Prize from INFORMS (2009), SIAM Outstanding paper award (2014), Euro Gold Medal from Association of European Operations Research Societies (2016), Memberships in Academia Europaea (2021) and National Academy of Sciences (USA, 2022), Lanchester prize from INFROMS (2022).

Nicolas Gillis

Nicolas Gillis is Professor with the Department of Mathematics and Operational Research, University of Mons, Belgium. He is recipient of the Householder award (2014), an ERC starting grant (2015), and an ERC consolidator grant (2022). He is editor for the IEEEE Transactions on Signal Processing, and the SIAM Journals on Matrix Analysis and Applications and on Mathematics of Data Science. His research interests lie in optimization, numerical linear algebra, signal processing, machine learning and data mining.

François Glineur

François Glineur earned dual engineering degrees from CentraleSupélec and Université de Mons in 1997, and a PhD in Applied Sciences from the latter institution in 2001. After visiting Delft University of Technology and working as a post-doctoral researcher at McMaster University, he joined Université catholique de Louvain, where he is currently a full professor of applied mathematics in the Engineering School. He is also a member of the Center for Operations Research and Econometrics and the Institute of Information and Communication Technologies, Electronics and Applied Mathematics. He served as the Engineering School's vice-dean between 2016 and 2020. His primary areas of interest in research are optimization models and methods, with a particular emphasis on convex optimization and algorithmic efficiency. He received the 2017 Optimization Letters best paper award for the worst-case analysis of gradient descent with line search. He is also interested in the use of optimization in engineering, as well as nonnegative matrix factorization and its application to data analysis.