Worst-case results for positive semidefinite rank (Q745690): Difference between revisions

The positive semidefinite rank is an extension of the notion of the nonnegative rank of a matrix. The nonnegative rank of a matrix is the smallest possible integer \(k\) such that each entry \((i,j)\) of the matrix can be written as the inner product of two vectors \(a_i\) and \(b_j\) in the cone of nonnegative vectors of size \(k\). The positive semidefinite rank is the smallest possible integer \(k\) such that each entry \((i,j)\) of the matrix can be written as the inner product of two matrices \(A_i\) and \(B_j\) in the cone of positive semidefinite matrices of size \(k\). These ranks can be interpreted as a measure of complexity of a polytope, in the sense that they encode the size of a sparse representation of a polytope through a factorization of its matrix description. The paper under review reports on state-of-the-art results on lower bounds on the positive semidefinite rank, both for generic polytopes and for specific polytopes.