Fast Unit-modulus Least Squares with Applications in Beamforming and Phase Retrieval

Abstract

Unit-modulus Least Squares (ULS) problems arise in many applications, including phase-only beamforming, phase retrieval and radar code design. These problems are NP-hard, so there exist problem instances that we cannot solve efficiently, and whether such solution exists remains elusive. ULS formulations can always be recast as Unit-modulus Quadratic Programs (UQPs), to which Semi-Definite Relaxation (SDR) can be applied, and is often the state-of-the-art approach (e.g., PhaseCut). SDR lifts the problem dimension and requires solving a much larger-scale convex problem, which makes it ill-suited for large-scale ULS/UQP. In this paper, we propose several first-order algorithms that meet or exceed SDR performance in terms of minimizing the cost function, and compare favorably to SDR in terms of runtime complexity. We establish convergence of the proposed first-order algorithms to a KKT point, and we demonstrate their superiority in two applications: beamforming using only phase-shifts, and phase retrieval.