@PHDTHESIS\{IMM2003-02455, author = "T. Fabricius", title = "Multiuser detection and channel estimation: Exact and approximate methods", year = "2003", keywords = "Communication, multiuser detection, channel estimation, mean field theory", pages = "272", school = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}", address = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby", type = "", note = "Supervisor: Lars Kai Hansen", url = "http://www2.compute.dtu.dk/pubdb/pubs/2455-full.html", 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 self-averaging 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 non-convex 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 {8-PSK} 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 {W-CDMA} scenario. We show that by such an approach we are able to gain some dB compared to a reference {RAKE} receiver." }