Performance Analysis of Quasi-Maximum-Likelihood Detector Based on Semi-Definite Programming

Despite its optimal bit-error-rate (BER) performance, maximum-likelihood (ML) detection is known to be NP-hard and suffers from high computational complexity. The currently popular suboptimal detectors either achieve a polynomial time complexity at the expense of BER performance degradation (e.g., MMSE detector), or offer a near ML performance with a complexity that is exponential in the worst case. The paper considers a highly efficient (polynomial worst case complexity) quasi-ML detection method based on semi-definite (SDP) relaxation. It is shown that, for a standard vector Rayleigh fading channel, this SDP-based quasi-ML detector achieves, in the high signal-to-noise ratio (SNR) region, a BER which is identical to that of the exact ML detector. In the low SNR region, we use the random matrix theory to show that the SDP-based detector serves as a constant factor approximation to the ML detector for large systems.