\documentclass[pdf,blends,slideColor,colorBG]{prosper}

\usepackage[latin1]{inputenc}
\usepackage{pstricks,pst-node,pst-text,pst-3d}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{graphicx}
% Definition of new colors
\newrgbcolor{mag}{0.6 0 0.6}
\newrgbcolor{dgreen}{0 0.5 0.5}
\newcommand{\X}{{\cal X}}
\newcommand{\diag}{{\rm diag\,}}
\def\SDP{\mbox{\boldmath$SDP\,$}}
\def\EDM{\mbox{\boldmath$EDM\,$}}
\def\EDMC{\mbox{\boldmath$EDMC\,$}}
\def\EDMCR{\mbox{\boldmath$EDMC-R\,$}}
\def\EDMCD{\mbox{\boldmath$EDMC-D\,$}}


\newcommand{\offDiag}{{\rm offDiag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\Ss}{{\mathcal S}}
\newcommand{\Sn}{{\mathcal S}^n }
\newcommand{\Snm}{{\mathcal S}^{n-1} }
\newcommand{\hn}{{\mathcal H}^n }
\newcommand{\D}{{\mathcal D_n} }
\newcommand{\E}{{\mathcal E_n} }
\newcommand{\Sd}{{\mathcal S}_d }
\newcommand{\Sc}{{\mathcal S}_C }
\newcommand{\Sh}{{\mathcal S}_H }
\newcommand{\snn}{{\mathcal S}_{n-1} }
\newcommand{\CC}{{\mathcal C} }
\newcommand{\KK}{{\mathcal K} }
\newcommand{\LL}{{\mathcal L} }
\newcommand{\NN}{{\mathcal N} }
\newcommand{\MM}{{\mathcal M} }
\newcommand{\Mn}{{\MM^n} }
\newcommand{\ZZ}{{\mathcal Z} }
\newcommand{\YY}{{\mathcal Y} }
\newcommand{\EE}{{\mathcal E} }
\newcommand{\FF}{{\mathcal F} }
\newcommand{\DD}{{\mathcal D} }
\newcommand{\BB}{{\mathcal B} }
\newcommand{\GG}{{\mathcal G} }
\newcommand{\II}{{\mathcal I} }
\newcommand{\RR}{{\mathcal R} }
\newcommand{\PP}{{\mathcal P} }
\newcommand{\TT}{{\mathcal T} }
\newcommand{\UU}{{\mathcal U} }
\newcommand{\A}{{\mathcal A} }
\newcommand{\p}{{\mathcal P} }
\newcommand{\n}{{\mathcal N} }
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\relint}{{\rm relint\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\cone}{{\rm cone\,}}
\newcommand{\sspan}{{\rm span\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\sblk}{{\rm sblk\,}}
\newcommand{\sBlk}{{\rm sBlk\,}}
\newcommand{\blk}{{\rm Blk\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\Mat}{{\rm Mat\,}}
\newcommand{\bpr}{{\bf Proof.} \hspace{1 em}}
\newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\newcommand{\epr}{\QED}

\newcommand{\ip}[2]{\left\langle #1, #2 \right\rangle}


\title{
Anchored Graph Realization and Sensor Localization
}
%\subtitle{at: Dalhousie University, Faculty of Computer Science, May/06}
\author{
{\red Nathan Krislock},
{\blue Veronica Piccialli}, 
{\red Jiawei  Qian},
and
\underline {\red Henry Wolkowicz}}
\institution{
{\blue University of Rome}
 and
%\blue University of Windsor and 
{\red University of Waterloo}}
%\email{\blue ???? and {\red hwolkowicz@uwaterloo.ca}}


\begin{document}
\maketitle


%---------------------------------------------------------------------- SLIDE -


%\overlays{2}{
\begin{slide}{Outline}
\tiny{
\begin{description} \blue
\item 
%$\bullet$
Problem Formulation, \EDMC
\item 
%$\bullet$
Matrix Reformulation, \EDMC \\
\quad -  Semidefinite Programming connection
\item 
%$\bullet$
SDP Relaxation of Hard Constraint $\bar Y =PP^T$
\item 
%$\bullet$
Facial Reduction - Reduced Problem Model
\item 
%$\bullet$
Adjoints/Duality for \EDMCR
\item 
%$\bullet$
Primal-Dual Bilinear Optimality Conditions (overdetermined)
\item 
%$\bullet$
{\red \bf Robust Interior-Point algorithm}\\
\quad - Gauss-Newton Direction, crossover, exact p-d feasibility,
preconditioning
\item
MATLAB demonstration
\item
Concluding Remarks
\end{description}
}
\end{slide}

\begin{slide}{Problem}
\blue
\begin{description} \blue
\item $\bullet$
Ad hoc wireless sensor network
\item $\bullet$
A few anchors (e.g. with GPS/bulky) have fixed, known locations
\item $\bullet$
sensors within a given range have
some known distance measurements (approximate)
\item $\bullet$
{\red Problem}: Determine positions of all sensors
\item $\bullet$
{\red Parameters}: Radio range, \# of anchors, noise level
\item $\bullet$
Semidefinite Relaxations/Robust Algorithm
\end{description}

\end{slide}


\begin{slide}{Problem Applications}
\blue
\begin{description} \blue
\item $\bullet$
health, military, home
\item $\bullet$
natural habitat monitoring, earthquake detection, weather/current
monitoring
\item $\bullet$
random deployment in inaccessible terrains or disaster relief operations
\item $\bullet$
{\red Future ?}: bicycles (prevent theft); guns; 
~~~~~~~ students/kids (prevent class absence :)  )
\end{description}
\end{slide}

%\overlays{2}{
\begin{slide}{Problem Example - with Radio Range}
\begin{figure}[htb]
\epsfxsize=210pt
\centerline{\epsfbox{plot4.eps}}
\caption{Connected Graph}
\end{figure}

\end{slide}

%\overlays{2}{
\begin{slide}{Problem Formulation}
\begin{description} \blue
\item $\bullet$
$\mag p^1,  \ldots, p^n \in \Re^r$ \quad unknown (sensor) points\\
$\mag a^1,  \ldots ,a^m \in \Re^r$ \quad known (anchor) points\\
$\mag r$ \quad embedding dimension (usually $\mag 2$ or $\mag 3$)
\item $\bullet$
$\mag A^T := [a^1, a^2, \ldots ,a^m]$\quad  
         $\mag X^T := [p^1, p^2, \ldots, p^n]$\\
\[
\mag P^T:= \left( p^1, p^2, \ldots, p^n, a^1, a^2, \ldots ,a^m \right) 
\]
$\mag P=  \begin{pmatrix}  X \\ A  \end{pmatrix}$
\quad rows are sensor/anchor points
\end{description}
\end{slide}




\begin{slide}{Assumption (avoids some trivialities)}
\begin{description} \blue
\item $\bullet$
The number of sensors and anchors, and the embedding dimension satisfy
\[
\mag n > m > r, ~ A^Te=0~ \mbox{\blue and }
\mag A \mbox{  \blue is full rank}.
\]

\end{description}
\end{slide}
%}



\begin{slide}{Definitions}
\blue
\begin{description} 
\item $\bullet$
 \underline{\black index sets} of existing values
of distances $\mag d_{ij}$ between pairs of sensors, $\mag \{p^i\}_1^n$:\\
\quad $\mag \NN_e$  distance values\\
\quad $\mag \NN_u$ upper bounds on distances \\
\quad $\mag  \NN_l$ lower bounds on distances\\

Similarly, the
 index sets $\mag \left(\MM_e, \MM_u, \MM_l\right)$  are for 
pairs $\mag \{p^i\}_1^n$ (sensors) to/from $\mag \{a^k\}_1^m$ (anchors)
\item $\bullet$
\underline{{\black partial}} EDM matrix $\mag E$ of 
\underline{\black squared} distances\\
$
\mag
E_{ij}:=  \left\{ \begin{array}{cl}
  d_{ij}^2  & \mbox{if    }~~ ij \in \NN_e \cup \MM_e  \\
  0       &   \mbox{otherwise}.
\end{array} \right.
$
\end{description}
\end{slide}



\begin{slide}{Definitions}
\blue
Similarly, we define 
\begin{description}
\item $\bullet$
the (partial) matrix of (squared distances) upper bounds\\
\quad  $\mag U$, using $\mag ij \in \NN_u \cup \MM_u$
\item $\bullet$
 and the (partial) matrix of (squared distances) lower bounds\\
 \quad $\mag L$, using $\mag ij \in \NN_l \cup \MM_l$

\end{description}
\end{slide}


\begin{slide}{Weighted Least Squares Error}
\blue
\begin{description}
\item
In the case $\mag E_{ij}$ have errors:\\
Let $\mag W_p, W_a$ be weight matrices.
We minimize the weighted least squares error.
(\EDMC)
\[
\mag
  \begin{array}{rcl}
    f_1(P) &:=&  \displaystyle\sum_{(i,j) \in
\mathcal{N}_e}(W_p)_{ij}(\|p^i-p^j\|^2 - E_{ij})^2 \\
              &&             + \displaystyle\sum_{(i,k) \in
\mathcal{M}_e}(W_a)_{ik}(\|p^i-a^k\|^2 - E_{ik})^2
\end{array}
\]
\end{description}
\end{slide}



\begin{slide}{HARD (nonconvex) Constrained LS}
\blue
\EDMC Problem:

\[
\mag
  \begin{array}{ll}
      \mbox{\blue min } &   f_1(P)    \quad  \mbox{\blue (weighted least squares)}\\
%\displaystyle\sum_{(i,j) \in
%\mathcal{N}_e}(W_p)_{ij}(\|p^i-p^j\|^2 - E_{ij})^2 \\
%                          & + \displaystyle\sum_{(i,k) \in
%\mathcal{M}_e}(W_a)_{ik}(\|p^i-a^k\|^2 - E_{ik})^2 \\
       \mbox{\blue s.t.} &\mag \|p^i-p^j\|^2 \leq U_{ij} ~~  \forall (i,j) \in \mathcal{N}_u ~~ \left(n_u=\frac {|\mathcal{N}_u|}{2} \right)\\
                          & \|p^i-a^k\|^2 \leq U_{ik} ~~  \forall (i,k) \in \mathcal{M}_u ~~ \left(m_u=\frac {|\mathcal{M}_u|}{2} \right)\\
                          & \|p^i-p^j\|^2 \geq L_{ij} ~~  \forall (i,j) \in \mathcal{N}_l ~~ \left(n_l=\frac {|\mathcal{N}_l|}{2} \right)\\
                          & \|p^i-a^k\|^2 \geq L_{ik} ~~  \forall (i,k) \in \mathcal{M}_l ~~ \left(m_l=\frac {|\mathcal{M}_l|}{2}\right)
  \end{array}
\]
\end{slide}


\begin{slide}{$\KK(\SDP)=\EDM$}
\blue
$\mag B=PP^T$ (\SDP).  $\mag B_{ii}=(p^i)^Tp^i$; $\mag B_{ij}=(p^i)^Tp^j$\\
 The squared distance
\[
\mag
\begin{array}{rcrclrcl}
D_{ij}
&=&
\|p^i-p^j\|^2  && \mbox{\blue (\EDM)}
\\&=&
(p^i)^Tp^i   &+& (p^j)^Tp^j  &-& 2(p^i)^Tp^j
\\&=&
 \updownarrow ~~~&&  ~~~\updownarrow  &&  \updownarrow 
\\&=&
 (\diag (B) e^T   &+&  e \diag(B)^T  &-& 2B)_{ij}
\\&=:&
\left(\KK(B)\right)_{ij}
\end{array}
\]
$\mag D=\KK(B)$ \quad change \EDM $\mag D$ $\mag \leftrightarrow$ \SDP $\mag B$
\end{slide}
%}



\begin{slide}{L\"owner Partial Order}
\blue
matrix inner-product \fbox{$\mag \left<M,N\right>=\trace M^TN$} and Frobenius
norm  \fbox{$\mag \|M\|^2 = \trace M^TM$}.\\
In $\mag \Sn$, $\mag n \times n$ symmetric matrices:
\[
\mag
\begin{array}{c}
B \succeq 0 \quad \mbox{\blue (is positive semidefinite)}
\\ \iff \\ 
\exists  P \mbox{ with } B=PP^T,~\rank (B)=\rank (P)
\end{array}
\]
the positive semidefinite (L\"owner) partial order is:
\[
\mag
A \succeq B ~(A \succ B) \mbox{ if } A- B \succeq 0~(A- B\succ 0)
\]

\end{slide}


\begin{slide}{Matrix Reformulation of \EDMC}
\blue
Let $\mag \bar Y:= PP^T = 
      \begin{pmatrix}
        XX^T & XA^T \\ AX^T &  AA^T
        \end{pmatrix}$ \\
 We get the equivalent \EDMC
\[
\mag
  \begin{array}{crcl}
      {\blue \min} &   f_2(\bar Y) :=  \frac{1}{2}{\| W \circ (\KK(\bar Y) - E) \|}_F^2 \\
\mbox{\blue subject to } & g_u(\bar Y) :=H_u \circ (\KK(\bar Y) - U) &\leq& 0 \\
                          & g_l(\bar Y) :=H_l \circ (\KK(\bar Y) - L) & \geq& 0\\
                  & 
                   \mbox{\blue hard constraint  }
             \fbox{$\bar Y-PP^T=0$} 
  \end{array}
\]

\end{slide}

\begin{slide}{SDP Relaxation of Hard Constraint}
\blue
\[
\mag
\begin{array}{lcl}
\bar Y=PP^T=\begin{pmatrix} XX^T & XA^T \\ AX^T  & 
\fbox{$AA^T$} \end{pmatrix} 
\quad \mbox{holds}
\\
\qquad \qquad \iff
\\
\qquad   \bar Y_{11}=XX^T \mbox{ and } \bar Y_{21} = AX^T, 
              \fbox{$\bar Y_{22} = AA^T$}.
\end{array}
\]
Relax $\mag \bar Y=PP^T$ to (L\"owner partial order) 
\[
\mag
\fbox{$\bar Y_{22}=AA^T$}\quad PP^T-\bar Y \preceq 0 \quad
\mbox{ \blue quadr convex constr}
\]
{\red (But .... why this relaxation?)} 

\end{slide}



\begin{slide}{Convex wrt L\"owner Partial Order}
\blue
The constraint
$ \mag g(P,Y)=PP^T -Y \preceq 0$ is $\mag \succeq$-convex, 
since each function
\[
\mag
\phi_Q(P,Y)=\trace Qg(P,Y)\quad
\mbox{is convex }  \forall Q\succeq 0.
\]
Note
\[
\mag
\begin{array}{rcl}
\trace QPP^T
&=&
\trace QPIP^T
\\&=&
\kvec(P)^T \left( I \otimes Q \right)
\kvec(P)
\end{array}
\]
Hessian is $\mag I \otimes Q \succeq 0$;\\
 and the cone {\mag \SDP} is self-polar.

\end{slide}



\begin{slide}{Linearization of SDP Relaxation}
\blue
$
\mag
\begin{array}{lcl}
PP^T-\bar Y \preceq 0, \qquad  
  P=  \begin{pmatrix}  X \\ A  \end{pmatrix}, \fbox{$\bar Y_{22}=AA^T$}
\\ \qquad \qquad \iff 
     \mbox{\blue  (by Schur complement)} \\
     Z = \begin{pmatrix} I & P^T \\
                 P & \bar Y \end{pmatrix} \succeq 0, \quad 
  P=  \begin{pmatrix}  X \\ A  \end{pmatrix}, \fbox{$\bar Y_{22}=AA^T$}
\\ \qquad \qquad \iff  \mbox{  \blue (ignore  } \bar \cdot {\blue )} \\
    Z = \begin{pmatrix} I & X^T &A^T \\
                  X & Y & Y_{21}^T \\
                  A &  Y_{21}& \fbox{$AA^T$}  \end{pmatrix} \succeq 0,
         \quad    
\left(\begin{array}{c}
\mbox{\blue NOT! } \succ 0 \\
\Rightarrow Y_{21} = AX^T
\end{array}\right)
\end{array}
$
\end{slide}



\begin{slide}{Facial Reduction}
\blue
\[
\mag
Z_s:=\begin{pmatrix}I & X^T \\ X & Y\end{pmatrix} \qquad
\begin{array}{lcl}
\mbox{ \blue (NE $2 \times 2$ block)}\\
\mbox{ \blue (Lin.Tr. but {\red \underline{NOT}} onto)}
\end{array}
\]
{\bf THEOREM:}
\[
\mag
\begin{array}{lcl}
    Z = \begin{pmatrix} I & X^T &A^T \\
                  X & Y & Y_{21}^T \\
                  A &  Y_{21}& \fbox{$AA^T$}  \end{pmatrix} \succeq 0
\\ \qquad \qquad \iff \\
     Z_s \succeq 0 \mbox{ and } Y_{21} = AX^T
\end{array}
\]
\end{slide}




\begin{slide}{Facial Reduction - Proof Outline}
\blue
(compact) singular value decomposition\\
$
\mag
\fbox{$A = U \Sigma V^T$}~~ U {m\times r}, V r\times r$\\

\[
\mag
    Z=Z_1 := \begin{pmatrix}
          I & X^T & V\Sigma U^T \cr
        X & Y & Y_{21}^T\cr
            U \Sigma V^T
        & Y_{21} & U \Sigma^2 U^T\end{pmatrix} \succeq 0
\]
 choose $\mag \bar U$ so that $\mag \begin{pmatrix}U&\bar U\end{pmatrix}$ 
is orthogonal;



\end{slide}






\begin{slide}{Facial Reduction - Proof Outline cont...}
\blue

Nonsingular congruence (apply Sylvester Lemma on inertia)
\[
\mag
\begin{array}{lll}
0\preceq Z_2:=T^TZT=\\
       =
    \begin{pmatrix}V^T & 0 & 0 \\ 0&I&0 \\ 0& 0 &
        \begin{pmatrix}U&\bar U\end{pmatrix}^T
                          \end{pmatrix}
      Z
      \begin{pmatrix}V & 0 & 0 \\ 0&I&0 \\ 0& 0 &
      \begin{pmatrix}U&\bar U \end{pmatrix}
                      \end{pmatrix}
\end{array}
\]



\end{slide}


\begin{slide}{Facial Reduction - Congruence cont...}
\blue
\[
\mag
= \begin{pmatrix}
          I & V^TX^T & 
            \begin{pmatrix} \Sigma & 0\end{pmatrix} \\
\vspace{.05in}
        XV & Y & 
                  \begin{pmatrix}Y_{21}^TU &Y_{21}^T \bar
                           U\end{pmatrix}\\
            \begin{pmatrix} \Sigma \cr 0\end{pmatrix} 
     & \begin{pmatrix}U^TY_{21}\\ \bar U^TY_{21}\end{pmatrix}
                        & \begin{pmatrix} \Sigma^2 & 0 \\ 0 & 0
                              \end{pmatrix}
\end{pmatrix}
\perp 
                        \begin{pmatrix} 0 & 0  
                               \\ 0  & \fbox{\tiny{$I$}}
                              \end{pmatrix}
\]
\[
\mag
\Rightarrow  Z \perp \left[T
                        \begin{pmatrix} 0 & 0  
                               \\ 0  & \fbox{\tiny{$I$}}
                              \end{pmatrix} T^T \right]
                     =  \begin{pmatrix} 
                                   0 & 0 & 0   \\
                                   0 & 0 & 0   \\
                                0  & 0& \fbox{$\bar U \bar U^T$}
                              \end{pmatrix} :=Q
\]
\end{slide}

\begin{slide}{Minimal and Conjugate Faces}
\blue
Conjugate face to feasible set $\mag \FF_Z$ is
\[
\mag
  \SDP \cap \left\{ \begin{pmatrix} 
                           0 & 0 & 0   \\
                          0 & 0 & 0   \\
                      0  & 0& \bar U \bar U^T
                              \end{pmatrix}  \right\} ^\perp
\]
Minimal face of \SDP containing $\mag \FF_Z=\cone \FF_Z$ is
\[
\mag
   \begin{pmatrix} 
                           I & 0 & 0   \\
                          0 & I & 0   \\
                      0  & 0& U 
                              \end{pmatrix} 
\Ss^{2r+n}_+
   \begin{pmatrix} 
                           I & 0 & 0   \\
                          0 & I & 0   \\
                      0  & 0& U 
                              \end{pmatrix}^T
\]
\end{slide}

\begin{slide}{Minimal Face}
\blue
 each given feasible
$
\mag
    Z = \begin{pmatrix} I & X^T &A^T \cr
                  X & Y & Y_{21}^T \cr
                  A &  Y_{21}& AA^T \end{pmatrix} \succeq 0,
$
can be expressed as (using $\mag A=U\Sigma V^T$)
\[
\mag
=\begin{pmatrix}
          I & 0 & 0  \cr
        0 & I & 0 \cr
            0 & 0 & U \end{pmatrix}
     \begin{pmatrix} I & X^T &V\Sigma \cr
                  X & Y & X V\Sigma \cr
                  \Sigma V^T &  \Sigma V^T X^T & \Sigma^2 \end{pmatrix} 
      \begin{pmatrix}
          I & 0 & 0  \cr
        0 & I & 0 \cr
            0 & 0 & U \end{pmatrix}^T
\]



\end{slide}

\begin{slide}{Matrix $\leftrightarrow$ Vector Notation I}
\blue
vector \fbox{$\mag v=\kvec V$} is matrix $\mag V$ taken columnwise\\
\fbox{
$
\mag
 \sblk_{21} \begin{pmatrix} 0 & X^T \\ X & 0
          \end{pmatrix}=
\sqrt{2} X
$}
pulls out the $\mag 21$ block - the $\mag \sqrt 2$ is for isometry in
Frobenius norm
\[
\mag
\begin{array}{c}
x:= \kvec\left( \sblk_{21} \begin{pmatrix} 0 & X^T \\ X & 0
          \end{pmatrix}\right)=
\sqrt{2} \kvec(X)\\
 \fbox{$ y:=\svec(Y)$} \quad (Y=Y^T, \mbox{ \blue isometry})
\end{array}
\]



\end{slide}

\begin{slide}{Matrix $\leftrightarrow$ Vector Notation II}
\blue

(adjoints: $\mag \sblk_{21}^*(X) =$) $\mag \sBlk_{21}(X)=
\frac 1{\sqrt 2}\begin{pmatrix} 0 & X^T \\ X & 0 \end{pmatrix}$\\
$\mag \svec^{-1} (\cdot) =\svec^* (\cdot) = \sMat (\cdot)$

\[
\mag
\begin{array}{rcl}
    {\ZZ}^x_s(x):=\sBlk_{21}(\Mat(x)), &
                    {\ZZ}^y_s(y):=\sBlk_2(\sMat(y))\\
       {\ZZ}_s(x,y):=\ZZ^x_s(x)+\ZZ^y_s(y),
                &
    Z_s  := \sBlk_1(I)+{\ZZ}_s(x,y) \\
\end{array}
\]
$
\mbox{\blue to build   } \quad
\red
\begin{array}{lcl}
     Z_s = \begin{pmatrix} I & X^T \\ X & Y
          \end{pmatrix}  \in \Ss^{r+n}
\end{array}
$


\end{slide}




\begin{slide}{Matrix $\leftrightarrow$ Vector Notation III}
\blue

\[
\mag
\begin{array}{rcl}
\YY^x(x)=\sBlk_{21}(A\Mat(x)^T),~
\YY^y(y)=\sBlk_1(\sMat(y))\\
\YY(x,y)= \YY^x(x)+ \YY^y(y),~ 
      \fbox{${\red \bar Y=\sBlk_2(AA^T)+\YY(x,y)}$}
\end{array}
\]
\[
\mag
\begin{array}{rcl}
\bar E:= W \circ \left[ E- \KK(\sBlk_2(AA^T))\right]\\
\bar U:=  H_u \circ \left[\KK(\sBlk_2(AA^T)) - U\right]\\
\bar L:= H_l\circ \left[L-\KK(\sBlk_2(AA^T))\right]
\end{array}
\]
The unknown matrix $\mag \bar Y$ is equal to
$\mag \YY(x,y)$ (with additional constant $\mag 2,2$ block), 
i.e. unknowns are the vectors $\mag x,y$.


\end{slide}




\begin{slide}{Equivalent Reduced Problem Model}
\blue

\mbox{(\EDMC{\boldmath$-R\,$})}
\[
\mag
  \begin{array}{crcl}
      \min  &  f_3(x,y) :=  \frac{1}{2}{\| W \circ (\KK(\YY(x,y))) - \bar E \|}_F^2 \\
  \mbox{s.t.} & g_u(x,y):=H_u \circ \KK(\YY(x,y)) - \bar U &\leq& 0 \\
                   & g_l(x,y):=\bar L -H_l \circ \KK(\YY(x,y))& \leq& 0 \\
                & \sBlk_1(I)+{\ZZ}_s(x,y)&\succeq& 0
  \end{array}
\]

(objective is $\mag \ell_2$ rather than $\mag \ell_1$ in the literature, e.g.
H. Jin(05), A. So, Y. Ye(05), 
P. Biswas, T. Liang, K. Toh, T. Wang, Y. Ye(06).)

\end{slide}



\begin{slide}{Problems with Relaxation}
\blue
\begin{enumerate}
\item
$
\mag
\{(\bar Y, P): \bar Y= PP^T \} \subset \{(\bar Y, P): \bar  PP^T-
            \bar Y \preceq 0 \}
$
{\red (But, is Lagrangian relaxation stronger?)}
\item
linearization (using Schur complement) results in a
constraint that is {\em NOT} onto, i.e.\\
{\red two relaxations {\em NOT} numerically equivalent}
\item
Least squares problem is (usually) {\red underdetermined}.
\end{enumerate}

\end{slide}



\begin{slide}{Lagrangian of \EDMCR}
\blue
\[
\mag
\begin{array}{lcl}
    L(x,y,\Lambda_u,\Lambda_l,\Lambda) =\\
      \quad \frac{1}{2}{\| W \circ \KK(\YY(x,y) - \bar E \|}_F^2   \\
      \qquad +\ip{\Lambda_u}{H_u \circ \KK(\YY(x,y))-\bar U}
  \\ \qquad\quad  +  \ip{\Lambda_l}{\bar L -H_l \circ \KK(\YY(x,y))}
     \\  \qquad\qquad - \ip{\Lambda}{\sBlk_1(I)+{\ZZ}_s(x,y)},
\end{array}
\]
where $\mag 0\leq \Lambda_u, 0\leq \Lambda_l \in \Ss^{m+n},$~~
$\mag 0\preceq \Lambda \in \Ss^{m+n}$
\[
\mag
\Lambda
=\begin{pmatrix}\Lambda_1 & \Lambda_{21}^T\\ \Lambda_{21} &
\Lambda_{2}\end{pmatrix}, \qquad
\ip{A}{B}=\trace A^TB.
\]

\end{slide}



\begin{slide}{Matrix $\leftrightarrow$ Vector Dual Variable Notation}
\blue
\[
\mag
\begin{array}{c}
                \lambda_u:=\svec(\Lambda_u), \quad
                      \lambda_l:=\svec(\Lambda_l), 
      \\ h_u:=\svec(H_u), \quad
                      h_l:=\svec(H_l),\\
\lambda:=\svec(\Lambda), \quad  \lambda_1:=\svec(\Lambda_1),
\\ \lambda_2:=\svec(\Lambda_2), \quad
 \lambda_{21}:=\kvec \sblk_{21}(\Lambda).
\end{array}
\]


\end{slide}



\begin{slide}{Adjoints}
\blue
To differentiate the Lagrangian, we need the adjoints of the various
linear transformations, e.g. part of $\KK$:
\[
\mag
\begin{array}{cclrcl}
 \DD_e(B) &=&  \diag (B)\,e^T + e \, \diag (B)^T \\ 
\DD^*_e(D)&=& 2 \Diag(De)\\
 \ip{\DD_e(B)}{D}
&=&
 \trace (\diag(B) e^T D + e \diag(B)^T D)  
\\&=&
 \trace ( De (\diag B )^T  + De (\diag B )^T)
\\&=&
 2\trace  \left(\diag B \right)^T(De)
\\&=&
\ip{B}{\DD^*_e(D)}, \forall  D,B
\end{array}
\]

\end{slide}



\begin{slide}{\underline{Primal}-Dual Optimal. Conditions 1}
\blue
{\bf THEOREM:}
The primal-dual variables
 $\mag x,y,\Lambda,\lambda_u,\lambda_l$ are optimal for \EDMCR if and only if:
\begin{description}
\item[1.] \underline{Primal Feasibility}:\\
The slack variables satisfy
$
\mag
\begin{array}{lcl} S_u  =  \bar U - H_u \circ \left(
\KK\left(\YY(x,y)\right)\right),~
          s_u=\svec S_u \geq 0 \\
  S_l  =  H_l \circ \left(\KK\left(\YY(x,y)\right)\right) -\bar L, ~~~
          s_l=\svec S_l \geq 0
\end{array}
$
and\\
$
\mag
\begin{array}{rcl}
\mag
    Z_s &=& \sBlk_1(I)+\sBlk_2\sMat (y)
           +\sBlk_{21}\Mat(x)
          \\&  \succeq &0
\end{array}
$

\end{description}



\end{slide}




\begin{slide}{Primal-\underline{Dual} Optimal. Conditions 2a}
\blue
\begin{description}
\item[2a.] \underline{Dual Feasibility}:\\
The stationarity equations ($\mag \Rightarrow$ exact p-d feas.)
$
\mag
\begin{array}{rcl}
(\ZZ_s^x)^*(\Lambda)
&=&
\lambda_{21}     \quad \mbox{\blue (eliminated)}
\\&=&
  \left[W\circ(\KK \YY^x)\right]^*
       \left( W \circ \KK(\YY(x,y)) - \bar E \right)
\\&&
     \quad  + \left[H_u\circ(\KK \YY^x)\right]^* (\Lambda_u)
\\&& 
\qquad  -\left[H_l\circ(\KK \YY^x)\right]^* (\Lambda_l)
\end{array}
$
$
\mag
\begin{array}{rcl}
(\ZZ_s^y)^*(\Lambda)
&=&
\lambda_{2}  \quad \mbox{\blue (eliminated)}
\\&=&
  \left[W\circ(\KK \YY^y)\right]^*
       \left( W \circ \KK(\YY(x,y)) - \bar E \right) 
\\&&  \quad + \left[H_u\circ(\KK \YY^y)\right]^* (\Lambda_u) 
 \\&& \qquad - \left[H_l\circ(\KK \YY^y)\right]^* (\Lambda_l)
\end{array}
$

\end{description}



\end{slide}



\begin{slide}{Primal-\underline{Dual} Optimal. Conditions 2b}
\blue
\begin{description}
\item[2b.] \underline{Dual Feasibility}:\\
Nonnegativity
$
\mag
\begin{array}{rcl}
  \Lambda &=&
     \sBlk_1\sMat(\lambda_1)+\sBlk_2\sMat(\lambda_2)
   \\&& \quad +\sBlk_{21}\Mat(\lambda_{21})
          \succeq 0; 
\end{array}
$
\[
\mag
\lambda_u\geq 0;\lambda_l\geq 0
\]
\[
\mag
  \Lambda = \Lambda(\lambda_1,x,y,\lambda_u,\lambda_l)
\qquad \mbox{\blue (from stationarity)}
\]

\end{description}



\end{slide}



\begin{slide}{Primal-Dual Optimal. Conditions 3 
    (\underline{C.S.})}
\blue
\begin{description}
\item[3.] \underline{Complementary Slackness}:\\
\[
\mag
\begin{array}{rcl}
    \lambda_u \circ s_u & = & 0 \\
    \lambda_l \circ s_l & = & 0 \\
    \Lambda Z_s & = & 0 \qquad \mbox{\blue (equivalently }
                          \trace \Lambda Z_s = 0 \mbox{\blue )}
\end{array}
\]


\end{description}

\end{slide}




\begin{slide}{Perturbed Compl. Slack. Conditions}
\blue
\[
\mag
\begin{array}{rcl}
F_\mu(x,y,\lambda_u,\lambda_l,\lambda_1):= \begin{pmatrix}
    \lambda_u \circ s_u  - \mu_u e\\
    \lambda_l \circ s_l  - \mu_l e \\
\fbox{\mbox{
    $\Lambda Z_s  -  \mu_c I $}}
                     \end{pmatrix} = 0,
\end{array}
\]
where $\mag s_u=s_u(x,y)$, $\mag s_l=s_l(x,y)$,
$\mag \Lambda=\Lambda(\lambda_1,x,y,\lambda_u,\lambda_l)$,  
$\mag Z_s=Z_s(x,y)$\\
an \fbox{overdetermined} bilinear system with
$\mag 
(m_u+n_u)+ (m_l+n_l)+(n+r)^2 \mbox{ equations}$
$\mag nr +t(n) + (m_u+n_u)+ (m_l+n_l)+t(r) \mbox{ variables}.
$

\end{slide}


\begin{slide}{Gauss-Newton Search Direction}
\blue
\[
\mag
    \Delta s := \left(\begin{array}{c}
        \Delta x \\\Delta y \\  \Delta \lambda_u \\ \Delta \lambda_l \\ \Delta \lambda_1
    \end{array}\right)
\]
\underline{overdetermined} linearized system is:
\[
\mag
F^\prime_\mu(\Delta s) \cong
F^\prime_\mu(x,y,\lambda_u,\lambda_l,\lambda_1) (\Delta s)
=-F_\mu(x,y,\lambda_u,\lambda_l,\lambda_1)
\]
 

\end{slide}



\begin{slide}{Notation - Compos. of Lin. Tr.}
\blue
\[
\mag
\begin{array}{rcl}
\KK^x_H (x)&:=& H\circ (\KK (\YY^x(x))),\\
\KK^y_H (y)&:=& H\circ (\KK (\YY^y(y))),\\
\KK_H (x,y)&:=& H\circ (\KK (\YY(x,y))).
\end{array}
\]


\end{slide}

\begin{slide}{GN: Three blocks of Equations}
\blue
1.
$
\mag
\lambda_u \circ \svec \KK_{H_u} (\Delta x,\Delta y) + s_u \circ
\Delta \lambda_u = \mu_u e - \lambda_u \circ s_u
$

2.
$
\mag
\lambda_l \circ \svec \KK_{H_l} (\Delta x,\Delta y) + s_l \circ
\Delta \lambda_l = \mu_l e - \lambda_l \circ s_l
$

3.
$
\mag
\begin{array}{lcl}
\Lambda \ZZ_s(\Delta x, \Delta
y)+
\left[
     \sBlk_1\left(\sMat(\Delta\lambda_1)\right)\right.
\\
~~+\left.\sBlk_2\left(
       \sMat\left\{(\KK_W^y)^*\KK_W(\Delta x,\Delta y)+\right.\right.\right.
   \\
     ~~~~\left.\left.\left.  (\KK^y_{H_u})^*\left(\sMat(\Delta\lambda_u)\right)
      -(\KK^y_{H_l})^*\left(\sMat(\Delta\lambda_l)\right)\right\}\right)\right.
\\
 ~~~~~~ \left.+\sBlk_{21}\left(\Mat\left\{(\KK_W^x)^*\KK_W(\Delta x,\Delta y)
\right.\right.\right.
\\
~~~~~~~~ 
    \left.\left.\left.+ 
    (\KK^x_{H_u})^*\left(\sMat(\Delta\lambda_u)\right)-(\KK^x_{H_l})^*\left(\sMat(\Delta\lambda_l)\right)\right\}\right)\right]Z_s
\\=
\mu_cI-\Lambda Z_s
\end{array}
$

\end{slide}


\begin{slide}{Initial Str. Feas. Start Heuristic}
\blue

If the graph is connected, we can use the stationarity equations and
get a strictly feasible primal-dual starting point and {\em \red maintain
exact numerical primal-dual feasibility} throughout the iterations.

\end{slide}



\begin{slide}{Diagonal Preconditioning}
\blue
Given $\mag A\in\MM^{m\times n}$, $\mag m\ge n$ full rank matrix;
and using condition number of $\mag K \succ 0$:
$\mag \omega(K)=\frac {\trace(K)/n}{\det(K)^{1/n}}$, 
the \underline{\red optimal diagonal scaling}
\[
\mag
\min_{D \succ 0}{\omega\left((AD)^T(AD)\right)}, \quad
D^*=\Diag(1/\|A_{:,i}\|)
\]
\small{(cite Dennis-W.)}
Therefore, need to evaluate columns of 
$\mag F_\mu^\prime(\cdot)$ (can be done explicitly/efficiently)


~~\\
---------------------------------\\
(Partial block Cholesky precondioning)


\end{slide}


\begin{slide}{dens: W .75,L .8;\\ n 15, m 5, r 2}
\blue
\tiny{
\begin{table}[htbp]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline
nf & optvalue & relaxation & cond.number & sv($\ZZ_s$) & sv($F^\prime_\mu$) \\
\hline 0.0000e+000 & 3.9909e-009 & 1.1248e-005 & 3.8547e+006 &  15
&  19 \\ \hline 5.0000e-002 & 7.5156e-004 & 4.4637e-002 &
1.0244e+011 &   6 &  27 \\ \hline 1.0000e-001 & 3.7103e-003 &
1.1286e-001 & 1.9989e+010 &   5 &  25 \\ \hline 1.5000e-001 &
6.2623e-003 & 1.3125e-001 & 1.0065e+010 &   6 &  14 \\ \hline
2.0000e-001 & 1.3735e-002 & 1.3073e-001 & 6.8833e+009 &   7 &  12
\\ \hline 2.5000e-001 & 2.3426e-002 & 2.4828e-001 & 2.4823e+010 &
8 &   6 \\ \hline 3.0000e-001 & 6.0509e-002 & 2.3677e-001 &
3.4795e+010 &   7 &   7 \\ \hline 3.5000e-001 & 5.5367e-002 &
3.7260e-001 & 2.3340e+008 &   6 &   4 \\ \hline 4.0000e-001 &
7.6703e-002 & 3.6343e-001 & 8.9745e+010 &   8 &   3 \\ \hline
4.5000e-001 & 1.2493e-001 & 6.9625e-001 & 3.2590e+010 &   6 &   9
\\ \hline 5.0000e-001 & 1.3913e-001 & 3.9052e-001 & 2.2870e+005 &
8 &   0 \\ \hline 5.5000e-001 & 8.8552e-002 & 3.8742e-001 &
5.8879e+007 &   8 &   2 \\ \hline 6.0000e-001 & 4.2425e-001 &
4.1399e-001 & 4.9251e+012 &   8 &   4 \\ 
 \hline
\end{tabular}
\end{table}
}

\end{slide}


\begin{slide}{dens: W .75,L .8;\\ n 15, m 5, r 2}
\blue
\tiny{
\begin{table}[htbp]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline
nf & optvalue & relaxation & cond.number & sv($\ZZ_s$) & sv($F^\prime_\mu$) \\
\hline 0.0000e+000 & 3.9909e-009 & 1.1248e-005 & 3.8547e+006 &  15
&  19 \\ 
\hline 5.0000e-002 & 7.5156e-004 & 4.4637e-002 &
1.0244e+011 &   6 &  27 \\ 
\hline 5.5000e-001 & 8.8552e-002 & 3.8742e-001 &
5.8879e+007 &   8 &   2 \\ \hline 6.0000e-001 & 4.2425e-001 &
4.1399e-001 & 4.9251e+012 &   8 &   4 \\ \hline 6.5000e-001 &
2.0414e-001 & 6.6054e-001 & 2.4221e+010 &   7 &   4 \\ \hline
7.0000e-001 & 1.2028e-001 & 3.4328e-001 & 1.9402e+010 &   7 &   6
\\ \hline 7.5000e-001 & 2.6590e-001 & 7.9316e-001 & 1.3643e+011 &
7 &   4 \\ \hline 8.0000e-001 & 4.7155e-001 & 3.7822e-001 &
6.6910e+009 &   8 &   2 \\ \hline 8.5000e-001 & 1.8951e-001 &
5.8652e-001 & 1.4185e+011 &   6 &   7 \\ \hline 9.0000e-001 &
2.1741e-001 & 9.8757e-001 & 2.9077e+005 &   8 &   0 \\ \hline
9.5000e-001 & 4.4698e-001 & 4.6648e-001 & 2.7013e+006 &   9 &   2
\\ \hline
\end{tabular}
\caption{Robust Algorithm for Ill-posed Problem}
\end{table}
}

\end{slide}



\end{document}
