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

—The problem of recovering a signal x ∈ R ⁿ from a quadratic system {y _i = x ^TA _ix, i = 1, . . ., m} with full-rank matrices A _i 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 ≪ 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 ² 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 l2-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 ⁽√k log(L)/m) l2-error given m = O(k log(Lnr)) measurements, and the projected gradient descent that refines the l2-error to O(δ) at a geometric rate when m = O(k log ^Lrn _{δ 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.