Randomized Algorithms for Optimal Solutions of Double-Sided QCQP With Applications in Signal Processing

摘要

Quadratically constrained quadratic programming (QCQP) with double-sided constraints has plenty of applications in signal processing as have been addressed in recent years. QCQP problems are hard to solve, in general, and they are typically approached by solving a semidefinite programming (SDP) relaxation followed by a postprocessing procedure. Existing postprocessing schemes include Gaussian randomization to generate an approximate solution, rank reduction procedure (the so-called purification), and some specific rank-one matrix decomposition techniques to yield a globally optimal solution. In this paper, we propose several randomized postprocessing methods to output not an approximate solution but a globally optimal solution for some solvable instances of the double-sided QCQP (i.e., instances with a small number of constraints). We illustrate their applicability in robust receive beamforming, radar optimal code design, and broadcast beamforming for multiuser communications. As a byproduct, we derive an alternative (shorter) proof for the Sturm-Zhang rank-one matrix decomposition theorem.