  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 in terms of computation time. While the rate of convergence has
been studied well 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. In this paper, we provide the first theoretical guarantees for it.
We show that for random measurements $\mathbf{a}_j \in \mathbb{C}^n,
j=1,\ldots,m $ which are drawn independently and uniformly from the complex
unit sphere, or equivalent 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.
