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

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.

Inspec keywords: sensor placement; convex programming; sensor fusion; time-of-arrival estimation

Other keywords: SDP algorithms; quadratically constrained quadratic programme; sensors; nonconvex optimisation problem; complexity analysis; time difference of arrival; source localisation; optimisation problem; Lagrange multiplier methods; relaxation technique; TDOA; performance analysis; SDP-based methods; semidefinite programming; squared range-difference errors

Subjects: Signal processing theory; Sensing devices and transducers; Optimisation techniques; Signal processing and detection; Optimisation techniques

References

    1. 1)
    2. 2)
    3. 3)
    4. 4)
    5. 5)
    6. 6)
    7. 7)
    8. 8)
    9. 9)
    10. 10)
      • 2. Wang, H., Chu, P.: ‘Voice source localization for automatic camera pointing system in videoconferencing’. Proc. IEEE Workshop Applications Signal Processing Audio Acoustics, 1997.
    11. 11)
      • 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.
    12. 12)
    13. 13)
      • 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.
    14. 14)
    15. 15)
    16. 16)
      • 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).
    17. 17)
    18. 18)
    19. 19)
    20. 20)
    21. 21)
    22. 22)
      • 4. Wang, C., Brandstein, M.S.: ‘A hybrid real-time face tracking system’. Proc. IEEE ICASSP, 1998, Vol. 6, pp. 37373741.
    23. 23)
      • 29. Grant, M., Boyd, S.: ‘CVX: Matlab software for disciplined convex programming’, 2009. [Online]. Available at http://www.stanford.edu/~boyd/cvx.
    24. 24)
    25. 25)
    26. 26)
    27. 27)
      • 36. Golub, G.H., Van Loan, C.F.: ‘Matrix computations’ (Johns Hopkins University Press, 1996, 3rd edn.).
    28. 28)
      • 26. Boyd, S., Vandenberghe, L.: ‘Convex optimization’ (Cambridge U.K., Cambridge University Press, 2003).
    29. 29)
      • 28. Lutkepohl, H.: ‘Handbook of matrices’ (John Wiley & Sons Ltd., Chichester, 1996).
    30. 30)
    31. 31)
      • 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.
    32. 32)
    33. 33)
    34. 34)
    35. 35)
      • 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.
    36. 36)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2013.0457
Loading

Related content

content/journals/10.1049/iet-spr.2013.0457
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading