Theory of semidefinite programming for sensor network localization

DOI10.1007/S10107-006-0040-1zbMath1278.90482OpenAlexW3138835833MaRDI QIDQ868476

Anthony Man-Cho So, Yinyu Ye

Publication date: 5 March 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0040-1

zbMATH Keywords

semidefinite programminggraph realizationrigidity theorysensor network localizationEuclidean distance geometry

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (63)

A block coordinate descent method for sensor network localization ⋮ Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ A penalty method for rank minimization problems in symmetric matrices ⋮ Sum of squares method for sensor network localization ⋮ Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning ⋮ The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances ⋮ Stable Camera Motion Estimation Using Convex Programming ⋮ Exact matrix completion via convex optimization ⋮ Mathematical programming techniques for sensor networks ⋮ Sensor network localization, Euclidean distance matrix completions, and graph realization ⋮ Arithmetic modeling of random processes and \(r\)-algorithms ⋮ Dealing with missing information in data envelopment analysis by means of low-rank matrix completion ⋮ Approximation accuracy, gradient methods, and error bound for structured convex optimization ⋮ The discretizable distance geometry problem ⋮ Generically globally rigid graphs have generic universally rigid frameworks ⋮ Recent advances on the interval distance geometry problem ⋮ Hilbert mobile beacon for localisation and coverage in sensor networks ⋮ Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier ⋮ Exact Recovery with Symmetries for Procrustes Matching ⋮ A facial reduction approach for the single source localization problem ⋮ Phase retrieval via sensor network localization ⋮ Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates ⋮ Covariate-assisted matrix completion with multiple structural breaks ⋮ A note on probably certifiably correct algorithms ⋮ An approximation theory of matrix rank minimization and its application to quadratic equations ⋮ Exact SDP relaxations for quadratic programs with bipartite graph structures ⋮ Characterizing the universal rigidity of generic tensegrities ⋮ Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization ⋮ Least-squares approximations in geometric buildup for solving distance geometry problems ⋮ On the efficiency of routing in sensor networks ⋮ Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization ⋮ (Robust) edge-based semidefinite programming relaxation of sensor network localization ⋮ On the number of realizations of certain Henneberg graphs arising in protein conformation ⋮ Algorithmic Aspects of Sensor Localization ⋮ Exact matrix completion based on low rank Hankel structure in the Fourier domain ⋮ Multiscale semidefinite programming approach to positioning problems with pairwise structure ⋮ Distributed localization with mixed measurements under switching topologies ⋮ Visualizing data as objects by DC (difference of convex) optimization ⋮ Universal rigidity of complete bipartite graphs ⋮ Global optimization of general nonconvex problems with intermediate polynomial substructures ⋮ Discretization orders for distance geometry problems ⋮ Comparing SOS and SDP relaxations of sensor network localization ⋮ Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints ⋮ The discretizable molecular distance geometry problem ⋮ On bar frameworks, stress matrices and semidefinite programming ⋮ Global strong convexity and characterization of critical points of time-of-arrival-based source localization ⋮ A Riemannian dimension-reduced second-order method with application in sensor network localization ⋮ Euclidean Distance Matrices and Applications ⋮ Spectrally constrained optimization ⋮ Characterizing the universal rigidity of generic frameworks ⋮ Loraine – an interior-point solver for low-rank semidefinite programming ⋮ Molecular distance geometry methods: from continuous to discrete ⋮ Retracting Graphs to Cycles ⋮ Six mathematical gems from the history of distance geometry ⋮ Robust Low-Rank Matrix Completion by Riemannian Optimization ⋮ Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming ⋮ Diagonally Dominant Programming in Distance Geometry ⋮ An adaptation for iterative structured matrix completion ⋮ Truncated sparse approximation property and truncated \(q\)-norm minimization ⋮ Selected Open Problems in Discrete Geometry and Optimization ⋮ Global Registration of Multiple Point Clouds Using Semidefinite Programming ⋮ Sensitivity of low-rank matrix recovery ⋮ Global Optimization Approaches to Sensor Placement: Model Versions and Illustrative Results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convergence behavior of interior-point algorithms
• Solving Euclidean distance matrix completion problems via semidefinite progrmming
• Problems of distance geometry and convex properties of quadratic maps
• Distance matrix completion by numerical optimization
• Connected rigidity matroids and unique realizations of graphs
• Extensions of classical multidimensional scaling via variable reduction
• The geometry of graphs and some of its algorithmic applications
• Graph rigidity via 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
• Multidimensional scaling. I: Theory and method
• Conditions for Unique Graph Realizations
• Interior Point Trajectories in Semidefinite Programming
• Linear Matrix Inequalities in System and Control Theory
• Global Continuation for Distance Geometry Problems
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• The Molecule Problem: Exploiting Structure in Global Optimization
• Algorithmic Aspects of Wireless Sensor Networks
• Low-dimensional embedding with extra information
• Some distance properties of latent root and vector methods used in multivariate analysis
• On rigidity and realizability of weighted graphs
• Two theorems on Euclidean distance matrices and Gale transform

This page was built for publication: Theory of semidefinite programming for sensor network localization