Solving Quadratic Systems with Full-Rank Matrices Using Sparse or
  Generative Priors
Junren Chen Shuai Huang Michael K. Ng Zhaoqiang Liu
The problem of recovering a signal $\boldsymbol{x} \in \mathbb{R}^n$ from a
quadratic system $\{y_i=\boldsymbol{x}^\top\boldsymbol{A}_i\boldsymbol{x},\
i=1,\ldots,m\}$ with full-rank matrices $\boldsymbol{A}_i$ frequently arises in
applications such as unassigned distance geometry and sub-wavelength imaging.
With i.i.d. standard Gaussian matrices $\boldsymbol{A}_i$, this paper addresses
the high-dimensional case where $m\ll n$ by incorporating prior knowledge of
$\boldsymbol{x}$. First, we consider a $k$-sparse $\boldsymbol{x}$ and
introduce the thresholded Wirtinger flow (TWF) algorithm that does not require
the sparsity level $k$. TWF comprises two steps: the spectral initialization
that identifies a point sufficiently close to $\boldsymbol{x}$ (up to a sign
flip) when $m=O(k^2\log n)$, and the thresholded gradient descent (with a good
initialization) that produces a sequence linearly converging to
$\boldsymbol{x}$ with $m=O(k\log n)$ measurements. Second, we explore the
generative prior, assuming that $\boldsymbol{x}$ lies in the range of an
$L$-Lipschitz continuous generative model with $k$-dimensional inputs in an
$\ell_2$-ball of radius $r$. We develop the projected gradient descent (PGD)
algorithm that also comprises two steps: the projected power method that
provides an initial vector with $O\big(\sqrt{\frac{k \log L}{m}}\big)$
$\ell_2$-error given $m=O(k\log(Lnr))$ measurements, and the projected gradient
descent that refines the $\ell_2$-error to $O(\delta)$ at a geometric rate when
$m=O(k\log\frac{Lrn}{\delta^2})$. Experimental results corroborate our
theoretical findings and show that: (i) our approach for the sparse case
notably outperforms the existing provable algorithm sparse power factorization;
(ii) leveraging the generative prior allows for precise image recovery in the
MNIST dataset from a small number of quadratic measurements.