Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization
Speaker: | Henry Wolkowicz |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.
This
is
joint
work
with
Nathan
Krislock.