%\documentclass{slides}
\documentclass[landscape]{seminar}
\usepackage{amssymb}
\usepackage{latexsym}
\input epsf
\usepackage{psfig}
\pagestyle{plain}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{alg}{Algorithm}
\newcommand{\cone}{{\rm cone\,}}
\newcommand{\NN}{{\mathcal N} }
\newcommand{\RR}{{\mathcal R} }
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\sn}{{\cal S}^n }
\newcommand{\Sn}{{\cal S}^n }
\newcommand{\hn}{{\cal H}^n }
\newcommand{\p}{{\cal P} }
\newcommand{\g}{{\cal G} }
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\Se}{{\mathcal S}_e }
\newcommand{\Sd}{{\mathcal S}_d }
\newcommand{\Sc}{{\mathcal S}_C }
\newcommand{\Sh}{{\mathcal S}_H }
\newcommand{\snn}{{\mathcal S}_{n-1} }
\newcommand{\GG}{{\mathcal G} }
\newcommand{\KK}{{\mathcal K} }
\newcommand{\DD}{{\mathcal D} }
\newcommand{\BB}{{\mathcal B} }
\newcommand{\PP}{{\mathcal P} }
\newcommand{\TT}{{\mathcal T} }
\newcommand{\FF}{{\mathcal F} }
\newcommand{\EE}{{\mathcal E} }
\newcommand\T{{\mathcal T}}
\newcommand{\bt}{ \begin{tabular} }
\newcommand{\et}{ \end{tabular} }
\newcommand\A{{\mathcal A}}
\newcommand\E{{\mathcal E}}
\newcommand{\bpr}{{\bf Proof.} \hspace{1 em}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
%\newcommand{\epr}{\\ \hspace*{4.5in}  $\Box$}
\newcommand{\QED}{\hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\newcommand{\epr}{\QED}
\begin{document}
%\bibliographystyle{plain}
\begin{slide}{}
\mbox{
\begin{figure}
\psfig{file=an01logo.ps,height=15mm}
\end{figure}
}

\begin{center}
{\bf Semidefinite Programming
 and Matrix Completions}
\end{center}

\vspace{2mm}

{
Henry Wolkowicz \\
 }

\vspace{2mm}

Department of Combinatorics \& Optimization \\
University of Waterloo

\vspace{2mm}

\mbox{
\begin{figure}
\psfig{file=UWlogori.ps,height=20mm}
\end{figure}
}




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


\begin{center}OUTLINE
\end{center}

\begin{enumerate}
\item
Short intro. to SDP
\item
SDP and positive definite matrix completions
\item
Euclidean distance matrix (EDM) completions
\item
New characterization for EDM;\\
solving large sparse problems
\end{enumerate}

(Advantages of using $X-\mu Z^{-1}=0$ form of perturbed complementary
slackness.)




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



\begin{center}SDP  BACKGROUND and NOTATION
\end{center}

~~\\
\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

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

adjoint operator,~~ ${\cal A}^*y= \sum_i y_i A_i $
\[
\left<{\cal A}^*y,X \right>= \left<y,{\cal A}X \right>, ~~~ \forall X,y
\]

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

payoff function, player $Y$ to player $X$ (Lagrangian)
\[ L(X,y) :=  \tr (CX) +y^t(b-{\cal A}X)
\]
\[p^* = 
       \max_{X \succeq 0 } \min_{y }  L(X,y) 
\leq d^*:=\min_y \max_{X \succeq 0} L(X,y) 
\]
dual obtained from optimal strategy of competing player
Y;\\
use {\em hidden constraint} $C-{\cal A}^*y \preceq 0$
\[ {\bf (DSDP)}
\begin{array}{ccc}
    d^*=& \min &b^ty \\
 &  \mbox{s.t.} & {\cal A}^*y \succeq  C \\
    \end{array}
\]

for the primal
\[ {\bf (PSDP)}
\begin{array}{ccc}
    p^*=  & \max &\tr CX \\
 &  \mbox{s.t.} & {\cal A}X = b\\
  && X \succeq 0
    \end{array}
\]
\end{slide}
\begin{slide}{}
Characterization of optimality for the\\
   dual pair $X,y$~~(slack $Z\succeq 0$)
 \[ 
\begin{array}{cc} 
    {\cal A}^*y -Z = C  & \mbox{dual feasibility}\\
    AX = b & \mbox{primal feasibility}\\
    ZX  = 0 & \mbox{complementary slackness}
\end{array}
\]
\[
    ZX = \mu I ~~~~~ \mbox{perturbed}
\]

Forms the basis for:\\ ~~\\
interior point methods\\
(primal simplex method,
dual simplex method)
\end{slide}
\begin{slide}{}

\begin{center}
{\bf Positive Definite Completions\\
of\\
Partial Hermitian Matrices}
\end{center}
\begin{description}
\item[~~$\bullet$]
$\GG(V,E)$ finite undirected graph
\item[~~$\bullet$]
$A(\GG)$ is a $\GG$-partial matrix
($a_{ij}$ defined iff $\{i,j\} \in E$)
\item[~~$\bullet$]
$A(\GG)$ is a $\GG$-partial positive matrix if
$a_{ij}=\overline{a_{ji}}, \forall \{i,j\} \in E$ and all existing
principal minors are positive.
\item[~~$\bullet$]
with ${\mathcal J}=(V,\bar{E}), E \subset \bar{E}$ a 
$\mathcal J$-partial matrix
$B({\mathcal J})$ extends the $\GG$-partial matrix $A(\GG)$ if
$b_{ij}=a_{ij}, \forall \{i,j\} \in E$
\item[~~$\bullet$]
$\GG$ is positive
completable if every $\GG$-partial positive matrix can be
extended to a positive definite matrix.
\end{description}

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

$\GG$ is {\bf chordal} if there are no minimal cycles of length $\geq
4$. (every cycle of length $\geq 4$ has a chord)

{\bf THEOREM}
(Grone, Johnson, Sa, Wolkowicz)\\
$\GG$ is positive completable iff $\GG$ is chordal.
\epr
~~\\
~~\\
equivalently - strict feasibility for SDP:\\
\[\begin{array}{cl}
\trace E_{ij}P=a_{ij}, & \forall \{i,j\} \in E\\
P \succ 0
\end{array}\]
~~\\
where $E_{ij}=e_ie_j^t+e_je_k^t$

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

\begin{center}
{\bf Approximate Positive Semidefinite Completions}
\end{center}
\begin{flushright}
\small{
(with Charlie Johnson\\
 and Brenda Kroschel)
}
\end{flushright}

given:\\
~~\\
 $H=H^t \geq 0$ a real, nonnegative (elementwise) {\bf symmetric
matrix of weights},
 with positive diagonal elements $ H_{ii} > 0,~ \forall i$;\\
and $A=A^*$ the {\bf given partial Hermitian matrix}
~~\\
(i.e. some elements approximately fixed; 
others free; for notational purposes, assume
free elements set to 0 if not specified.)

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


$||A||_F = \sqrt{ \tr A^*A}$
{\em Frobenius norm},
$\circ$ denotes {\em Hadamard product}.\\
\[ \begin{array}{cc}
  f(P):=||H \circ (A-P) ||_F^2 
\end{array}
\]
~~\\
~~\\
{\bf weighted, best approximate,\\ completion problem}
\[
(AC)~~
\begin{array}{ccc}
       \mu^*:=&\min &f(P) \\
 &  \mbox{~subject to~} & KP=b\\
  &  &  P \succeq 0,
    \end{array}
\]
where $K: \hn \rightarrow {\cal C}^m$ linear operator




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


Lagrangian:
\[
L(P,y,\Lambda) = f(P)  + \left<y,b-KP\right> - \tr \Lambda P
\]
~~\\
Dual problem:
 \[
(DAC)
\begin{array}{ccc}
       \max &f(P) +\left<y,b-KP\right>- \tr \Lambda P \\
   \mbox{~subject to~} &  \nabla f(P)  -K^*y- \Lambda =  0\\
          &       \Lambda \succeq 0.
    \end{array}
\]

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

{\bf THEOREM} \label{thm:optcond}
The matrix $\bar{P}\succeq 0$ and vector-matrix
$\bar{y},\bar{\Lambda} \succeq 0$ solve AC and DAC if and only if
\[
\begin{array}{cc}
 K\bar{P}  = b & \mbox{primal feas.}\\
 2H^{(2)} \circ (\bar{P}-A)-K^*\bar{y}
  -\bar{\Lambda} =  0 & \mbox{dual feas.}\\
\tr \bar{\Lambda} \bar{P} = 0 & \mbox{compl. slack.}\\
\end{array}
\]
\epr


\end{slide}
\begin{slide}{}
For simplicity and sparsity, discard linear operator $K$ and replace 
with appropriate weights in $H$.

Use ({\em square}) perturbed optimality conditions.
\[
\begin{array}{cc}
 2H^{(2)} \circ (P-A) -\Lambda =  0 & \mbox{dual
feasibility}\\
-P + \mu \Lambda^{-1}  = 0 & \mbox{perturbed C.S.}\\
\end{array}
\]

Linearization of second equation\\
and solve for $h$ and $l$

\[
h= \mu \Lambda^{-1} - \mu \Lambda^{-1} l \Lambda^{-1}-P
\]
\[
l= \frac 1{\mu}\left\{
     - \Lambda (P+h) \Lambda
 \right\}+\Lambda
\]



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

Dual Step First:\\
(if many elements of $P$ are free)

We can eliminate the primal step $h$ and solve for the dual
step $l$.
\[
\begin{array}{ccl}
l & = &  2 H^{(2)} \circ h + \left( 2H^{(2)} \circ (P-A)
-\Lambda  \right)  \\
  & = &  2 H^{(2)} \circ  \left(\mu \Lambda^{-1} - 
 \mu \Lambda^{-1} l \Lambda^{-1}  -P \right) \\
   &&  ~~~~~~~  + ( 2H^{(2)} \circ (P-A) -\Lambda).
\end{array}
\]
Equivalently, we get the Newton equation
\[
\begin{array}{ccl}
 2 H^{(2)} \circ (\mu \Lambda^{-1} l \Lambda^{-1}  ) + l =
 2 H^{(2)} \circ (\mu \Lambda^{-1} -A  ) -\Lambda.
\end{array}
\]

$l,\Lambda$ have same sparsity pattern as $H$,\\
order is number of nonzeros/2 in $H$.



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


\begin{flushleft}
\begin{tiny}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}\hline
 dim& toler&$H$dens./infty&
           $A$psd &cond(A)&$H$pd&min/max&iters\\ \hline
  60   & $10^{-6}$& .01/.001  & yes & 79.7& no & 15/23 & 16.8  \\
 65   & $10^{-6}$& .015/.001  & yes & 49.9& yes & 18/24 & 21.3  \\
 83   & $10^{-6}$& .007/.001  & no & 235.1 & no & 24/29 & 25.5 \\
 85   & $10^{-5}$& .008/.001  & yes & 94.7 & no & 11/17 & 13.1 \\
 85   & $10^{-6}$& .0075/.001  & no & 299.9 & no & 23/27 & 25.2 \\
 87   & $10^{-6}$& .006/.001  & yes & 74.2 & yes & 14/19 & 16.9 \\
 89   & $10^{-6}$& .006/.001  & no & 179.3 & no & 23/28 & 15.2 \\
110   & $10^{-6}$& .007/.001  & yes & 172.3& yes & 15/20 & 17.8  \\
155   & $10^{-6}$& .01/0  & yes &643.9& yes & 14/18 & 15.3  \\
655   & $10^{-6}$& .017/0  & yes &1.4& no & 14/14 & 14.  \\
755   & $10^{-6}$& .002/0  & yes &1.5& no & 15/15 & 15.  \\
\hline
\end{tabular}
~~\\
data for dual-step-first (20 problems per test for $n \leq 155$; one otherwise): \\
dimension;  tolerance for duality gap;\\
 density of nonzeros in $H$/ density of infinite values in $H$;\\
positive semidefiniteness of $A$; condition number of $A$; 
positive definiteness of $H$;\\
(only one test for: 655,755)
\end{tiny}
\end{flushleft}

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

\begin{center}
{\bf Euclidean Distance Matrix Completion Problem}
\end{center}

\begin{flushright}
\small{
(with Abdo Alfakih)
}
\end{flushright}

{\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 (squared) {\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 approximate EDMCP:\\
$A$ is a pre-distance matrix,
$H$ is an $n \times n$ symmetric  weight matrix,
\[ f(D) := {\| H \circ (A - D) \|}^2_F,   \]
\[
(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 {\em 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.

\end{slide}
\begin{slide}{}
Define {\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 two linear operators
\[ \begin{array}{rcl} \label{KK} 
\KK(B)& := &  \mbox{diag}(B)\,e^t + e \, \mbox{diag}(B)^t - 2B,
\end{array} \] 
\[ \begin{array}{rcl} \label{T} 
\TT(D)& := &  -\frac 12 JDJ.
\end{array} \]
The operator $- 2 \TT$ is an orthogonal projection onto $\Sc.$ 

{\bf THEOREM}
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.
\epr

\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 For Projection:}
$V$ $n \times (n-1),$ full column rank with $V^te=0.$
\[ \label{eq:Vmp}
J := V V^{\dagger}= I- \frac{e e^t}{n}
\]
is orthogonal projection onto $M$,
where $V^{\dagger}$ denotes Moore-Penrose generalized inverse.
\end{slide}
\begin{slide}{}

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

\[ V \cdot V : {\cal S}_{n-1}  \rightarrow {\cal S}_{n}  
\]
\[ V \cdot V : {\cal P}_{n-1}  \rightarrow {\cal P}_{n}  
\]

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}{}


{\bf LEMMA}
\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.
\epr

{\bf COROLLARY}
\begin{eqnarray*} 
\KK_V(\p)  & = &  \E , \\
\TT_V(\E) & = &\p.
\end{eqnarray*} 
\epr
\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)

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

\end{slide}
\begin{slide}{}
{\bf THEOREM}
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} \]  
\epr
{\bf LEMMA}
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.  \epr

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

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}
 2 \KK^*_V\left(H^{(2)} \circ \KK_V(X)\right) - C
- \Lambda &=&0 &  \mbox{dual feas.} \\
 \Lambda X - \mu I&=&0  &  \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}{}
