  This paper presents a computationally efficient decoder for multiple antenna
systems. The proposed algorithm can be used for any constellation (QAM or PSK)
and any labeling method. The decoder is based on matrix-lifting Semi-Definite
Programming (SDP). The strength of the proposed method lies in a new relaxation
algorithm applied to the method of Mobasher et al. This results in a reduction
of the number of variables from $(NK+1)^2$ to $(2N+K)^2$, where $N$ is the
number of antennas and $K$ is the number of constellation points in each real
dimension. Since the computational complexity of solving SDP is a polynomial
function of the number of variables, we have a significant complexity
reduction. Moreover, the proposed method offers a better performance as
compared to the best quasi-maximum likelihood decoding methods reported in the
literature.
