On the Low Rank Solutions for Linear Matrix Inequalities

In this paper we present a polynomial-time procedure to find a low-rank solution for a system of linear matrix inequalities (LMI). The existence of such a low-rank solution was shown in the work of Au-Yeung and Poon and the work of Barvinok. In the approach of Au-Yeung and Poon an earlier unpublished manuscript of Bohnenblust played an essential role. Both proofs in the work of Au-Yeung and Poon and that of Barvinok are nonconstructive in nature. The aim of this paper is to provide a polynomial-time constructive procedure to find such a low-rank solution approximatively. Extensions of our new results and their relations to some of the known results in the literature are discussed.