Multiuser detection and channel estimation: Exact and approximate methods  Thomas Fabricius
 Abstract  This dissertation deals with optimal and close to optimal multiuser detection in Code Division Multiple Access. We derive optimal detection strategies in the sense of minimum expected probability of bit error, sequence error, and mean square error. These are implemented efficiently by the use of the Junction Tree Algorithm, which is a generalisation of Pearl's Belief Propagation, the BCJR, sum product, min/max sum, and Viterbi's algorithm. Although efficient algoithms, they have an inherent exponential complexity in the number of users when applied to CDMA multiuser detection. For this reason we propose here to use accurate approximations borrowed from statistical mechanics and machine learning. These give us various algorithms that all can be formulated in a subtractive interference cancellation formalism. The suggested algorithms can e ectively be seen as bias corrections to standard subtractive interference cancellation with hyperbolic tangent tentative decision device, in statistical mechanics and machine learning called the naive mean field approach. The differences between the proposed algorithms lie in how the bias is estimated/approximated. We propose approaches based on a second order Plefka expansion, adaptive TAP, and large system limit selfaveraging behaviours, and a method based on Kikuchi and Bethe free energy approximations, which we denote the Generalised Graph Expansion. Since all these methods are improvements of the naive mean field approach we make a thorough analysis of the convexity and bifurcations of the naive mean field free energy and optima. This proves that we can avoid local minima by tracking a global convex solution into the nonconvex region, effectively avoiding error propagation. This method is in statistical physics denoted mean field annealing.
We also derive optimal detectors when nuisance parameters such as the channel and noise level are unknown, and show how well the proposed methods fit into this framework via the Generalised Expectation Maximisation algorithm.
Our numerical evaluation show that naive mean field annealing and adaptive TAP mean field annealing provides results identical or better than cases found in the literature. While annealing is an important ingredient, the adaptive TAP always has better or identical performance compared to the naive method, but a complexity scaling quadratic per user detected, compared to the naive approach being linear per users detected.
We also show how to use the naive mean eld approach to derive a low complexity approximative MMSE bit detection from an 8PSK symbol. The results are nearly indistictable from the optimal.
The last application is the use of the junction tree algorithm for decoding a subset of channels in a downlink WCDMA scenario. We show that by such an approach we are able to gain some dB compared to a reference RAKE receiver.  Keywords  Communication, multiuser detection, channel estimation, mean field theory  Type  Ph.D. thesis [Academic thesis]  Year  2003 pp. 272  Publisher  Informatics and Mathematical Modelling, Technical University of Denmark, DTU  Address  Richard Petersens Plads, Building 321, DK2800 Kgs. Lyngby  Series  IMMPHD2003115  Note  Supervisor: Lars Kai Hansen  Electronic version(s)  [zip]  BibTeX data  [bibtex]  IMM Group(s)  Intelligent Signal Processing 
