Performance Analysis of Quasi-Maximum-Likelihood Detection Based on Semidefinite Relaxation

Zhi-Quan (Tom) Luo
University of Minnesota

Monday, October 29, 2007 at 1:00PM

54-134 Engineering IV Building
Refreshments Served

Abstract: Consider the NP-hard problem of maximum likelihood (ML) detection for a multiple-input-multiple-output channel. We analyze two quasi-ML detectors based on semidefinite relaxation: the SDR detector for BPSK constellation and the PSK detector for M-PSK constellation. Both detectors are capable of delivering near-ML BER performance with a polynomial worst-case complexity. For a general class of random channels, we prove that the SDR detector provides a constant factor approximation in terms of the log-likelihood value, and this constant factor remains bounded with increasing system size. Furthermore, we show that the SNR gap between the ML and SDR detectors (expressed in dB) is bounded by a constant for large systems. For the PSK detector we show that each local maximum of the low-rank semidefinite relaxation that is feasible for the ML detection problem achieves at least a half of the maximum relative log-likelihood value, and for the BPSK case even yields an exact ML solution. Our analysis shows that the ML detection performance can be well approximated in polynomial time using semidefinite relaxation.

Biography: Zhi-Quan (Tom) Luo is a professor in the Department of Electrical and Computer Engineering at the University of Minnesota (Twin Cities) where he holds an endowed ADC Chair in digital technology. He received his B.Sc. degree in Applied Mathematics in 1984 from Peking University, China, and a Ph.D degree in Operations Research from MIT in 1989. From 1989 to 2003, Dr. Luo was with the Department of Electrical and Computer Engineering, McMaster University, Canada, where he eventually served as the department head and held a Canada Research Chair in Information Processing. His research interests lie in the union of optimization algorithms, signal processing and digital communication. Dr. Luo is a fellow of IEEE. He serves on the IEEE Signal Processing Society Technical Committees on Signal Processing Theory and Methods (SPTM), and on the Signal Processing for Communications (SPCOM). He is a co-recipient of the 2004 IEEE Signal Processing Society's Best Paper Award, and has held editorial positions for several international journals including Journal of Optimization Theory and Applications, Mathematics of Computation, and IEEE Transactions on Signal Processing. He currently serves on the editorial boards for SIAM Journal on Optimization, Mathematical Programming, and Mathematics of Operations Research.