Given a subset of all the pair-wise 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 non-convex optimization problem. In this thesis, we introduce a polynomial-time 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 pair-wise 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 3-D 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.
Citation
PhD. Thesis, Department of Electrical Engineering, Stanford University. http://pratik.biswas.googlepages.com
Article
View Semidefinite Programming Approaches to Distance Geometry Problems