View source for a Rank Minimization Heuristic with Application to Minimum Order System Approximation

=== Introduction ===
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 computationally 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 semidefinite, 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 method on the minimum order system approximation.

=== Nuclear Norm Heuristic 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>.

The nuclear norm is dual of the spectrial norm 
<math>\|X\|_* =\sup \{ \mbox{Tr } Y^T X | \|Y\| \leq 1 \}</math>. So the relaxed version of the rank minimization problem is a convex optimization problem.

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.



[[Image:Convex Envelope.png|thumb|200px|right|convex envelope of a function, borrowed from <ref>Rank Minimization and Applications in System Theory, M. Fazel, H. Hindi, and S. Body</ref>]]
''' 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>.

'''Theorem 1''' The convex envelope of the function <math>\phi(X)=\mbox{Rank }(X)</math>, on <math>C=\{X\in \real^{m\times n} | \|X\|\leq 1\} </math> is <math>\phi_{\mbox{env}}(X) = \|X\|_*</math>.


Suppose <math>X\in C</math> is bounded by <math>M</math> that is <math>\|X\|\leq M</math>, then the convex envelope of <math>\mbox{Rank }X</math> on <math>\{X |  \|X\|\leq M\}</math> is given by <math>\frac{1}{M}\|X\|_*</math>. 

<math>\mbox{Rank } X \geq \frac{1}{M} \|X\|_*</math>
That means if <math>p_{\mbox{rank}}</math> and <math>p_{*}</math> are the optimal values of the rank minimization problem and dual spectrial norm minimization problem then we have
<math>p_{\mbox{rank}}\geq \frac{1}{M} p_{*}</math>

=== Expressing as an SDP ===

To express the relaxed version as a SDP we need to express the constraints by linear matrix inequalityes (LMIs). 

'''Lemma 1''' For <math>X\in \real^{m\times n}</math> and <math>t\in \real</math>, we have <math>R^{m\times m}</math> and <math>Z\in \real^{n\times n}</math> such that

<math>
\left[\begin{array}{cc}
Y & X\\
X^T & Z
\end{array}\right]\geq 0, \quad \mbox{Tr}(Y) + \mbox{Tr}(Z) \leq 2t
</math>


Using this lemma the nuclear norm minimization problem

<math>
\begin{array}{ l l }
\mbox{minimize} & t \\
\mbox{subject to: } & \|X\|_*\leq t\\
& X \in C
\end{array}
</math>

can be expressed as 

<math>
\begin{array}{ l l }
\mbox{minimize} & \mbox{Tr}(Y) + \mbox{Tr}(Z) \\
\mbox{subject to: } & \left[\begin{array}{cc}
Y & X\\
X^T & Z
\end{array}\right] \leq 0 \\
& X \in C
\end{array}
</math>

where <math>Y=Y^T, Z=Z^T</math> are new variables. If the constraint set <math>C</math> can be expressed as linear matrix inequalityes then the problem is an SDP, and can be solved using available SDP solvers.


== Minimum Order System Approximation ==

The rank minimization heuristic can be used in the minimum order system approximation problem.
In system theory, the effect of a system can be modeled using a ratioanl matrix <math>H(s)</math>:
<math> H(s) = R_0 +\sum_{i=1}^N \frac{R_i}{s-p_i}</math> where <math>R_i \in C^{m\times n}</math>  and <math>p_i</math> are the complex poles of the system with the property that for each complex <math>p_i</math> its  compelx conjucate is also a pole, and whenever <math>p_i = p_j^*</math> we have <math>R_i=R_j^*</math>.

We want the simpler description for the system. That is to say we are looking for <math>H</math> such that
<math>
\deg(H) = \sum_{i=1}^N \mbox{Rank}(R_i)
</math>
is minimized.

The transfer matrix is measured for a few frequencies, <math>\omega_1,\dots,\omega_K\in \real</math> with athe accuracy of <math>\epsilon</math>.
So the <math>G_k</math> are given as the measured approximation of <math>H(j\omega_k)</math>.
Therefore we have the following minimization problem:

<math>
\begin{array}{ l l }
\mbox{minimize} &\sum_{i=1}^N \mbox{Rank}(R_i) \\
\mbox{subject to: } & \|H(j\omega_k)-G_k\| \leq \epsilon, \quad k=1,\dots,K
\end{array}
</math>

This optimization problem can be expressed in SDP representation using above discussion.



===References===
<references />