Sensor network localization, Euclidean distance matrix completions, and graph realization

DOI10.1007/S11081-008-9072-0MaRDI QIDQ374660zbMATH OpenOpenAlexFDO

Authors Yichuan Ding, Nathan Krislock, Jiawei Qian, Henry Wolkowicz

Publication date 24 October 2013

Published in Optimization and Engineering (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0612388

zbMATH Keywords

Euclidean distance matrix completionssemidefinite programmingsensor network localizationgraph realizationanchors

Mathematics Subject Classification ID

Semidefinite programming (90C22) Control, switches and devices (``smart materials) in solid mechanics (74M05) Optimization of other properties in solid mechanics (74P10)

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.

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

Cites work

• scientific article; zbMATH DE number 3728055 (Why is no real title available?)
• scientific article; zbMATH DE number 1182568 (Why is no real title available?)
• scientific article; zbMATH DE number 1182772 (Why is no real title available?)
• scientific article; zbMATH DE number 2188749 (Why is no real title available?)
• A Unified Theorem on SDP Rank Reduction
• A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
• A note on the approximability of the dense subgraph problem.
• Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming
• Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
• Characterization of the barrier parameter of homogeneous convex cones
• Connections between the real positive semidefinite and distance matrix completion problems
• Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• Invariance and efficiency of convex representations
• Local results for the Gauss-Newton method on constrained rank-deficient nonlinear least squares
• Multidimensional scaling. I: Theory and method
• Properties of Euclidean and non-Euclidean distance matrices
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Second‐Order Cone Programming Relaxation of Sensor Network Localization
• Solving Euclidean distance matrix completion problems via semidefinite progrmming
• The Euclidian Distance Matrix Completion Problem
• The Gauss-Newton direction in semidefinite programming
• The cone of distance matrices
• Theory of semidefinite programming for sensor network localization
• Three theorems with applications to Euclidean distance matrices

Cited in

(34)

• Theory of semidefinite programming for sensor network localization
• Explicit sensor network localization using semidefinite representations and facial reductions
• Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
• 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
• Euclidean distance matrices, semidefinite programming and sensor network localization
• Selected open problems in discrete geometry and optimization
• Semidefinite Programming for Sensor Network and Graph Localization
• A multiplicative weights update algorithm for MINLP
• Optimal partial discretization orders for discretizable distance geometry
• A Lipschitzian error bound for convex quadratic symmetric cone programming
• (Robust) edge-based semidefinite programming relaxation of sensor network localization
• Preface
• 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
• Localization from incomplete noisy distance measurements
• Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
• 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

Describes a project that uses

Uses Software

• SNLSDP

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)