% formatted on 970304 by morris
\documentstyle{article}
\setcounter{page}{10}
\textheight 9.5in
\textwidth 5.75in
\voffset -1in
\hoffset -0.55in
\begin{document}

%\documentstyle[12pt]{llncs}


\def\R{{\bf R}}
\def\x{\times}
\def\pref#1{(\ref{#1})}
\def\tr{{\rm tr}}
\def\rank{{\rm rank}}
%\begin{document}

\title{The Numerical Solution of  Orthogonal Procrustes Problems }
\author{Lars Eld\'en \\
Department of Mathematics,
Link\"oping University\\
S-581 83 Link\"oping, Sweden\\
e-mail: laeld@math.liu.se\\}% {http://www.math.liu.se/~laeld/}}
\date{}
\maketitle
Let two matrices $ A \in \R^{ m \x m}$, and $ B
\in \R^{ m \x n}$ be given, where $m \geq n$.  We consider {\em
the orthogonal Procrustes problem} of finding a matrix $ Q \in R^{ m
\x n}$ that solves the minimization problem
%
\begin{equation}\label{eq:procr}
\min_{Q^T Q =I} \Vert  A Q -  B \Vert_F.
\end{equation}
%
We will refer to the case when $m=n$ as {\em balanced }
and the case $m > n$ as {\em unbalanced}.
Although there is a well understood theory for the
balanced case, see e.g. \cite{govl:89},
as well as an explicit formula for the solution,
we are  aware of  substantial results for the unbalanced case only 
 for  $n=1$, see e.g. \cite{gol:73,eld:77,gand:81}.

The function to be minimized \pref{eq:procr} can be written 
%
\begin{equation}\label{eq:tra}
{ \Vert AQ - B \Vert_F } ^2 = \tr ( B^T B) + \tr(Q^T A^T AQ)
-2 \tr( Q^T A^T B).
\end{equation}
%
The balanced case is simpler than
the unbalanced case due to the fact that when $m=n$ we have
%
\begin{equation}\label{eq:QA}
\tr(Q^T A^T A Q ) = \tr(A^T A),
\end{equation}
%
so that we are left with only one term to mimimize in \pref{eq:tra}, 
see \cite{govl:89}. The solution is $Q = U V^T$, where $A^T B = U
\Sigma V^T$ is the singular value decomposition. 

When $m > n$, \pref{eq:QA} does not hold, and we cannot simplify the
function to be minimized as in the case $m=n$. Moreover,  no
explicit formula for the solution is known. The problem of solving
\pref{eq:procr} can be considered as a minimization problem on the
Stiefel manifold \cite{eas:96}.

In this talk we consider the unbalanced Procrustes problem, and
derive results on the characterization of the solution.  We first
briefly review some results for the case $n=1$. 
Then, using Lagrange multipliers, we define two
matrix equations, the normal equations and the secular equation, which
any candidate for the solution of \pref{eq:procr} 
must satisfy.  
Necessary and sufficient conditions are given for a solution of the
normal and secular equations to be the solution of
\pref{eq:procr}. The analysis is partly based on results from \cite{eas:96}.
Finally we discuss some algorithms for computing the solution of the
problem. 


This is joint work with {Haesun Park}. 

\begin{thebibliography}{1}

\bibitem{eas:96}
A.~Edelman, T.~Arias, and S.~T. Smith.
\newblock Conjugate gradient on the {Stiefel} and {Grassman} manifolds.
\newblock Technical report, Department of Mathematics, MIT, Cambridge, MA
  02139, August 1996.

\bibitem{eld:77}
L.~Eld\'en.
\newblock Algorithms for the regularization of ill-conditioned least squares
  problems.
\newblock {\em BIT}, 17:134--145, 1977.

\bibitem{gand:81}
W.~Gander.
\newblock Least squares with a quadratic constraint.
\newblock {\em Numer. Math.}, 36:291--307, 1981.

\bibitem{gol:73}
G.~H. Golub.
\newblock Some modified eigenvalue problem.
\newblock {\em SIAM Review}, 15:318--344, 1973.

\bibitem{govl:89}
G.~H. Golub and C.~F. {Van Loan}.
\newblock {\em Matrix Computations. 2nd ed.}
\newblock Johns Hopkins Press, Baltimore, MD., 1989.

\end{thebibliography}



\end{document}

Lar Elden
