Due to their computational efficiency and strong empirical performance, semidefinite relaxation (SDR)-based algorithms have gained much attention in multiple-input, multiple-output (MIMO) detection. However, the theoretical performance of those algorithms, especially when applied to constellations other than the binary phase-shift keying (BPSK) constellation, is still not very well-understood. In this chapter we describe a recently-developed approach for analyzing the approximation guarantees of various SDR-based algorithms in the low signal-to-noise ratio (SNR) region. Using such an approach, we show that in the case of M-ary phase-shift keying (MPSK) and quadrature amplitude modulation (QAM) constellations, various SDR-based algorithms will return solutions with near-optimal log-likelihood values with high probability. The results described in this chapter can be viewed as average-case analyses of certain SDP relaxations, where the input distribution is motivated by physical considerations. More importantly, they give some theoretical justification for using SDR-based algorithms for MIMO detection in the low SNR region.

Introduction

Semidefinite programming (SDP) has now become an important algorithm design tool for a wide variety of optimization problems. From a practical standpoint, SDP-based algorithms have proven to be effective in dealing with various fundamental engineering problems, such as control system design [1, 2], structural design [3], signal detection [4, 5], and network localization [6–8]. From a theoretical standpoint, SDP is playing an important role in advancing the theory of algorithms.