Conic optimization-based algorithms for nonnegative matrix factorization

DOI10.1080/10556788.2023.2189714MaRDI QIDQ6113533zbMATH OpenOpenAlexFDO

Authors Valentin Leplat, Yuri Nesterov, Nicolas Gillis, François Glineur

Publication date 9 August 2023

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.13646

zbMATH Keywords

nonnegative matrix factorizationsecond-order conenonnegative rankconcave minimizationconic optimizationexponential coneconvergence to stationary pointsFrank-Wolfe gap

Mathematics Subject Classification ID

Semidefinite programming (90C22)

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 $mathcalO(frac1i)$, 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-one factorizations (that is, $K=1$), we show that one of our formulations can be expressed as a convex optimization problem implying that optimal rank-one approximations can be computed efficiently. Finally, we show on several numerical examples that our approaches are able to frequently compute exact NMFs (that is, with $V=WH$), and compete favorably with the state of the art.

Recommendations

• Efficient nonnegative matrix factorization by DC programming and DCA
• Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
• Exact and heuristic algorithms for semi-nonnegative matrix factorization
• Nonnegative matrix factorization with constrained second-order optimization
• scientific article; zbMATH DE number 7404610

Cites work

• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• A new dual based procedure for the transportation problem
• An almost optimal algorithm for computing nonnegative rank
• Computing a nonnegative matrix factorization -- provably
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• DC programming and DCA: thirty years of developments
• Fast nonnegative matrix factorization: an active-set-like method and comparisons
• Heuristics for exact nonnegative matrix factorization
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On the combinatorial and algebraic complexity of quantifier elimination
• On the complexity of nonnegative matrix factorization
• Stability of propagation features under time-asymptotic approximations for a class of dispersive equations
• The nonnegative rank of a matrix: hard problems, easy solutions
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• Using underapproximations for sparse nonnegative matrix factorization

Cited in

(4)

• Multiplicative updates for symmetric-cone factorizations
• Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
• A convergent algorithm for bi-orthogonal nonnegative matrix tri-factorization
• Majorization-minimization Bregman proximal gradient algorithms for NMF with the Kullback-Leibler divergence

This page was built for publication: Conic optimization-based algorithms for nonnegative matrix factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6113533)