# 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.

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

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.

$\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 a SDP, and hence effectively solved.
3. Applying the method on the minimum order system approximation.

### Nuclear Norm Heuristic: A Generalization Of The Trace Heuristic

This heuristic 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 the dual of the spectrial norm $\|X\|_* =\sup \{ \mbox{Tr } Y^T X | \|Y\| \leq 1 \}$ (with $\|Y\|$ representing the maximum singular value). 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.

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\|_*$.

Not that this implies that $\mbox{Rank } X \geq \frac{1}{M} \|X\|_*$. Particularly, 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 inequalities (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}$

where $Y=Y^T, Z=Z^T$ are new variables. If the constraint set $C$ can be expressed as linear matrix inequalities 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 rational matrix $H(s)$: $H(s) = R_0 +\sum_{i=1}^N \frac{R_i}{s-p_i}$ where $R_i \in C^{m\times n}$ and $p_i$ are the complex poles of the system with the property that for each complex $p_i$ its complex conjugate is also a pole, and whenever $p_i = p_j^*$ we have $R_i=R_j^*$.

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

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

$\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}$

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

<references />