abstract
We study Semidefinite Programming, SDP, relaxations for
Sensor Network Localization, SNL, with anchors and
with noisy distance information.
The main point of the paper is to view SNL as a
(nearest) Euclidean Distance Matrix, EDM, completion problem and to show the
advantages for using this latter, well studied model.
We first show that the current popular SDP relaxation is equivalent to
known relaxations in the literature for EDM completions.
The existence of anchors in the problem is not special. The
set of anchors simply
corresponds to a given fixed clique for the graph of the EDM problem.
We next propose a method of projection when a large clique
or a dense subgraph is identified
in the underlying graph. This projection reduces the size, and
improves the stability, of the relaxation.
In addition, viewing the problem as an EDM completion problem yields
better low rank approximations for the low dimensional realizations.
And, the projection/reduction
procedure can be repeated for other given cliques of sensors or for sets of
sensors, where many distances are known. Thus, further size reduction can
be obtained.
Optimality/duality conditions
and a primal-dual interior-exterior path following algorithm are
derived for the SDP relaxations
We discuss the relative stability and strength of two
formulations and the corresponding algorithms that are used.
In particular, we show that the quadratic formulation arising from the
SDP relaxation is better conditioned than the linearized form, that
is used in the literature and that arises from applying a Schur complement.