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 also propose a method of projection when a large clique is identified in the underlying graph. This projection reduces the size, and
improves the stability, of the relaxation.
In addition, viewing the problem as a EDM completion problem yields
better low rank approximations for the low dimensional realizations.
This approach shows that 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.
In addition, we discuss the relative stability and strength of the
different formulations and the corresponding algorithms that are used.