Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
In the authors' words
We present tight lower bounds for the size of any linear matrix inequality representation of the Euclidean ball, and on the semidefinite extension complexity of the ball. Specifically, we show that any linear matrix inequality representing the Euclidean ball must involve matrices of size at least , and any spectrahedral extension of the Euclidean ball must involve matrices of size at least . These match the bounds given by existing explicit constructions. Our proofs rely on elementary facts about the dimension of the set of faces of spectrahedra, and indeed extend to any convex set whose extreme points form a semialgebraic set.
Main resultThe abstract does not state a limitation.
Appeared: Monday, September 21. arXiv. Preprint, not yet peer-reviewed.