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.