PERFORMANCE COMPARISON OF NONLINEAR PROGRAMMING

Performance Comparison of the Nonlinear Programming and Soft Decision Approaches to Resolving the Complexity of the Optimum Maximum Likelihood Multiuser Receiver



Performance Comparison of the Nonlinear Programming

Introduction

The expectation-maximization (EM) algorithm 111 pro- vides an iterative approach to likelihood-based parameter estimation when direct maximization of the likelihood function may not be feasible. The generality of the algorithm, combined with its amenability for incomplete-data problems, has led to its widespread use for such diverse applications as speech recognition [2], identification of impulsive noise channels

[3], quantum-limited imaging [4], and numerous others [5]

in economics, medicine, psychology, etc. In the context of incomplete-data or missing-data problems, the basic approach of EM is to alternate between the following: 1) computing complete-data sufficient statistics based on the incompletedata and current parameter estimates and 2) re-estimating the parameters based on the computed complete-data sufficient statistics. Although convergence of the algorithm to the maximum-likelihood estimator is not always guaranteed, EM does possess the intuitively pleasing property of producing estimates that monotonically increase in likelihood.

This report illustrates the use of EM algorithms for discrete parameter estimation-specifically, for joint data detection in

Paper approved by A Duel-Hallen, the Editor for Communications of the IEEE Communications Society Manusciipt received March 25, 1994, revised July 10, 1995, and April 18, 1996 This research was supported by the U S Army Research Office under Grant DAAH04-93-G-0219 and by an AT&T Bell Laboratories Ph D Scholarship This paper was presented in part at the IEEE International Symposium on Information Theory Trondheim, Norway, June 1994, and the IEEE and IMS Workshop on Information Theory and Statistics, Alexandria, VA, October 1994 L B Nelson is with the Department of Electrical Engineering, University of Minnesota, Minneapolis, MN 55455 USA H V Poor is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA Publisher Item Identifier S 0090-6778(96)09028-9

multiple-access channels. In applying the EM and related algorithms,

our general approach is to treat the bits of interfering users as probabilistic missing data when updating the estimate for a given user's bit. The resulting derivations lead to iterative multiuser receivers that use soft-decisions for interference cancellation andor sequential (rather than parallel) updates of estimates for the users' data.

Several recent applications of EM to digital communications consider related problems of parameter estimation for superimposed signals in noise. In the context of direct-sequence codedivision multiple-access (CDMA) over multipath channels, Fawer and Aazhang [6] propose multiuser receivers that iterate between EM-based amplitude estimation and multi-stage data detection. Poor also applies EM to amplitude estimation for direct-sequence CDMA 171; the approach differs from that of [6] in that the users' data are not assumed known, but are instead treated probabilistically as missing data. In [8], Georghiades and Han consider maximum-likelihood sequence estimation (MLSE) with unknown random phase or fading parameters treated as missing data. The E-step of the resulting algorithms produces estimates of the unknown parameters; the M-step is then equivalent to MLSE for deterministic signals in additive noise.

The applications of EM to multiuser detection in the current paper demonstrate ...