HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

A lower bound on the positive semidefinite rank of convex bodies

Abstract : The positive semidefinite rank of a convex body C is the size of its smallest positive semidef-inite formulation. We show that the positive semidefinite rank of any convex body C is at least $\sqrt{log d}$ where d is the smallest degree of a polynomial that vanishes on the boundary of the polar of C. This improves on the existing bound which relies on results from quantifier elimination. Our proof relies on the Bézout bound applied to the Karush-Kuhn-Tucker conditions of optimality. We discuss the connection with the algebraic degree of semidefinite programming and show that the bound is tight (up to constant factor) for random spectrahedra of suitable dimension.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

Contributor : Mohab Safey El Din Connect in order to contact the contributor
Submitted on : Thursday, December 7, 2017 - 10:45:38 AM
Last modification on : Friday, February 4, 2022 - 3:10:02 AM


Files produced by the author(s)



Hamza Fawzi, Mohab Safey El Din. A lower bound on the positive semidefinite rank of convex bodies. SIAM Journal on Applied Algebra and Geometry, Society for Industrial and Applied Mathematics 2018, 2 (1), pp.126-139. ⟨10.1137/17M1142570⟩. ⟨hal-01657849⟩



Record views


Files downloads