##
Minisymposium on Rank Minimization

###
Title:
Explicit Sensor Network Localization using Semidefinite Programming and
Clique Reductions

(Authors: Nathan Krislock and __Henry Wolkowicz__)
ABSTRACT:

The sensor network localization, \SNL, problem in embedding dimension
$r$, 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).
\index{radio range, $R$}
There are advantages for formulating this problem as a Euclidean distance matrix
completion, \EDMCc problem, and ignoring the distinction between anchors and
sensors.
Current solution techniques relax this problem
to a weighted, nearest, (positive) semidefinite
programming, \SDP, completion problem, by
using the linear mapping between \EDMs and \SDP matrices.
The relaxation consists in ignoring the rank $r$ for the \SDP matrices.
The resulting \SDP is solved using primal-dual interior point solvers,
yielding an expensive and inexact solution.

Moreover, the 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. These cliques implicitly restrict the dimension of the face
containing the feasible \SDP matrices.
In this paper, we take advantage of the absence of the Slater
constraint qualification and derive a technique for the \SNL problem,
with exact data, that explicitly solves the corresponding
rank restricted \SDP problem. No \SDP solvers are used.
We are able to efficiently solve this NP-hard problem with high probability,
by finding a representation of the minimal face of the \SDP
cone that contains the \SDP matrix representation of the \EDM.
The main work of our algorithm
consists in repeatedly finding the intersection of subspaces that
represent the faces of the \SDP cone that correspond
to cliques of the \SNL problem.