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 journalArticlepeer-review

11 Scopus citations


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 languageEnglish (US)
Pages (from-to)719-742
Number of pages24
JournalSIAM Journal on Optimization
Issue number1
StatePublished - 2019

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.


  • Complex quadratic programming
  • MIMO detection
  • Semidefnite relaxation
  • Tight relaxation


Dive into the research topics of 'Tightness of a new and enhanced semidefinite relaxation for MIMO detection'. Together they form a unique fingerprint.

Cite this