%%    \begin{figure}[htb]
%%     \centering
%%     \centerline{\
%%\psfig{figure=fig11513.ps,width=5.3in}
%%      \label{fig2}
%%   \caption{Approximate Completion Problem}
%%    \end{figure}
%\psfig{figure=fig11513.ps,width=5.5in}
%\end{slide}
%\begin{slide}{}
%
%\psfig{figure=fig13513.ps,width=5.3in}
%\end{slide}
%\begin{slide}{}
%
%\psfig{figure=fig8513.ps,width=5.3in}
%\end{slide}
%\begin{slide}{}
%
%\psfig{figure=fig9513.ps,width=5.3in}
%
%
%\end{slide}
%\begin{slide}{}
%




\begin{center}
\psfig{figure=fig11513.ps,width=3.1in}
\end{center}
\end{slide}
\begin{slide}{}


\begin{center}
\psfig{figure=fig13513.ps,width=3.1in}
\end{center}
\end{slide}
\begin{slide}{}

\begin{center}
\psfig{figure=fig8513.ps,width=3.1in}
\end{center}
\end{slide}
\begin{slide}{}


\begin{center}
\psfig{figure=fig9513.ps,width=3.1in}
\end{center}



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


\begin{center}
{\em Larger} Models
\end{center}
Instead of projecting and reducing the dimension to get
Slater's condition, add a variable and increase the dimension.

\begin{lem}
\label{lem:newcharact}
Let
\[
\begin{array}{rcl}
\FF &:=& \{X \in \Sn : v^Te=0 \quad \Rightarrow \quad v^TXv
\leq 0
           \},\\
\FF_0 &:=&\{ X \in \Sn :
       X - \alpha ee^t \preceq 0, \quad \mbox{for some } \alpha
\geq 0
        \},\\
\FF_1 &:=&\{ X \in \Sn :
X - \alpha ee^t \preceq 0, \quad \forall ~ \alpha \geq
\bar{\alpha},\\
&& ~~~~~~~~~\mbox{ for some } \bar{\alpha} \geq 0 \}.
\end{array}
\]
Then
\beq  \label{eq:subsets}
  {\rm ri} \left(\FF \right) \subset
  \FF_0  = \FF_1 \subset \FF \subset \overline{\FF_0}.
\eeq
\end{lem}


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


\bpr
Suppose that $\bar{X} \in {\rm ri} \left(\FF \right)$ (i.e.
$v^Te=0, v \neq 0 \Rightarrow v^T\bar{X}v < 0$) but
$\bar{X} \notin  \FF_0$.
Then, for each $\alpha \geq 0$,
there exists $w_{\alpha}$ with $||w_{\alpha}||=1$, such that
$w_{\alpha} \rightarrow \bar{w}$, as $\alpha \rightarrow
\infty$ and
\[
w_{\alpha}^T(\bar{X} - \alpha  ee^t)w_{\alpha} > 0, \quad
\forall ~
            \alpha\geq 0,
\]
i.e.
\[
w_{\alpha}^T\bar{X}w_{\alpha} >
\alpha w_{\alpha}^T  ee^tw_{\alpha} , \quad \forall ~
            \alpha\geq 0.
\]
Since $w_{\alpha}$ converges and the left-hand-side of the
above
inequality must be finite, this implies that $e^t \bar{w} =
\bar{w}^T\bar{X}\bar{w} = 0$, a contradiction. Therefore,
  ${\rm ri} \left(\FF \right) \subset \FF_0$.
That $\FF_0 = \FF_1$ is clear.

Now suppose that $\bar{X} - \alpha ee^t \preceq 0, ~ \alpha
\geq 0$. Let $v^T
e
= 0$. Then $0 \geq v^T(\bar{X} - \alpha ee^t)v=v^T\bar{X}v$,
i.e.
$\FF_0 \subset \FF$. The final inclusion comes from the first
and
the fact that $\FF$ is closed.
\epr


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

\begin{cor}
\label{cor:newcharacthollow}
Let
\[
\begin{array}{rcl}
\EE &:=& \{X \in \Sh : v^Te=0 \quad \Rightarrow \quad v^TXv
\leq 0
           \},\\
\EE_0 &:=&\{ X \in \Sh :
       X - \alpha ee^t \preceq 0, \quad \mbox{for some } \alpha
        \},\\
\EE_1 &:=&\{ X \in \Sh :
X - \alpha ee^t \preceq 0, \quad \forall ~ \alpha \geq
\bar{\alpha},\\
&& ~~~~~~~~~~~~ \mbox{ for some } \bar{\alpha} \}.
\end{array}
\]
Then
\beq  \label{eq:subsetsE}
  \EE = \EE_0  = \EE_1.
\eeq
\end{cor}
\bpr
(Similar to Lemma \ref{lem:newcharact}.) For closure,
suppose $0 \neq X_k \in \EE_0$, i.e.
$\diag(X_k)=0, X_k \preceq \alpha_k E$, for some $\alpha_k$;
and, suppose 
$X_k \rightarrow \bar{X}$. Since $X_k$ is hollow it has exactly
one positive eigenvalue which must be smaller than $\alpha_k$.
However, since $X_k$ converges to $\bar{X}$,
$\bar{X} \leq \lambda_{\max}(\bar{X}) E$, where
$\lambda_{\max}(\bar{X})$ is the largest eigenvalue of
$\bar{X}$.  \epr
\end{slide}
\begin{slide}{}

let: $E=ee^t$;
$f(P) := {\| H \circ (A - P) \|}^2_F$;\\
$\KK$ lin. operator with constraint $\diag (P)=0$.\\
{\bf primal problem} is:
\[
({\rm CDM})
 \begin{array}{ccc}
          \mu^* := & \min   &   f(P)  \\
                  &  \mbox{subject to}     &  \alpha E-P \succeq 0
  \end{array}
\]
and {\bf dual problem (DCDM)} is
\[
\begin{array}{ccc}
   \nu^*:= 
 &\max &f(P) +\left<y,b-KP\right>- \tr \Lambda (\alpha E-P)\\
  &  \mbox{subject to} &  \nabla_P f(P)  -\KK^*y+ \Lambda = 0\\
   &                   & -\trace \Lambda E =  0\\
    &      &       \Lambda \succeq 0.
    \end{array}
\]
(Slater's holds for primal but fails for dual.)
\end{slide}
\begin{slide}{}

(perturbed) Optimality Conditions are:
\[
\begin{array}{cl}
  \diag (P) = 0  & \mbox{primal feas.}\\
\left.
\begin{array}{cl}
 2H^{(2)} \circ (P-A)-\Diag(y) +\Lambda =  0 \\
  ~~~  -\trace \Lambda E= 0   
\end{array}  \right\}
&\mbox{dual feas.}\\
-(\alpha E -P) + \mu \Lambda^{-1}  = 0, ~
                  & \mbox{pert. C.S.}\\
\end{array}
\]


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


\subsubsection{On a New Characterization of EDMs}
\label{sect:newedm}

The above application for EDM uses 
\[
D=\lambda E - P, ~ P \succeq 0, ~\diag P = \lambda e, ~\lambda \geq 0;
\]
this raises the {\bf question}:\\
\begin{quote}
{\em {\bf which}
Euclidean distance matrices $D$ can be expressed
as $D= \lambda (E - C)$ for some nonnegative scalar $\lambda$ and some 
correlation matrix $C$, where $E$ is the matrix of all ones.}
\end{quote}


We {\bf show (and characterize)} that the cones
\[  
\cone \left(E-\EE_n \right) \,  \varsubsetneq
\, \overline{\cone \left(E-\EE_n \right)} =\DD_n,
\]
where $\EE_n$ is the elliptope (set of correlation matrices) and $\DD_n$
is the (closed convex) cone of Euclidean distance matrices.

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


The characterization is given using the 
Gale transform of the points generating $D$.
We also show that given points $p^1$, $p^2$, \ldots, $p^n \in \RR^r$,  
for any scalars $\lambda_1$, $\lambda_2$, \ldots,
$\lambda_n$ such that  
\[\sum_{j=1}^n \lambda_j \; p^j = 0, \;\;\;\;\;\;\;  \sum_{j=1}^n \lambda_j = 0,
\]       
we have  
\[ \sum_{j=1}^n \lambda_j \; \| p^i - p^j \|^2 = \alpha \mbox{ for all } i=1,\ldots,n, \]        
for some scalar $\alpha$ independent of $i$. 


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


{\bf Recall}:\\
\begin{itemize}
\item
$n \times n$ matrix $D=(d_{ij})$ is 
{\em Euclidean distance matrix (EDM)} if 
\[
\exists \quad p^1,p^2,\ldots,p^n \in \RR^r, \mbox{ such that }
 \|p^i-p^j\|^2= d_{ij},\quad  \forall i,j
\]
\item
dimension of smallest Euclidean space containing $p^1,p^2, \ldots,p^n$ is 
the {\em embedding dimension} of $D$.
\item
$D$ (hollow) EDM $\iff$ $D$ negative semidefinite on $e^{\perp}$
\item
the set of $n \times n$ EDM matrices 
is a closed convex cone, $\DD_n$
\end{itemize}



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


Since ${\EE}_n$ denotes set of $n \times n$ {\em correlation matrices}, 
i.e., set of positive semidefinite symmetric matrices
whose diagonal is equal to $e$, 
we are using the
well known fact \cite{MR98g:52001} 
that $\DD_n$ is the tangent cone of ${\EE}_n$ at $E$,
the matrix of all ones, i.e.,
\beq \label{eq:cones}    \DD_n = 
\overline{\cone \left(  E - \EE_n \right)} = 
\overline{\left\{ \lambda ( E - C ): \lambda \geq 0, C \in \EE_n \right\} },
\eeq
where $\bar{\cdot}$ denotes closure.

In general, it is difficult to determine whether the generated cone of a
set, $cone (C)$ is closed, though there are sufficient conditions, e.g.
$C$ is convex and compact and 0 is not in $C$.




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

\begin{itemize}
\item
Let $V$ be $n \times (n-1)$  such that
\beq \label{Vmp} V^Te=0\;, \;\;\;\;  V^TV=I_{n-1} \;. \eeq  
\item
orthogonal projection on $M=e^{\perp}$, denoted by $J$, is 
$J:= VV^T = I - e e^T/n$. 
\item
$D$ hollow is EDM $\iff$
$ B := - \frac{1}{2} \; J D J \succeq 0$
\item
embedding dimension of $D$ is equal, $r$, rank of $B$. 
\item
the points $p^1, p^2, \ldots, p^n$ that 
generate $D$ are given by the rows of the $n \times r$ matrix
$P$ where $B:= P P^T$. 
\item
since $B e = 0$, centroid of the points $p^i$, $i=1,\ldots, n$
coincides with the origin
\end {itemize}



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

Let $p^1,p^2,\ldots,p^n$ be points in $\RR^{r}$  whose 
centroid coincides with the origin, and 
are not contained in a proper hyperplane. Then   
\[ 
P := \left[ \begin{array}{c} {p^1}^T \\ {p^2}^T \\ \vdots \\ {p^n}^T 
  \end{array} \right]  
\] 
is of rank $r$. Let $B = P P^T$. 
Then it follows that the EDM matrix $D$ generated by 
$p^i$, $i=1,\ldots,n$ is given by
\beq \label{defK} D = 
\diag B  e^T + e  \left(\diag B\right)^T - 2 B.  \eeq  



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

\begin{itemize}
\item
Let $\bar{r}=n-1-r$ and
\[ 
Z \mbox{ be } n \times \bar{r},  \mbox{ full column rank with}, ~
 {P}^T Z = 0,  e^T Z = 0
\]
\item
${z^i}^T$ denotes the $i$-th row of $Z$. i.e., 
\[ 
Z^T := \left[ {z^1} ~|~ {z^2} ~|~  \ldots ~|~  {z^n} \right].  
\] 
\item
$z^i$ is called Gale transform of $p^i$;
$Z$ is called a {\em Gale matrix} corresponding to $D$.
\item
The columns of $Z$ represent the {\em affine dependence relations} among the
points ${p}^1, {p}^2, \ldots , {p}^n$, 
i.e., among the rows of $P$.  
\end{itemize}

\end{slide}
\begin{slide}{}
{\bf Main Results}
\begin{thm} \label{thm1} 
Let $D$ be a Euclidean distance matrix and let $Z$ be a Gale matrix corresponding to $D$. Then,
the columns of $DZ$ are proportional to $e$.
\end{thm}
Equivalently
\begin{thm} 
Let $\lambda_1$, $\lambda_2$, \ldots, $\lambda_n$ be 
coefficients, not all zero, of the affine
dependence equation of the points ${p}^1, {p}^2, 
\ldots , {p}^n$, in $\RR^r$, i.e.,  
\[ \sum_{j=1}^n \lambda_j  p^j = 0, \quad \sum_{j=1}^n \lambda_j = 0.
    \]       
Then 
\[ \sum_{j=1}^n \lambda_j \; \| p^i - p^j \|^2 = \alpha \mbox{ for all } i=1,\ldots,n, \]        
for some scalar $\alpha$ independent of $i$. 
\end{thm}


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

\begin{thm} \label{thm2} 
Let $D$ be a Euclidean distance matrix and let $Z$ be a Gale matrix 
corresponding to $D$. Then {\bf the following are equivalent}:
\begin{enumerate}
\item
\beq
D = \lambda ( E - C),
\end{equation}
for some nonnegative scalar $\lambda$ and some correlation matrix $C$; 
\item
\beq
 DZ=0.
\end{equation}
\end{enumerate}
\end{thm}




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


{\bf Proof of the Main Results}\\

\begin{lem} \label{lem1}
Let $D$ be a Euclidean distance matrix and let 
$B= - \frac{1}{2} J D J$.  Then:
\begin{enumerate}
\item
\[ - \frac{1}{2} V^T D V = V^T B V;
\]
\item
\[
\NN(V^TDV)= \NN(P^T V).
\]
\end{enumerate}
\end{lem} 
\bpr
The first part follows directly from (\ref{defK}) and the 
definition of $V$. This yields the second
part since $B=PP^T$ and 
$\NN(V^T B V)= \NN(V^T P P^T V)= \NN(P^T V)$.   
\epr     


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

\begin{lem} \label{lemLam}
Let $D$ be a Euclidean distance matrix and 
let $U$ be the matrix whose columns
form an orthonormal basis of the null space of $V^T D V$. Then $VU$ is a Gale matrix corresponding to $D$.  
\end{lem}

\bpr   
It follows from Lemma \ref{lem1} that $P^T V U = V^T D V U = 0$ and from the definition of $V$ in
(\ref{Vmp}) that  
$e^T V U =0$. Hence, the columns of     
$V U$ form an orthonormal basis
for the null space of  $\left[ \begin{array}{c}
           {P}^T  \\  e^T \end{array} \right] $.
\epr


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

\noindent {\bf Proof of Theorem \ref{thm1}.}
Let $Z$ be a Gale matrix corresponding to $D$. Then  
It follows from Lemma \ref{lemLam} that 
$VU = Z Q$ for some nonsingular $\bar{r} \times \bar{r}$ matrix $Q$.  
Thus $V^T D Z = V^T D V U Q^{-1}= 0$. Hence, 
the columns of $D Z$ are proportional to $e$.
\epr 

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


\noindent {\bf Proof of Theorem \ref{thm2}.}
$D = \lambda ( E - C)$ for some nonnegative scalar $\lambda$ and some correlation matrix $C$ 
if and only if $E - \frac{1}{\lambda} D$ is positive semidefinite.  
Let $Q= [ \frac{e}{\sqrt{n}} \;  V]$. Then, 
$E- D/\lambda \succeq 0 $  if and only if
$Q^T \; ( E - D/ \lambda ) \; Q \succeq 0 $. But 
\[ Q^T \; (E - D / \lambda )\; Q  =  \left[ \begin{array}{cc}
     n- \frac{1}{\lambda \; n } \; e^T D e & - \frac{1}{\lambda \; \sqrt{n}} \; e^T D V \\  
      - \frac{1}{\lambda \; \sqrt{n}} \; V^T D e  & - \frac{1}{\lambda } \; V^T D V  \\  
                                     \end{array} \right] .
\]
Recall that $ V^T (- D) V \succeq 0$ follows
from Lemma  \ref{lem1}.
Let $W$ and $U$ be the matrices whose columns form an orthonormal
basis for the range space and null space of $V^T (- D) V$, respectively. 


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


Hence, $V^T (-D) V= W \Lambda W^T$,
where $\Lambda$ is the diagonal matrix of the positive eigenvalues of $V^T (-D) V$. Let  $Q^\prime =  
 \left[ \begin{array}{ccc}
           1  &  0 & 0 \\  0 & W  & U \end{array} \right]$.    
Then, $E- D/\lambda$ is positive semidefinite if and only if 
\beq \label{big} 
\begin{array}{rcl}
R &=&
{Q^\prime}^T  Q^T ( E - D/ \lambda) Q Q^\prime  \\
~\\
&=& 
\left[ \begin{array}{ccc}
   n- \frac{1}{\lambda  n }  e^T D e & - \frac{1}{\lambda  \sqrt{n}}  e^T D V W   
                          & - \frac{1}{\lambda \sqrt{n}}  e^T D V U  \\   
  - \frac{1}{\lambda \sqrt{n}} W^T V^T D e & \frac{1}{\lambda } \Lambda  &  0 \\  
  - \frac{1}{\lambda \sqrt{n}} U^T V^T D e  & 0  &  0  
                          \end{array} \right] \succeq 0.  
\end{array}
\eeq

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

Now for sufficiently large  $\lambda$ the submatrix 
\[
 \left[ \begin{array}{cc}
     n- \frac{1}{\lambda \; n } \; e^T D e & - \frac{1}{\lambda \; \sqrt{n}} \; e^T D V W \\   
      - \frac{1}{\lambda \; \sqrt{n}} \; W^T V^T D e  &  \frac{1}{\lambda } \; \Lambda   \\  
                                  \end{array} \right] 
\]  
is positive definite. 

Thus $E - D/ \lambda$ is positive semidefinite 
if and only if
 $e^T D V U = e^T D Z= 0$. But it follows from Theorem \ref{thm1} that
$e^T D Z = 0$ if and only if
 $DZ=0$ and the result follows.     
\epr


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

{\bf Given the two Euclidean distance matrices:}
\[ 
D_1 = \left[ \begin{array}{ccc} 0 & 1 & 4 \\ 1 & 0  & 1 \\  4 & 1 & 0 \end{array} \right], \;\;\;\;\;\;  
D_2 = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0  & 1 \\  0 & 1 & 0 \end{array} \right],
\]
Gale matrices $Z_1,Z_2$ corresponding to $D_1,D_2$, resp. are:
\[ 
Z_1^T = \left[  1  ~ -2 ~  1  \right], \quad
Z_2^T = \left[  1  ~  0  ~ -1 \right],  
\]
Now $D_1 Z_1 = 2 e$ and $D_2 Z_2 = 0$.
 Then: $D_2 = E - C_2$, where   
\[ C_2 = \left[ \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1  & 0 \\  1 & 0 & 1 \end{array} \right] \succeq 0. \]
However, there exists no $\lambda \geq 0$ such that $D_1= \lambda ( E - C_1)$ for some correlation
matrix $C_1$.    



\end{slide}

%\bibliography{.psd,.master,.publs}
\end{document}
