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

By

Professor Man-Cho So, Anthony

Department of Systems Engineering & Engineering Management
The Chinese University of Hong Kong

Date: March 2, 2009

Time: 4:30pm - 5:30 pm

Venue: Rm. 121, Ho Sin Hang Engineering Building, CUHK

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.