Exact solutions of time difference of arrival source localisation based on semi-definite programming and Lagrange multiplier: complexity and performance analysis

Exact solutions of time difference of arrival source localisation based on semi-definite programming and Lagrange multiplier: complexity and performance analysis

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Signal Processing — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this study, the authors investigate the problem of source localisation based on the time difference of arrival (TDOA) in a group of sensors. Aiming to minimise the squared range-difference errors, the problem leads to a quadratically constrained quadratic programme. It is well known that this approach results in a non-convex optimisation problem. By proposing a relaxation technique, they show that the optimisation problem would be transformed to a convex one which can be solved by semi-definite programming (SDP) and Lagrange multiplier methods. Moreover, these methods offer the exact solution of the original problem and the affirmation of its uniqueness. In contrast to other complicated state-of-the-art SDP algorithms presented in the TDOA localisation literature, the authors methods are derived in a few straightforward reformulations and insightful steps; thus, there are no confusing and unjustifiable changes in the main optimisation problem. Furthermore, complexity analysis and a new approach for performance analysis, which show the merit of their methods, are introduced. Simulations and numerical results demonstrate that the positioning estimators resulted from the proposed algorithms outperform existing SDP-based methods presented so far.


    1. 1)
      • 1. Huang, Y., Benesty, J., Elko, G.W.: ‘Microphone arrays for video camera steering’, in Gay, S.L., Benesty, J. (Eds.): ‘Acoustic signal processing for telecommunication’ (Springer, US, 2000), pp. 239259.
    2. 2)
      • 2. Wang, H., Chu, P.: ‘Voice source localization for automatic camera pointing system in videoconferencing’. Proc. IEEE Workshop Applications Signal Processing Audio Acoustics, 1997.
    3. 3)
      • 3. Rabinkin, D.V., Ranomeron, R.J., French, J.C., Flanagan, J.L.: ‘A DSP implementation of source location using microphone arrays’. Proc. SPIE, 1996, Vol. 2846, pp. 8899.
    4. 4)
      • 4. Wang, C., Brandstein, M.S.: ‘A hybrid real-time face tracking system’. Proc. IEEE ICASSP, 1998, Vol. 6, pp. 37373741.
    5. 5)
    6. 6)
    7. 7)
    8. 8)
    9. 9)
    10. 10)
    11. 11)
    12. 12)
    13. 13)
    14. 14)
    15. 15)
    16. 16)
      • 16. Yang, K., An, J., Xu, Z.: ‘A quadratic constraint total least-squares algorithm for hyperbolic location’, Int. J. Commun. Netw. Syst. Sci., 2008, 2, pp. 105206.
    17. 17)
    18. 18)
      • 18. Fucheng, Q., Ho, K.C.: ‘A quadratic constraint solution method for TDOA and FDOA localization’. IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, 2011, pp. 25882591.
    19. 19)
    20. 20)
    21. 21)
    22. 22)
    23. 23)
    24. 24)
    25. 25)
    26. 26)
      • 26. Boyd, S., Vandenberghe, L.: ‘Convex optimization’ (Cambridge U.K., Cambridge University Press, 2003).
    27. 27)
    28. 28)
      • 28. Lutkepohl, H.: ‘Handbook of matrices’ (John Wiley & Sons Ltd., Chichester, 1996).
    29. 29)
      • 29. Grant, M., Boyd, S.: ‘CVX: Matlab software for disciplined convex programming’, 2009. [Online]. Available at
    30. 30)
    31. 31)
      • 32. Pataki, G.: ‘Geometry of semidefinite programming’, in Wolkowicz, H., Saigal, R., Vandenberghe, L. (Eds.): ‘Handbook of semidefinite programming: theory, algorithms, and applications’ (Kluwer Academic Publishers, Boston, MA, 2000).
    32. 32)
    33. 33)
    34. 34)
    35. 35)
      • 36. Golub, G.H., Van Loan, C.F.: ‘Matrix computations’ (Johns Hopkins University Press, 1996, 3rd edn.).
    36. 36)

Related content

This is a required field
Please enter a valid email address