A geometric analysis of phase retrieval

Given nonlinear measurements y_k = |〈a_k, x〉| for k = 1.,m, is it possible to recover x ⋯ Cⁿ? This generalized phase retrieval (GPR) problem is a fundamental task in various disciplines. Natural nonconvex methods often work remarkably well for GPR in practice, but lack clear theoretical explanations. In this paper, we take a step towards bridging this gap. We show that when the sensing vectors a_k's are generic (i.i.d. complex Gaussian) and the number of measurements is large enough (m ≥ Cn log³ n), with high probability (w.h.p.), a natural least-squares formulation for GPR has the following benign geometric structure: (1) all local minimizers are global-they are the target signal x and its equivalent copies; and (2) the objective function has a negative directional curvature around each saddle point. Such structure allows a number of algorithmic possibilities for efficient global optimization. We describe a second-order trust-region algorithm that provably finds a global minimizer in polynomial time, from arbitrary initializations.