Tightness of a new and enhanced semidefinite relaxation for MIMO detection

Cheng Lu; Ya Feng Liu; Wei Qiang Zhang; Shuzhong Zhang

doi:10.1137/17M115075X

Tightness of a new and enhanced semidefinite relaxation for MIMO detection

Cheng Lu, Ya Feng Liu, Wei Qiang Zhang, Shuzhong Zhang

Research output: Contribution to journal › Article › peer-review

16 Scopus citations

Abstract

In this paper, we consider a fundamental problem in modern digital communications known as multiple-input multiple-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst show that conventional SDR is generally not tight for the problem. Then, we propose a new and enhanced SDR and show its tightness under an easily checkable condition, which essentially requires the level of the noise to be below a certain threshold. The above results have answered an open question posed by So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.

Original language	English (US)
Pages (from-to)	719-742
Number of pages	24
Journal	SIAM Journal on Optimization
Volume	29
Issue number	1
DOIs	https://doi.org/10.1137/17M115075X
State	Published - 2019
Externally published	Yes

Bibliographical note

Funding Information:
\ast Received by the editors October 5, 2017; accepted for publication (in revised form) December 21, 2018; published electronically March 5, 2019. http://www.siam.org/journals/siopt/29-1/M115075.html Funding: C. Lu's research was supported in part by NSFC grants 11701177 and 11771243 and Fundamental Research Funds for the Central Universities grant 2018ZD14. Y.-F. Liu's research was supported in part by NSFC grants 11671419, 11688101, and 11631013. W.-Q. Zhang's research was supported in part by NSFC grant U1836219. S. Zhang's research was supported in part by NSF grant CMMI-1462408 and the Shenzhen Fundamental Research Fund under grant KQTD2015033114415450.

Publisher Copyright:
© 2019 Society for Industrial and Applied Mathematics.

Keywords

Complex quadratic programming
MIMO detection
Semidefnite relaxation
Tight relaxation

Access

10.1137/17M115075X

OpenUrl availability

Full text

Cite this

@article{ddd3cc1eb81b47e790e1ca74389a93c6,

title = "Tightness of a new and enhanced semidefinite relaxation for MIMO detection",

abstract = "In this paper, we consider a fundamental problem in modern digital communications known as multiple-input multiple-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst show that conventional SDR is generally not tight for the problem. Then, we propose a new and enhanced SDR and show its tightness under an easily checkable condition, which essentially requires the level of the noise to be below a certain threshold. The above results have answered an open question posed by So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.",

keywords = "Complex quadratic programming, MIMO detection, Semidefnite relaxation, Tight relaxation",

author = "Cheng Lu and Liu, {Ya Feng} and Zhang, {Wei Qiang} and Shuzhong Zhang",

note = "Funding Information: \ast Received by the editors October 5, 2017; accepted for publication (in revised form) December 21, 2018; published electronically March 5, 2019. http://www.siam.org/journals/siopt/29-1/M115075.html Funding: C. Lu's research was supported in part by NSFC grants 11701177 and 11771243 and Fundamental Research Funds for the Central Universities grant 2018ZD14. Y.-F. Liu's research was supported in part by NSFC grants 11671419, 11688101, and 11631013. W.-Q. Zhang's research was supported in part by NSFC grant U1836219. S. Zhang's research was supported in part by NSF grant CMMI-1462408 and the Shenzhen Fundamental Research Fund under grant KQTD2015033114415450. Publisher Copyright: {\textcopyright} 2019 Society for Industrial and Applied Mathematics.",

year = "2019",

doi = "10.1137/17M115075X",

language = "English (US)",

volume = "29",

pages = "719--742",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Tightness of a new and enhanced semidefinite relaxation for MIMO detection

AU - Lu, Cheng

AU - Liu, Ya Feng

AU - Zhang, Wei Qiang

AU - Zhang, Shuzhong

N1 - Funding Information: \ast Received by the editors October 5, 2017; accepted for publication (in revised form) December 21, 2018; published electronically March 5, 2019. http://www.siam.org/journals/siopt/29-1/M115075.html Funding: C. Lu's research was supported in part by NSFC grants 11701177 and 11771243 and Fundamental Research Funds for the Central Universities grant 2018ZD14. Y.-F. Liu's research was supported in part by NSFC grants 11671419, 11688101, and 11631013. W.-Q. Zhang's research was supported in part by NSFC grant U1836219. S. Zhang's research was supported in part by NSF grant CMMI-1462408 and the Shenzhen Fundamental Research Fund under grant KQTD2015033114415450. Publisher Copyright: © 2019 Society for Industrial and Applied Mathematics.

PY - 2019

Y1 - 2019

N2 - In this paper, we consider a fundamental problem in modern digital communications known as multiple-input multiple-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst show that conventional SDR is generally not tight for the problem. Then, we propose a new and enhanced SDR and show its tightness under an easily checkable condition, which essentially requires the level of the noise to be below a certain threshold. The above results have answered an open question posed by So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.

AB - In this paper, we consider a fundamental problem in modern digital communications known as multiple-input multiple-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst show that conventional SDR is generally not tight for the problem. Then, we propose a new and enhanced SDR and show its tightness under an easily checkable condition, which essentially requires the level of the noise to be below a certain threshold. The above results have answered an open question posed by So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.

KW - Complex quadratic programming

KW - MIMO detection

KW - Semidefnite relaxation

KW - Tight relaxation

UR - http://www.scopus.com/inward/record.url?scp=85065445862&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065445862&partnerID=8YFLogxK

U2 - 10.1137/17M115075X

DO - 10.1137/17M115075X

M3 - Article

AN - SCOPUS:85065445862

SN - 1052-6234

VL - 29

SP - 719

EP - 742

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -

Tightness of a new and enhanced semidefinite relaxation for MIMO detection

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this