Some upper and lower bounds on PSD-rank (Q517316)

Let \(A\) be a nonnegative \(m\)-by-\(n\) matrix. A positive semidefinite factorization of size \(r\) of \(A\) is given by \(r\)-by-\(r\) positive semidefinite matrices \(E_1, \dots , E_m\) and \(F_1, \dots , F_n\) satisfying \(A(i, j) = \text{Tr}(E_i, F_j)\) for all \(i, j\). The positive semidefinite rank (PSD-rank) of \(A\) is the smallest \(r\) such that \(A\) has a positive semidefinite factorization of size \(r\). The PSD-rank has applications to combinatorial optimization and communication complexity. The authors investigate properties of the PSD-rank; they study several bounds on the PSD-rank with particular attention to lower bounds.