Rank minimization using sums of squares of nonnegative matrices

Recently, moment dual approach of sums of squares relaxations developed for polynomial optimization problems was successfully extended to optimization problems with polynomial matrix inequality constraints. In this paper, we first derive an efficient polynomial formulization for matrix rank minimization problem which does not add any slack variable or additional equality or inequality constraint. Using the aforementioned theory, then we propose a hierarchy of convex LMI relaxations to provide a sequence of increasingly tight lower bounds on the global minimum rank of an arbitrary matrix under linear and polynomial matrix inequality constraints. Surprisingly enough, these lower bounds are usually exact and the optimal rank is often attained at early stages of the algorithm, make it possible to extract all optimal minimzers using Curto-Fialkow flat extension results. Special issues on complexity, implementation and numerical results are also properly addressed.