A Lagrangian dual approach to the single-source localization problem

Hou Duo Qi, Naihua Xiu, Xiaoming Yuan

Research output: Contribution to journalJournal articlepeer-review

24 Citations (Scopus)


The single-source localization problem (SSLP), which is nonconvex by its nature, appears in several important multidisciplinary fields such as signal processing and the global positioning system. In this paper, we cast SSLP as a Euclidean distance embedding problem and study a Lagrangian dual approach. It is proved that the Lagrangian dual problem must have an optimal solution under the generalized Slater condition. We provide a sufficient condition for the zero-duality gap and establish the equivalence between the Lagrangian dual approach and the existing Generalized Trust-Region Subproblem (GTRS) approach studied by Beck ['Exact and Approximate Solutions of Source Localization Problems,' IEEE Trans. Signal Process., vol. 56, pp. 1770-1778, 2008]. We also reveal new implications of the assumptions made by the GTRS approach. Moreover, the Lagrangian dual approach has a straightforward extension to the multiple-source localization problem. Numerical simulations demonstrate that the Lagrangian dual approach can produce localization of similar quality as the GTRS and can significantly outperform the well-known semidefinite programming solver SNLSDP for the multiple source localization problem on the tested cases.

Original languageEnglish
Article number6519327
Pages (from-to)3815-3826
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number15
Publication statusPublished - Aug 2013

Scopus Subject Areas

  • Signal Processing
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Euclidean distance matrix
  • Lagrangian duality
  • low-rank approximation
  • orthogonal projection


Dive into the research topics of 'A Lagrangian dual approach to the single-source localization problem'. Together they form a unique fingerprint.

Cite this