An upper bound for nonnegative rank

DOI10.1016/j.jcta.2013.10.004zbMath1316.52020arXiv1303.1960OpenAlexW2015290853MaRDI QIDQ2341256

Yaroslav N. Shitov

Publication date: 23 April 2015

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

convex polytopeextended formulationnonnegative factorization

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Matrices of integers (15B36)

Related Items (20)

Extended formulations for convex heptagons ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring ⋮ A separation between tropical matrix ranks ⋮ Common information and unique disjointness ⋮ Extension complexity of low-dimensional polytopes ⋮ An elementary method to compute the algebra generated by some given matrices and its dimension ⋮ On Ranks of Regular Polygons ⋮ Symmetric nonnegative matrix trifactorization ⋮ Unnamed Item ⋮ Lifts of non-compact convex sets and cone factorizations ⋮ Euclidean distance matrices and separations in communication complexity theory ⋮ Extension complexity and realization spaces of hypersimplices ⋮ On the linear extension complexity of regular \(n\)-gons ⋮ Polygons as sections of higher-dimensional polytopes ⋮ Hidden vertices in extensions of polytopes ⋮ Tropical lower bounds for extended formulations ⋮ Worst-case results for positive semidefinite rank ⋮ Extension Complexity of Polytopes with Few Vertices or Facets ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

Cites Work

• Polytopes of minimum positive semidefinite rank
• On the nonnegative rank of distance matrices
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• On the nonnegative rank of Euclidean distance matrices
• Real rank versus nonnegative rank
• Expressing combinatorial optimization problems by linear programs
• On the geometric interpretation of the nonnegative rank
• Constructing Extended Formulations from Reflection Relations
• On the Complexity of Nonnegative Matrix Factorization
• Lifts of Convex Sets and Cone Factorizations
• Linear vs. semidefinite extended formulations
• Extended formulations in combinatorial optimization

This page was built for publication: An upper bound for nonnegative rank