Title: Probabilistic Analysis of Semidefinite Programming Relaxations, 
with Application to Detection for Multiple-Input Multiple-Output Systems 

Speaker: Man-Cho Anthony So
CUHK

Date: Friday  May 22, 2009
Time 11:00-11:50
Venue: Room 3494 (Lifts 25/26), HKUST

Abstract: 
One of the fundamental problems in modern digital communication is that of
the joint detection of several information carrying symbols that are
transmitted over a multiple-input multiple-output (MIMO) communication
channel. It can be solved by the so-called semidefinite relaxation (SDR)
detector, which is a popular heuristic for the problem. As its name
suggests, the SDR detector solves a semidefinite programming (SDP)
relaxation of the problem, and simulations show that it has excellent
empirical performance. However, its theoretical properties are still not
well understood. In this talk we introduce a general approach for analyzing
the approximation guarantee of the SDR detector when the communication
channel follows a widely used probabilistic model. The approach is based on
SDP duality theory, as well as results from non-asymptotic random matrix
theory. Consequently, we are able to obtain theoretical guarantees for
several variants of the SDR detector and provide some justification for
their use in practice.