Positive semidefinite rank
Let \(M \in \mathbb {R}^{p \times q}\) be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices \(A_i, B_j\) of size \(k \times k\) such that \(M_{ij} = {{\mathrm{trace}}}(A_i B_j)\). The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects.
90c22 15a23 68q17