research-article

On a New SDP-SOCP Method for Acoustic Source Localization Problem

Authors:

Ka-Fai Cedric Yiu,

Yinyu YeAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 12, Issue 4

Article No.: 36, Pages 1 - 26

https://doi.org/10.1145/2968449

Published: 25 October 2016 Publication History

Abstract

Acoustic source localization has many important applications. Convex relaxation provides a viable approach of obtaining good estimates very efficiently. There are two popular convex relaxation methods using either semi-definite programming (SDP) or second-order cone programming (SOCP). However, the performances of the methods have not been studied properly in the literature and there is no comparison in terms of accuracy and performance. The aims of this article are twofold. First of all, we study and compare several convex relaxation methods. We demonstrate, by numerical examples, that most of the convex relaxation methods cannot localize the source exactly, even in the performance limit when the time difference of arrival (TDOA) information is exact. In addressing this problem, we propose a novel mixed SDP-SOCP relaxation model and study the characteristics of the optimal solutions and its localizable region. Furthermore, an error correction scheme for the proposed SDP-SOCP model is developed so that exact localization can be achieved in the performance limit. Experimental data have been collected in a room with two different array configurations to demonstrate our proposed approach.

References

[1]

P. Biswas and Y. Y. Ye. 2004. Semidefinite programming for ad hoc wireless network localization. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN). ACM, New York, 46--54.

Digital Library

[2]

M. Brandstein and D. B. Ward. 2001. Microphone Arrays: Signal Processing Techniques and Applications. Springer-Verlag, Berlin.

[3]

C. G. Carter. 1993. Coherence and Time Delay Estimation: An Applied Tutorial for Research, Development, Test, and Evaluation Engineers. IEEE Press, Piscataway, NJ.

[4]

Z. G. Feng and K. F. C. Yiu. 2014. The design of multi-dimensional acoustic beamformers via window functions. Digital Signal Process. 29 (2014), 107--116.

[5]

Z. G. Feng, K. F. C. Yiu, and S. Nordholm. 2011. A two-stage method for the design of near-field broadband beamformer. IEEE Trans. Signal Process. 59, 8 (2011), 3647--3656.

Digital Library

[6]

Z. G. Feng, K. F. C. Yiu, and S. Nordholm. 2012. Placement design of microphone arrays in near-field broadband beamformers. IEEE Trans. Signal Process. 60, 3 (2012), 1195--1204.

Digital Library

[7]

X. X. Huang, X. Q. Yang, and K. L. Teo. 2003. A sequential quadratic penalty method for nonlinear semidefinite programming. Optimization 52 (2003), 715--738.

[8]

H. H. Kha, H. D. Tuan, B. Vo, and T. Q. Nguyen. 2007. Symmetric orthogonal complex-valued filter bank design by semidefinite programming. IEEE Trans. Signal Process. 55, 9 (2007), 4405--4414.

Digital Library

[9]

E. Lehmann and A. Johansson. 2008. Prediction of energy decay in room impulse responses simulated with an image-source model. J. Acoust. Soc. Am. 124, 1 (2008), 269--277.

[10]

S. J. Li, X. Q. Yang, K. L. Teo, and S. Wu. 2003. A solution method for combined semi-infinite and semi-definite programming. ANZIAM J. 45 (2003), 477--494.

[11]

Z. B. Li, K. F. C. Yiu, and S. Nordholm. 2014. On the indoor beamformer design with reverberation. IEEE Trans. Audio. Speech Lang. Proc. 22, 8 (2014), 1225--1235.

Digital Library

[12]

S. H. Low. 2014a. Convex relaxation of optimal power flow—-part 1: Formulations and equivalence. IEEE Trans. Control Network Syst. 1, 1 (2014), 15--27.

[13]

S. H. Low. 2014b. Convex relaxation of optimal power flow—-part 2: Exactness. IEEE Trans. Control Network Syst. 1, 2 (2014), 177--189.

[14]

