a Rank Minimization Heuristic with Application to Minimum Order System Approximation

From statwiki
Jump to navigation Jump to search

Introduction

The Rank Minimization Problem (RMP) has applications in a variety of areas including control theory, system identification, statistics and signal processing. Except in some special cases the RMP is known to be computationally hard.

[math]\displaystyle{ \begin{array}{ l l } \mbox{minimize} & \mbox{Rank } X \\ \mbox{subject to: } & X \in C, \end{array} }[/math]

where [math]\displaystyle{ \, X \in \mathbb{R}^{m \times n} }[/math] is the decision variable and [math]\displaystyle{ \, C }[/math] is a convex set.

If the matrix is symmetric and positive semidefinite, trace minimization is a very effective heuristic for solving the rank minimization problem. Trace minimization results in a semidefinite programming problem which can be easily solved.

[math]\displaystyle{ \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:

  1. Describing a generalization of the trace heuristic for general non-square matrices.
  2. Showing that the new heuristic can be reduced to a SDP, and hence effectively solved.
  3. Applying the method to the minimum order system approximation problem.

Nuclear Norm Heuristic: A Generalization Of The Trace Heuristic

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

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

The nuclear norm is the dual of the spectrial norm [math]\displaystyle{ \|X\|_* =\sup \{ \mbox{Tr } Y^T X | \|Y\| \leq 1 \} }[/math] (with [math]\displaystyle{ \|Y\| }[/math] representing the maximum singular value). So the relaxed version of the rank minimization problem is a convex optimization problem.

When the matrix variable [math]\displaystyle{ 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]\displaystyle{ \mbox{Tr } X }[/math], 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 [math]\displaystyle{ f:C \rightarrow\real }[/math] where [math]\displaystyle{ C\subseteq \real^n }[/math]. The convex envelope of [math]\displaystyle{ f }[/math] (on [math]\displaystyle{ C }[/math]) is defined as the largest convex function [math]\displaystyle{ g }[/math] such that [math]\displaystyle{ g(x)\leq f(x) }[/math] for all [math]\displaystyle{ x\in X }[/math].

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


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

Not that this implies that [math]\displaystyle{ \mbox{Rank } X \geq \frac{1}{M} \|X\|_* }[/math]. Particularly, that means if [math]\displaystyle{ p_{\mbox{rank}} }[/math] and [math]\displaystyle{ p_{*} }[/math] are the optimal values of the rank minimization problem and dual spectrial norm minimization problem then we have [math]\displaystyle{ 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 inequalities (LMIs).

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

[math]\displaystyle{ \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]\displaystyle{ \begin{array}{ l l } \mbox{minimize} & t \\ \mbox{subject to: } & \|X\|_*\leq t\\ & X \in C \end{array} }[/math]

can be expressed as

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

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

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

[math]\displaystyle{ \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.

Numerical Example

Consider a MIMO system (i.e. multiple inputs and outputs); in particular, we will analyze one with 2 inputs and 2 outputs. We have a normalized transfer matrix [math]\displaystyle{ F }[/math] (i.e. [math]\displaystyle{ \|F\|_{\infty} = 1 }[/math]). Additionally, assume this matrix is of order 8 so that we have poles [math]\displaystyle{ p_1,\dots,p_8 }[/math] which come in pairs (i.e. complex conjugates). The goal is to reduce the order while minimizing the information lost.

Using the SDP representation mentioned above ([math]\displaystyle{ \epsilon = 0.05 }[/math]) gives an approximation of order 6. Additionally, the 8th order and 6th order representations are similar and are the same in many cases.

References

<references />