SFSDP

(A Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems)

Sunyoung Kim, Masakazu Kojima, Hayato Waki, and Makoto Yamashita

August, 2008. Revised January, 2010

SFSDP is a Matlab package for solving sensor network localization problems. The package contains  four functions, SFSDP.m, SFSDPplus.m, generateProblem.m, test_SFDP.m, and  some numerical examples. The function SFSDP.m is an Matlab implementation of the semidefinite programming relaxation  proposed in the paper [2] by Kim, Kojima and Waki for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP)  by Biswas and Ye [1]. To improve the efficiency of FSDP, SFSDP.m  exploits the aggregated and correlative sparsity of a sensor network localization problem. See also [3].

[1] P. Biswas and Y. Ye, "Semidefinite programming for ad hoc wireless sensor network localization," in Proceedings of the third international symposium on information processing in sensor networks, ACM press, 46-54  (2004).

[2] S. Kim, M. Kojima, and H. Waki, "Exploiting sparsity in SDP relaxation for sensor network localization," SIAM Journal of Optimization Vol.20 (1) 192-215 (2009).

[3] S. Kim, M. Kojima, H. Waki, M. Yamashita, " SFSDP: a Sparse version of Full SemiDefinite Programming relaxation for sensor network localization problems," Research Report B-457, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, July 2009, Revised January 2010.


If you have any questions, please send a message to kojima.m.aa-sfsdp "insert at mark" m.titech.ac.jp