Title: Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval,
Abstract: We develop procedures, based on minimization of the composition $f(x) =
h(c(x))$ of a convex function $h$ and smooth function $c$, for solving random
collections of quadratic equalities, applying our methodology to phase
retrieval problems. We show that the prox-linear algorithm we develop can solve
phase retrieval problems---even with adversarially faulty measurements---with
high probability as soon as the number of measurements $m$ is a constant factor
larger than the dimension $n$ of the signal to be recovered. The algorithm
requires essentially no tuning---it consists of solving a sequence of convex
problems---and it is implementable without any particular assumptions on the
measurements taken. We provide substantial experiments investigating our
methods, indicating the practical effectiveness of the procedures and showing
that they succeed with high probability as soon as $m / n \ge 2$ when the
signal is real-valued.