%======================= main.tex ===========================================
\documentclass{slides}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{alg}{Algorithm}
\newcommand\T{{\cal T}}
\newcommand\A{{\cal A}}
\newcommand{\E}{{\cal E}}
\newcommand{\Sc}{{\cal S}_C }
\newcommand{\Sn}{{\cal S}_n }
\newcommand{\snn}{{\cal S}_{n-1} }
\newcommand{\KK}{{\cal K} }
\newcommand{\QQ}{{\cal Q} }
\newcommand{\XX}{{\cal X} }
\newcommand{\OO}{{\Omega} }
\newcommand{\TT}{{\cal T} }
\newcommand{\Sh}{{\cal S}_H }
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\p}{{\cal P}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\trian}{{\rm trian\,}}
\newcommand{\Trian}{{\rm Trian\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\OoDiag}{{\rm O^0Diag\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\oodiag}{{\rm o^0diag\,}}
\newcommand{\ck}{{\cal C}_k}
\newcommand{\dk}{{\cal D}_k}
\newcommand{\uu}{{\cal U}}
\newcommand{\uk}{{\cal U}_k}
\newcommand{\vk}{{\cal V}_k}
\newcommand{\wk}{{\cal W}_k}
\newcommand{\wm}{{\cal W}_m}
\newcommand{\w}{{\cal W}}
\newcommand{\wks}{{\cal W}^s_k}
\newcommand{\wms}{{\cal W}^s_m}
\newcommand{\zk}{{\cal Z}_k}
\newcommand{\zks}{{\cal Z}^s_k}
\newcommand{\z}{{\cal Z}}
\newcommand{\n}{{\cal N}}
\newcommand{\ra}{{\cal R}}
\newcommand{\q}{{\cal Q}}
\newcommand{\s}{{\cal S}_n}
\newcommand{\m}{{\cal M}_{n}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\relint}{{\rm relint\,}}
\newcommand{\Z}{{\cal Z}}
\newcommand{\X}{{\cal X}}
\newcommand{\LL}{{\cal L} }
\newcommand{\hh}{ H^{(2)} }
\newcommand{\eij}{E_{ij} }
\newcommand{\eii}{E_{ii} }
\pagestyle{plain}
\begin{document}
%\blackandwhite{example}
%======================= example.tex
%  the file example.tex must exist - it is empty though
%======================= 
%======================= 
\begin{slide}{}
\begin{center}{\bf
EUCLIDEAN DISTANCE MATRIX COMPLETION PROBLEMS\\
{VIA} \\
SEMIDEFINITE PROGRAMMING
 }
\end{center}
 
~~\\
~~\\
~~\\
~~\\
~~\\
Henry Wolkowicz (University of Waterloo)\\
in collaboration with\\ Abdo Alfakih,  Amir Khandani,
Serge Kruk

\end{slide}
\begin{slide}{}

\begin{center}
Outline:

\end{center}
\begin{description}
\item[$\bullet$]
SDP model for EDM
\item[$\bullet$]
Primal-dual interior-point (p-d i-p) method for SDP
\item[$\bullet$]
Gauss-Newton (G-N) search direction
\item[$\bullet$]
Elimination techinique for G-N direction
\end{description}
\end{slide}
\begin{slide}{}
\begin{large}
\end{large}
~~\
~~\
~~\
~~\
~~\
\begin{center}
Semidefinite Programming\\
 looks just like\\
Linear Programming
\end{center}
\[ {\bf (PSDP)}
\begin{array}{cccc}
    p^*=  & \max &\tr CX & (\left< C,X \right>) \\
 &  \mbox{s.t.} & {\cal A}X = b & \mbox{(linear)}\\
  && X \succeq 0,~~(X \in \p)& \mbox{(nonneg)}
    \end{array}
\]
\end{slide}
\begin{slide}{}
$\preceq$ denotes the L{\"{o}}wner partial order\\
$A\preceq B$ if $B-A \succeq 0$\\

${\cal S}_n$ denotes  $n \times n$ symmetric matrices

\[ {\cal A} :{\cal S}_n \rightarrow \Re^m
\]
\[({\cal A}X)_i =\tr (A_iX),~
  \mbox{for given}~ A_i \in {\cal S}_n 
\]

$\p$ - 
cone of positive semidefinite matrices
\begin{center}
replaces
\end{center}
$\Re^n_+$ - nonnegative orthant

\end{slide}
\begin{slide}{}
{\bf What are EDMs?}

-----\\
A {\bf pre-distance matrix} (or dissimilarity matrix):\\
$\bullet$ an $n \times n$ symmetric
matrix $D=(d_{ij})$ with nonnegative elements and zero
diagonal

~~\\
~~\\
-----\\
A {\bf Euclidean distance matrix} (EDM):\\
$\bullet$ a pre-distance matrix such that there
exists points $x^1,x^2,\ldots,x^n$ in $\Re^r$ such that
\[
d_{ij} = {\| x^i- x^j\|}^2, ~~~ i,j=1,2,\ldots,n.
\]

~~\\
~~\\
-----\\
The smallest value of $r$ is called {\bf the embedding dimension} of
$D$.
($r$ is always $\leq n-1$)

\end{slide}
\begin{slide}{}
{\bf EDM problem:}\\
 Given a partial symmetric matrix $A$ with certain elements specified,
the Euclidean distance matrix completion problem
(EDMCP) consists in finding the unspecified elements
of $A$ that make $A$ a EDM. 

{\bf WHY?}\\
e.g.: \\
$\bullet$ 
The shape of an enzyme determines it chemical function. Once the
shape is known, then the proper drug can be designed.\\
~~\\
$\bullet$ 
distance geometry on molecules: atoms are points in space with pairwise
distances; find a set of points which yield those distances.
\end{slide}
\begin{slide}{}
For the approximate EDMCP,
let $A$ be a pre-distance matrix,
$H$ be an $n \times n$ symmetric  matrix with nonnegative elements, and
let $\|A\|_F= \sqrt{
     \trace A^tA}$ denote the {\em Frobenius norm} of $A.$ Consider
the objective function
\[ f(D) := {\| H \circ (A - D) \|}^2_F,   \]
where $\circ$ denotes {\em Hadamard product}.
~~\\
~~\\
{\bf weighted, closest Euclidean distance matrix problem}
\[
(CDM_0)
 \begin{array}{ccc}
          \mu^* := & \min   &   f(D)  \\
                  & \mbox{ subject to } & D \in {\cal E}, 
  \end{array}
\]
where $\cal E$ denotes the cone of EDMs.
\end{slide}
\begin{slide}{}
{\bf DISTANCE GEOMETRY}

A pre-distance matrix 
$D$ is a EDM if and only if $D$ is negative semidefinite on 
\[ M:=\left\{ x \in \Re^n : x^t e = 0 \right\},
\]
where $e$ is the vector of all ones.

Define $V$ $n \times (n-1),$ full column rank such that $V^te=0.$
Then
\[ \label{eq:Vmp}
J := V V^{\dagger}= I- \frac{e e^t}{n}
\]
is the orthogonal projection onto $M$,
where $V^{\dagger}$ denotes Moore-Penrose generalized inverse.

\end{slide}
\begin{slide}{}
Define the {\bf centered} and {\bf hollow} subspaces
\[ \begin{array}{rcl}
\Sc &:=&  \{ B \in \Sn :  Be = 0 \}, \\ 
\Sh& := & \{ D \in \Sn :  \diag(D) = 0 \}. 
\end{array}
\] 
Define the two linear operators
\[ \begin{array}{rcl} \label{KK} 
\KK(B)& := &  \mbox{diag}(B)\,e^t + e \, \mbox{diag}(B)^t - 2B,
\end{array} \] 
and
\[ \begin{array}{rcl} \label{T} 
\TT(D)& := &  -\frac 12 JDJ.
\end{array} \]
The operator $- 2 \TT$ is an orthogonal projection onto $\Sc.$ 

\begin{thm} \label{KT} 
The linear operators satisfy
\begin{eqnarray*}
\KK (  \Sc) = \Sh, \\
\TT (  \Sh) = \Sc, 
\end{eqnarray*} 
and $\KK_{|\Sc}$ and $\TT_{|\Sh}$ are inverses of each other.
\end{thm} 
\end{slide}
\begin{slide}{}

A hollow matrix $D$ is EDM \\
if and only if\\
 $B=\TT(D) \succeq 0$ (positive semidefinite)

$D$ is EDM\\
 if and only if\\
 $D=\KK(B),$ for some $B$ with $Be=0$ and $B \succeq 0$.   

In this case the embedding dimension $r$ is given
by the rank of $B$. Moreover if $B=XX^t$, then
the coordinates of the points  $x^1,x^2,\ldots,x^n$ that generate $D$ are
given by the rows of $X$ and, since $Be=0,$
it follows that the origin coincides with the  centroid
of these points.
\end{slide}
\begin{slide}{}

{\bf Difficulty}\\
The cone of EDMs, $\cal E$, has empty interior. This can cause problems
for interior-point methods.\\
-------------------------------

\[ V \cdot V^t : {\cal S}_{n-1}  \rightarrow {\cal S}_{n}  \quad (\mbox{into})
\]
\[ V \cdot V^t : {\cal P}_{n-1}  \rightarrow {\cal P}_{n}  
           \quad (\mbox{onto face})
\]

-------------------------------\\
Define the composite operators
\[ \begin{array}{rcl} \label{KV} 
\KK_V(X)& := &  \KK( V X V^t),
\end{array} \] 
and
\[ \begin{array}{rcl} \label{TV} 
\TT_V(D)& := &  V^{\dagger}\TT( D)(V^{\dagger})^t= 
                     - \frac 12 V^{\dagger} D (V^{\dagger})^t.
\end{array} \] 

\end{slide}
\begin{slide}{}


\begin{lem} \label{KVTV} 
\begin{eqnarray*} 
\KK_V ( \snn) =\Sh, \\
\TT_V ( \Sh) =\snn, 
\end{eqnarray*} 
and $\KK_V$ and $\TT_V$ are inverses of each other on these two spaces.
\end{lem}

\begin{cor} \label{co} 
\begin{eqnarray*} 
\KK_V(\p)  & = &  \E , \\
\TT_V(\E) & = &\p.
\end{eqnarray*} 
\end{cor}
\end{slide}
\begin{slide}{}

\begin{center}
Summary
\end{center}

(Re)Define the closest EDM problem:
\begin{eqnarray*}
 f(X) := {\| H \circ (A - \KK_V ( X)) \|}^2_F\\
          = {\| H \circ \KK_V(B - X) \|}^2_F, 
\end{eqnarray*}
where $B = \TT_V(A)$.\\
($\KK_V$ and $\TT_V$ are both linear operators)

{\bf
\[
(CDM)
 \begin{tabular}{ccc}
          $\mu^*$ := & $\min$   &   $f(X)$  \\
                  &  subject to  & $\A X=b $ \\ 
               &   &  $X \succeq 0.$
  \end{tabular}
\]
}

~\\

~\\
The additional constraint
using $\A : \snn \longrightarrow \Re^m$, 
could represent some of the fixed
elements in the given matrix $A$.
\end{slide}
\begin{slide}{}

{\bf Primal-Dual Interior-Point Framework:}

\begin{enumerate}
\item[Step 1]
derive a dual program

\item[Step 2]
state optimality conditions for log-barrier problem (perturbed
primal-dual optimality conditions)

\item[Step 3]
find a search direction for {\bf solv}ing the 
{\bf perturbed optimality conditions}

\item[Step 4]
take a step and backtrack to stay strictly feasible (positive definite)

\item[Step 5]
Update and go to Step 3
(adaptive update of log-barrier parameter)
\end{enumerate}

\end{slide}
\begin{slide}{}

{\bf Step 1.  derive a dual program:}

$\Lambda \in \snn, \Lambda \succeq 0$ and $y \in R^m$, \\
Lagrangian is
\[
L(X,y,\Lambda) = f(X) + \langle y, b - \A(X) \rangle - 
   \langle \Lambda, X  \rangle
\]

primal program (CDM) is
\[
       =  \min_{X} \max_{\stackrel{y}{\Lambda 
                    \succeq 0}}  L(X,y,\Lambda).   
\]

dual program is:
\[
         = \max_{\stackrel{y}{\Lambda \succeq 0}} \min_{X}  
          L(X,y,\Lambda),  
\]
\end{slide}
\begin{slide}{}

The inner minimization of the convex, in $X$, Lagrangian is unconstrained
so we add the hidden constraint which makes the minimization redundant.

dual program (DCDM)
\[
 \max_{\stackrel{\nabla f(X) - \A^*y=\Lambda}{\Lambda \succeq 0}}
                f(X) + \langle y, b - \A(X) \rangle - \mbox{trace} \Lambda X.
\]
or
\[
\begin{array}{cccc} 
 & & \max & f(X)+\langle y, b - \A(X) \rangle -
      \trace  \Lambda X \\  
       &           & \mbox{subject to} & \nabla f(X) - \A^*y- \Lambda = 0  \\
       &           &             &   \Lambda \succeq 0, (X \succeq 0).   
\end{array}  \]


\end{slide}
\begin{slide}{}

the duality gap,\\
 $  f(X)-\left(f(X)+\langle y, b - \A(X) \rangle - \trace  \Lambda X
           \right),$\\
in the case of primal and dual
feasibility, is given by the complementary slackness condition:
\[
\mbox{ trace } X (\KK^*_V( H^{(2)} \circ \KK_V( {X}-B))- \A^*{y}) = 0,
\]
or equivalently 
\[
 X (\KK^*_V( H^{(2)} \circ \KK_V( {X}-B))- \A^* {y}) = 0 ,
\]
where $H^{(2)}=H \circ H.$
\end{slide}
\begin{slide}{}


\begin{thm} \label{opt} 
Suppose that Slater's condition holds. Then
$\bar{X} \succeq 0$, and $\bar{y}$, $\bar{ \Lambda} 
      \succeq 0$ solve (CDM) and (DCDM),
respectively, if and only if the following three equations hold.
\[ \begin{array}{cc}
 \A (\bar{X}) = b  & \mbox{prim. feas.}  \\
  2\KK^*_V( H^{(2)} \circ \KK_V( \bar{X}-B)) - \A^* \bar{y} - 
                          \bar{\Lambda} =0 &
                                           \mbox{dual feas.}  \\
\trace \bar{ \Lambda} \bar{X}=0 & \mbox{C.S.}
\end{array} \]  
\end{thm}

--------------------------------------

\begin{lem}  
Let $H$ be an $n \times n$ symmetric matrix with nonnegative elements
and 0 diagonal such that the graph of $H$ is connected.  Then 
\[ \KK_V^*(H^{(2)} \circ \KK_V(I)) \succ 0 ,  \]
where $I \in \snn$ is the identity matrix.
\end{lem}  

--------------------------------------

i.e. when ${\cal A}=0,$ we have a {\bf Slater point}
(now assumed for what follows) for the dual (and
primal)



\end{slide}
\begin{slide}{}

{\bf Step 2.  
state optimality conditions for log-barrier problem (perturbed
primal-dual optimality conditions):}


equating $\Lambda = \mu X^{-1}$ and multiplying through by $X$

optimality conditions,
$F:=\left( \begin{array}{c} F_d \\ F_c  \end{array} \right)=0,$
\[ \begin{array}{llccl}
 F_d&:= 2 \KK^*_V\left(H^{(2)} \circ \KK_V(X)\right) - C
- \Lambda  &  \mbox{dual feas.} \\
 F_c&:= \Lambda X - \mu I  &  \mbox{pert. C.S.},
\end{array} \]
~~\\
~~\\
~~\\
~~\\
(an OVERDETERMINED nonlinear system since $\Lambda X$ not
symmetric)

estimate of the barrier parameter
\[  \mu = \frac{1}{n-1} \mbox{ trace }\Lambda X    \]


\end{slide}
\begin{slide}{}

$\sigma_k$ centering parameter \\
${\cal F}^0$ set of strictly feasible primal-dual
points\\
 $F^\prime$ derivative of $F$

\begin{alg}
 (p-d i-p framework:)\\
{\bf Given} $(X^0,\Lambda^0) \in {\cal F}^0$\\
{\bf for} $k=0,1,2 \ldots $\\
\hspace{.5in}{\bf solve} for the search direction\\
     \[
  ~~~~F^{\prime}(X^k,\Lambda^k)
\left(
\begin{array}{ccc}
\delta X^k \\  \delta \Lambda^k
\end{array}
\right)
= 
\left(
\begin{array}{ccc}
-F_d \\ -\Lambda^k X^k+ \sigma_k \mu_k I
\end{array}
\right)
\]
\hspace{.5in}where $\sigma_k$ centering, $\mu_k=\trace
X^k\Lambda^k/(n-1)$

\[ (X^{k+1},\Lambda^{k+1}) = (X^k,\Lambda^k) +
\alpha_k
(\delta X^k,    \delta \Lambda^k)
\]
\hspace{.5in}so that $(X^{k+1},\Lambda^{k+1}) \succ 0$\\
{\bf end (for)}.
\end{alg}




\end{slide}
\begin{slide}{}

{\bf Step 3.  
find a search direction for  solving the 
 perturbed optimality conditions:}

What is a good (local) search direction?\\
 What linear system should we
solve?\\
(Still an active area of research.)

We use the {\bf Gauss-Newton direction};
the (Frobenius norm) lss of
\[ F^{\prime} s = - F,\]
i.e.
\[ \begin{array}{rcll}
 2 \KK^*_V\left(H^{(2)} \circ \KK_V (h)\right) - l&=&-F_d    \\ 
  \Lambda h + l X&=&-F_c.
\end{array} \]

~~\\
Let
$t(n)=\frac {(n+1)n}2$ be dimension of $\Sn.$\\
$F^{\prime}$ maps $\Re^{2(t(n-1))}$ to $\Re^{t(n-1)+(n-1)^2}.$ 




\end{slide}
\begin{slide}{}
\begin{center}
Motivation
\end{center}
In numerical analysis, how do we
solve a nonlinear system of equations?

The standard approach is to solve the equivalent
 nonlinear least squares problem using
``Gauss-Newton'' method. 
\[  \min \frac 12 || F_{\mu} (X,y,Z) ||^2_2  \]
subject to $X,Z>0.$

~~\\
Advantages: obvious merit function; always descent direction; 
direction always exists; known convergence analysis.

\end{slide}
\begin{slide}{}
In the LP case (or symmetrized SDP case),
when we differentiate we get a square system and Gauss-Newton
reduces to Newton's method. (So G-N is always being used.)

i.e. solving
\[
\left( F_{\mu}^{\prime}\right)^t F_{\mu}^{\prime} (\Delta s)
   = - \left( F_{\mu}^{\prime}\right)^t F_{\mu}
\]
(where $F_{\mu}^{\prime}$ is the Jacobian)\\
 is equivalent to solving
\[
 F_{\mu}^{\prime} (\Delta s)
   = -  F_{\mu}
\]
for the search direction $\Delta s.$


\end{slide}
\begin{slide}{}
Complications in the SDP case:

Overdetermined system, i.e.
should we symmetrize $ZX$, e.g. $ZX+XZ$, many others ...

line search

\end{slide}
\begin{slide}{}
\begin{center}
SYMMETRIZATION
\end{center}
from log-barrier we get:\\
$X-\mu Z^{-1} =0$\\
with linearization:\\
$X + \Delta X - \mu \left(Z^{-1} - Z^{-1}\Delta ZZ^{-1} \right) = 0$

more linear version  - multiply by $Z$:\\
$ZX - \mu I=0$\\
with linearization:\\
$ZX  - \mu I +Z \Delta X + \Delta ZX = 0$

symmetrize:\\
$ZX+ZX - 2\mu I=0$\\
with linearization:\\
$ZX +ZX  - 2\mu I +Z \Delta X + \Delta XZ+ \Delta ZX  +X \Delta Z  = 0$

Others:\\
$Z^{1/2} XZ^{1/2} - \mu I=0$, etc...\\
$H_P(M):= \frac 12 \left( PMP^{-1} + (PMP^{-1})^t \right)$\\
$M=XZ$ and $P$ any nonsingular matrix

\end{slide}
\begin{slide}{}
AHO direction $XZ+ZX$:\\
 advantage: fast convergence and stability;\\
 disadvantage: solve Lyapunov equation when finding Newton direction

HRVW-KSH-M direction:
Heuristic; symmetrize $\Delta X$ after it is calculated:\\
advantages: fast convergence  and inexpensive
Newton direction, especially for max-cut problem!\\
disadvantage: stability

NT direction:  adaptive scaling\\
advantage: self-scaling, symmetry\\
disadvantage: expensive


\end{slide}
\begin{slide}{}

For a standard (linear) SDP,
{\bf finding the GN-direction} is
equivalent to solving the normal equations
\[
        \left((F_{\mu})^{\prime}\right)^*
       (F_{\mu})^{\prime}(\Delta s)=-
        \left((F_{\mu})^{\prime}\right)^*
       \left(F_{\mu}\right).
\]
which is equivalent to finding the least squares solution of the
overdetermined system
\[
       (F_{\mu})^{\prime}(\Delta s)=-
       \left(F_{\mu}\right).
\]
Or:
\[
 \left[
\begin{array}{ccc}
0 & -\A^* & I \\
-\A & 0 & 0 \\
Z \cdot & 0 &
\cdot X
\end{array}
\right]
\left( \begin{array}{c}
    \Delta X \\
    \Delta y \\
\Delta Z \\
            \end{array} \right)
=
\left( \begin{array}{c}
     -F_d\\
     -F_p\\
     -  F_c\\
            \end{array} \right).
\]

Use QR? Preconditioned CG?



\end{slide}
\begin{slide}{}

{\bf Basic Elimination}

Use block elimination and
\[
\Delta Z = \A^*(\Delta y) - F_d \]
to obtain the $(m+n^2)\times (t(n)+m)$ reduced \textit{dual feasible}
system
\[
  \left[
    \begin{array}{cc}
      -\A & 0 \\ Z \cdot & \A^* \cdot X
    \end{array}
    \right]
    \left[
      \begin{array}{c}
        \Delta X \\ \Delta y
      \end{array}
    \right] =
    \left[
      \begin{array}{c}
        -F_p \\ F_dX-F_c
      \end{array}
    \right].
\]



\end{slide}
\begin{slide}{}



write
\[
  \A = \left[ \A_B \A_N \right],
\]
$\A_B$ is a subset of size $m \times m$ of $\A$ that is
easily invertible. 

\[
  \Delta X_B = \A_B^{-1}F_p - \A_B^{-1}\A_N\Delta X_N,
\]
which we substitute back into the dual feasible system
 to obtain the $(n^2 \times t(n))$ system
\[
\begin{array}{c}
  \left[
    \begin{array}{cc}
    -Z_B\A_B^{-1}\A_N+Z_N & \A^* \cdot X
    \end{array}
  \right]
  \left[
    \begin{array}{c}
      \Delta X_N \\ \Delta y
    \end{array}
  \right] = 
  F_dX - F_c \\
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~      -  Z_B \A_B^{-1}F_p.
    \end{array}
\]



\end{slide}
\begin{slide}{}
{\bf Exploiting Special Structure}

Consider the
system of linear equations 
\[
Ax-By=c
\]

The vectors $x^*,y^*$ are (best) least squares solutions if
$x^*=A^{\dagger}(By^*+c),$ 
where
$A^{\dagger}$ is the Moore-Penrose inverse of $A$.

Therefore, we can eliminate $x$ and solve the
equivalent least squares problem with objective
\[ || (I-AA^{\dagger})(By+c)||^2_2  \]



\end{slide}
\begin{slide}{}

{\bf Adjoints? Generalized Inverses?}

Let
\[ \Z(\cdot) := Z \cdot
\]
and
\[ \X(\cdot) := \cdot X
\]
Then the adjoint operators are
\[ \Z^*(M) = \frac 12 \left(M^tZ+ZM\right)
\]
and
\[ \X^*(M)  = \frac 12 \left(XM^t+MX\right).
\]



\end{slide}
\begin{slide}{}

\[  \Z^*\Z(S) = \frac 12 \left(SZ^2+Z^2S\right)
\]
and
\[  \X^*\X(S)  = \frac 12 \left(X^2S+SX^2\right).
\]

Both $\Z^*\Z(S)$ and $\X^*\X(S)$ are nonsingular 
operators.

\[ \Z^{\dagger}(M)  = \frac 12 \left(M^tZ^{-1}+Z^{-1}M\right)
\]
and
\[ \X^{\dagger}(M) = \frac 12 \left(X^{-1}M^t+MX^{-1}\right)
\]


\end{slide}
\begin{slide}{}

The orthogonal projections are:

\[
\X \X^{\dagger}(M) = \frac 12 \left( X^{-1}M^tX +M \right)
\]
and
\[
\Z \Z^{\dagger} (M) =  \frac 12 \left( ZM^tZ^{-1} +M \right).
\]


\end{slide}
\begin{slide}{}
\begin{center}
 Concluding Remarks
\end{center}

$\bullet$
{\bf EDM:}
Typically, low rank solutions were obtained for problems where no
completion exists; (explanation using complementary slackness;)\\
purification to reduce rank.\\
~~\\
~~\\
$\bullet$
{\bf GN-direction:} always exists; full rank Jacobian at each iteration
and at solution; high accuracy in optimal solution; 
elimination approach work per iteration is competitive\\
($n=42,$ sec per iteration: 1000 cpu G-N $\rightarrow$ 200 cpu elimination).
~~\\
~~\\
$\bullet$
In progress:
more tests; better rank reduction techniques.
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\end{document}

