University of Washington
Recently Wang, Zheng, Boyd, and Ye proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, which they called edge-based SDP (ESDP). We show that, when there is no noise in the distance measurements, the zero trace condition is not only necessary but also sufficient for a sensor to be correctly positioned. We show by example that the zero trace is not a reliable certificate of accuracy when there is noise in the distance measurements. Finally, we propose a robust version of the ESDP relaxation for which small trace is a good certificate of accuracy. The position error is provably to be in the order of the square root of its trace. This is an ongoing work with Paul Tseng.
University of Washington