Abstract: We present semidefinite programming (SDP) based approaches for the position estimation problem in Euclidean distance geometry such as graph realization and 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 “realizable or localizable” or not, when the distance measures are accurate. We also present error analyses of the SDP solution when the distance measures are noisy. Furthermore, we develop a further relaxation such that large-scale problems can be solved efficiently, and demonstrate computational results to show the effectiveness of the SDP relaxation model.
- This event has passed.