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

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)}$.

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_{*}$

<references />