Phase Retrieval Under a Generative Prior
  The phase retrieval problem asks to recover a natural signal $y_0 \in
\mathbb{R}^n$ from $m$ quadratic observations, where $m$ is to be minimized. As
is common in many imaging problems, natural signals are considered sparse with
respect to a known basis, and the generic sparsity prior is enforced via
$\ell_1$ regularization. While successful in the realm of linear inverse
problems, such $\ell_1$ methods have encountered possibly fundamental
limitations, as no computationally efficient algorithm for phase retrieval of a
$k$-sparse signal has been proven to succeed with fewer than $O(k^2\log n)$
generic measurements, exceeding the theoretical optimum of $O(k \log n)$. In
this paper, we propose a novel framework for phase retrieval by 1) modeling
natural signals as being in the range of a deep generative neural network $G :
\mathbb{R}^k \rightarrow \mathbb{R}^n$ and 2) enforcing this prior directly by
optimizing an empirical risk objective over the domain of the generator. Our
formulation has provably favorable global geometry for gradient methods, as
soon as $m = O(kd^2\log n)$, where $d$ is the depth of the network.
Specifically, when suitable deterministic conditions on the generator and
measurement matrix are met, we construct a descent direction for any point
outside of a small neighborhood around the unique global minimizer and its
negative multiple, and show that such conditions hold with high probability
under Gaussian ensembles of multilayer fully-connected generator networks and
measurement matrices. This formulation for structured phase retrieval thus has
two advantages over sparsity based methods: 1) deep generative priors can more
tightly represent natural signals and 2) information theoretically optimal
sample complexity. We corroborate these results with experiments showing that
exploiting generative models in phase retrieval tasks outperforms sparse phase
retrieval methods.
