a Rank Minimization Heuristic with Application to Minimum Order System Approximation: Difference between revisions
No edit summary |
No edit summary |
||
Line 19: | Line 19: | ||
#Showing that the new heuristic can be reduced to an SDP, and hence effictively solved. | #Showing that the new heuristic can be reduced to an SDP, and hence effictively solved. | ||
#Applying the mothod on the minimum order system approximation. | #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> | |||
\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> |
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:
- Describing a generalization of the trace heuristic for genaral non-square matrices.
- Showing that the new heuristic can be reduced to an SDP, and hence effictively solved.
- 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]