Polytopes of minimum positive semidefinite rank
From MaRDI portal
Publication:377501
DOI10.1007/S00454-013-9533-XzbMATH Open1279.52023arXiv1205.5306OpenAlexW2071242430MaRDI QIDQ377501FDOQ377501
Authors: João Gouveia, Richard Z. Robinson, Rekha Thomas 
Publication date: 6 November 2013
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1205.5306
Recommendations
Cites Work
- On the Shannon capacity of a graph
- Expressing combinatorial optimization problems by linear programs
- Geometric algorithms and combinatorial optimization.
- On the geometric interpretation of the nonnegative rank
- Constructing extended formulations from reflection relations
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Title not available (Why is that?)
- Linear vs. semidefinite extended formulations
- Extended formulations for polygons
- The strong perfect graph theorem
- Convex Polytopes
- Lifts of Convex Sets and Cone Factorizations
- Combinatorial bounds on nonnegative rank and extended formulations
- Smallest compact formulation for the permutahedron
- Theta bodies for polynomial ideals
Cited In (33)
- The Phaseless Rank of a Matrix
- Extended formulations for convex heptagons
- On Ranks of Regular Polygons
- Rank functions of tropical matrices
- 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
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
- Binary positive semidefinite matrices and associated integer polytopes
- Two-Level Polytopes with a Prescribed Facet
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank
- 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
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Complex psd-minimal polytopes in dimensions two and three
- On the matrix-cut rank of polyhedra.
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- Lifting for Simplicity: Concise Descriptions of Convex Sets
- Theta rank, levelness, and matroid minors
- On Vertices and Facets of Combinatorial 2-Level Polytopes
- 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
- Enumeration of 2-level polytopes
- Two results on the size of spectrahedral descriptions
- Extension complexity and realization spaces of hypersimplices
Uses Software
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)
