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.