Wing-Kin (Ken) Ma, Timothy N. Davidson, K. Max Wong, Zhi-Quan (Tom) Luo, and P.-C. Ching.
Quasi-maximum-likelihood multiuser detection using semi-definite
relaxation with application to synchronous CDMA.
IEEE Transactions on Signal Processing,
50(4):912-922, April 2002.
The maximum-likelihood (ML) multiuser detector is well known to exhibit better bit-error-rate (BER) performance than many other multiuser detectors. Unfortunately, ML detection (MLD) is a nondeterministic polynomial-time hard (NP-hard) problem, for which there is no known algorithm that can find the optimal solution with polynomial-time complexity (in the number of users). A polynomial-time approximation method called semi-definite (SD) relaxation is applied to the MLD problem with antipodal data transmission. SD relaxation is an accurate approximation method for certain NP-hard problems. The SD relaxation ML (SDR-ML) detector is efficient in that its complexity is of the order of $K^{3.5}$, where $K$ is the number of users. We illustrate the potential of the SDR-ML detector by showing that some existing detectors, such as the decorrelator and the linear-minimum-mean-square-error detector, can be interpreted as degenerate forms of the SDR-ML detector. Simulation results indicate that the BER performance of the SDR-ML detector is better than that of these existing detectors and is close to that of the true ML detector, even when the cross-correlations between users are strong or the near-far effect is significant
This idea has been extended to the asynchronous case by combining the semi-definite relaxation idea with block co-ordinate ascent.
Back to my publications-by-topic page.