Efficient quasi-maximum-likelihood multiuser detection by semi-definite relaxation

W. K. Ma, T. N. Davidson, K. M. Wong, Z. Q. Luo, P. C. Ching

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


In multiuser detection, maximum-likelihood detection (MLD) is optimum in the sense of minimum error probability. Unfortunately, MLD involves a computationally difficult optimization problem for which there is no known polynomial-time solution (with respect to the number of users). In this paper, we develop an approximate maximum-likelihood (ML) detector using semi-definite (SD) relaxation for the case of anti-podal data transmission. SD relaxation is an accurate and efficient approximation algorithm for certain difficult optimization problems. In MLD, SD relaxation is efficient in that its complexity is O(K3.5), where K stands for the number of users. Simulation results indicate that the SD relaxation ML detector has its bit error performance close to 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)6-10
Number of pages5
JournalIEEE International Conference on Communications
StatePublished - Jan 1 2001
EventInternational Conference on Communications (ICC2001) - Helsinki, Finland
Duration: Jun 11 2000Jun 14 2000


Dive into the research topics of 'Efficient quasi-maximum-likelihood multiuser detection by semi-definite relaxation'. Together they form a unique fingerprint.

Cite this