\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{SIAM Conference on Applied Linear Algebra\\
{\cg Monterey, Oct. 26-29, 2009}}

%\date{Interdisciplinary Workshop on Fixed-Point Algorithms for Inverse Problems
%in Science and Engineering\\
%{\cg BIRS, Nov. 1-6, 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}

%%
%%\begin{frame}
%%  \frametitle{Proceedings Call for Papers}
%%  \begin{block}{Refereed Volume of Selected Papers from the Workshop}
%%$\cg \bullet$
%%  {\cg Interdisciplinary Workshop on: Fixed-Point Algorithms for Inverse Problems in Science and Engineering}\\
%%$\crr \bullet$
%%{\crr We are planning to publish the best papers from the workshop
%%in the series entitled: Springer Optimization and Its Applications.}\\
%%
%%$\cg \bullet$
%%Please submit your paper to one of the editors/organizers: \\
%%Heinz Bauschke;
%% Regina Burachik;
%% Patrick Combettes;
%% Veit Elser;
%% Henry Wolkowicz.
%%
%%$\cg \bullet$
%%Deadline: May 1, 2009.
%%  \end{block}
%%\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}{
	\href{http://www.businessweek.com/1999/99_35/b3644024.htm}{
	%Horst Stormer (Nobel Prize, Physics, 1998), 
	``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{-.04in}
$\cm \rank B = r$;
 $\cm D \in \En$ be corresponding \EDM.
\vspace{-.15in}
\[ \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{Popular 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\{\left\| H\circ\left(\KK(B) - D\right) \right\|: 
\underline{\color{rred} \fbox{$\cm \rank B\leq r$}} \right\}$;\\
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{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}{}
	$\bullet$
$\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).$

	$\bullet$
All faces of $\cm \Snp$ are exposed.
\end{block}
\begin{block}{Faces of cone $K$}
\begin{itemize}
\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}

\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; 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Clique Unions and Node Absorptions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%\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{Numerics (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   \mathbb{E}  (\mbox{density of } \GG) = \pi R^2$;
$\cm M= \mathbb{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{Noisy Data: 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:\\
  		feasible set is restricted to a low dim. face \\
  		(Slater CQ - strict feasibility - fails)
  
  	\pause
	\item take advantage of degeneracy using
		explicit representations of intersections
  of faces corresponding to
		unions of intersecting cliques
		
  	\pause
	\item \underline{Without} using an SDP-solver, 
  		we efficiently compute exact solutions to SDP
		relaxation\\
		(dual/extended view of geometric buildup)
 
  \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}