Title: Phase retrieval using alternating minimization in a batch setting,
Abstract: This paper considers the problem of phase retrieval, where the goal is to
recover a signal $z\in C^n$ from the observations $y_i=|a_i^* z|$,
$i=1,2,\cdots,m$. While many algorithms have been proposed, the alternating
minimization algorithm has been one of the most commonly used methods, and it
is very simple to implement. Current work has proved that when the observation
vectors $\{a_i\}_{i=1}^m$ are sampled from a complex Gaussian distribution
$N(0, I)$, it recovers the underlying signal with a good initialization when
$m=O(n)$, or with random initialization when $m=O(n^2)$, and it conjectured
that random initialization succeeds with $m=O(n)$. This work proposes a
modified alternating minimization method in a batch setting, and proves that
when $m=O(n\log^{3}n)$, the proposed algorithm with random initialization
recovers the underlying signal with high probability. The proof is based on the
observation that after each iteration of alternating minimization, with high
probability, the angle between the estimated signal and the underlying signal
is reduced.