Explicit sensor network localization using semidefinite representations and facial reductions
From MaRDI portal
Abstract: The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion problem, by using the linear mapping between Euclidean distance matrices, EDM, and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy, by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.
Recommendations
- Sensor network localization, Euclidean distance matrix completions, and graph realization
- 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
- Theory of semidefinite programming for sensor network localization
Cited in
(55)- Computing the nearest Euclidean distance matrix with low embedding dimensions
- Perturbation analysis of the Euclidean distance matrix optimization problem and its numerical implications
- Geometric buildup algorithms for sensor network localization
- Constraint programming approaches for the discretizable molecular distance geometry problem
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- Euclidean distance matrices and applications
- Distance geometry on the sphere
- Barvinok's naive algorithm in distance geometry
- An impossible combinatorial counting method in distance geometry
- Universal Rigidity and Edge Sparsification for Sensor Network Localization
- Sensor network localization, Euclidean distance matrix completions, and graph realization
- Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation
- A least-squares approach for discretizable distance geometry problems with inexact distances
- A block coordinate descent method for sensor network localization
- A new algorithm for the \(^K\mathrm{DMDGP}\) subclass of distance geometry problems with exact distances
- The discretizable molecular distance geometry problem
- A facial reduction approach for the single source localization problem
- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- Recent advances on the interval distance geometry problem
- Preprocessing and regularization for degenerate semidefinite programs
- Cardinality-constrained structured data-fitting problems
- A fresh variational-analysis look at the positive semidefinite matrices world
- The discretizable distance geometry problem
- Multiscale semidefinite programming approach to positioning problems with pairwise structure
- A feasible method for sensor network localization
- Semidefinite Programming for Sensor Network and Graph Localization
- Iterative universal rigidity
- Diagonally dominant programming in distance geometry
- Low-rank matrix completion using nuclear norm minimization and facial reduction
- Preface: Special issue dedicated to distance geometry
- Validating numerical semidefinite programming solvers for polynomial invariants
- edmcr
- An application-based characterization of dynamical distance geometry problems
- Rejoinder on: ``Distance geometry and data science
- Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree
- Douglas-Rachford feasibility methods for matrix completion problems
- Comparing SOS and SDP relaxations of sensor network localization
- Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints
- On Farkas lemma and dimensional rigidity of bar frameworks
- Algorithm 920: SFSDP: a sparse version of full semidefinite programming relaxation for sensor network localization problems
- A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems
- Euclidean distance matrix completion problems
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Noisy Euclidean distance matrix completion with a single missing node
- Robust principal component analysis using facial reduction
- Strong duality and minimal representations for cone optimization
- Theory of semidefinite programming for sensor network localization
- Level-set methods for convex optimization
- A continuation method for large-sized sensor network localization problems
- Loraine – an interior-point solver for low-rank semidefinite programming
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Theory of semidefinite programming for sensor network localization
- Coordinate shadows of semidefinite and Euclidean distance matrices
This page was built for publication: Explicit sensor network localization using semidefinite representations and facial reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q121877)
