##### Department of Mathematics,

University of California San Diego

****************************

### Math 295 - Mathematics Colloquium

## Paul Tseng

#### University of Washington

## On SDP and ESDP Relaxation for Sensor Network Localization

##### Abstract:

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 than the SDP and, in simulation, yields solution about as accurate as the SDP relaxation. We show that, when the distance measurements are exact, we can determine which sensors are correctly positioned in the ESDP solution by checking if their individual traces are zero. On the other hand, we show that, when the distance measurements are inexact, this check is unreliable for both ESDP and SDP solutions. We then propose a robust version of ESDP relaxation for which small individual trace is a reliable check of sensor position accuracy. Moreover, the position error for such a sensor is in the order of the square root of its trace. Lastly, we propose a coordinate gradient descent method, using log-barrier penalty, to solve ESDP. This method is more efficient than interior-point method for solving SDP or ESDP and is implementable in a distributed manner. (This is joint work with Ting Kei Pong.)

### March 19, 2009

### 4:00 PM

### AP&M 6402

****************************