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)- Extended formulations for convex heptagons
- Lifting for simplicity: concise descriptions of convex sets
- Rank functions of tropical matrices
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- Two-level polytopes with a prescribed facet
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Deciding polyhedrality of spectrahedra
- Projectively unique polytopes and toric slack ideals
- Tropical lower bounds for extended formulations
- Worst-case results for positive semidefinite rank
- The phaseless rank of a matrix
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Binary positive semidefinite matrices and associated integer polytopes
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank
- Matrices of bounded psd rank are easy to detect
- Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
- An upper bound for nonnegative rank
- Bounds on the number of 2-level polytopes, cones, and configurations
- Rational and real positive semidefinite rank can be different
- A lower bound on the positive semidefinite rank of convex bodies
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- On ranks of regular polygons
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- On the matrix-cut rank of polyhedra.
- Complex psd-minimal polytopes in dimensions two and three
- Theta rank, levelness, and matroid minors
- Binary Positive Semidefinite Matrices and Associated Integer Polytopes
- Positive semidefinite rank and nested spectrahedra
- Lifts of non-compact convex sets and cone factorizations
- Four-dimensional polytopes of minimum positive semidefinite rank
- Equivariant semidefinite lifts of regular polygons
- Two results on the size of spectrahedral descriptions
- Extension complexity and realization spaces of hypersimplices
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)
