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, signal processing, and combinatorial optimization, and is known to be computationally NP-hard. As a special case, it includes the problem of finding the sparsest vector in a convex set.; In this dissertation, we propose two heuristics based on convex optimization that approximately solve the RMP. We refer to them as the trace/ nuclear norm and the log-det heuristics. Unlike the existing methods, these heuristics can handle any general matrix, are numerically very efficient, do not require a user-specified initial point, and yield a global lower bound on the RMP if the feasible set is bounded. We show that the nuclear norm heuristic is optimal in the sense that it minimizes the convex envelope of the rank function, thus providing theoretical support for its use. In the special case of finding sparse vectors, these heuristics reduce to the ℓ1-norm and iterative ℓ 1-norm minimization methods.; We catalog many practical applications of the RMP. By giving numerical examples of problems from different fields, we demonstrate that our proposed heuristics work very well in practice.
展开▼
