Rank Minimization and Applications in System Theory

M. Fazel, H. Hindi, and S. Boyd

Proceedings American Control Conference, pages 3273-3278, June 2004.

In this tutorial paper, we consider the problem of minimizing the rank of a matrix over a convex set. The Rank Minimization Problem (RMP) arises in diverse areas such as control, system identification, statistics and signal processing, and is known to be computationally NP-hard. We give an overview of the problem, its interpretations, applications, and solution methods. In particular, we focus on how convex optimization can be used to develop heuristic methods for this problem.