(Robust) edge-based semidefinite programming relaxation of sensor network localization
coordinate gradient descentlog-barrier penalty methodsemidefinite programmingsemidefinite programming relaxationsensor network localization
Numerical methods of relaxation type (49M20) Distributed algorithms (68W15) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Sensitivity, stability, parametric optimization (90C31) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90)
The paper deals with certain semidefinite programming (SDP) relaxations of the, in general NP-hard, ad hoc wireless sensor network localization problem. In particular, the authors study key properties of a SDP relaxiation and of the recently proposed edge-based SDP relaxation (ESDP). An outcome of this study is that these relaxations are more sensitive to noise than a second order cone-programming (SOCP) relaxation. To dampen this sensitivity the authors introduce a noise-aware robust version of the ESDP relaxation for which a small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution if the noise level is sufficiently small. For finding such a solution they suggest a log-barrier penalty coordinate gradient descent method. In simulations this method turns out to be much faster than a primal-dual interior-point method for the solution of the ESDP problem and to produce solutions of a comparable accuracy. The method is suitable for positioning and tracking in real time.
- Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints
- Semidefinite Programming for Sensor Network and Graph Localization
- Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Sensor network localization, Euclidean distance matrix completions, and graph realization
- A coordinate gradient descent method for nonsmooth separable minimization
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
- Algorithmic Aspects of Wireless Sensor Networks
- Asymptotic behavior of the central path for a special class of degenerate SDP problems
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
- Global Continuation for Distance Geometry Problems
- Graph rigidity via Euclidean distance matrices
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Sensor network localization, Euclidean distance matrix completions, and graph realization
- SpaseLoc: An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization
- Sum of squares method for sensor network localization
- Theory of semidefinite programming for sensor network localization
- Explicit sensor network localization using semidefinite representations and facial reductions
- A penalty method for rank minimization problems in symmetric matrices
- Visualizing data as objects by DC (difference of convex) optimization
- Geometric buildup algorithms for sensor network localization
- A block coordinate descent method for sensor network localization
- A modified quasisecant method for global optimization
- Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation
- A DC programming approach for sensor network localization with uncertainties in anchor positions
- Euclidean distance matrices and applications
- Conditions for correct sensor network localization using SDP relaxation
- Selected open problems in discrete geometry and optimization
- Algorithm 920: SFSDP: a sparse version of full semidefinite programming relaxation for sensor network localization problems
- Universal Rigidity and Edge Sparsification for Sensor Network Localization
- Semidefinite Programming for Sensor Network and Graph Localization
- Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
- Sensor network localization, Euclidean distance matrix completions, and graph realization
- Semi-definite programming based approaches for real-time tractor localization in port container terminals
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Multiscale semidefinite programming approach to positioning problems with pairwise structure
- Comparing SOS and SDP relaxations of sensor network localization
- Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints
- On bar frameworks, stress matrices and semidefinite programming
- Sum of squares method for sensor network localization
This page was built for publication: (Robust) edge-based semidefinite programming relaxation of sensor network localization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652286)
