  


Semidefinite Programming Approaches to Distance Geometry Problems
Pratik Biswas (pratik.biswasgmail.com) Abstract: Given a subset of all the pairwise distances between a set of points in a fixed dimension, and possibly the positions of few of the points (called anchors), can we estimate the (relative) positions of all the unknown points (in the given dimension) accurately? This problem is known as the Euclidean Distance Geometry or Graph Realization problem, and generally involves solving a hard nonconvex optimization problem. In this thesis, we introduce a polynomialtime solvable Semidefinite Programming (SDP) relaxation to the original formulation. The SDP yields higher dimensional solutions when the given distances are noisy. To alleviate this problem, we adopt ideas from dimensionality reduction and use local refinement to improve the estimation accuracy of the original relaxation. We apply this algorithm to Wireless Sensor Network Localization; i.e., estimating the positions of nodes in a wireless network using pairwise distance information (acquired from communications between the nodes within ‘hearing’ range of each other). Using this ‘cooperative’ approach, we can estimate network structures with very few anchors, and low communication range, offering a distinct advantage over schemes like GPS triangulation. As the number of unknown points increases, the problem starts becoming computationally intractable. We describe an iterative and distributed approach to realize the structure of a graph, even in the absence of anchor points. This algorithm is implemented for Molecule Conformation; i.e., finding the 3D structure of a molecule, given just the ranges on a few interatomic distances (acquired by Nuclear Magnetic Resonance measurements). We are able to derive accurate structures of molecules with thousands of atoms, with sparse and noisy interatomic distance data. We also extend these formulations to solve the problem of position estimation using angle information. Once again, we demonstrate the working of the algorithm for real life systems, in this case, image based sensor networks. Keywords: Semidefinite Programming Relaxations, Graph Realization, Sensor Network Localization, Molecule Conformation Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Global Optimization (Applications ) Citation: PhD. Thesis, Department of Electrical Engineering, Stanford University. http://pratik.biswas.googlepages.com Download: [PDF] Entry Submitted: 12/11/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  