Abstract:

We present semidefinite programming (SDP) based approaches for the position estimation problem in Euclidean distance geometry such as sensor network localization. We develop an SDP relaxation model and use the duality theory to derive necessary and/or sufficient conditions for whether a network is "localizable" or not, when the distance measures are accurate. We also present error analyses of the SDP solution when the distance measures are noisy. More importantly, we develop a further relaxation such that large-scale problems can be solved, and demonstrate computational results to show the effectiveness of the new relaxation model.