a Rank Minimization Heuristic with Application to Minimum Order System Approximation: Difference between revisions

From statwiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 28: Line 28:
\mbox{subject to: } & X \in C
\mbox{subject to: } & X \in C
\end{array}
\end{array}
 
\mbox{where}
||X||_*=\sum_{i=1}^{\min{m,n} \sigma_i(X)}
</math>
</math>

Revision as of 21:33, 23 November 2010

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.

The Heuristic

This heurisitic minimizes the sum of the singular values of the matrix, i.e, the nuclear norm.

[math]\displaystyle{ \begin{array}{ l l } \mbox{minimize} & ||X||_* \\ \mbox{subject to: } & X \in C \end{array} \mbox{where} ||X||_*=\sum_{i=1}^{\min{m,n} \sigma_i(X)} }[/math]