(10/16/17) Phase Retrieval by Linear Programming: Fundamental Limits and a New Algorithm (PhaseLamp)

October 16, 2017
In our recent paper, we present an exact asymptotic analysis of the PhaseMax method for solving the phase retrieval problem via linear programming. Our analysis reveals a sharp phase transition phenomenon, and it also verifies our previous predictions made by the non-rigorous replica method from statistical physics. In addition, we propose a new iterative algorithm, named PhaseLamp, based on the idea of successive linearization and maximization over a polytope. This new algorithm has provably superior recovery performance over the original PhaseMax method.