A Lagrangian Dual Approach to the Single-Source Localization Problem

• Published in: IEEE transactions on signal processing 2013-08, Vol.61 (15), p.3815-3826
• Main Authors: Qi, Hou-Duo, Xiu, Naihua, Yuan, Xiaoming
• Format: Article
• Language: English
• Subjects: Applied sciences; Detection, estimation, filtering, equalization, prediction; Euclidean distance; Euclidean distance matrix; Exact sciences and technology; Global Positioning System; Indexes; Information, signal and communications theory; Lagrangian duality; low-rank approximation; orthogonal projection; Programming; Signal and communications theory; Signal, noise; Symmetric matrices; Telecommunications and information theory
• ISSN: 1053-587X; 1941-0476
• DOI: 10.1109/TSP.2013.2264814

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 et al. ["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 for the multiple source localization problem on the tested cases.