Title

:

On the ESDP Relaxation for Sensor Network Localization

Speaker

:

Prof. Paul Tseng

Date

:

February 18th, 2008 (Monday)

Time

:

4:30 p.m. - 5:30 p.m.

Venue

:

Room 513

William M.W. Mong Engineering Building

(Engineering Building Complex Phase 2)

CUHK

Recently Wang, Zheng, Boyd, and Ye proposed a further convex relaxation of the SDP relaxation for the sensor network localization problem, which they called edge-based SDP (ESDP). The ESDP is easier to solve by interior-point method than the SDP and, in
simulation, yields solution about as accurate as the SDP relaxation. We prove that, in the noiseless case, zero trace is not only sufficient, but also necessary for a sensor to be uniquely (and hence correctly) positioned, assuming the ESDP solution lies in the relative
interior of the solution set. On the other hand, in the noisy case, zero trace does not imply a sensor is accurately positioned--even when the ESDP solution is unique. We then propose a robust version of ESDP relaxation for which small trace is a reliable certificate of sensor position accuracy. Moreover, the position error for such a sensor is provably in the order of the square root of its trace. (This is ongoing work with Ting Kei Pong.)

Paul Tseng received his B.Sc. from Queens University in 1981 and his Ph.D. from MIT in 1986. After spending one year at the University of British Columbia and three years at LIDS in MIT, he joined the University of Washington in 1990, where he remained since. His research area is mainly in continuous optimization, with side interests in discrete optimization, distributed computation, network/graph algorithms. He likes to optimize his travels by bicycle or kayak.

Host

:

Prof. Shuzhong Zhang

Tel

:

(852) 2609 8240

Email

:

zhang@se.cuhk.edu.hk

Enquiries

:

Prof. Nan Chen or Prof. Sean X. Zhou

:

Department of Systems Engineering and Engineering Management

CUHK

Website

:

http://www.se.cuhk.edu.hk/~seg5810

Email

:

seg5810@se.cuhk.edu.hk