(Robust) Edge-based semidefinite programming relaxation of sensor network localization

Ting Kei Pong, Paul Tseng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

19 Citations (Scopus)


Recently Wang, Zheng, Boyd, and Ye (SIAM J Optim 19:655-673, 2008) proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, named edge-based SDP (ESDP). In simulation, the ESDP is solved much faster by interior-point method than SDP relaxation, and the solutions found are comparable or better in approximation accuracy. We study some key properties of the ESDP relaxation, showing that, when distances are exact, zero individual trace is not only sufficient, but also necessary for a sensor to be correctly positioned by an interior solution. We also show via an example that, when distances are inexact, zero individual trace is insufficient for a sensor to be accurately positioned by an interior solution. We then propose a noise-aware robust version of ESDP relaxation for which small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution, assuming the noise level is sufficiently small. For this analytic center solution, the position error for each sensor is shown to be in the order of the square root of its trace. Lastly, we propose a log-barrier penalty coordinate gradient descent method to find such an analytic center solution. In simulation, this method is much faster than interior-point method for solving ESDP, and the solutions found are comparable in approximation accuracy. Moreover, the method can distribute its computation over the sensors via local communication, making it practical for positioning and tracking in real time.
Original languageEnglish
Pages (from-to)321-358
Number of pages38
JournalMathematical Programming
Issue number2
Publication statusPublished - 1 Dec 2011
Externally publishedYes


  • Coordinate gradient descent
  • Error bound
  • Log-barrier
  • Semidefinite programming relaxation
  • Sensor network localization

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this