ncku-talk2011-04-13

NCTS(South)/ NCKU Math Colloquium

DATE 2011-04-13　14:00-16:00

PLACE R204, 2F, NCTS, NCKU

SPEAKER Professor Makoto Yamashita（Tokyo Institute of Technology）

TITLE Part 1. Exploiting Sparsity in Sensor Network Localization Problem with the framework of SDP relaxation

ABSTRACT In the sensor network localization problem, we consider a situation in which sensors are scattered in a 2D or 3D region. If we know the exact sensors' locations, it is easy to compute the distance between some sensor-sensor pairs. However, its inverse is known as NP-hard problem; if the distances of some pairs are given, can we obtain the sensor locations? Biswas-Ye proposed a novel method based on Semidefinite Programming relaxation to obtain excellent approximate locations. We enhance its computational efficiency by focusing on a network structure of given sensor-sensor pairs and exploiting sparsity of the structure. We implement our methods into a software package SFSDP.

NCTS(South)/ NCKU Math Colloquium

DATE	2011-04-13　14:00-16:00

PLACE	R204, 2F, NCTS, NCKU

SPEAKER	Professor Makoto Yamashita（Tokyo Institute of Technology）

TITLE	Part 1. Exploiting Sparsity in Sensor Network Localization Problem with the framework of SDP relaxation

ABSTRACT	In the sensor network localization problem, we consider a situation in which sensors are scattered in a 2D or 3D region. If we know the exact sensors' locations, it is easy to compute the distance between some sensor-sensor pairs. However, its inverse is known as NP-hard problem; if the distances of some pairs are given, can we obtain the sensor locations? Biswas-Ye proposed a novel method based on Semidefinite Programming relaxation to obtain excellent approximate locations. We enhance its computational efficiency by focusing on a network structure of given sensor-sensor pairs and exploiting sparsity of the structure. We implement our methods into a software package SFSDP.