Title: 
On the Low Rank Solutions for Linear Matrix Inequalities

Authors:
Wenbao Ai
School of Science
Beijing University of Posts and Telecommunications
People's Republic of China
wenbaoai@gmail.com


Yongwei Huang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong
ywhuang@se.cuhk.edu.hk


Shuzhong Zhang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong
zhang@se.cuhk.edu.hk


Abstract:
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 Au-Yeung and Poon~\cite{AYP79} and Barvinok~\cite{B01}.
In Au-Yeung and Poon's approach, an earlier unpublished manuscript
of Bohnenblust~\cite{Boh} played an essential role. Both proofs
in~\cite{AYP79} and~\cite{B01} are nonconstructive in nature. The
aim of this paper is to offer a constructive and polynomial-time
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.