Recently, several quasi-maximum likelihood decoding methods have been introduced to solve the decoding problem in multiple antenna systems. Mobasher et al. proposed a general method with a near optimal performance for M-ary QAM or PSK constellation. However, it is more complex compared to some other methods specialized for a limited scenario. In this paper, we introduce a new general algorithm based on matrix-lifting Semi-Definite Programming (SDP). The new relaxation exploits the matrix structure of the system and introduces a degradation in the performance; however, the reduction in the complexity is significant. The number of variables is decreased from O(N2K2) to O((N + K)2). Moreover, this method can be implemented for any constellation and labeling method.