Semidefinite Relaxation of Quadratic Optimization Problems

In this article, we have provided general, comprehensive coverage of the SDR technique, from its practical deployments and scope of applicability to key theoretical results. We have also showcased several representative applications, namely MIMO detection, B¿ shimming in MRI, and sensor network localization. Another important application, namely downlink transmit beamforming, is described in [1]. Due to space limitations, we are unable to cover many other beautiful applications of the SDR technique, although we have done our best to illustrate the key intuitive ideas that resulted in those applications. We hope that this introductory article will serve as a good starting point for readers who would like to apply the SDR technique to their applications, and to locate specific references either in applications or theory.

Introduction

The introduction of SDR in the early 2000s has reshaped the way we see many topics today in the field of signal processing and communications. Many practical experiences have already indicated that SDR is capable of providing accurate (and sometimes near optimal) approximations. For instance, in MIMO detection, SDR is now known as an efficient high-performance approach [17]–[23] (see also [24]–[26] for blind MIMO detection). The promising empirical approximation performance of SDR has motivated new endeavors, leading to the creation of new research trends in some cases. One such example is in the area of transmit beamforming, which has attracted much recent interest; for a review of this exciting topic, please see the article by Gershman et al. [1] as well as [27]. The effectiveness of transmit beamforming depends much on how well one can handle (often nonconvex) QCQPs and its technical progress could have been slower if SDR had not been known to the signal processing community. Another example worth mentioning is sensor network localization, a practically important but technically challenging problem. SDR has proven to be an effective technique for tackling the sensor network localization problem, both in theory and practice [28]–[31]. In addition to the three major applications mentioned above, there are many other different applications of SDR, such as waveform design in radar [32], [33], phase unwrapping [34], robust blind beamforming [35], large-margin parameter estimation in speech recognition (see the article by Jiang and Li [36] for further details), transmit shim in MRI [37], and many more [38]–[41]. It is anticipated that SDR would find more applications in the near future. Fig1

A nonconvex QCQP in : Colored lines represent the contour of the objective function, the gray area represents the feasible set, and the black lines represent the boundary of each constraint.