(Robust) edge-based semidefinite programming relaxation of sensor network localization (Q652286): Difference between revisions

The paper deals with certain semidefinite programming (SDP) relaxations of the, in general NP-hard, ad hoc wireless sensor network localization problem. In particular, the authors study key properties of a SDP relaxiation and of the recently proposed edge-based SDP relaxation (ESDP). An outcome of this study is that these relaxations are more sensitive to noise than a second order cone-programming (SOCP) relaxation. To dampen this sensitivity the authors introduce a noise-aware robust version of the ESDP relaxation for which a small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution if the noise level is sufficiently small. For finding such a solution they suggest a log-barrier penalty coordinate gradient descent method. In simulations this method turns out to be much faster than a primal-dual interior-point method for the solution of the ESDP problem and to produce solutions of a comparable accuracy. The method is suitable for positioning and tracking in real time.