A facial reduction approach for the single source localization problem
From MaRDI portal
Abstract: The single source localization problem (SSLP) appears in several fields such as signal processing and global positioning systems. The optimization problem of SSLP is nonconvex and difficult to find its globally optima solution. It can be reformulated as a rank constrained Euclidean distance matrix (EDM) completion problem with a number of equality constraints. In this paper, we propose a facial reduction approach to solve such an EDM completion problem. For the constraints of fixed distances between sensors, we reduce them to a face of the EDM cone and derive the closed formulation of the face. We prove constraint nondegeneracy for each feasible point of the resulting EDM optimization problem without a rank constraint, which guarantees the quadratic convergence of semismooth Newton's method. To tackle the nonconvex rank constraint, we apply the majorized penalty approach developed by Zhou et al. (IEEE Trans Signal Process 66(3):4331-4346, 2018). Numerical results verify the fast speed of the proposed approach while giving comparable quality of solutions as other methods.
Recommendations
- Noisy Euclidean distance matrix completion with a single missing node
- Explicit sensor network localization using semidefinite representations and facial reductions
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem
- Sensor network localization, Euclidean distance matrix completions, and graph realization
Cites work
- A Fast Matrix Majorization-Projection Method for Penalized Stress Minimization With Box Constraints
- A Lagrangian Dual Approach to the Single-Source Localization Problem
- A remark on the faces of the cone of Euclidean distance matrices
- A semismooth Newton method for the nearest Euclidean distance matrix problem
- An exact duality theory for semidefinite programming and its complexity implications
- Circum-Euclidean distance matrices and faces
- Computing the nearest Euclidean distance matrix with low embedding dimensions
- Constrained best Euclidean distance embedding on a sphere: a matrix optimization approach
- Convex Analysis
- Coordinate shadows of semidefinite and Euclidean distance matrices
- Euclidean distance matrices and applications
- Euclidean distance matrices and their applications in rigidity theory
- Exact and Approximate Solutions of Source Localization Problems
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Faces of the cone of Euclidean distance matrices: characterizations, structure and induced geometry
- Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints
- scientific article; zbMATH DE number 3728055 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Iterative Minimization Schemes for Solving the Single Source Localization Problem
- Noisy Euclidean distance matrix completion with a single missing node
- Nonmetric multidimensional scaling. A numerical method
- On certain linear mappings between inner-product and squared-distance matrices
- On the cone of positive semidefinite matrices
- Regularizing the abstract convex program
- Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
- Robust principal component analysis using facial reduction
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Solving semidefinite-quadratic-linear programs using SDPT3
- The Strong Second-Order Sufficient Condition and Constraint Nondegeneracy in Nonlinear Semidefinite Programming and Their Implications
- Theory of cones
- Theory of semidefinite programming for sensor network localization
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(2)
This page was built for publication: A facial reduction approach for the single source localization problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6064050)
