- TITLE: A rank minimization heuristic with application to
minimum order system approximation
- AUTHORS: Maryam Fazel, Haitham Hindi, and Stephen P. Boyd
- ABSTRACT: Several problems arising in control system analysis
and design, such as reduced order controller synthesis, involve
minimizing the rank of a matrix variable subject to linear matrix
inequality (LMI) constraints. Except in some special cases, solving
this rank minimization problem (globally) is very difficult. One
simple and surprisingly effective heuristic, applicable when the
matrix variable is symmetric and positive semidefinite, is to
minimize its trace in place of its rank. This results in a
semidefinite program (SDP) which can be efficiently solved. In this
paper we describe a generalization of the trace heuristic that
applies to general non-symmetric, even non-square, matrices, and
reduces to the trace heuristic when the matrix is positive
semidefinite. The heuristic is to replace the (nonconvex) rank
objective with the sum of the singular values of the matrix, which
is the dual of the spectral norm. We show that this problem can be
reduced to an SDP, hence efficiently solved. To motivate the
heuristic, we show that the dual spectral norm is the convex
envelope of the rank on the set of matrices with norm less than
one. We demonstrate the method on the problem of minimum order
system approximation.
- STATUS: Proceedings American Control Conference, June
2001, volume 6, pages 4734-4739.
- ACC paper: ps file, pdf file