Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors

The problem of recovering a signal $x \in \mathbb{R}^{n}$ from a quadratic system $\{y{i}=x\,A{i}x,\,i=1,\dots,m\}$ with full-rank matrices frequently arises in applications such as unassigned distance geometry and sub-wavelength imaging. With i.i.d. standard Gaussian matrices $A_{i}$, this paper addresses the high-dimensional case where $m \lt\!\!\!\lt n$ by incorporating prior knowledge of x. First, we consider a k-sparse 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 x (up to a sign flip) when < >$m =O(k^{2}\log n)$, and the thresholded gradient descent which, when provided a good initialization, produces a sequence linearly converging to x with $m =O(k\log n)$ measurements. Second, we explore the generative prior, assuming that x lies in the range of an L-Lipschitz continuous generative model with k-dimensional inputs in an $\ell{2}$-ball of radius r. With an estimate correlated with the signal, we develop the projected gradient descent (PGD) algorithm that also comprises two steps: the projected power method that provides an initial vector with $O(\sqrt{k\log(L)/m})$ $\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.