The nonnegative rank of a matrix: hard problems, easy solutions

DOI10.1137/16M1080999zbMATH Open1377.15003MaRDI QIDQ4592948FDOQ4592948

Authors Ya. N. Shitov

Publication date 9 November 2017

Published in SIAM Review (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityranknonnegative matrix factorization

Mathematics Subject Classification ID

Factorization of matrices (15A23) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: Using elementary linear algebra, we develop a technique that leads to solutions of two widely known problems on nonnegative matrices. First, we give a short proof of the result by Vavasis stating that the nonnegative rank of a matrix is NP-hard to compute. This proof is essentially contained in the paper by Jiang and Ravikumar, who discussed this topic in different terms fifteen years before the work of Vavasis. Secondly, we present a solution of the problem of Cohen and Rothblum on rational nonnegative factorizations, which was posed in 1993 and remained open.

Recommendations

• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• An almost optimal algorithm for computing nonnegative rank
• An almost optimal algorithm for computing nonnegative rank
• Nonnegative rank depends on the field
• On the geometric interpretation of the nonnegative rank

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• Combinatorial bounds on nonnegative rank and extended formulations
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Fixed points of the EM algorithm and nonnegative rank boundaries
• Learning the parts of objects by non-negative matrix factorization
• Linear vs. semidefinite extended formulations
• Minimal NFA Problems are Hard
• Nearly tight approximability results for minimum biclique cover and partition
• Nonnegative matrix factorization requires irrationality
• Nonnegative rank vs. binary rank
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On the complexity of Boolean matrix ranks
• On the complexity of nonnegative matrix factorization
• Rational and real positive semidefinite rank can be different
• Reducibility among combinatorial problems
• Some \(0/1\) polytopes need exponential size extended formulations
• Uniquely restricted matchings

Cited in

(12)

• The NMF problem and lattice-subspaces
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Unilateral Orthogonal Nonnegative Matrix Factorization
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• Conic optimization-based algorithms for nonnegative matrix factorization
• An almost optimal algorithm for computing nonnegative rank
• On the geometric interpretation of the nonnegative rank
• An almost optimal algorithm for computing nonnegative rank
• Nonnegative rank depends on the field
• Factoring a band matrix over a semiring
• Symmetric nonnegative matrix trifactorization
• Matrices of bounded psd rank are easy to detect

This page was built for publication: The nonnegative rank of a matrix: hard problems, easy solutions

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