Localization from Incomplete Noisy Distance Measurements

Abstract

We consider the problem of positioning a cloud of points in the Euclidean space ${\mathbb{R}}^d$, using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. 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 local (or partial) metric information. Here we propose a reconstruction algorithm based on semidefinite programming. For a random geometric graph model and uniformly bounded noise, we provide a precise characterization of the algorithm's performance: In the noiseless case, we find a radius $r_0$ beyond which the algorithm reconstructs the exact positions (up to rigid transformations). In the presence of noise, we obtain upper and lower bounds on the reconstruction error that match up to a factor that depends only on the dimension $d$, and the average degree of the nodes in the graph.

46 pages, 8 figures, numerical experiments added. Journal version (v1,v2: Conference versions, ISIT 2011); Journal of Foundations of Computational Mathematics, 2012

References in corpus (1)

• On Sensor Network Localization Using SDP Relaxation

Cited by in corpus (21)

• Matrix estimation by Universal Singular Value Thresholding
• Distributed Maximum Likelihood Sensor Network Localization
• Convex recovery from interferometric measurements
• Localization from Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD-MDS Approach
• Learned multi-stability in mechanical networks
• Calibration Using Matrix Completion with Application to Ultrasound Tomography
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
• Large-Scale Sensor Network Localization via Rigid Subnetwork Registration
• Adapting to Unknown Noise Distribution in Matrix Denoising
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
• A Perturbation Inequality for the Schatten-$p$ Quasi-Norm and Its Applications to Low-Rank Matrix Recovery
• Iterative Universal Rigidity
• Accuracy of Range-Based Cooperative Localization in Wireless Sensor Networks: A Lower Bound Analysis
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• An Algorithm for Exact Super-resolution and Phase Retrieval
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
• Central Limit Theorems for Classical Multidimensional Scaling
• Robust Localization from Incomplete Local Information
• A Less Noise-Sensitive SDP Relaxation in Wireless Sensor Network Localization