The complexity of positive semidefinite matrix factorization

Abstract

Let $A$ be a matrix with nonnegative real entries. The PSD rank of $A$ is the smallest integer $k$ for which there exist $k\times k$ real PSD matrices $B_1,\dots ,B_m$, $C_1,\dots ,C_n$ satisfying $A(i|j)=\mathrm{tr}(B_i{C}_j)$ for all $i,j$. This paper determines the computational complexity status of the PSD rank. Namely, we show that the problem of computing this function is polynomial-time equivalent to the existential theory of the reals.

arXiv comment11 pages