2012/10/18 by Venkatesan Ekambaram, Giulia Fanti, Ekambaram, Venkatesan +3
Computer Science · Engineering · #FOS: Computer and information sciences #Indoor and Outdoor Localization Technologies #Information Theory (cs.IT) #Multiagent Systems (cs.MA) #Networking and Internet Architecture (cs.NI) #Sparse and Compressive Sensing Techniques #Target Tracking and Data Fusion in Sensor Networks
paper · pdf · doi:10.48550/arxiv.1210.5031
openalex publication_date 2012/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of estimating the locations of a set of points in a k-dimensional euclidean space given a subset of the pairwise distance measurements between the points. We focus on the case when some fraction of these measurements can be arbitrarily corrupted by large additive noise. Given that the problem is highly non-convex, we propose a simple semidefinite programming relaxation that can be efficiently solved using standard algorithms. We define a notion of non-contractibility and show that the relaxation gives the exact point locations when the underlying graph is non-contractible. The performance of the algorithm is evaluated on an experimental data set obtained from a network of 44 nodes in an indoor environment and is shown to be robust to non-line-of-sight errors.