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 journalArticle

3 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


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

Fingerprint 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