Semi-Definite Programming Relaxation for Non-Line-of-Sight Localization

Venkatesan Ekambaram, Giulia Fanti and Kannan Ramchandran

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2012-189
August 18, 2012

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-189.pdf

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.


BibTeX citation:

@techreport{Ekambaram:EECS-2012-189,
    Author = {Ekambaram, Venkatesan and Fanti, Giulia and Ramchandran, Kannan},
    Title = {Semi-Definite Programming Relaxation for Non-Line-of-Sight Localization},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2012},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-189.html},
    Number = {UCB/EECS-2012-189},
    Abstract = {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.}
}

EndNote citation:

%0 Report
%A Ekambaram, Venkatesan
%A Fanti, Giulia
%A Ramchandran, Kannan
%T Semi-Definite Programming Relaxation for Non-Line-of-Sight Localization
%I EECS Department, University of California, Berkeley
%D 2012
%8 August 18
%@ UCB/EECS-2012-189
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-189.html
%F Ekambaram:EECS-2012-189