Polytopes of minimum positive semidefinite rank
From MaRDI portal
(Redirected from 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
- 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.
- scientific article; zbMATH DE number 108068 (Why is no real title available?)
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- On the geometric interpretation of the nonnegative rank
- On the Shannon capacity of a graph
- Smallest compact formulation for the permutahedron
- The strong perfect graph theorem
- Theta bodies for polynomial ideals
Cited in
(36)- 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
- Extension complexity and realization spaces of hypersimplices
- Rational and real positive semidefinite rank can be different
- Lifts of non-compact convex sets and cone factorizations
- Projectively unique polytopes and toric slack ideals
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- An upper bound for nonnegative rank
- Extended formulations for convex heptagons
- Bounds on the number of 2-level polytopes, cones, and configurations
- Rank functions of tropical matrices
- On the matrix-cut rank of polyhedra.
- Two results on the size of spectrahedral descriptions
- Two-level polytopes with a prescribed facet
- Deciding polyhedrality of spectrahedra
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Binary Positive Semidefinite Matrices and Associated Integer Polytopes
- A lower bound on the positive semidefinite rank of convex bodies
- Matrices of bounded psd rank are easy to detect
- On ranks of regular polygons
- Lifting for simplicity: concise descriptions of convex sets
- Theta rank, levelness, and matroid minors
- Four-dimensional polytopes of minimum positive semidefinite rank
- The phaseless rank of a matrix
- Positive semidefinite rank and nested spectrahedra
- Equivariant semidefinite lifts of regular polygons
- Complex psd-minimal polytopes in dimensions two and three
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Binary positive semidefinite matrices and associated integer polytopes
- Sublinear extensions of polygons
- Stability for binary scalar products
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Tropical lower bounds for extended formulations
- Positive semidefinite rank
- Worst-case results for positive semidefinite rank
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)
