Corruption Robust Phase Retrieval via Linear Programming

We consider the problem of phase retrieval from corrupted magnitude observations. In particular we show that a fixed $x_0\in {\mathbb{R}}^n$ can be recovered exactly from corrupted magnitude measurements $|\langle a_i, x_0 \rangle | + \eta_i, \quad i =1,2\ldots m$withhighprobabilityfor$m = O(n)$, where $a_i\in {\mathbb{R}}^n$ are i.i.d standard Gaussian and $\eta \in $\mathbb{R}$^m$ has fixed sparse support and is otherwise arbitrary, by using a version of the PhaseMax algorithm augmented with slack variables subject to a penalty. This linear programming formulation, which we call RobustPhaseMax, operates in the natural parameter space, and our proofs rely on a direct analysis of the optimality conditions using concentration inequalities.