Polytopes of minimum positive semidefinite rank
From MaRDI portal
Publication:377501
Abstract: The positive semidefinite (psd) rank of a polytope is the smallest for which the cone of real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, and we characterize those polytopes whose psd rank equals this lower bound. We give several classes of polytopes that achieve the minimum possible psd rank including a complete characterization in dimensions two and three.
Recommendations
Cites work
- scientific article; zbMATH DE number 108068 (Why is no real title available?)
- Combinatorial bounds on nonnegative rank and extended formulations
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Constructing extended formulations from reflection relations
- Convex Polytopes
- Expressing combinatorial optimization problems by linear programs
- Extended formulations for polygons
- Geometric algorithms and combinatorial optimization.
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- On the Shannon capacity of a graph
- On the geometric interpretation of the nonnegative rank
- Smallest compact formulation for the permutahedron
- The strong perfect graph theorem
- Theta bodies for polynomial ideals
Cited in
(34)- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Rank functions of tropical matrices
- Lifting for simplicity: concise descriptions of convex sets
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
- Rational and real positive semidefinite rank can be different
- Bounds on the number of 2-level polytopes, cones, and configurations
- Equivariant semidefinite lifts of regular polygons
- Theta rank, levelness, and matroid minors
- An upper bound for nonnegative rank
- Complex psd-minimal polytopes in dimensions two and three
- Extension complexity and realization spaces of hypersimplices
- On ranks of regular polygons
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- Two results on the size of spectrahedral descriptions
- Tropical lower bounds for extended formulations
- Worst-case results for positive semidefinite rank
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Binary positive semidefinite matrices and associated integer polytopes
- Lifts of non-compact convex sets and cone factorizations
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Two-level polytopes with a prescribed facet
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank
- Four-dimensional polytopes of minimum positive semidefinite rank
- Projectively unique polytopes and toric slack ideals
- Positive semidefinite rank and nested spectrahedra
- The phaseless rank of a matrix
- Extended formulations for convex heptagons
- A lower bound on the positive semidefinite rank of convex bodies
- On the matrix-cut rank of polyhedra.
- Binary Positive Semidefinite Matrices and Associated Integer Polytopes
- Deciding polyhedrality of spectrahedra
- Matrices of bounded psd rank are easy to detect
This page was built for publication: Polytopes of minimum positive semidefinite rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q377501)
