The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions

DOI10.1137/16M1080999zbMath1377.15003arXiv1605.04000MaRDI QIDQ4592948

Yaroslav 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)

Related Items (8)

Matrices of Bounded Psd Rank are Easy to Detect ⋮ The NMF problem and lattice-subspaces ⋮ Alternating sign matrices, related (0,1)-matrices, and the Smith normal form ⋮ Conic optimization-based algorithms for nonnegative matrix factorization ⋮ Unilateral Orthogonal Nonnegative Matrix Factorization ⋮ Symmetric nonnegative matrix trifactorization ⋮ Nonnegative rank depends on the field ⋮ Factoring a band matrix over a semiring

Cites Work

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

This page was built for publication: The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions