A Lower Bound on the Positive Semidefinite Rank of Convex Bodies

on YouTube ↗29m

" summary

Claim: PSD rank m of a convex body is at least on the order of sqrt(log D) where D is the degree of the algebraic boundary of the polar. Proof turns the SDP optimality conditions into a KKT polynomial system, applies the Bézout/Basu bound to show the system has at most 2^{m^2} solutions, and uses known formulas for the algebraic degree of SDP to invert that bound. Gives matching constructions with random spectrahedra and implies any SDP lift with size m has at most 2^{m^2} vertices.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to PSD rank
2. 1:33Constructing SDP lifts
3. 2:57Motivation from LP lifts
4. 4:56Quantifier elimination limits
5. 7:59Polar-based lower bounds
6. 10:40Clarifying polar properties
7. 12:36KKT systems and optimization
8. 17:18Proving the lower bound
9. 21:09Tightness and applications
10. 23:17Irreducible decomposition
11. 27:05Concluding remarks