\documentclass[11pt]{article}
\setlength{\topmargin}{-0.54cm}
\setlength{\headheight}{0cm}
\setlength{\headsep}{0cm}
\setlength{\topskip}{0cm}
\setlength{\textwidth}{14.0cm}
\setlength{\textheight}{20.5cm}
\setlength{\evensidemargin}{1.46cm}
\setlength{\oddsidemargin}{1.46cm}
\setlength{\marginparsep}{0cm}
\setlength{\marginparwidth}{0cm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\def\SDPt{{\bf SDP\,}}
\def\SDP{\mbox{\boldmath$SDP\,$}}
\def\SDPc{{\mbox{\boldmath$SDP$,\,}}}
\def\EDM{\mbox{\boldmath$EDM\,$}}
\def\EDMc{\mbox{\boldmath$EDM$,\,}}
\def\SNL{\mbox{\boldmath$SNL\,$}}
\def\SNLt{{\bf SNL\,}}
\parindent 0pt
\pagestyle{empty}
%-----------------------------------------------------------------------------
\begin{document}
$\ $\hspace{-1.46cm}\rule{17cm}{0.4mm}\par
$\ $\hspace{-1.46cm}{\bf\sffamily Fixed-Point Algorithms for 
Inverse Problems in Science and Engineering}\par
$\ $\hspace{-1.46cm}{\sffamily Banff International Research Station, Canada}\par
$\ $\hspace{-1.46cm}{\sffamily November 1--6, 2009}\par
\vskip -2mm
$\ $\hspace{-1.46cm}\rule{17cm}{0.4mm}
\vspace{1cm}\par

\begin{center}
{
\large
{\bfseries \uppercase{Sensor Network Localization, Euclidean Distance Matrix Completions,
and Graph Realization}}\\
\normalsize
\vspace*{0.6cm}
{\bfseries Nathan Krislock$^{1}$ and Henry Wolkowicz$^{1}$\\
\vspace*{0.4cm}
$^{1}$Dept. Combinatorics \& Optimization\\ University of Waterloo\\
Waterloo, Ontario\\
\vspace*{0.4cm}}
}
\end{center}



Wireless sensor networks have many applications, e.g. in monitoring physical
or environmental conditions (temperature, sound, vibration, pressure,
battlefield surveillance, home automation, hospital patients,
traffic control, etc.).
The sensor network localization, \SNL, problem consists of locating 
the positions of ad hoc wireless sensors, given only the 
distances between sensors that are within
radio range and the positions of a subset of the sensors (called anchors).
One main point is to view \SNL as a
(nearest) Euclidean Distance Matrix, \EDM, completion problem that does
not distinguish between the anchors and the sensors.
We show that there are advantages for using the well-studied \EDM model.
This problem can be relaxed to a weighted, nearest, (positive) semidefinite
programming, \SDP, completion problem. This relaxation is ill-conditioned in two ways.
First, it is, implicitly, highly degenerate in the
sense that the feasible set is restricted to a low dimensional face of
the \SDP cone.
This means that the Slater constraint qualification fails.
Second, nonuniqueness of the optimal solution results in large sensitivity
to small perturbations in the data.


The degeneracy in the \SDP arises from cliques in the graph of the 
\SNL problem.  We take advantage of the absence of the Slater
constraint qualification and derive a
preprocessing technique that solves the \SNL problem.
With exact data, we explicitly solve the corresponding \SDP problem
without using any \SDP solver.
We do this by finding explicit representations of the faces of the \SDP
cone corresponding to intersections of cliques of the \SNL problem.
For problems with noise, we first solve nearest matrix problems to get
best \EDM approximations.


%%
%%The {\bfseries 1-page} 
%%summary of your talk starts here (everything must fit 
%%in {\bfseries 1-page}!). 
%%You can cite references [1],
%%[2] etc. Please use the reference style shown below.
%%You must submit this \LaTeX~file (no dvi, ps, pdf, etc.).
%%
%%\vspace*{0.6cm} \par 
%%\noindent {\bf References }\medskip\par
%%\vspace*{0.1cm}  
%%
%%\noindent [1] 
%%P. L. Combettes and J.-C. Pesquet, 
%%A Douglas-Rachford splitting approach to nonsmooth convex 
%%variational signal recovery,
%%{\em IEEE J. Selected Topics Signal Process.,}
%%{\bfseries 1} (2007), 564--574.
%%\medskip\par
%%
%%\noindent [2] 
%%P. L. Combettes and V. R. Wajs, 
%%Signal recovery by proximal forward-backward splitting,
%%{\em Multiscale Model. Simul.,} 
%%{\bfseries 4} (2005), 1168--1200.
%%\medskip\par
%%
%%\noindent [3] 
%%I. Daubechies,  M. Defrise and C. De Mol,
%%An iterative thresholding algorithm for linear
%%inverse problems with a sparsity constraint,
%%{\em Comm. Pure Appl. Math.}, {\bfseries 57} (2004), 1413--1457.
%%\medskip\par
%%
%%\noindent [4] 
%%{ D.~R. Luke}, 
%%{Finding Best Approximation Pairs Relative to 
%%a Convex and a Prox-regular Set in {H}ilbert Space}, 
%%{\em SIAM J. Optim.}, {\bfseries 19} (2008), 714--739.
%%\medskip\par
%%
%%\noindent [5] 
%%G. Oszl\'anyi and A. S\"ut\'o, The charge flipping algorithm,
%%{\em Acta Cryst. A}, {\bfseries 64} (2008) 123--134.
%%\medskip\par
%%
%%\noindent[6] 
%%J. Rehmeyer, The Sudoku Solution, {\em Science News}, 
%%December 23, 2008.
%%\medskip\par
\end{document}