Near maximum likelihood detection using an interior point method and semidefinite programming

In this paper a maximum likelihood detection problem for a digital communication system is reformulated as a semidefinite programming (SDP) problem. A relaxation of this problem is done. An interior point method will be used to efficiently solve the semidefinite program arising from the relaxation. From the solution given by this interior point method, an approximate of the solution of the initial ML detection problem will be extracted using a randomization method. The detection method presented in this paper will have near ML performances with a polynomial complexity.