a Rank Minimization Heuristic with Application to Minimum Order System Approximation
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.
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.
This paper<ref name="self">A rank minimization heuristic with application to minimum order system approximation, M. Fazel, H. Hindi, and S. Body</ref> focuses on the following problems:
- Describing a generalization of the trace heuristic for general non-square matrices.
- Showing that the new heuristic can be reduced to a SDP, and hence effectively solved.
- Applying the method to the minimum order system approximation problem.
Nuclear Norm Heuristic: A Generalization Of The Trace Heuristic
Solving the rank minimization problem using the trace norm heuristic is not possible when the matrix under consideration is non-symmetric, or non-square. In this case, the authors develop a new heuristic. This heuristic minimizes the sum of the singular values of the matrix [math]\displaystyle{ X \in \real^{m\times n} }[/math], which is known as the nuclear norm or Ky-Fan n-norm of [math]\displaystyle{ \,X }[/math] denoted by [math]\displaystyle{ \|X\|_* }[/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 singular values of [math]\displaystyle{ \,X }[/math]
The nuclear norm is the dual of the spectral norm [math]\displaystyle{ \|X\|_* =\sup \{ \mbox{Tr } Y^T X | \|Y\| \leq 1 \}, }[/math] where [math]\displaystyle{ \|Y\| }[/math] represents the spectral norm of [math]\displaystyle{ \,Y }[/math] defined as the maximum singular value of [math]\displaystyle{ \,Y }[/math]. So the relaxed version of the rank minimization problem is a convex optimization problem.It means that although the original problem is in general a difficult optimization problem,the dual spectral norm minimization problem is a convex optimization problem, and therefore (at least in principle) easily solved.
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], so the nuclear norm heuristic reduces to the trace minimization heuristic.
The authors suggest using the nuclear norm as a heuristic for solving the rank minimization problem because the nuclear norm is the convex envelope of the rank function on the set of matrices with norm less than one and thus the nuclear norm minimization problem can be seen as a relaxation of the rank minimization problem.
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_{\textrm{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].
Note 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] and by solving the nuclear norm minimization problem we obtain a lower bound on the optimal value of the rank minimization problem.
Expressing as an SDP Problem
To solve the nuclear norm minimization problem we can convert the problem into a SDP problem. We begin be transforming the problem into the following form
We can then use the following lemma to transform the constraints into 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{ \|X\|_*\leq t }[/math] if and only if there exists matrices [math]\displaystyle{ Y \in \real^{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]\succeq 0, \quad \mbox{Tr}(Y) + \mbox{Tr}(Z) \leq 2t
}[/math]
The nuclear norm minimization problem can now be expressed as
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 \Complex^{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 = \bar{p_j} }[/math] we have [math]\displaystyle{ R_i=\bar{R_j} }[/math].
We want to describe the system as simply as possible. 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 accuracy [math]\displaystyle{ \,\epsilon \gt 0 }[/math].
The matrices [math]\displaystyle{ \,G_k }[/math] are given as the measured approximation of [math]\displaystyle{ \,H(j\omega_k) }[/math].Note that [math]\displaystyle{ H(j\omega_k) }[/math] is a linear function of the variables [math]\displaystyle{ R_i }[/math].
Therefore we have the following minimization problem:
This optimization problem can be expressed as a SDP problem as discussed in the previous section.
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.
Solving the SDP representation of the problem discussed in the previous section ([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 />