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

(→Minimum Order System Approximation) |
(→Minimum Order System Approximation) |
||

Line 115: | Line 115: | ||

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

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

## Revision as of 00:29, 24 November 2010

## Contents

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

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

** 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 />