A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval
This addresses the problem of recovering signals from corrupted measurements in phase retrieval, with incremental improvements in efficiency and robustness.
The paper tackles robust phase retrieval with corrupted magnitude-only measurements by proposing an alternating minimization algorithm that converges to the true signal and achieves nearly linear sample complexity of O(d polylog(d)).
In this work, we study the robust phase retrieval problem where the task is to recover an unknown signal $θ^* \in \mathbb{R}^d$ in the presence of potentially arbitrarily corrupted magnitude-only linear measurements. We propose an alternating minimization approach that incorporates an oracle solver for a non-convex optimization problem as a subroutine. Our algorithm guarantees convergence to $θ^*$ and provides an explicit polynomial dependence of the convergence rate on the fraction of corrupted measurements. We then provide an efficient construction of the aforementioned oracle under a sparse arbitrary outliers model and offer valuable insights into the geometric properties of the loss landscape in phase retrieval with corrupted measurements. Our proposed oracle avoids the need for computationally intensive spectral initialization, using a simple gradient descent algorithm with a constant step size and random initialization instead. Additionally, our overall algorithm achieves nearly linear sample complexity, $\mathcal{O}(d \, \mathrm{polylog}(d))$.