Near-Quadratic Convergence of the Gauss–Newton Method for Complex Phase Retrieval

In this paper, we consider the Gauss-Newton method for solving the complex phase retrieval problem, namely, recovering a signal (Formula presented) from m quadratic samples (Formula presented). In contrast to the real-valued setting, the Gauss-Newton matrix for complex-valued signals is rank-deficient and, thus, non-invertible. To address this, we utilize a Gauss-Newton step that moves orthogonally to certain trivial directions. We establish that this modified Gauss-Newton step has a closed-form solution, which corresponds precisely to the minimal-norm Gauss-Newton method for underdetermined nonlinear least squares problems. Additionally, using the leave-one-out technique, we demonstrate that (Formula presented) independent complex Gaussian random measurements ensures that the entire trajectory of the minimal-norm Gauss-Newton iterations remains confined within a specific region of incoherence and contraction with high probability. This finding allows us to establish the near-quadratic convergence rate of the minimal-norm Gauss-Newton method without the need of sample splitting. Specifically, the minimal-norm Gauss-Newton method yields an \epsilon -accuracy solution in at most (Formula presented) iterations.