Return to Colloquia & Seminar listing
Theory and Computation of Semidefinite Programming for Sensor Network Localization and Graph Realization
Applied MathSpeaker: | Yinyu Ye, Stanford University |
Location: | 693 Kerr |
Start time: | Fri, Oct 7 2005, 4:10PM |
We describe a semidefinite programming (SDP) based model and method for the position estimation problem in Euclidean distance geometry such as wireless sensor network localization and molecular confirmation. The optimization problem is set up so as to minimize the error in sensor positions to fit incomplete and noisy distance measures. 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; and present a polynomial-time algorithm to locate it if it is ``localizable.'' We also present probabilistic analyses of the SDP solution when the distance measures are noisy. In all cases, observable gauges are developed to certify the quality of the position estimation of every sensor and to detect possible erroneous sensors. Furthermore, we develop a gradient-based local search method to round and improve the SDP solution. Computational solvers will be demonstrated to show the effectiveness of the method.