2011 Poster Sessions : Localization from Incomplete Noisy Distance Measurements

Student Name : Adel Javanmard
Advisor : Andrea Montanari
Research Areas: Information Systems
We consider the problem of positioning a cloud of points in the d-dimensional Euclidean space, using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localizations, NMR spectroscopy of proteins, and molecular conformation. Also, it is closely related to dimensionality reduction problems and manifold learning, where the goal is to learn the underlying global geometry of a data set using measured local (or partial) metric information. Here we propose a reconstruction algorithm based on a semi-definite programming approach. For a random geometric graph model, we provide a rigorous analysis of the algorithm's performance, and show that it has near-optimal robustness property. This work investigates some practically important questions about localization. As an instance, in the context of ad-hoc sensor networks, it shows how the radio range and the measurement noise affect the estimation error.

Adel Javanmard is a PhD candidate at Stanford University, Department of Electrical Engineering, working with professor Andrea Montanari. His research focuses on geometric inference problems. Before joining Stanford in 2009, he received B.S. degrees in Electrical Engineering and Mathematics from Sharif University of Technology.