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

arXiv: https://arxiv.org/abs/2309.09032 · HTML: https://mlsanity.com/paper/2309.09032/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 78 references that are in the map.
- First posted on arXiv 16 Sep 2023.

## Builds on (most cited first, 30 of 31)

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [Solving Linear Inverse Problems Using GAN Priors: An Algorithm with Provable Guarantees](https://mlsanity.com/paper/1802.08406/) (2018)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [Modeling Sparse Deviations for Compressed Sensing using Generative Models](https://mlsanity.com/paper/1807.01442/) (2018)
- [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016)
- [Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow](https://mlsanity.com/paper/1506.03382/) (2015)
- [Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors](https://mlsanity.com/paper/2002.01697/) (2020)
- [Exact asymptotics for phase retrieval and compressed sensing with random generative priors](https://mlsanity.com/paper/1912.02008/) (2019)
- [Alternating Phase Projected Gradient Descent with Generative Priors for Solving Compressive Phase Retrieval](https://mlsanity.com/paper/1903.02707/) (2019)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms](https://mlsanity.com/paper/1311.2745/) (2013)
- [Sparse Phase Retrieval via Truncated Amplitude Flow](https://mlsanity.com/paper/1611.07641/) (2016)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets](https://mlsanity.com/paper/1512.04433/) (2015)
- [Reconstructing Point Sets from Distance Distributions](https://mlsanity.com/paper/1804.02465/) (2018)
- [Geometric Invariants for Sparse Unknown View Tomography](https://mlsanity.com/paper/1811.09940/) (2018)
- [3D unknown view tomography via rotation invariants](https://mlsanity.com/paper/2003.10107/) (2020)
- [On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems](https://mlsanity.com/paper/2002.01066/) (2020)
- [Riemannian thresholding methods for row-sparse and low-rank matrix recovery](https://mlsanity.com/paper/2103.02356/) (2021)
- [An Oracle Gradient Regularized Newton Method for Quadratic Measurements Regression](https://mlsanity.com/paper/2202.09651/) (2022)
- [Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems](https://mlsanity.com/paper/2205.13827/) (2022)
- [Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography](https://mlsanity.com/paper/2207.02985/) (2022)
- [Phase Retrieval of Quaternion Signal via Wirtinger Flow](https://mlsanity.com/paper/2210.14170/) (2022)

## Built on by (most cited first, 4 of 4)

- [Integrating Intermediate Layer Optimization and Projected Gradient Descent for Solving Inverse Problems with Diffusion Models](https://mlsanity.com/paper/2505.20789/) (2025)
- [Image Restoration via Diffusion Models with Dynamic Resolution](https://mlsanity.com/paper/2605.14267/) (2026)
- [Diffusion Model Based Signal Recovery Under 1-Bit Quantization](https://mlsanity.com/paper/2511.12471/) (2025)
- [Tracing the Oracle: Improving Diffusion Timestep Scheduling for 3D CT Reconstruction](https://mlsanity.com/paper/2606.06236/) (2026)

## Abstract (arXiv)

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.