\documentclass[notes]{beamer}
\usepackage{graphics,graphicx} 
\usepackage{xcolor} 
\usepackage{epsfig}



\definecolor{rblue}{rgb}{.255,.41,.884} % RoyalBlue of svgnames
\definecolor{rred}{rgb}{1, 0, 0} % Red of svgnames
\definecolor{lgreen}{rgb}{.196,.804,.196} % LimeGreen of svgnames
\definecolor{oyellow}{rgb}{1,.648,0} % Orange of svgnames

%Beamer loads xcolor package by Uwe Kern, which also supports color
%and pstcol.
%?xcolor? definition
\xdefinecolor{lavendar}{rgb}{0.8,0.6,1}
\xdefinecolor{olive}{cmyk}{0.64,0,0.95,0.4}
%\colorlet{structure}{green!60!black} for color substitution
%Predefined colors: red, green, blue, cyan, magenta, yellow, black,
%darkgray, gray, lightgray, orange, violet, purple, and brown
%If you want to use the options of ?color? package, pass
%[color=option] option to Beamer.
%If you want to use ?pstcol?, pass [xcolor=pst,dvips] option to
%Beamer. Now you should use ?dvips/ps2pdf?

\newcommand{\cm}{\color{magenta}}
\newcommand{\cb}{\color{black}}
\newcommand{\cg}{\color{lgreen}}
\newcommand{\crr}{\color{rred}}
\newcommand{\co}{\color{olive}}



\def\Rnbyn{\mathbb{R}^{n\times n}}
\def\R{\mathbb{R}}
\def\Rm{\mathbb{R}^m}
\def\Rn{\mathbb{R}^n}


