# Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 74 references that are in the map.
- First posted on arXiv 29 Jun 2021.

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

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Deep Learning Techniques for Inverse Problems in Imaging](https://mlsanity.com/paper/2005.06001/) (2020)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Deep Decoder: Concise Image Representations from Untrained Non-convolutional Networks](https://mlsanity.com/paper/1810.03982/) (2018)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [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)
- [Compressed Sensing with Deep Image Prior and Learned Regularization](https://mlsanity.com/paper/1806.06438/) (2018)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Robust Compressed Sensing using Generative Models](https://mlsanity.com/paper/2006.09461/) (2020)
- [Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors](https://mlsanity.com/paper/1906.08763/) (2019)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [PhaseMax: Convex Phase Retrieval via Basis Pursuit](https://mlsanity.com/paper/1610.07531/) (2016)
- [Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models](https://mlsanity.com/paper/1908.10744/) (2019)
- [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)
- [The Generalized Lasso with Nonlinear Observations and Generative Priors](https://mlsanity.com/paper/2006.12415/) (2020)
- [Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization](https://mlsanity.com/paper/1702.06175/) (2017)
- [Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation](https://mlsanity.com/paper/1610.04210/) (2016)
- [Sum-of-Squares Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1507.06370/) (2015)
- [Sparse Phase Retrieval via Truncated Amplitude Flow](https://mlsanity.com/paper/1611.07641/) (2016)
- [Lower Bounds for Compressed Sensing with Generative Models](https://mlsanity.com/paper/1912.02938/) (2019)

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

- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [TurbuGAN: An Adversarial Learning Approach to Spatially-Varying Multiframe Blind Deconvolution with Applications to Imaging Through Turbulence](https://mlsanity.com/paper/2203.06764/) (2022)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priors](https://mlsanity.com/paper/2209.10093/) (2022)
- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Learning Single Index Models with Diffusion Priors](https://mlsanity.com/paper/2505.21135/) (2025)
- [Optimizing Intermediate Representations of Generative Models for Phase Retrieval](https://mlsanity.com/paper/2205.15617/) (2022)
- [Diffusion Model Based Signal Recovery Under 1-Bit Quantization](https://mlsanity.com/paper/2511.12471/) (2025)

## Abstract (arXiv)

Compressive phase retrieval is a popular variant of the standard compressive sensing problem in which the measurements only contain magnitude information. In this paper, motivated by recent advances in deep generative models, we provide recovery guarantees with near-optimal sample complexity for phase retrieval with generative priors. We first show that when using i.i.d. Gaussian measurements and an L-Lipschitz continuous generative model with bounded k-dimensional inputs, roughly O(k log L) samples suffice to guarantee that any signal minimizing an amplitude-based empirical loss function is close to the true signal. Attaining this sample complexity with a practical algorithm remains a difficult challenge, and finding a good initialization for gradient-based methods has been observed to pose a major bottleneck. To partially address this, we further show that roughly O(k log L) samples ensure sufficient closeness between the underlying signal and any em globally optimal solution to an optimization problem designed for spectral initialization (though finding such a solution may still be challenging). We also adapt this result to sparse phase retrieval, and show that O(s log n) samples are sufficient for a similar guarantee when the underlying signal is s-sparse and n-dimensional, matching an information-theoretic lower bound. While these guarantees do not directly correspond to a practical algorithm, we propose a practical spectral initialization method motivated by our findings, and experimentally observe performance gains over various existing spectral initialization methods for sparse phase retrieval.