• 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