a Rank Minimization Heuristic with Application to Minimum Order System Approximation

From statwiki
Revision as of 22:59, 23 November 2010 by Mderakhs (talk | contribs)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Rank Minimization Problem (RMP) has application in a variety of areas such as control, system identification, statistics and signal processing. Except in some special cases RMP is known to be computationaly hard. [math]\displaystyle{ \begin{array}{ l l } \mbox{minimize} & \mbox{Rank } X \\ \mbox{subject to: } & X \in C \end{array} }[/math]

If the matrix is symmetric and positive semidifinite, trace minimization is a very effective heuristic for rank minimization problem. The trace minimization results in a semidefinite problem which can be easily solved. [math]\displaystyle{ \begin{array}{ l l } \mbox{minimize} & \mbox{Tr } X \\ \mbox{subject to: } & X \in C \end{array} }[/math]

This paper focuses on the following problems:

  1. Describing a generalization of the trace heuristic for genaral non-square matrices.
  2. Showing that the new heuristic can be reduced to an SDP, and hence effictively solved.
  3. Applying the mothod on the minimum order system approximation.

A Generalization Of The Trace Heuristic

This heurisitic minimizes the sum of the singular values of the matrix [math]\displaystyle{ X\in \real^{m\times n} }[/math], which is the nuclear norm of [math]\displaystyle{ X }[/math] denoted by [math]\displaystyle{ |X|_* }[/math].

[math]\displaystyle{ \begin{array}{ l l } \mbox{minimize} & |X|_* \\ \mbox{subject to: } & X \in C \end{array} }[/math]

According to the definition of the nuclear norm we have [math]\displaystyle{ |X|_*=\sum_{i=1}^{\min\{m,n\} }\sigma_i(X) }[/math] where [math]\displaystyle{ \sigma_i(X) = \sqrt{\lambda_i (X^TX)} }[/math].

When the matrix variable [math]\displaystyle{ X }[/math] is symmetric and positive semidefinite, then its singular values are the same as its eigenvalues, and therefore the nuclear norm reduces to [math]\displaystyle{ \mbox{Tr } X }[/math], and that means the heuristic reduces to the trace minimization heuristic.

Nuclear Norm Minimization vs. Rank Minimization

Definition: Let [math]\displaystyle{ f:C \rightarrow\real }[/math] where [math]\displaystyle{ C\subseteq \real^n }[/math]. The convex envelope of [math]\displaystyle{ f }[/math] (on [math]\displaystyle{ C }[/math]) is defined as the largest convex function [math]\displaystyle{ g }[/math] such that [math]\displaystyle{ g(x)\leq f(x) }[/math] for all [math]\displaystyle{ x\in X }[/math]

convex envelope of a function (borrowed from Rank Minimization and Applications in System Theory


References

<references />