Exploiting Sparsity in SDP Relaxation for Sensor Network Localization

A sensor network localization problem can be formulated as a quadratic optimization problem (QOP). For quadratic optimization problems, semidefinite programming (SDP) relaxation by Lasserre with relaxation order 1 for general polynomial optimization problems (POPs) is known to be equivalent to the sparse SDP relaxation by Waki {¥it et al.} with relaxation order 1, except the size and sparsity of the resulting SDP relaxation problems. We show that the sparse SDP relaxation applied to the QOP is at least as strong as the Biswas-Ye SDP relaxation for the sensor network localization problem. A sparse variant of the Biswas-Ye SDP relaxation, which is equivalent to the original Biswas-Ye SDP relaxation, is also derived. Numerical results are compared with the Biswas-Ye SDP relaxation and the edge-based SDP relaxation by Wang {¥it et al.}. We show that the proposed sparse SDP relaxation is faster than the Biswas-Ye SDP relaxation. In fact, the computational efficiency in solving the resulting SDP problems increases as the number of anchors and/or the radio range grow. The proposed sparse SDP relaxation also provides more accurate solutions than the edge-based SDP relaxation when exact distances are given between sensors and anchors and there are only a small number of anchors.