Conic optimization-based algorithms for nonnegative matrix factorization

Valentin Leplat, Yurii Nesterov (), Nicolas Gillis and François Glineur
Additional contact information
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3254, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 O(1i) , 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 (search for similar items in EconPapers)
Pages: 23
Date: 2023-04-01
Note: In: Optimization Methods and Software. 2023, vol. 38(4), p. 837-859
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3254

DOI: 10.1080/10556788.2023.2189714

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().