# A coherence parameter characterizing generative compressed sensing with Fourier measurements

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 67 references that are in the map.
- First posted on arXiv 19 Jul 2022.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep Decoder: Concise Image Representations from Untrained Non-convolutional Networks](https://mlsanity.com/paper/1810.03982/) (2018)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk](https://mlsanity.com/paper/1705.07576/) (2017)
- [Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models](https://mlsanity.com/paper/1908.10744/) (2019)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Global Guarantees for Blind Demodulation with Generative Priors](https://mlsanity.com/paper/1905.12576/) (2019)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [Structure Preserving Compressive Sensing MRI Reconstruction using Generative Adversarial Networks](https://mlsanity.com/paper/1910.06067/) (2019)
- [The Restricted Isometry Property of Subsampled Fourier Matrices](https://mlsanity.com/paper/1507.01768/) (2015)
- [Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applications](https://mlsanity.com/paper/2001.10631/) (2020)
- [Beyond Independent Measurements: General Compressed Sensing with GNN Application](https://mlsanity.com/paper/2111.00327/) (2021)
- [GenMod: A generative modeling approach for spectral representation of PDEs with random inputs](https://mlsanity.com/paper/2201.12973/) (2022)

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

- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Model-adapted Fourier sampling for generative compressed sensing](https://mlsanity.com/paper/2310.04984/) (2023)
- [A unified framework for learning with nonlinear model classes from arbitrary linear samples](https://mlsanity.com/paper/2311.14886/) (2023)
- [Denoising guarantees for optimized sampling schemes in compressed sensing](https://mlsanity.com/paper/2504.01046/) (2025)
- [How many measurements are enough? Bayesian recovery in inverse problems with general distributions](https://mlsanity.com/paper/2505.10630/) (2025)
- [Infinite dimensional generative sensing](https://mlsanity.com/paper/2603.03196/) (2026)
- [Partially deterministic sampling for compressed sensing with denoising guarantees](https://mlsanity.com/paper/2604.04802/) (2026)
- [Active Learning for Conditional Generative Compressed Sensing](https://mlsanity.com/paper/2605.05435/) (2026)

## Abstract (arXiv)

In Bora et al. (2017), a mathematical framework was developed for compressed sensing guarantees in the setting where the measurement matrix is Gaussian and the signal structure is the range of a generative neural network (GNN). The problem of compressed sensing with GNNs has since been extensively analyzed when the measurement matrix and/or network weights follow a subgaussian distribution. We move beyond the subgaussian assumption, to measurement matrices that are derived by sampling uniformly at random rows of a unitary matrix (including subsampled Fourier measurements as a special case). Specifically, we prove the first known restricted isometry guarantee for generative compressed sensing with subsampled isometries and provide recovery bounds, addressing an open problem of Scarlett et al. (2022, p. 10). Recovery efficacy is characterized by the coherence, a new parameter, which measures the interplay between the range of the network and the measurement matrix. Our approach relies on subspace counting arguments and ideas central to high-dimensional probability. Furthermore, we propose a regularization strategy for training GNNs to have favourable coherence with the measurement operator. We provide compelling numerical simulations that support this regularized training strategy: our strategy yields low coherence networks that require fewer measurements for signal recovery. This, together with our theoretical results, supports coherence as a natural quantity for characterizing generative compressed sensing with subsampled isometries.