Phase Retrieval by Alternating Minimization with Random Initialization

Abstract

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 \infty$ when $m/{\log }^{3}m\ge M{n}^{3/2}{\log }^{1/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.

References in corpus (6)

• Alternating Projection, Ptychographic Imaging and Phase Synchronization
• A Partial Derandomization of PhaseLift using Spherical Designs
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Corruption Robust Phase Retrieval via Linear Programming
• Phase retrieval using alternating minimization in a batch setting

Cited by in corpus (1)

• Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation