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

The problem of recovering a signal boldsymbol x∈ ℝn from a quadratic system yi=boldsymbol x^topboldsymbol Aiboldsymbol x, i=1,ldots,m with full-rank matrices boldsymbol Ai frequently arises in applications such as unassigned distance geometry and sub-wavelength imaging. With i.i.d. standard Gaussian matrices boldsymbol Ai, this paper addresses the high-dimensional case where mll 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(k2log n), and the thresholded gradient descent which, when provided a good initialization, produces a sequence linearly converging to boldsymbol x with m=O(klog 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 ℓ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 Obig(√frack log Lmbig) ℓ2-error given m=O(klog(Lnr)) measurements, and the projected gradient descent that refines the ℓ2-error to O(δ) at a geometric rate when m=O(klogfracLrnδ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.