next up previous contents index
Next: Trace Minimization Up: Sample Problems and Their Previous: The Procrustes Problem   Contents   Index


Nearest-Jordan Structure

Now suppose that the $B$ block in the Procrustes problem is allowed to vary with $Y$. Moreover, suppose that $B(Y)$ is in the nearest staircase form to $Y^*AY$; that is,

\begin{displaymath}B(Y) = \left[ \begin{array}{ccc}
\lambda_1 I & * & * \cr
0 & \lambda_2 I & * \cr
0 & 0 & \dots
\end{array}\right]\end{displaymath}

for fixed block sizes, where the *-elements are the corresponding matrix elements of $Y^*AY$ and the $\lambda_i I$ blocks are either fixed or determined by some heuristic, e.g., taking the average trace of the blocks they replace in $Y^*AY$. Then a minimization of $\vert\vert AY-YB(Y)\vert\vert _F$ finds the nearest matrix as a particular Jordan structure, where the structure is determined by the block sizes and the eigenvalues are $\lambda_i$. When the $\lambda_i$ are fixed, we call this the orbit problem, and when the $\lambda_i$ are selected by the heuristic given we call this the bundle problem.

Such a problem can be useful in regularizing the computation of Jordan structures of matrices with ill-conditioned eigenvalues.

The form of the differential of $F(Y)$, surprisingly, is the same as that of $F(Y)$ for the Procrustes problem

\begin{displaymath}dF(Y) = A^*(AY-YB(Y))-(AY-YB(Y))B(Y)^*.\end{displaymath}

This is because $\tr( -(AY-YB(Y))^*Y \dot{B} ) = \tr( (B(Y)-Y^*AY)^* \dot{B}) = 0$ for the $B$ selected as above for either the orbit or the bundle case, where $\dot{B} = \frac{d}{dt} B(Y(t)) \vert _{t=0}$.

In contrast, the form of the second derivatives is a bit more complicated, since $B$ now depends on $Y$:

\begin{displaymath}\frac{d}{dt} dF(Y(t))\vert _{t=0} =
\frac{d}{dt} dF_{Proc}(Y(...
...rt _{t=0}
-A^*Y\dot{B}-AY \dot{B}^*+YB \dot{B}^*+Y \dot{B} B^*,\end{displaymath}

where $\dot{Y}(0) = H$, $dF_{\rm Proc}$ is just short for the Procrustes ($B$ constant) part of the second derivative, and $\dot{B} = \frac{d}{dt} B(Y(t)) \vert _{t=0}$, which is the staircase part of $Y^*AH+H^*AY$ (with trace averages or zeros on the diagonal depending on whether bundle or orbit).


next up previous contents index
Next: Trace Minimization Up: Sample Problems and Their Previous: The Procrustes Problem   Contents   Index
Susan Blackford 2000-11-20