A polynomial-time algorithm for computing low CP-rank decompositions

This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for checking if a given PSD matrix has cp-rank of at most r, when r is a given constant. In addition, we present a polynomial-time algorithm for computing a (rational) cp-decomposition of such a matrix if it exists, within any desired accuracy.