W. S. Lu and T. Hinamoto. 2003. Optimal design of frequency-response-masking filters using semidefinite programming. IEEE Trans. Circuits Syst. I Fundam. Theory Appl. 50, 4 (2003), 715--738.

[15]

K. C. Toh, R. H. Tütüncü, and M. J. Todd. 2012. On the implementation and usage of SDPT3-a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0. In Handbook on Semidefinite, Conic and Polynomial Optimization. Springer, New York, 166 (2012), 715--754.

[16]

P. Tseng. 2007. Second-order cone programming relaxation of sensor network localization. SIAM J. Optim. 18, 1 (2007), 156--185.

Digital Library

[17]

F. Wang, V. Balakrishnan, Y. P. Zhou, J. N. Chen, R. Yang, and C. Frank. 2003. Optimal array pattern synthesis using semidefinite programming. IEEE Trans. Signal Process. 51, 5 (2003), 1172--1183.

Digital Library

[18]

H. Wolkowicz, R. Saigal, and L. Vandenberghe. 2003. Handbook of Semidefinite Programming, Theory, Algorithms and Applications. Kluwer Academic, Boston.

[19]

K. Yang, G. Wang, and Z. Q. Luo. 2009. Efficient convex relaxation methods for robust target localization by a sensor network using time differences of arrivals. IEEE Trans. Signal Process. 57, 7 (2009), 2775--2784.

Digital Library

Cited By

He QGao MYiu KNordholm S(2023)Distributed Microphone Array Localization Problem via SDP-SOCP MethodIEEE/ACM Transactions on Audio, Speech, and Language Processing10.1109/TASLP.2023.331343731(3579-3588)Online publication date: 2023
https://doi.org/10.1109/TASLP.2023.3313437
Qi QLi YGuo Q(2021)A Convex Relaxation Algorithm for Source Localization Considering Sensor Motion in Wireless Sensor NetworksIEEE Communications Letters10.1109/LCOMM.2021.306266825:6(1867-1871)Online publication date: Jun-2021
https://doi.org/10.1109/LCOMM.2021.3062668
Chen SZhang JXu C(2019)Robust Distributed Cooperative Localization With NLOS Mitigation Based on Multiplicative Convex ModelIEEE Access10.1109/ACCESS.2019.29155127(112907-112920)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2915512

Index Terms

On a New SDP-SOCP Method for Acoustic Source Localization Problem

Recommendations

Extending the QCR method to general mixed-integer programs

Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with ...
Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of ...
A p-cone sequential relaxation procedure for 0-1 integer programs
GLOBAL OPTIMIZATION

Several authors have introduced sequential relaxation techniques-based on linear and/or semi-definite programming-to generate the convex hull of 0-1 integer points in a polytope in at most n steps. In this paper, we introduce a sequential relaxation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 12, Issue 4

November 2016

309 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/2994619

Editor:
Chenyang Lu
Department of Computer Science and Engineering / School of Engineering and Applied Sciences / Washington University / 1 Brookings Drive / St. Louis, MO 63130

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 25 October 2016

Accepted: 01 July 2016

Revised: 01 March 2016

Received: 01 December 2015

Published in TOSN Volume 12, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

RGC
Hong Kong Polytechnic University

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
224
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)3

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

He QGao MYiu KNordholm S(2023)Distributed Microphone Array Localization Problem via SDP-SOCP MethodIEEE/ACM Transactions on Audio, Speech, and Language Processing10.1109/TASLP.2023.331343731(3579-3588)Online publication date: 2023
https://doi.org/10.1109/TASLP.2023.3313437
Qi QLi YGuo Q(2021)A Convex Relaxation Algorithm for Source Localization Considering Sensor Motion in Wireless Sensor NetworksIEEE Communications Letters10.1109/LCOMM.2021.306266825:6(1867-1871)Online publication date: Jun-2021
https://doi.org/10.1109/LCOMM.2021.3062668
Chen SZhang JXu C(2019)Robust Distributed Cooperative Localization With NLOS Mitigation Based on Multiplicative Convex ModelIEEE Access10.1109/ACCESS.2019.29155127(112907-112920)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2915512

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents