Department of Systems Engineering and Engineering Management,

                    The Chinese University of Hong Kong


Probabilistic Analysis of SDP Relaxation for Binary Quadratic
Minimization with Application to Wireless Communication

Prof. Zhi-Quan Luo
ADC Chair in Digital Technology
Department of Electrical and Computer Engineering
University of Minnesota

Date : September 9, 2005 (Friday)

Time : 4:30 p.m. - 5:30 p.m.

Venue : Room 513, William M.W. Mong Engineering Building

(Engineering Building Complex Phase 2), CUHK


Despite its optimal bit-error-rate (BER) performance, the
maximum-likelihood (ML) detection is known to be NP-hard and suffers from
high computational complexity. The currently popular suboptimal detectors
either achieve a polynomial time complexity at the expense of BER
performance degradation (e.g., MMSE Detector), or offer a near ML
performance with a complexity that is exponential in the worst case. In a
recent work of Ma-Davidson-Wong-Luo-Ching, we proposed a highly efficient
(polynomial worst case complexity) quasi-ML detection method based on
Semi-Definite (SDP) relaxation. We show in this work that, for a standard
vector Rayleigh fading channel, this SDP-based quasi-ML detector achieves,
in the high signal-to-noise ratio (SNR) region, a BER which is identical
to that of the exact ML detector. In the low SNR region we use the random
matrix theory to show that the SDP-based detector serves as a constant
factor approximation to the ML detector for large systems.


Zhi-Quan (Tom) Luo received his B.Sc. degree in Applied Mathematics in 1984
from Peking University, Beijing, China. Subsequently, he was selected by a
joint committee of American Mathematical Society and the Society of
Industrial and Applied Mathematics to pursue Ph.D study in the United States.
After an one-year intensive training in mathematics and English at the
Nankai Institute of Mathematics, Tianjin, China, he was admitted to the
Department of Electrical Engineering and Computer Science, Massachusetts
Institute of Technology, where he received the Ph.D degree in 1989. Upon
graduation, he joined the Department of Electrical and Computer Engineering,
McMaster University, Hamilton, Canada, where he became the department head
and held a Canada Research Chair in Information Processing. In 2003, he
joined the Department of Electrical and Computer Engineering of the
University of Minnesota as ADC Chair in Digital Technology.

His general research interests include the design and analysis of efficient
algorithms in data communication, information theory and coding, wireless
and optical networks and systems, and signal processing, especially in
computation/communication complexity issues arising from these problem areas.
His current research interest lies in the theory of multi-user communications
and the application of optimization techniques to the design of multi-antenna
communication systems. He currently serves on the editorial boards for a
number of international journals including SIAM Journal on Optimization and
IEEE Transactions on Signal Processing.

                       ***** ALL ARE WELCOME *****

Host : Prof. Li Duan
Tel : 26098316 / 26098323
Email : dli@se.cuhk.edu.hk

For more information please

refer to http://www.se.cuhk.edu.hk/~seg5810/