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.
- Complex quadratic programming
- MIMO detection
- Semidefnite relaxation
- Tight relaxation