# Difference between revisions of "a Rank Minimization Heuristic with Application to Minimum Order System Approximation"

Line 20: | Line 20: | ||

#Applying the mothod on the minimum order system approximation. | #Applying the mothod on the minimum order system approximation. | ||

− | === The Heuristic === | + | === A Generalization Of The Trace Heuristic === |

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

<math> | <math> | ||

\begin{array}{ l l } | \begin{array}{ l l } | ||

− | \mbox{minimize} & | + | \mbox{minimize} & |X|_* \\ |

\mbox{subject to: } & X \in C | \mbox{subject to: } & X \in C | ||

\end{array} | \end{array} | ||

− | |||

− | |||

</math> | </math> | ||

+ | |||

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

+ | |||

+ | When the matrix variable <math>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>\mbox{Tr } X</math>, and that means the heuristic reduces to the trace minimization heuristic. | ||

+ | |||

+ | ==== Nuclear Norm Minimization vs. Rank Minimization ==== | ||

+ | |||

+ | ''' Definition:''' Let <math>f:C \rightarrow\real</math> where <math>C\subseteq \real^n</math>. The convex envelope of <math>f</math> (on <math>C</math>) is defined as the largest convex function <math>g</math> such | ||

+ | that <math>g(x)\leq f(x)</math> for all <math>x\in X</math> | ||

+ | [[Image:Convex Envelope|thumb|100px|right|Convex Envelope of a function]] |

## Revision as of 21:47, 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] \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] \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.

### A Generalization Of The Trace Heuristic

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

[math] \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]|X|_*=\sum_{i=1}^{\min\{m,n\} }\sigma_i(X)[/math] where [math] \sigma_i(X) = \sqrt{\lambda_i (X^TX)}[/math].

When the matrix variable [math]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]\mbox{Tr } X[/math], and that means the heuristic reduces to the trace minimization heuristic.

#### Nuclear Norm Minimization vs. Rank Minimization

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