# Difference between revisions of "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 computationaly hard. $\begin{array}{ l l } \mbox{minimize} & \mbox{Rank } X \\ \mbox{subject to: } & X \in C \end{array}$

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. $\begin{array}{ l l } \mbox{minimize} & \mbox{Tr } X \\ \mbox{subject to: } & X \in C \end{array}$

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 $X\in \real^{m\times n}$, which is the nuclear norm of $X$ denoted by $\|X\|_*$.

$\begin{array}{ l l } \mbox{minimize} & \|X\|_* \\ \mbox{subject to: } & X \in C \end{array}$

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

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

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

#### Nuclear Norm Minimization vs. Rank Minimization

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 $f:C \rightarrow\real$ where $C\subseteq \real^n$. The convex envelope of $f$ (on $C$) is defined as the largest convex function $g$ such that $g(x)\leq f(x)$ for all $x\in X$.

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

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

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

### 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 $X\in \real^{m\times n}$ and $t\in \real$, we have $R^{m\times m}$ and $Z\in \real^{n\times n}$ such that

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

Using this lemma the nuclear norm minimization problem

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

can be expressed as $\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}$

<references />