A facial reduction approach for the single source localization problem

He Shi, Qingna Li*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 optimal 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.

Original languageEnglish
Pages (from-to)831-855
Number of pages25
JournalJournal of Global Optimization
Volume87
Issue number2-4
DOIs
Publication statusPublished - Nov 2023

Keywords

  • Constraint nondegeneracy
  • Euclidean distance matrix
  • Facial reduction
  • Majorized penalty approach
  • Single source localization

Fingerprint

Dive into the research topics of 'A facial reduction approach for the single source localization problem'. Together they form a unique fingerprint.

Cite this