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

DOI10.1137/16M1080999zbMATH Open1377.15003arXiv1605.04000MaRDI QIDQ4592948FDOQ4592948

Authors: Ya. N. Shitov 

Publication date: 9 November 2017

Published in: SIAM Review (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• On the complexity of nonnegative matrix factorization
• Reducibility among Combinatorial Problems
• Learning the parts of objects by non-negative matrix factorization
• Expressing combinatorial optimization problems by linear programs
• Linear vs. semidefinite extended formulations
• Extended formulations in combinatorial optimization
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On the complexity of Boolean matrix ranks
• Combinatorial bounds on nonnegative rank and extended formulations
• Rational and real positive semidefinite rank can be different
• Minimal NFA Problems are Hard
• Fixed points of the EM algorithm and nonnegative rank boundaries
• Some \(0/1\) polytopes need exponential size extended formulations
• Uniquely restricted matchings
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• Title not available (Why is that?)
• Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
• Nonnegative rank vs. binary rank
• Nonnegative Matrix Factorization Requires Irrationality

Cited In (9)

• Matrices of Bounded Psd Rank are Easy to Detect
• Unilateral Orthogonal Nonnegative Matrix Factorization
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Conic optimization-based algorithms for nonnegative matrix factorization
• Factoring a band matrix over a semiring
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• Nonnegative rank depends on the field
• The NMF problem and lattice-subspaces
• Symmetric nonnegative matrix trifactorization

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)