A Rank Minimization Heuristic with Application to Minimum Order System Approximation

Authors

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

Year

2001

Conference Paper

Source

Proceedings of the American Control Conference. (Cat. No.01CH37148)

Identifiers

DOI 10.1109/ACC.2001.945730

Abstract¶

We describe a generalization of the trace heuristic that applies to general nonsymmetric, 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 a semidefinite program, 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.

Summary¶

Generalizes the trace heuristic for rank minimization by replacing rank with the sum of singular values, now commonly called the nuclear norm. The paper motivates the relaxation as a convex envelope on a spectral-norm ball and reduces the resulting problem to semidefinite programming, with minimum-order system approximation as a motivating application.