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.
Bibliographical noteFunding 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.
© 2019 Society for Industrial and Applied Mathematics.
- Complex quadratic programming
- MIMO detection
- Semidefnite relaxation
- Tight relaxation