- TITLE: Log-det heuristic for
matrix rank minimization with applications to Hankel and Euclidean
distance matrices
- AUTHORS: Maryam Fazel, Haitham Hindi, and Stephen P. Boyd
- ABSTRACT: We present a heuristic
for minimizing the rank of a positive semidefinite matrix over a
convex set. We use the logarithm of the determinant as a
smooth approximation for rank, and locally minimize this function
to obtain a sequence of trace minimization problems.
We then present a lemma that relates the rank of any general matrix
to that of a corresponding positive semidefinite one. Using this,
we readily extend the proposed heuristic to handle general matrices.
We examine the
vector case as a special case, where the heuristic reduces to
an iterative $\ell_1$-norm minimization technique.
As practical applications of the rank minimization problem
and our heuristic, we consider two examples:
minimum-order system realization with time-domain constraints, and
finding lowest-dimension embedding of points in a Euclidean space
from noisy distance data.
- STATUS: Proceedings American Control Conference,
pages 2156-2162, Denver, Colorado, June 2003.
- ACC paper: pdf file