In this paper, we consider the Gauss-Newton method for solving the complex phase retrieval problem, namely, recovering a signalx♯∈ Cnfrommquadratic samplesyj= |⟨aj,x♯⟩|2,j= 1, . . . ,m. 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 thatm≥O(nlog3m) 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 ϵ-accuracy solution in at mostO(logn+ log log(1/ϵ)) iterations.

A randomized Kaczmarz method was recently proposed for phase retrieval, which has been shown numerically to exhibit empirical performance over other state-of-the-art phase retrieval algorithms both in terms of the sampling complexity and computation time. While the rate of convergence has been well studied in the real case where the signals and measurement vectors are all real-valued, there is no guarantee for the convergence in the complex case. In fact, the linear convergence of the randomized Kaczmarz method for phase retrieval in the complex setting is left as a conjecture by Tan and Vershynin [ Inf. Inference, 8 (2019), pp. 97--123]. In this paper, we provide the first theoretical guarantees for it. We show that for random measurements ${a}_j \in \mathbb{C}^n,\, j=1,\ldots,m,$ which are drawn independently and uniformly from the complex unit sphere, or equivalently are independent complex Gaussian random vectors, when $m\ge Cn$ for some universal positive constant $C$, the randomized Kaczmarz scheme with a good initialization converges linearly to the target solution (up to a global phase) in expectation with high probability. This gives a positive answer to that conjecture.

Suppose that y = |Ax0| + η where x0∈ Rdis the target signal and η ∈ Rmis a noise vector. The aim of phase retrieval is to estimate x0from y. A popular model for estimating x0is the nonlinear least squares x̂ := argminx|||Ax| - y||2. One has already developed many efficient algorithms for solving the model, such as the seminal error reduction algorithm. In this paper, we present the estimation performance of the model with proving that ||x̂ - x0|| ≲ ||η||2/√m under the assumption of A being a Gaussian random matrix. We also prove the reconstruction error ||η||2/√m is sharp. For the case where x0is sparse, we study the estimation performance of both the nonlinear Lasso of phase retrieval and its unconstrained version. Our results are non-asymptotic, and we do not assume any distribution on the noise η. To the best of our knowledge, our results represent the first theoretical guarantee for the nonlinear least squares and for the nonlinear Lasso of phase retrieval.