Phase Retrieval by Alternating Minimization with Random Initialization

We consider a phase retrieval problem, where the goal is to reconstruct a $n$-dimensional complex vector from its phaseless scalar products with $m$ sensing vectors, independently sampled from complex normal distributions. We show that, with a random initialization, the classical algorithm of alternating minimization succeeds with high probability as $n,m\to \mathrm{\infty }$ when $m\mathrm{/}{\log }^{3}m\ge M{n}^{3\mathrm{/}2}{\log }^{1\mathrm{/}2}n$ for some $M>0$. This is a step toward proving the conjecture in \cite{Waldspurger2016}, which conjectures that the algorithm succeeds when $m=O(n)$. The analysis depends on an approach that enables the decoupling of the dependency between the algorithmic iterates and the sensing vectors.