Universal binary semidefinite relaxation for ML signal detection

Semidefinite relaxation (SDR) provides a computationally efficient polynomial-time approximation of the maximum likelihood detector. However, most of the existing works mainly focus on particular signal constellations. In this paper, we propose a universal binary semidefinite relaxation scheme that can handle arbitrary signal constellations in polynomial time. The proposed scheme first binarizes the original signal space to a linearly constrained binary space, and then solves the detection problem through SDR.colorblack{{} A specialized dual barrier method is provided to solve the SDR more efficiently. In addition, we propose to apply on-the-fly decision feedback to further reduce the computational complexity and improve the detection performance. The} proposed binary SDR, together with on-the-fly decision feedback scheme, can provide comparable or better solutions compared to existing SDR methods specialized to specific constellations such as 16-QAM and 8-PSK in terms of computational complexity and symbol error rate. Furthermore, the proposed scheme is universal and can solve any other constellations such as 12-QAM, 32-QAM, or M-PSK.