# Exact asymptotics for phase retrieval and compressed sensing with random generative priors

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2019.

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

- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)
- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Theoretical characterization of uncertainty in high-dimensional linear classification](https://mlsanity.com/paper/2202.03295/) (2022)
- [Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD](https://mlsanity.com/paper/2305.18502/) (2023)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Fundamental limits of overparametrized shallow neural networks for supervised learning](https://mlsanity.com/paper/2307.05635/) (2023)
- [Asymptotics of Learning with Deep Structured (Random) Features](https://mlsanity.com/paper/2402.13999/) (2024)
- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (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)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems](https://mlsanity.com/paper/2111.03237/) (2021)
- [Bayesian Inference with Nonlinear Generative Models: Comments on Secure Learning](https://mlsanity.com/paper/2201.09986/) (2022)
- [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)

## Abstract (arXiv)

We consider the problem of compressed sensing and of (real-valued) phase retrieval with random measurement matrix. We derive sharp asymptotics for the information-theoretically optimal performance and for the best known polynomial algorithm for an ensemble of generative priors consisting of fully connected deep neural networks with random weight matrices and arbitrary activations. We compare the performance to sparse separable priors and conclude that generative priors might be advantageous in terms of algorithmic performance. In particular, while sparsity does not allow to perform compressive phase retrieval efficiently close to its information-theoretic limit, it is found that under the random generative prior compressed phase retrieval becomes tractable.