A rank minimization heuristic with application to minimum order system approximation

TLDR

The trace heuristic, traditionally limited to positive semidefinite matrices, is extended to general nonsymmetric and non‑square matrices. The paper aims to generalize the trace heuristic to these broader matrix classes. This is achieved by replacing the rank objective with the sum of singular values, the dual of the spectral norm, which is shown to be the convex envelope of rank on matrices with norm ≤1. The resulting problem is a semidefinite program that can be solved efficiently, and the method is validated on minimum‑order system approximation.

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.