Sensor network localization, Euclidean distance matrix completions, and graph realization
From MaRDI portal
Publication:374660
DOI10.1007/S11081-008-9072-0zbMATH Open1273.74387arXivmath/0612388OpenAlexW2009394266MaRDI QIDQ374660FDOQ374660
Authors: Yichuan Ding, Nathan Krislock, Jiawei Qian, Henry Wolkowicz 
Publication date: 24 October 2013
Published in: Optimization and Engineering (Search for Journal in Brave)
Abstract: We study Semidefinite Programming, SDPc relaxations for Sensor Network Localization, SNLc with anchors and with noisy distance information. The main point of the paper is to view SNL as a (nearest) Euclidean Distance Matrix, EDM, completion problem and to show the advantages for using this latter, well studied model. We first show that the current popular SDP relaxation is equivalent to known relaxations in the literature for EDM completions. The existence of anchors in the problem is {em not} special. The set of anchors simply corresponds to a given fixed clique for the graph of the EDM problem. We next propose a method of projection when a large clique or a dense subgraph is identified in the underlying graph. This projection reduces the size, and improves the stability, of the relaxation. In addition, viewing the problem as an EDM completion problem yields better low rank approximations for the low dimensional realizations. And, the projection/reduction procedure can be repeated for other given cliques of sensors or for sets of sensors, where many distances are known. Thus, further size reduction can be obtained. Optimality/duality conditions and a primal-dual interior-exterior path following algorithm are derived for the SDP relaxations We discuss the relative stability and strength of two formulations and the corresponding algorithms that are used. In particular, we show that the quadratic formulation arising from the SDP relaxation is better conditioned than the linearized form, that is used in the literature and that arises from applying a Schur complement.
Full work available at URL: https://arxiv.org/abs/math/0612388
Recommendations
- Explicit sensor network localization using semidefinite representations and facial reductions
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- Semidefinite Programming for Sensor Network and Graph Localization
- Theory of semidefinite programming for sensor network localization
- (Robust) edge-based semidefinite programming relaxation of sensor network localization
Euclidean distance matrix completionssemidefinite programmingsensor network localizationgraph realizationanchors
Semidefinite programming (90C22) Control, switches and devices (``smart materials) in solid mechanics (74M05) Optimization of other properties in solid mechanics (74P10)
Cites Work
- Multidimensional scaling. I: Theory and method
- Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
- Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming
- Title not available (Why is that?)
- Properties of Euclidean and non-Euclidean distance matrices
- Connections between the real positive semidefinite and distance matrix completion problems
- Local results for the Gauss-Newton method on constrained rank-deficient nonlinear least squares
- Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
- The Euclidian Distance Matrix Completion Problem
- Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
- Solving Euclidean distance matrix completion problems via semidefinite progrmming
- Title not available (Why is that?)
- Characterization of the barrier parameter of homogeneous convex cones
- A note on the approximability of the dense subgraph problem.
- Invariance and efficiency of convex representations
- The cone of distance matrices
- The Gauss-Newton direction in semidefinite programming
- A Unified Theorem on SDP Rank Reduction
- Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
- Title not available (Why is that?)
- Title not available (Why is that?)
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Three theorems with applications to Euclidean distance matrices
- Theory of semidefinite programming for sensor network localization
Cited In (34)
- Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
- Explicit sensor network localization using semidefinite representations and facial reductions
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Comparing SOS and SDP relaxations of sensor network localization
- Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints
- On the exact solution of the distance geometry with interval distances in dimension 1
- A continuation method for large-sized sensor network localization problems
- A penalty method for rank minimization problems in symmetric matrices
- Noisy Euclidean distance matrix completion with a single missing node
- Selected open problems in discrete geometry and optimization
- Euclidean distance matrices, semidefinite programming and sensor network localization
- Semidefinite Programming for Sensor Network and Graph Localization
- A multiplicative weights update algorithm for MINLP
- Optimal partial discretization orders for discretizable distance geometry
- Preface
- A Lipschitzian error bound for convex quadratic symmetric cone programming
- (Robust) edge-based semidefinite programming relaxation of sensor network localization
- A dual basis approach to multidimensional scaling
- Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs
- An efficient method for non-negative low-rank completion
- Low-rank matrix completion in a general non-orthogonal basis
- A facial reduction approach for the single source localization problem
- Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation
- Universal Rigidity and Edge Sparsification for Sensor Network Localization
- UNLOC: optimal unfolding localization from noisy distance data
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Localization from incomplete noisy distance measurements
- Euclidean distance matrices and applications
- Cycle-based formulations in distance geometry
- Theory of semidefinite programming for sensor network localization
- New error measures and methods for realizing protein graphs from distance data
- The referenced vertex ordering problem: theory, applications, and solution methods
- On bar frameworks, stress matrices and semidefinite programming
- Theory of semidefinite programming for sensor network localization
Uses Software
This page was built for publication: Sensor network localization, Euclidean distance matrix completions, and graph realization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q374660)
