%\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, ~~~ \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 - \tr \Lambda P \] ~~\\ Dual problem: \[ (DAC) \begin{array}{ccc} \max &f(P) +\left- \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- \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}