This thesis is concerned with signal processing for improving the performance of wireless communication receivers for well-established cellular networks such as the GSM/EDGE and WCDMA/HSPA systems. The goal of doing so, is to improve the end-user experience and/or provide a higher system capacity by allowing an increased reuse of network resources. To achieve this goal, one must first understand the nature of the problem and an introduction is therefore provided. In addition, the concept of graph-based models and approximations for wireless communications is introduced along with various Belief Propagation (BP) methods for detecting the transmitted information, including the Turbo principle. Having established a framework for the research, various approximate detection schemes are discussed. First, the general form of linear detection is presented and it is argued that this may be preferable in connection with parameter estimation. Next, a realistic framework for interference whitening is presented, allowing flexibility in the selection of whether interference is accounted for via a discrete or a Gaussian distribution. The approximate method of sphere detection and decoding is outlined and various suggestions for improvements are presented. In addition, methods for using generalized BP to perform approximate joint detection and decoding in systems with convolutional codes are outlined. One such method is a natural generalization of the traditional Turbo principle and a generalized Turbo principle can therefore be established. For realistic wireless communication scenarios, a multitude of parameters are not known and must instead be estimated. A general variational Bayesian EM-algorithm is therefore presented to provide such estimates. It generalizes previously known methods for communication systems by estimating parameter densities instead of point-estimates and can therefore account for uncertainty in the parameter estimates. Finally, an EM-algorithm for band-Toeplitz covariance estimation is presented as such an estimate is desirable for noise and interference whitening. Using simulations, the method is shown to be near-optimal in the sense that it achieves the unbiased Cramer-Rao lower-bound for medium and large sample-sizes.