Application of computational geometry to multiuser detection in CDMA

The maximum-likelihood multiuser detection problem in code-division multiple-access is known to be an optimization problem with an objective function that is required to be optimized over a combinatorial decision region. Conventional suboptimal detectors relax the combinatorial decision region by a convex region, without altering the objective function to be optimized. We take an approach wherein the objective function is reduced to a form appropriate for the application of a polynomial complexity algorithm in computational geometry, while keeping the decision region combinatorial. The resulting detector allows a tradeoff between performance and computational complexity. The bit-error rate performance of the detector has been found to be better than the decorrelator and the linear minimum mean-square error detectors, for the same level of complexity.