# Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2017.

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

- [Understanding Overparameterization in Generative Adversarial Networks](https://mlsanity.com/paper/2104.05605/) (2021)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction](https://mlsanity.com/paper/2310.03956/) (2023)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [Poisson-Gaussian Holographic Phase Retrieval with Score-based Image Prior](https://mlsanity.com/paper/2305.07712/) (2023)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [Low Complexity Regularized Phase Retrieval](https://mlsanity.com/paper/2407.16413/) (2024)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view](https://mlsanity.com/paper/2506.18279/) (2025)
- [Phase retrieval with rank d measurements -- descending algorithms phase transitions](https://mlsanity.com/paper/2506.18282/) (2025)
- [Two-Timescale Fine-tuning Provably Learns New Features for Two-Layer ReLU Networks](https://mlsanity.com/paper/2609.34667/) (2026)

## Abstract (arXiv)

This paper concerns the problem of recovering an unknown but structured signal x ∈ Rn from m quadratic measurements of the form yr=|<ar,x>|2 for r=1,2,...,m. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal (m<<n). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove that projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for any constraint set (convex or nonconvex) providing convergence guarantees to the global optimum even when the objective function and constraint set is nonconvex. Furthermore, these results hold with a number of measurements that is only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in recent literature. In a companion paper we demonstrate favorable properties for the optimization problem that may enable similar results to continue to hold more globally (over the entire ambient space). Collectively these two papers utilize and develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. The mathematical results in this paper also pave the way for a new generation of data-driven phase-less imaging systems that can utilize prior information to significantly reduce acquisition time and enhance image reconstruction, enabling nano-scale imaging at unprecedented speeds and resolutions.