Matrices of Bounded Psd Rank are Easy to Detect
Yaroslav Nikolaevich Shitov · SIAM Journal on Optimization · 2018
Gouveia, Parrilo, and Thomas gave a description of certain rank functions of matrices in geometric terms, generalizing a celebrated result of Yannakakis on the nonnegative rank. We analyze the algorithmic complexity of their description using the results of Renegar on the first-order theory of the reals. This gives a proof that matrices whose positive semidefinite rank is equal to an integer fixed in advance can be detected in polynomial time.