A Strengthened Barvinok-Pataki Bound on SDP Rank

Jiyoung Im(j5imuwaterloo.ca)
Henry Wolkowicz(hwolkowiuwaterloo.ca)

Abstract: The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit this bound and provide a strengthened upper bound on the rank using the singularity degree of the spectrahedron. Thus we bring in the geometry and stability of the spectrahedron, i.e., increased instability as seen by higher singularity degree, yields a lower, strengthened rank bound.

Keywords: Barvinok-Pataki bound, facial reduction, rank, singularity degree, Semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: April/2021

Download: [PDF]

Entry Submitted: 04/19/2021
Entry Accepted: 04/20/2021
Entry Last Modified: 04/19/2021

Modify/Update this entry