Submitted or in preparation:
My PhD work concerns the problem of minimizing the rank of a matrix over a convex set. In many engineering applications, notions such as order, complexity, or dimension of a model or design can be expressed as the rank of an appropriate matrix. If the set of feasible models or designs is convex, then choosing the simplest model can be cast as a Rank Minimization Problem (RMP). For example, a low-rank matrix could correspond to a low-order controller for a plant, a low-degree statistical model fit for a random process, a shape that can be embedded in a low-dimensional space, or a design with a small number of components. It is thus not surprising that rank minimization has diverse applications: following Occam's razor, we often seek simple explanations and designs.
The RMP is known to be NP-hard. If the variable in an RMP is a positive semidefinite matrix, a simple and effective relaxation commonly used is trace minimization. We prove that any general RMP involving non-positive semidefinite or even non-square matrices, can be embedded in a larger, positive semidefinite RMP. This semidefinite embedding lemma is then used to extend the trace relaxation, as well as other methods using semidefiniteness, to general matrices. The generalized trace relaxation minimizes the dual of the matrix 2-norm, referred to as the nuclear norm. Furthermore, we show that this relaxation is equivalent to minimizing the convex envelope of the rank function over the unit ball, thus providing theoretical support for its use. We also propose another heuristic based on (locally) minimizing the logarithm of the determinant (log-det) of the matrix, to refine the result of the trace relaxation and reduce the rank further. This heuristic is in fact equivalent to iteratively minimizing a weighted trace objective, and thus also admits an interpretation in terms of convex envelopes. Finally, applying these methods to application examples shows they work well in practice.