\newcommand{\QED}{\rule{8pt}{8pt}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bsl}{\begin{slide}}
\newcommand{\esl}{\end{slide}}
\newcommand{\BB}{{\mathcal B} }
\newcommand{\uu}{{\bf u}}
\newcommand{\A}{{\mathcal A\,}}
\newcommand{\GG}{{\mathcal G\,}}
\newcommand{\RR}{{\mathcal R\,}}
\newcommand{\VV}{{\mathcal V\,}}
\newcommand{\EE}{{\mathcal E\,}}
\newcommand{\KK}{{\mathcal K\,}}
\newcommand{\LL}{{\mathcal L\,}}
\def\Ssum{\mathop{\mathcal S_\Sigma}}
\def\Sprod{\mathop{\mathcal S_\Pi}}
\newcommand{\TT}{{\mathcal T\,}}
\newcommand{\CC}{{\mathcal C\,}}
\newcommand{\MM}{{\mathcal M\,}}
\newcommand{\NN}{{\mathcal N\,}}
\newcommand{\YY}{{\mathcal Y\,}}
\newcommand{\FF}{{\mathcal F\,}}
\newcommand{\F}{{\mathcal F\,}}
\newcommand{\ZZ}{{\mathcal Z\,}}
\newcommand{\SDP}{{\bf{\rm SDP\,}}}
\newcommand{\EDM}{{\bf{\rm EDM\,}}}
\newcommand{\EDMC}{{\bf{\rm EDMC\,}}}
\newcommand{\SNL}{{\bf{\rm SNL\,}}}
\newcommand{\NLLS}{{\bf{\rm NLLS\,}}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\face}{{\rm face\,}}% smallest face containing a set
\newcommand{\facee}{{\rm face^{ef}\,}}% smallest face containing a set
\newcommand{\argmin}{{\rm argmin\,}}
\newcommand{\relint}{{\rm relint\,}}
\newcommand{\cone}{{\rm cone\,}}
\newcommand{\sspan}{{\rm span\,}}
\newcommand{\Sn}{{\mathcal S^n\,}}
\newcommand{\En}{{{\mathcal E}^n} }
\newcommand{\Ek}{{{\mathcal E}^k} }
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\PP}{{\mathcal P} }
\newcommand{\DD}{{\mathcal D} }
\newcommand{\corr}{{\rm corr\,}}
\newcommand{\its}{{\rm its\,}}
\newcommand{\stitle}[1]{\begin{center} {\bf\large {#1} } \end{center}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\offDiag}{{\rm offDiag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\Ss}{{\mathcal S}}
\newcommand{\Ekyb}{{\mathcal E}^{n}(1\!:\!k,\bar D)}
\newcommand{\Eayb}{{\mathcal E}^{n}(\alpha,\bar D)}
\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{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\sblk}{{\rm sblk\,}}
\newcommand{\sBlk}{{\rm sBlk\,}}
\newcommand{\blk}{{\rm Blk\,}}
\DeclareMathOperator{\usMat}{{us2Mat}}
\DeclareMathOperator{\usvec}{{us2vec}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\Mat}{{\rm Mat\,}}
\newcommand{\Sk}{\Ss^k}%
\newcommand{\Skp}{\Ss^k_+}%
\newcommand{\Snp}{\Ss^n_+}%
\newcommand{\Srpp}{\Ss^r_{++}}%

\newcommand{\Sayb}{{\mathcal S}^{n}(\alpha,\bar Y)}
\newcommand{\Sapyb}{{\mathcal S}_+^{n}(\alpha,\bar Y)}
\newcommand{\Skyb}{{\mathcal S}^{n}(1\!:\!k,\bar Y)}
\newcommand{\Skpyb}{{\mathcal S}_+^{n}(1\!:\!k,\bar Y)}
\newcommand{\Sok}{{\mathcal S}^{1\!:\!k}}









\mode<presentation>
{
  \usetheme{Warsaw}
  \usecolortheme{seahorse}
  \setbeamercovered{transparent}
}
\beamertemplatenavigationsymbolsempty

\usefoottemplate{\hfil\tiny{\color{black!90}\insertframenumber}} 

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}

\usepackage{times}
\usepackage[T1]{fontenc}

\title{
\color{blue} Explicit 
Sensor Network Localization\\
 using\\
 Semidefinite Programming and\\ Facial Reduction
}

\author[Henry Wolkowicz]{Nathan Krislock and \underline{\bf Henry Wolkowicz}  }
\institute{Dept. of Combinatorics and Optimization\\
University of Waterloo
}

\date{INFORMS, San Diego\\Oct. 11-14, 2009}

\subject{Talks}

\def\defn#1{{\color{red} #1}}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  %\tableofcontents
  \tableofcontents[pausesections]
  % You might wish to add the option [pausesections]
\end{frame}



\section{Preliminaries}



\subsection{SNL <--> GR <--> EDM <--> SDP}
\begin{frame}
   \frametitle{Sensor Network Localization, SNL, Problem}
\begin{block}{ SNL - a Fundamental Problem of Distance Geometry;\\
{\color{lgreen} easy to describe} - {\co dates back to Grasssmann 1886} } 
\begin{itemize}
\item
{\color{brown}$\cm n$ ad hoc wireless sensors (nodes)} 
  to locate in {$\cm  \R^r$},\\
            ($\cm  r$ is embedding dimension;\\
 sensors $\cm p_i \in \R^r, i\in V:=1,\ldots,n$)
\item
{\color{orange}$\cm  m$ of the sensors are anchors},
$\cm p_i, i=n-m+1,\ldots,n$)\\
(positions known, using e.g. GPS)
\item
{\color{rred}pairwise distances} 
  $\cm D_{ij}=\|p_i-p_j\|^2, ij \in E,$ are known
            within {\color{rred} radio range $\cm R>0$}
\item
		\[\cm 
			P 
			=
			\begin{bmatrix} 
		   	p_1^T \cr \vdots \cr p_{n}^T 
		   	\end{bmatrix} 
			= 
			\begin{bmatrix}
			X \cr
			A
			\end{bmatrix}
			\in \mathbb{R}^{n \times r}
		\]

\end{itemize}
\end{block}

%%\pause\uncover{
%%\begin{block}{Current Techniques: Nearest, Weighted, \SDP Approx.}
%%$ \cm
%%\min_{Y \succeq 0, Y\in \Omega} \left\| H\circ\left(\KK(Y) - D\right) \right\|
%%$\\
%%SDP program is: 
%%{\color{rblue}Expensive}/{\color{lgreen}low
%%accuracy}/{\color{rred}implicitly highly degenerate
%%(cliques restrict ranks of feasible $\cm Y$s)}
%%\end{block}
%%}
\end{frame}



\begin{frame}
\frametitle{Applications}

\begin{block}{Horst Stormer (Nobel Prize, Physics, 1949), 
``21 Ideas for the 21st Century'', Business Week. 8/23-30, 1999}
{\cg Untethered micro sensors will go anywhere and measure
anything - traffic flow, water level, number of people
walking by, temperature. This is developing into
something like a nervous system for the earth, {\crr a skin for
the earth}. The world will evolve this way.}
\end{block}
\begin{block}{Tracking Humans/Animals/Equipment/Weather \quad \crr
(smart dust)}
\begin{itemize} 
\item 
geographic routing; data aggregation; topological control;
soil humidity; earthquakes and volcanos; 
weather and ocean currents.
\item 
military; tracking of goods; vehicle positions; surveillance;
random deployment in inaccessible terrains.
\end{itemize}
\end{block}
%%\pause\uncover{
%%\begin{block}{\color{green} Future Applications?}
%%\begin{itemize} 
%%\item
%%bicycles, car/computer parts, guns {\color{rblue}(to prevent theft)}
%%\item
%%students/teenagers  {\color{rblue} (prevent class absence)}
%%%~~~~~~ {\black sensors everywhere - by 2084!}
%%%~~~~~~ {\black Lobster migration}
%%\end{itemize}
%%\end{block}
%%}
\end{frame}



\begin{frame}
\frametitle{Conferences/Journals/Research Groups/Books/Theses/Codes}
\begin{block}{}
\begin{itemize}
\item
\href{http://www2.parc.com/isl/projects/MELT08/}{Conference, MELT 2008}
\item
\href{http://www.inderscience.com/browse/index.php?journalID=186}{International
Journal of Sensor Networks}
\item
Research groups include:
\href{http://research.cens.ucla.edu/}{CENS at UCLA},
\href{http://local.cs.berkeley.edu/webs/}{Berkeley WEBS},
\item
recent related theses and books include:
\cite{Hendrickson1990,Romer:05,dattorro:05,ChakrabartyIyengar:05,Jin:05,danielkim:06,cassioli:08,nawaz:08,Urabl:09}
\item
recent algorithms specific for SNL:
\cite{BYACM:06,BYIEEE:06,BY:04,MR2191577,MR2274505,DiKrQiWo:06,PongTseng:09,WangZhengBoydYe:06,kriswolk:09}
\end{itemize}
\end{block}
\end{frame}



\begin{frame}
\frametitle{Underlying Graph Realization/Partial \EDM \quad \crr NP-Hard}
\begin{block}{Graph $\cm {\GG=(\VV,\EE,\omega)}$}
\begin{itemize}
\item 
node set $\cm \VV = \{1, \ldots, n\}$
\item 
edge set $\cm (i,j) \in \EE$; $\cm \omega_{ij}=\|p_i-p_j\|^2$ 
known {\color{rblue} approximately}
\item 
The anchors form a \underline{\color{rred} clique}
{\color{olive} (complete subgraph)}
\item
{\color{rred} Realization of $\cm \GG$ in $\cm \Re^r$}: a mapping of node
$\cm v_i\rightarrow p_i \in \Re^r$ with squared distances given by $\cm \omega$. 
\end{itemize}
\end{block}
\pause\uncover{
\begin{block}{Corresponding Partial Euclidean Distance Matrix, \EDM}
\[\cm
D_{ij}=  \left\{ \begin{array}{cl}
  d_{ij}^2  & \mbox{if    }~ (i,j) \in \EE  \\
  0       &   \mbox{otherwise \cb (unknown distance)},
\end{array} \right.
\]
{\color{rblue}
$\cm d_{ij}^2=\omega_{ij}$ are known squared
Euclidean distances between sensors $\cm p_i,p_j$};
anchors correspond to a {\color{rred} clique}.
\end{block}
}
\end{frame}




\begin{frame}
\frametitle{Sensor Localization Problem/Partial \EDM}

\begin{block}{
{\color{red} Sensors $\circ$} and
{ Anchors $\color{black} \QED$}
}
\begin{figure}[htb]
\epsfxsize=180pt
%\centerline{\epsfbox{fig300.eps}}
\centerline{\epsfbox{SNLfig.eps}}
\end{figure}

\end{block}


\end{frame}



\begin{frame}
   \frametitle{Connections to Semidefinite Programming (SDP)}
\begin{block}{$\cm \Snp$, Cone of (symmetric) 
     SDP matrices in $\cm \Sn; x^TAx \geq 0$}
 inner product $\cm \langle A,B \rangle = \trace AB$ \\
L\"owner (psd) partial order $\cm A \succeq B, A \succ B$  
\end{block}

\pause\uncover{
\begin{block}{$\cm D=\KK(B) \in \En$, $\cm B=\KK^\dagger(D)\in \Sn\cap \Sc$
(centered $\cm Be=0$)}
\vspace{-.05in}
$\cm P^T=\begin{bmatrix}
p_1 & p_2 & \ldots & p_n \end{bmatrix} \in \MM^{r\times n}$;
$\cm B:=PP^T\in \Snp$;\\
\vspace{-.05in}
$\cm \rank B = r$;
 $\cm D \in \En$ be corresponding \EDM.
\vspace{-.2in}
\[ \cm
\begin{array}{rcl}
(\mbox{\cb to } D\in \En )\quad  
       D  
      &=&  
          \left( \| p_{i} - p_{j} \|_{2}^{2} \right)_{i,j = 1}^{n} 
         \\&=&  
        \left( p_{i}^{T} p_{i} + p_{j}^{T} p_{j} 
                     - 2 p_{i}^{T} p_{j} \right)_{i,j = 1}^{n} 
         \\&=&  
    {\cb \fbox{$\cm
       \diag (B)\,e^T + e \, \diag (B)^T - 2B $}}
         \\&=:&  
            \DD_e(B)-2B 
         \\&=:&  
       \KK(B) \quad (\mbox{\cb from } B \in \Snp).
\end{array} 
\]
\end{block}
}
\end{frame}




\begin{frame}
   \frametitle{Current Techniques; SDP Relax.; Highly Degen.}
\begin{block}{Nearest, Weighted, \SDP Approx. (relax $\cm \rank B$)}
\begin{itemize}
\item
$ \cm \min_{B \succeq 0, B\in \Omega} 
\left\| H\circ\left(\KK(B) - D\right) \right\|$; $\cm \rank B=r$;\\
typical weights: $\cm H_{ij}= 
               1/\sqrt{D_{ij}},  \mbox{  \cb if } ij \in E$.

\item
with rank constraint: a non-convex, NP-hard program 
\item
SDP relaxation is convex, {\crr \underline{BUT}}: 
{\color{rblue}expensive}/{\color{lgreen}low
accuracy}/{\color{rred}implicitly highly degenerate
(cliques restrict ranks of feasible $\cm B$s)}
\end{itemize}
\end{block}
\pause\uncover{
\begin{block}{Instead: (Shall) Take Advantage of Degeneracy!}
clique $\cm \alpha, |\alpha|=k$ (corresp.  $\cm D[\alpha]$) with embed. dim. $\cm =t\leq r<k$
$\cm \implies$
$\cm  \rank \KK^\dagger (D[\alpha]) =t\leq r$
$\cm \implies$
$\cm  \rank B[\alpha] \leq \rank \KK^\dagger (D[\alpha])+1$
$\cm \implies$
$\cm  \rank B = \rank \KK^\dagger (D) \leq n-\fbox{$(k-t-1)$}$ 
$\cm \implies$\\
Slater's CQ (strict feasibility) \crr \underline{fails}

\end{block}
}
\end{frame}

\begin{frame}
\frametitle{{\cg ($\Sn$:)}\quad $\cm \KK : 
         \Snp \cap \Sc \rightarrow \En \subset \Sn \cap
           \Sh \qquad \leftarrow :\TT$ \quad {\cg(:$\En$)}} 
\begin{block}{Linear Transformations: $\cm \DD_v(B), \KK(B), \TT(D)$}
\begin{itemize}
\item
allow: $\cm \DD_v(B) := \mbox{diag}(B)\,v^T + v \, \mbox{diag}(B)^T$; 
 $\cm \DD_v(y) := yv^T+vy^T$

\item
adjoint $\cm \KK^*(D) = 2(\Diag(De)-D)$.

\item
\fbox{
$\cm \KK$ is $\cm 1\!-\!1$, onto between
{\color{rblue} centered} \& {\color{rblue} hollow} subspaces }:
$\cm
\Sc :=  \{ B \in \Sn :  Be = 0 \}$; 
$\cm \Sh :=  \{ D \in \Sn :  \diag(D) = 0 \}   = \RR(\offDiag)$
\item
$\cm J:=I-\frac 1n ee^T$ (orthogonal projection onto
$\cm M:= \{e\}^\perp$);
\item
	\fbox{
$\cm \TT (D) := -\frac 12 J \offDiag (D) J \qquad (= \KK^\dagger (D) )$
}
\end{itemize}
\end{block}
\end{frame}



\begin{frame}
\frametitle{Properties of Linear Transformations}
\begin{block}{$\cm \KK, \TT, \Diag, \DD_e$}
\[\cm 
\begin{array}{rcl}
	\vspace{.1in}
	\RR (\KK) = \Sh; & \quad  &\underline{\NN(\KK) = \RR(\DD_e)};\\
\RR(\KK^*)=\RR (\TT) = \Sc; & \quad & \NN(\KK^*)= \NN(\TT) = \RR(\Diag);
\end{array}
\]
\[\cm
\begin{array}{rcl}
\Sn= \Sh \oplus  \RR(\Diag) = \Sc \oplus \RR(\DD_e).
\end{array}
\]
\[\cm  \TT(\En) = \Snp \! \cap \Sc 
   \quad \mbox{\color{rblue} \underline{and}} \quad 
   \KK(\Snp \! \cap \Sc) = \En. \]
%\epr

\end{block}
\end{frame}


\subsection{Further Notation/Preliminaries; Facial Structure of Cones}
\begin{frame}
   \frametitle{Semidefinite Cone, Faces}
%%\begin{block}{$\cm v=\diag(S) \in \Rn$, $\cm S=\Diag(v)\in \Sn$}
%%$\cm \diag = \Diag^*$ (adjoint)
%%
%%for $\cm B\in \Sn$, $\cm \offDiag(B) := B-\Diag(\diag (B))$
%%\end{block}

\begin{block}{Faces of cone $K$}
\begin{itemize}
\item
$\cm F\subseteq K$ is a \underline{\color{rblue} face of $\cm K$}, denoted
\fbox{$\cm F \unlhd K$},  if
$\cm 
\left( x, y \in K, \ \frac 12(x+y) \in  F\right)
                 \implies \left(\cone \{x,y\} \subseteq F\right).$
\item
\fbox{$\cm F \lhd K$}, if $\cm F \unlhd K$, $\cm F \neq K$; 
$\cm F$ is \fbox{\color{rblue} proper face} if $\cm \{0\} \neq F \lhd K$.
\item
$\cm F \unlhd K$ is \fbox{\color{rblue} exposed} if: 
intersection of $\cm K$ with a hyperplane.
\item
\fbox{$\cm \face\!(S)$} denotes 
smallest face of $\cm K$ that contains set $\cm S$. 
\end{itemize}
\end{block}
\pause\uncover{
\begin{block}{
$\cm \Snp$ is a {\color{rred} Facially Exposed Cone}} 
All faces are exposed.
\end{block}
}

\end{frame}


\begin{frame}
\frametitle{{\color{rred} Facial} Structure of SDP Cone; 
        Equivalent \color{rred} SUBSPACES}

\begin{block}{{\color{rred} Face } $\cm F \unlhd \Snp$
             Equivalence to {\color{olive} $\cm \RR(U)$ Subspace of} $\cm \R^n$}


$\cm F\unlhd \Snp$ determined by
 {\color{rblue} range of \underline{any}} $\cm S \in \relint F$,\\
 i.e.  let $\cm S=U\Gamma U^T$ be
compact spectral decomposition;
$\cm \Gamma \in \Ss_{++}^t$ is diagonal matrix of pos. eigenvalues; 
\fbox{ 
 $\cm
F=U \Ss_+^t U^T$}
\qquad $\left({\cm F \mbox{ associated with  } \RR(U)}\right) $\\
\qquad\qquad\qquad\qquad    $\cm {\rm dim\,} F = t(t+1)/2.$
\end{block}

\pause\uncover{
\begin{block}{face $\cm F$ representation by subspace $\cm\LL$}
(subspace) $\cm\LL= \RR(T)$, $\cm T$ is $\cm n\times t$ full column,
then:
\[\cm
F:=T \Ss_+^t T^T \unlhd \Snp
\]

\end{block}
}


\end{frame}





\begin{frame}
\frametitle{Further Notation}

\begin{block}{Matrix with Fixed Principal Submatrix}
For $\cm Y\in \Sn$, $\cm \alpha \subseteq \{1,\ldots,n\}$: 
$\cm Y[\alpha]$ 
denotes {\color{rblue} principal submatrix} formed from rows \& cols 
with indices $\cm \alpha$. 
\end{block}

\pause\uncover{
\begin{block}{Sets with Fixed Principal Submatrices}
If $\cm |\alpha |=k$ and $\cm \bar Y \in \Ss^k$,  then:
\begin{itemize}
\item
$\cm  \Sayb:= \left\{ Y \in \Sn : Y[\alpha] = \bar Y \right\}$,
\item
$\cm \Sapyb:= \left\{ Y \in \Snp : Y[\alpha] = \bar Y \right\}$

i.e. the subset of matrices $\cm Y \in \Sn$ ($\cm Y \in \Snp$)
with principal submatrix $\cm Y[\alpha]$ fixed to $\cm \bar Y$.
\end{itemize}
\end{block}
}
\end{frame}





\section{Clique/Facial Reduction (Exploit degeneracy)}
\subsection{Basic Single Clique Reduction}

\begin{frame}
\frametitle{Basic Single Clique/Facial Reduction}

\begin{block}{$\cm \bar D \in \EE^k$, 
            $\cm \alpha \subseteq 1\!:\!n$, $\cm |\alpha| = k$}
Define 
$\cm \Eayb:= \left\{ D \in \En : D[\alpha] = \bar D \right\}$.
\end{block}
\begin{block}{}
	Given $\cm \bar D$; find a corresponding $\cm B \succeq 0$; find the
	corresponding face; find the corresponding subspace.
\end{block}
\begin{block}{if $\cm \alpha = 1:k$; embed. dim of $\cm \bar D$ 
        is $\cm t \leq r$}
		\[ \cm
			D = \begin{bmatrix}
			 \alert{\bar D} & \cdot \cr
			 \cdot & \cdot
			\end{bmatrix},
		\]
\end{block}
\end{frame}




\begin{frame}
\frametitle{{\crr BASIC THEOREM} for Single Clique/Facial Reduction}
\begin{block}{THEOREM 1: Single Clique/Facial Reduction}
Let: $\cm \bar D := D[1\!:\!k] \in \Ek$, $\cm k<n$, with embedding 
dimension $\cm t \leq r$;
$\cm B := \KK^\dagger(\bar D) = \bar U_B S \bar U_B^T$,
$\cm \bar U_B \in \MM^{k\times t}$, $\cm \bar U_B^T \bar U_B = I_t$,
$\cm S \in \Ss^t_{++}$. 
Furthermore, let $\cm U_B := 
\begin{bmatrix} 
\bar U_B & \frac 1{\sqrt{k}} e 
\end{bmatrix}
\in \MM^{k\times (t+1)}$,  
$\cm U := \begin{bmatrix} U_B & 0 \cr 0 & I_{n-k}  \end{bmatrix}$,
and let $\cm \begin{bmatrix} V & \frac{U^Te}{\|U^Te\|}  \end{bmatrix}
\in \MM^{n-k+t+1}$ be orthogonal.  Then:
\fbox{
$\cm \begin{array}{rcl} 
\face \KK^\dagger\left(\Ekyb\right) 
&=& \left( U \Ss_+^{n-k+t+1} U^T \right) \cap \Sc\\
&=& (U V) \Ss_+^{n-k+t} (U V)^T
\end{array}$
}

\end{block}

\begin{block}{}
	Note that we add $\cm \frac 1{\sqrt{k}} e$ to represent $\cm \NN(\KK)$; 
	then we use $\cm V$ to eliminate $\cm e$ to recover a 
\underline{centered} face.
\end{block}

\end{frame}




\subsection{Two Clique Reduction and EDM DELAYED Completion}


\begin{frame}
\frametitle{Sets for Intersecting Cliques/Faces}

\begin{block}{$\cm \alpha_1  :=  1\!:\!(\bar k_1 + \bar k_2); 
  \quad \alpha_2  :=  (\bar k_1 + 1)\!:\!(\bar k_1 + \bar k_2 + \bar k_3)$
}

\begin{figure}[htb]
\epsfxsize=180pt
\centerline{\epsfbox{alpha.eps}}
\end{figure}
\end{block}
\begin{block}{}
	For each clique $\cm |\alpha|=k$, we get a corresponding 
	face/subspace ($\cm k \times r$ matrix)
	representation. We now see how to handle two cliques,
	$\cm \alpha_1, \alpha_2$, that
	intersect.
\end{block}


\end{frame}


\begin{frame}
\frametitle{Two (Intersecting) Clique Reduction/Subsp. Repres.}

\begin{block}{THEOREM 2: Clique/Facial Intersection Using Subspace Intersection}
$\cm \left\{
\begin{array}{l}
 \alpha_1,  \alpha_2  \subseteq 1\!:\!n; \quad
k := |  \alpha_1 \cup \alpha_2 |
\end{array}\right. $\\
For $\cm i=1,2$: $\cm \bar D_i := D[\alpha_i] \in \EE^{k_i}$, 
embedding dimension $\cm t_i$;
$\cm B_i := \KK^\dagger(\bar D_i) = \bar U_i S_i \bar U_i^T$,
$\cm \bar U_i \in \MM^{k_i\times t_i}$, 
$\cm \bar U_i^T \bar U_i = I_{t_i}$,
$\cm S_i \in \Ss^{t_i}_{++}$; \\
$\cm U_i := \begin{bmatrix} 
\bar U_i & \frac 1{\sqrt{k_i}} e 
\end{bmatrix}
\in \MM^{k_i \times (t_i+1)}$;  
and $\cm \bar U \in \MM^{k \times (t+1)}$ satisfies
{\color{rred}
\fbox{
$\cm 
\RR(\bar U) = 
\RR \left(
\begin{bmatrix} U_1 & 0 \cr 0 & I_{\bar k_3}  \end{bmatrix}
\right)
\cap
\RR \left(
\begin{bmatrix} I_{\bar k_1} & 0 \cr 0 & U_2 \end{bmatrix}
\right), \mbox{\color{black}  with  }  \bar U^T \bar U = I_{t+1}$
}
}

cont\ldots
\end{block}


\end{frame}



\begin{frame}
\frametitle{Two (Intersecting) Clique Reduction, cont\ldots}

\begin{block}{THEOREM 2 Nonsing. Clique/Facial Inters. cont\dots}
cont\ldots with
{\color{rred}
\fbox{
$\cm 
\RR(\bar U) = 
\RR \left(
\begin{bmatrix} U_1 & 0 \cr 0 & I_{\bar k_3}  \end{bmatrix}
\right)
\cap
\RR \left(
\begin{bmatrix} I_{\bar k_1} & 0 \cr 0 & U_2 \end{bmatrix}
\right), \mbox{\color{black}  with  }  \bar U^T \bar U = I_{t+1}$};
}
let:
$\cm U := \begin{bmatrix} \bar U & 0 \cr 0 & I_{n-k} \end{bmatrix}
  \in \MM^{n \times (n-k+t+1)}$
and
$\cm \begin{bmatrix} V & \frac{U^Te}{\|U^Te\|} \end{bmatrix}
\in \MM^{n-k+t+1}$ be orthogonal. Then
\fbox{
$\cm 
\begin{array}{rcl}
\underline{\underline{\bigcap_{i=1}^2
\face \KK^\dagger\left(\En(\alpha_i,\bar D_i)\right)}
}
&=& \left( U \Ss_+^{n-k+t+1} U^T \right) \cap \Sc
\\&=& (U V) \Ss_+^{n-k+t} (U V)^T
\end{array}$
}
\end{block}

\end{frame}




\begin{frame}
	\frametitle{Expense/Work of (Two) Clique/Facial Reductions}
	\begin{block}{Subspace Intersection for Two Intersecting
		Cliques/Faces}
		Suppose:
\vspace{-.1in}
		\[\cm 	U_1 = 	
			\begin{bmatrix}
				U_1' & 0 \cr
				U_1'' & 0 \cr
				0 & I
			\end{bmatrix}
			\quad \mbox{\cb and} \quad
			U_2 = 	
			\begin{bmatrix}
				I & 0 \cr
				0 & U_2'' \cr
				0 & U_2'
			\end{bmatrix}
		\]
		Then:
\vspace{-.1in}
		\[\cm
			U := 
			\begin{bmatrix}
				U_1' \cr
				U_1'' \cr
				U_2' (U_2'')^\dagger U_1''
			\end{bmatrix}
			\quad \mbox{\cb or} \quad
			U := 
			\begin{bmatrix}
				U_1' (U_1'')^\dagger U_2'' \cr
				U_2'' \cr
				U_2'
			\end{bmatrix}
		\]
		(Efficiently) satisfies:
\vspace{-.1in}
		\[
			\alert{\RR(U) = \RR(U_1) \cap \RR(U_2)}
		\]

	
	\end{block}


\end{frame}


\begin{frame}
\frametitle{Two (Intersecting) Clique Reduction Figure}

\begin{block}{}

\begin{figure}[htb]
\epsfxsize=150pt
\centerline{\epsfbox{clique_intersect.eps}}
\end{figure}
\end{block}
\vspace{-.1in}
\begin{block}{}
	Completion: missing distances can be recovered if desired.
\end{block}


\end{frame}



\begin{frame}
\frametitle{Two (Intersecting) Clique Explicit {\crr Delayed} Completion}

\begin{block}{COR. Intersection with Embedding Dim. $\cm r$/Completion}
Hypotheses of Theorem 2 holds.
Let $\cm \bar D_i := D[\alpha_i] \in \EE^{k_i}$, for $\cm i=1,2$,
$\cm 
  \beta \subseteq \alpha_1 \cap \alpha_2,
  \gamma := \alpha_1 \cup \alpha_2,
  \bar D := D[\beta],
  B := \KK^\dagger(\bar D), \quad \bar U_\beta := \bar U(\beta,:)$,
where $\cm \bar U  \in \MM^{k \times (t+1)}$
satisfies intersection equation of Theorem 2.
Let 
$\cm \begin{bmatrix} \bar V & \frac{\bar U^Te}{\|\bar U^Te\|} \end{bmatrix}
\in \MM^{t+1}$ 
be orthogonal.
Let \fbox{$\cm Z := 
(J \bar U_\beta \bar V)^\dagger B ((J \bar U_\beta \bar V)^\dagger)^T$}. 
If the embedding dimension for $\cm \bar D$ is $\cm r$, \underline{THEN} 
$\cm t = r$ in Theorem 2, and $\cm Z \in \Ss^{r}_+$ is the unique 
solution of the equation
$\cm (J \bar U_\beta \bar V) Z (J \bar U_\beta \bar V)^T = B$,
and the {\color{rred} exact completion} is\\
\qquad \qquad 
{\color{rred} \fbox{$\cm 
D[\gamma] = 
\KK\left(PP^T\right)$}
}
	where \fbox{$\cm P := UV \alert{Z^\frac12} \in \R^{|\gamma| \times r}$}

\end{block}


\end{frame}





\begin{frame}
\frametitle{$2$ (Inters.) Clique Red. {\color{rred} Figure}/Singular Case}

\begin{block}{Two (Intersecting) Clique Reduction Figure/Singular Case}

\begin{figure}[htb]
\epsfxsize=135pt
\centerline{\epsfbox{deg_clique_intersect.eps}}
\end{figure}
\end{block}
\begin{block}{}
	Use $\cm R$ as lower bound in singular/nonrigid case.
\end{block}


\end{frame}




\begin{frame}
\frametitle{Two (Inters.) Clique Explicit Compl.; Sing. Case}

\begin{block}{COR. Clique-Sing.; 
Intersect. Embedding Dim. $\cm r-1$}
Hypotheses of previous COR  holds. 
For $\cm i=1,2$, let $\cm \beta \subset \delta_i \subseteq \alpha_i$,
$\cm A_i := J \bar U_{\delta_i} \bar V$, where 
$\cm \bar U_{\delta_i} := \bar U(\delta_i,:)$, 
and $\cm B_i := \KK^\dagger(D[\delta_i])$.
Let $\cm \bar Z \in \Ss^t$ be a particular solution of the linear systems
\[\cm
  \begin{array}{rcl}
    A_1 Z A_1^T & = & B_1 \\
    A_2 Z A_2^T & = & B_2.  
  \end{array}.\]
If the embedding dimension of $\cm D[\delta_i]$ is $\cm r$, for $\cm i=1,2$, but
the embedding dimension of $\cm \bar D := D[\beta]$ is $\cm r-1$, 
then the following holds.  cont\ldots
\end{block}
\end{frame}


\begin{frame}
\frametitle{$2$ (Inters.) Clique Expl. Compl.; Degen. cont\ldots}

\begin{block}{COR.  Clique-Degen. cont\ldots} 
The following holds:
\begin{enumerate}
  \item 
    $\cm \dim \NN(A_i) = 1$, for $\cm i=1,2$.
  \item 
For $\cm i=1,2$, let $\cm n_i \in \NN(A_i)$, $\cm \|n_i\|_2 = 1$, 
    and $\cm \Delta\!Z := n_1 n_2^T + n_2 n_1^T$. Then, 
    $\cm Z$ is a solution of the linear systems if and only if\\
    $\cm
      Z = \bar Z + \tau \Delta\!Z, 
      \quad \mbox{\color{rblue} for some }  \tau \in \RR$
  \item
    There are at most two nonzero solutions, $\cm \tau_1$ and $\cm \tau_2$,
          for the generalized eigenvalue
        problem $\cm -\Delta\!Z v = \tau \bar Z v$, $\cm v \neq 0$.
    Set $\cm Z_i := \bar Z + \frac{1}{\tau_i} \Delta\!Z$,  for $\cm i=1,2$. Then
    the {\color{rred} exact completion} is one of 
    {\color{rred} \fbox{$\cm D[\gamma] \in \left\{
        \KK(\bar U \bar V Z_i \bar V^T \bar U^T) : i=1,2 \right\}$}
	}
\end{enumerate}

\end{block}
\end{frame}

\subsection{Completing SNL; DELAYED use of Anchor
Locations}

\begin{frame}
	\frametitle{Completing SNL ({\crr Delayed} use of Anchor
Locations)}
	
	\begin{block}{Rotate to Align the Anchor Positions}
	
	\begin{itemize}
	
	\item Given $\cm P = 
			\begin{bmatrix}
			P_1 \cr
			P_2
			\end{bmatrix}
			\in \R^{n \times r}$ such that 
               $\cm D = \KK(PP^T)$
			
	\item Solve the orthogonal Procrustes problem:
	\[\cm 	
		\fbox{$
		\begin{array}{rc}
		\min 		& \|A-P_2Q\| \cr
		\mbox{s.t.}	& Q^TQ = I
		\end{array}
		$}
	\]
 $\cm P_2^TA=U\Sigma V^T$ SVD decomposition; set $\cm  Q=UV^T$;
	(Golub/Van Loan, Algorithm 12.4.1)
	
	\item Set $\cm X := P_1Q$
	
	\end{itemize}
	
	\end{block}
\end{frame}


%%\subsection{Clique Initialization and Clique Absorption of a Sensor}
%%
%%
%%
%%\begin{frame}
%%\frametitle{Clique Initialization}
%%
%%\begin{block}{LEMMA Clique Initialization 
%%{\color{lgreen} \quad (by triangle inequality)} }
%%For each $\cm i \in \{1,\ldots,n\}$, use half the radio range
%%and define the set
%%\[\cm
%%C_i := \left\{ j \in \{1,\ldots,n\} : D_{ij} \leq (R/2)^2 \right\}.
%%\]
%%Then each $\cm C_i$ corresponds to a clique of sensors that are
%%within radio range of each other.
%%\end{block}
%%\pause\uncover{
%%\begin{block}{Current Set of Cliques, $\cm \{C_i\}_{i\in \CC}$ }
%%indices $\cm \CC \subseteq 1:n$  corresponding to at
%%most $\cm n$ cliques
%%$\cm \{C_i\}_{i\in \CC}$.
%%\end{block}
%%}
%%\end{frame}
%%
%%
%%
%%
%%\begin{frame}
%%\frametitle{Node Absorbtion}
%%
%%\begin{block}{Clique $\cm C_i$ Absorbs Node $\cm j$}
%%
%%\begin{figure}[htb]
%%\epsfxsize=160pt
%%\centerline{\epsfbox{node_absorb.eps}}
%%\end{figure}
%%\end{block}
%%
%%
%%\end{frame}
%%
%%
%%\begin{frame}
%%\frametitle{Clique Absorption}
%%
%%\begin{block}{COROLLARY Clique Absorption}
%%Let  $\cm C_k$, for $\cm k\in \CC$, be a given clique with node 
%%$\cm l \notin  C_k$,
%%$\cm \beta := \left\{j_1,j_2,j_3\right\} \subseteq C_k$, 
%%and $\cm \max_{i=1,2,3} D_{lj_i} \leq R^2$. If
%%\vspace{-.15in}
%%\[\cm 
%%\rank \KK^\dagger (D[\beta]) = r,
%%\vspace{-.1in}
%%\]
%%then $\cm l$ can be absorbed by the clique $\cm C_k$; and, we can complete
%%the missing elements in column (row) $\cm l$ of $\cm D[C_k\cup \{l\}]$.
%%\end{block}
%%\begin{block}{COROLLARY Clique Absorption-Degenerate}
%%Similar to the {\color{rblue} degenerate case}
%% for the intersection, we can {\color{lgreen} use the lower
%%bound} and obtain clique absorption for the case that the embedding
%%dimension is only $\cm r-1$.
%%\end{block}
%%\end{frame}
%%
%%
%%%%
%%%%\begin{frame}
%%%%\frametitle{Node Absorbtion/Degenerate Case}
%%%%
%%%%\begin{block}{Clique $\cm C_i$ Absorbs Node $\cm j$/Degenerate Case}
%%%%
%%%%\begin{figure}[htb]
%%%%\epsfxsize=160pt
%%%%\centerline{\epsfbox{deg_node_absorb.eps}}
%%%%\end{figure}
%%%%\end{block}
%%%%
%%%%
%%%%\end{frame}
%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Algorithm: Facial Reduct. via Subsp. Inters./DELAYED Compl.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Clique Unions and Node Absorptions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace{-.15in}

\begin{frame}
	\frametitle{Algorithm: Four Cases}
\vspace{-.10in}
	\begin{center}
	\begin{tabular}{|c|c|c|}
		\hline
		& Clique Union & Node Absorption \\
		\hline
		Rigid &
		\raisebox{-8ex}{\includegraphics[height=3.25cm]{clique_intersect.eps}} &
		\raisebox{-8ex}{\includegraphics[height=2.90cm]{node_absorb.eps}} \\
		\hline
		Non-rigid & 
		\raisebox{-8ex}{\includegraphics[height=3.25cm]{deg_clique_intersect.eps}} &
		\raisebox{-8ex}{\includegraphics[height=2.90cm]{deg_node_absorb.eps}} \\
		\hline
	\end{tabular}
	\end{center}
\end{frame}




\begin{frame}
	\frametitle{ALGOR: clique union; facial reduct.; delay compl.}
	
	\begin{block}{Initialize: Find initial set of cliques.}
		$\cm
			C_i := \left\{ j : (D_p)_{ij} < (R/2)^2 \right\},
			\quad \mbox{\color{black} for } i=1,\ldots,n
		$
	\end{block}
\vspace{-.1in}
	
	\pause 
	\begin{block}{Iterate}
		\begin{itemize}
			\item For $\cm |C_i \cap C_j| \geq r+1$, do \alert{Rigid Clique Union}
			\item For $\cm |C_i \cap \NN(j)| \geq r+1$, do \alert{Rigid Node Absorption}
			\item For $\cm |C_i \cap C_j| = r$, do \alert{Non-Rigid Clique Union}
				(lower bnds)
			\item For $\cm |C_i \cap \NN(j)| = r$, do \alert{Non-Rigid Node Absorp.}
				(lower bnds)
		\end{itemize}
	\end{block}
	
	\pause
	\begin{block}{Finalize}
		When $\cm \exists$ a clique containing all \alert{anchors}, 
		use computed \alert{facial representation} and
		\alert{positions of anchors}
		to solve for $\cm X$
	\end{block}
	
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Results (low CPU time; high accuracy)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{frame}
	\frametitle{Results - Data for Random Noisless Problems}
	
	\begin{itemize}
		\item  2.16 GHz Intel Core 2 Duo, 2 GB of RAM
		\item Dimension $\cm r=2$ 
		\item Square region: $\cm [0,1] \times [0,1]$
		\item $\cm m = 9$ anchors
		\item Using only Rigid Clique Union and Rigid Node Absorption
		\item Error measure:  Root Mean Square Deviation
		\[\cm 
			\mbox{RMSD} = 
			\left( \frac{1}{n} \sum_{i=1}^n \| p_i - p_i^{\mbox{\tiny true}} \|^2 \right)^{1/2}
		\]
	\end{itemize}


\end{frame}


\begin{frame}
	\frametitle{Results - Large $\cm n$ \qquad (SDP size $\cm O(n^2)$)}

	\begin{footnotesize}
	\begin{center}
	\vspace{-.1in}
	{$\cm n$ \# of Sensors Located} \vspace{.05in}
	
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$\cm n$ \# sensors~\textbackslash~$R$ & $0.07$ & $0.06$ & $0.05$ & $0.04$
 \\
\hline
$2000$ & $2000$ & $2000$ & $1956$ & $1374$  \\
$6000$ & $6000 $ & $6000 $ & $6000 $ & $6000 $  \\
$10000$ & $10000 $ & $10000 $ & $10000 $ & $10000 $
\\ \hline
\end{tabular}
	
%\pause	
\vspace{.1in} {CPU Seconds}
		
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
 \# sensors~\textbackslash~$R$ & $0.07$ & $0.06$ & $0.05$ & $0.04$
 \\
\hline
$2000$ & $1$ & $1$ & $1$ & $3$  \\
$6000$ & $5$ & $5$ & $4$ & $4$  \\
$10000$ & $10$ & $10$ & $9$ & $8$
\\ \hline
\end{tabular}

%\pause	
\vspace{.1in} {RMSD (over located sensors)}
		
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$\cm n$ \# sensors~\textbackslash~$R$ & $0.07$ & $0.06$ & $0.05$ & $0.04$
 \\
\hline
$2000$ & $4e{-16}$ & $5e{-16}$ & $6e{-16}$ & $3e{-16}$  \\
$6000$ & $4e{-16}$ & $4e{-16}$ & $3e{-16}$ & $3e{-16}$  \\
$10000$ & $3e{-16}$ & $5e{-16}$ & $4e{-16}$ & $4e{-16}$
\\ \hline
\end{tabular}

	\end{center}
	\end{footnotesize}
	
\end{frame}



\begin{frame}
	\frametitle{Results - $\cm N$ Huge SDPs Solved}

	\begin{block}{Large-Scale Problems}

	\begin{footnotesize}
	\begin{center}
	
\begin{tabular}{|ccc|c|c|}
\hline
\# sensors & \# anchors & radio range & RMSD & Time
\\ \hline
$20000$ & 9 & $.025$ & $5e{-16}$ & $25$s \\
$40000$ & 9 & $.02$ & $8e{-16}$ & $1$m $23$s \\
$60000$ & 9 & $.015$ & $5e{-16}$ & $3$m $13$s \\
\hline
$100000$ & 9 & $.01$ & $6e{-16}$ & $9$m $8$s \\
\hline
\end{tabular}

	\end{center}
	\end{footnotesize}
	
	\end{block}

	\begin{block}{Size of SDPs Solved:
$\cm N=  \begin{pmatrix} n\cr 2 \end{pmatrix}$ (\# vrbls)}
$\cm  \E (\mbox{density of } \GG) = \pi R^2$;
$\cm M= \E ( |E|) = \pi R^2 N$ (\# constraints) \\
Size of SDP Problems:\\
$\cm M = \begin{bmatrix}3,078,915  & 12,315,351  & 27,709,309 &
76,969,790\end{bmatrix}$
$\cm N =
10^9 \begin{bmatrix} 0.2000  & 0.8000  & 1.8000  & 5.0000 \end{bmatrix} 
$
	\end{block}
\end{frame}




%%
%%\vspace{-.15in}
%%\begin{frame}
%%	\frametitle{$10$ random noiseless probs; $\cm r=2, m=9$}
%%\vspace{-.25in}
%%	
%%	\begin{tiny}
%%	\begin{center}
%%	\begin{tabular}{|c|c|}
%%	
%%	\hline
%%	& \\
%%	{\scriptsize  Rigid Clique Union} 
%%	& 
%%	{\scriptsize  Rigid Clique Union and Node Absorption}
%%	
%%	\\
%%	\hline
%%	& \\
%%	
%%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%%\hline
%%$n$~/~$R$ & $0.7$ & $0.6$ & $0.5$ & $0.4$  
%% \\
%%\hline
%%$2000$ & $1$ & $7$ & $91$ & $362$ \\
%%$4000$ & $1$ & $1$ & $1$ & $16$  \\
%%$6000$ & $1$ & $1$ & $1$ & $1$  \\
%%$8000$ & $1$ & $1$ & $1$ & $1$  \\
%%$10000$ & $1$ & $1$ & $1$ & $1$ 
%%\\ \hline
%%\end{tabular}
%%	
%%	&
%%	
%%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%%\hline
%%$n$~/~$R$ & $0.7$ & $0.6$ & $0.5$ & $0.4$    
%% \\
%%\hline
%%$2000$ & $1$ & $1$ & $2$ & $78$  \\
%%$4000$ & $1$ & $1$ & $1$ & $1$  \\
%%$6000$ & $1$ & $1$ & $1$ & $1$  \\
%%$8000$ & $1$ & $1$ & $1$ & $1$  \\
%%$10000$ & $1$ & $1$ & $1$ & $1$    
%%\\ \hline
%%\end{tabular}
%%
%%	\\
%%	& \\
%%	
%%	{Remaining Cliques} & {Remaining Cliques} 
%%	
%%	\\ \hline
%%	& \\
%%	
%%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%%\hline
%%$n$~/~$R$ & $0.7$ & $0.6$ & $0.5$ & $0.4$   
%% \\
%%\hline
%%$2000$ & $4.8$ & $4.6$ & $4.2$ & $4.1$  \\
%%$4000$ & $9.2$ & $9.4$ & $9.1$ & $9.2$  \\
%%$6000$ & $16.0$ & $14.7$ & $15.3$ & $14.9$  \\
%%$8000$ & $22.9$ & $22.5$ & $20.9$ & $21.0$  \\
%%$10000$ & $38.3$ & $32.7$ & $29.1$ & $30.7$    
%%\\ \hline
%%\end{tabular}
%%
%%	&
%%	
%%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%%\hline
%%$n$~/~$R$ & $0.7$ & $0.6$ & $0.5$ & $0.4$   
%% \\
%%\hline
%%$2000$ & $4.9$ & $4.9$ & $6.1$ & $13.2$  \\
%%$4000$ & $9.2$ & $9.5$ & $9.1$ & $9.8$  \\
%%$6000$ & $16.1$ & $15.1$ & $15.1$ & $14.8$  \\
%%$8000$ & $22.7$ & $22.4$ & $21.0$ & $21.3$ \\
%%$10000$ & $32.5$ & $32.4$ & $28.8$ & $30.6$  
%%\\ \hline
%%\end{tabular}
%%
%%	\\
%%	& \\
%%	
%%	{\color{rred} CPU Seconds} & {\color{rred} CPU Seconds} 
%%	
%%	\\ \hline
%%	& \\
%%	
%%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%%\hline
%%$n$~/~$R$ & $0.7$ & $0.6$ & $0.5$ & $0.4$   
%% \\
%%\hline
%%$2000$ & $-10.1$ & $-10.8$ & $-$ & $-$ \\
%%$4000$ & $-10.9$ & $-11.0$ & $-10.5$ & $-9.6$  \\
%%$6000$ & $-11.6$ & $-10.7$ & $-10.6$ & $-10.0$ \\
%%$8000$ & $-11.1$ & $-11.0$ & $-10.7$ & $-9.2$ \\
%%$10000$ & $-11.0$ & $-11.0$ & $-10.2$ & $-10.4$ 
%%\\ \hline
%%\end{tabular}
%%
%%	&
%%	
%%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%%\hline
%%$n$~/~$R$ & $0.7$ & $0.6$ & $0.5$ & $0.4$  
%% \\
%%\hline
%%$2000$ & $-10.1$ & $-10.8$ & $-9.8$ & $-8.8$  \\
%%$4000$ & $-10.9$ & $-11.0$ & $-10.5$ & $-9.6$  \\
%%$6000$ & $-11.6$ & $-10.7$ & $-10.6$ & $-10.0$  \\
%%$8000$ & $-11.1$ & $-11.0$ & $-10.7$ & $-9.2$  \\
%%$10000$ & $-11.0$ & $-11.0$ & $-10.2$ & $-10.4$    
%%\\ \hline
%%\end{tabular}
%%
%%	\\
%%	& \\
%%	
%%	{Max log(Error)} & {Max log(Error)} 
%%	
%%	\\
%%	\hline
%%
%%
%%	\end{tabular}
%%	\end{center}
%%	\end{tiny}
%%
%%
%%
%%
%%
%%\end{frame}
%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Noisy Data}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
	\frametitle{Locally Recover Exact EDMs}
\begin{block}{Nearest EDM}
\begin{itemize}
\item
Given clique $\cm \alpha$; corresp. \EDM
$\cm D_\epsilon=D+N_\epsilon$, $\cm N_\epsilon$ noise
\item
we need to find the smallest face containing 
$\cm \En(\alpha,D)$.
\item
$\cm \left\{\begin{array}{rll}
\min    &   \left \| \KK(X) - D_\epsilon \right\|  \\
\mbox{s.t.}   &   \rank (X) = r, Xe=0, X\succeq 0 \\
              &    X \succeq 0.
\end{array} \right.$
\item  Eliminate the constraints: $\cm Ve=0, V^TV=I$,
$\cm \KK_V(X):=\KK(VXV^T)$:
\[ \cm
\label{eq:bestapprox}
\begin{array}{rccl}
U^*_r &\in& 
\argmin    &   \frac 12\left \| \KK_V(UU^T) - D_\epsilon \right\|^2_F \\
&&\mbox{s.t.}   &   U \in M^{(n-1)r}.
\end{array}
\]
The nearest \EDM is $\cm D^*= \KK_V( U^*_r (U^*_r)^T)$.
\end{itemize}


\end{block}
\end{frame}


\begin{frame}
	\frametitle{Solve Overdetermined Nonlin.
Least Squares Prob.}

\begin{block}{Newton (expensive) or Gauss-Newton  (less
accurate)}
\[\cm
F(U):= \usvec\left(\KK_V(UU^T) - D_\epsilon\right), \quad
\min_U f(U):=\frac 12 \left \| F(U) \right\|^2
\]

\end{block}
\begin{block}{Derivatives: gradient and Hessian}
\[\cm
 \nabla f(U)(\Delta U) =
 \langle 2 \left(\KK_V^* \left[\KK_V(UU^T)-D_\epsilon\right] \right)U,
 \Delta U \rangle
\]
\[\cm
\nabla^2f(U) =
2 \kvec \left(
\LL_U^* \KK_V^* \KK_V \Ssum \LL_U  
+ \KK_V^* \left(\KK_V(UU^T)-D_\epsilon\right) 
\right)
\Mat 
\]
where
$\cm \LL_U(\cdot)=\cdot U^T$;\quad $\cm \Ssum (U)=\frac 12 (U+U^T)$  


\end{block}
\end{frame}



\begin{frame}
	\frametitle{random noisy probs; $\cm r=2, m=9,
nf=1e-6$}
\vspace{-.15in}

	\begin{itemize}
		\item Using only Rigid Clique Union, 
         preliminary results:\\

\begin{table}
\begin{tiny}
\begin{center} remaining cliques\qquad \qquad
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$~/~$R$ & $1.0$ & $0.9$ & $0.8$ & $0.7$ & $0.6$   
 \\
\hline
$1000$ & $1.00$ & $5.00$ & $11.00$ & $40.00$ & $124.00$ \\
$2000$ & $1.00$ & $1.00$ & $1.00$ & $1.00$ & $7.00$ \\
$3000$ & $1.00$ & $1.00$ & $1.00$ & $1.00$ & $1.00$ \\
$4000$ & $1.00$ & $1.00$ & $1.00$ & $1.00$ & $1.00$ \\
$5000$ & $1.00$ & $1.00$ & $1.00$ & $1.00$ & $1.00$   
\\ \hline
\end{tabular}
\end{center}
\end{tiny}
\end{table}


\begin{table}
\begin{tiny}
\begin{center}cpu seconds \qquad \qquad
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$~/~$R$ & $1.0$ & $0.9$ & $0.8$ & $0.7$ & $0.6$   
 \\
\hline
$1000$ & $9.43$ & $6.98$ & $5.57$ & $5.04$ & $4.05$ \\
$2000$ & $12.46$ & $12.18$ & $12.43$ & $11.18$ & $9.89$ \\
$3000$ & $18.08$ & $18.50$ & $19.07$ & $18.33$ & $16.33$ \\
$4000$ & $25.18$ & $24.01$ & $24.02$ & $23.80$ & $22.12$ \\
$5000$ & $38.13$ & $31.66$ & $30.26$ & $30.32$ & $29.88$   
\\ \hline
\end{tabular}
\end{center}
\end{tiny}
\end{table}



\begin{table}
\begin{tiny}
\begin{center}
   max-log-error \qquad \qquad
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$~/~$R$ & $1.0$ & $0.9$ & $0.8$ & $0.7$ & $0.6$   
 \\
\hline
$1000$ & $-3.28$ & $-4.19$ & $-2.92$ & $Inf$ & $Inf$ \\
$2000$ & $-3.63$ & $-3.81$ & $-3.82$ & $-2.39$ & $-3.73$ \\
$3000$ & $-3.51$ & $-3.98$ & $-3.25$ & $-3.90$ & $-3.28$ \\
$4000$ & $-4.15$ & $-4.05$ & $-3.52$ & $-3.04$ & $-3.33$ \\
$5000$ & $-4.80$ & $-4.38$ & $-3.89$ & $-4.13$ & $-3.40$   
\\ \hline
\end{tabular}
\end{center}
\end{tiny}
\end{table}

	
\end{itemize}




\end{frame}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Summary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
  \frametitle<presentation>{Summary}

  	% Keep the summary *very short*.
	\begin{itemize}
  
  	\item SDP relaxation of SNL is highly (implicitly) degenerate:
  		The feasible set of this SDP is restricted to a low dim. face of the SDP
  		cone, causing the Slater constraint qualification (strict feasibility) to fail
  
  	\pause
	\item We take advantage of this degeneracy by finding
		explicit representations of intersections
  of faces of the SDP cone corresponding to
		unions of intersecting cliques
		
  	\pause
	\item \underline{Without} using an SDP-solver (eg. SeDuMi or SDPT3), 
  		we quickly compute the exact solution to the SDP relaxation
 
  \end{itemize}
  
\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{}

\small{
\bibliographystyle{amsplain}
\bibliography{.master,.edm,.psd,.bjorBOOK}
}


\end{frame}



\begin{frame}
\frametitle{
Thanks for your attention!}
%\hypertarget{targetname}{text} to create target.
%Some useful buttons are \beamerbutton, \beamergotobutton,
%and \beamerreturnbutton.
%To go to the last slide, click here .
\titlepage
\end{frame}



\end{document}