Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMA

Wing Kin Ma, Timothy N. Davidson, Kon Max Wong, Zhi Quan Luo, Pak Chung Ching

Research output: Contribution to journalArticle

265 Scopus citations


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). In this paper, 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.

Original languageEnglish (US)
Pages (from-to)912-922
Number of pages11
JournalIEEE Transactions on Signal Processing
Issue number4
StatePublished - Apr 1 2002


  • Maximum likelihood detection
  • Multiuser detection
  • Relaxation methods
  • Semi-definite programming

Fingerprint Dive into the research topics of 'Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMA'. Together they form a unique fingerprint.

  • Cite this