  We study algorithms for solving quadratic systems of equations based on
optimization methods over polytopes. Our work is inspired by a recently
proposed convex formulation of the phase retrieval problem, which estimates the
unknown signal by solving a simple linear program over a polytope constructed
from the measurements. We present a sharp characterization of the
high-dimensional geometry of the aforementioned polytope under Gaussian
measurements. This characterization allows us to derive asymptotically exact
performance guarantees for PhaseMax, which also reveal a phase transition
phenomenon with respect to its sample complexity. Moreover, the geometric
insights gained from our analysis lead to a new nonconvex formulation of the
phase retrieval problem and an accompanying iterative algorithm, which we call
PhaseLamp. We show that this new algorithm has superior recovery performance
over the original PhaseMax method. Finally, as yet another variation on the
theme of performing phase retrieval via polytope optimization, we propose a
weighted version of PhaseLamp and demonstrate, through numerical simulations,
that it outperforms several state-of-the-art algorithms under both generic
Gaussian measurements as well as more realistic Fourier-type measurements that
arise in phase retrieval applications.
