at the Technion, May 18-21, 2009;
under the auspices of the Technion's Center for
Mathematical Sciences.
This will be the fifteenth in a sequence of matrix theory conferences
held at the Technion since 1984.

pictures from the conference
e.g.
group picture;
... Miroslav Fiedler, Ludwig Elsner, Henry Wolkowicz, Hans Schneider,
Thomas Laffey ...;
Olga Holtz, Avi Berman, Shmuel Friedland

##
Title:
Sensor Network Localization, Euclidean Distance Matrix Completions,
and Graph Realization
( talk pdf file,
( talk ps file)
(
related paper)

####
speaker: Henry Wolkowicz (joint work with Nathan Krislock)

Department of Combinatorics and Optimization,
University of Waterloo,
Canada

Abstract (pdf)

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 feasble 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. In this paper, we take advantage of the absence of the Slater
constraint qualification and derive a
preprocessing technique that solves the SNL problem,
with exact data, by explicitly solving the corresponding SDP problem.
We do this by finding explicit representations of the faces of the SDP
cone corresponding to intersections of cliques of the SNL problem.