Sequence of Linear Program for Robust Phase Retrieval

We consider a robust phase retrieval problem that aims to recover a signal from its absolute measurements corrupted with sparse noise. The least absolute deviation (LAD) provides a robust estimation against outliers. However, the corresponding optimization problem is nonconvex. We propose an "unregularized" iterative convexification approach to LAD through a sequence of linear programs (SLP). We provide a non-asymptotic convergence analysis under the standard Gaussian assumption of the measurement vectors. The SLP algorithm, when suitably initialized, linearly converges to the ground truth at optimal sample complexity up to a numerical constant. Furthermore, SLP empirically outperforms existing methods that provide a comparable performance guarantee.