# Beyond Independent Measurements: General Compressed Sensing with GNN Application

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 30 Oct 2021.

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

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Compressed Sensing with Deep Image Prior and Learned Regularization](https://mlsanity.com/paper/1806.06438/) (2018)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Robust Compressed Sensing using Generative Models](https://mlsanity.com/paper/2006.09461/) (2020)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [The Squared-Error of Generalized LASSO: A Precise Analysis](https://mlsanity.com/paper/1311.0830/) (2013)
- [The Average-Case Time Complexity of Certifying the Restricted Isometry Property](https://mlsanity.com/paper/2005.11270/) (2020)
- [Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applications](https://mlsanity.com/paper/2001.10631/) (2020)
- [Simple Error Bounds for Regularized Noisy Linear Inverse Problems](https://mlsanity.com/paper/1401.6578/) (2014)

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

- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [A coherence parameter characterizing generative compressed sensing with Fourier measurements](https://mlsanity.com/paper/2207.09340/) (2022)
- [Denoising guarantees for optimized sampling schemes in compressed sensing](https://mlsanity.com/paper/2504.01046/) (2025)
- [Active Learning for Conditional Generative Compressed Sensing](https://mlsanity.com/paper/2605.05435/) (2026)

## Abstract (arXiv)

We consider the problem of recovering a structured signal x ∈ ℝn from noisy linear observations y =M x+w. The measurement matrix is modeled as M = BA, where B ∈ ℝl × m is arbitrary and A ∈ ℝm × n has independent sub-gaussian rows. By varying B, and the sub-gaussian distribution of A, this gives a family of measurement matrices which may have heavy tails, dependent rows and columns, and singular values with a large dynamic range. When the structure is given as a possibly non-convex cone T subset ℝn, an approximate empirical risk minimizer is proven to be a robust estimator if the effective number of measurements is sufficient, even in the presence of a model mismatch. In classical compressed sensing with independent (sub-)gaussian measurements, one asks how many measurements are needed to recover x? In our setting, however, the effective number of measurements depends on the properties of B. We show that the effective rank of B may be used as a surrogate for the number of measurements, and if this exceeds the squared Gaussian mean width of (T-T) cap mathbbSn-1, then accurate recovery is guaranteed. Furthermore, we examine the special case of generative priors in detail, that is when x lies close to T = ran(G) and G: ℝk rightarrow ℝn is a Generative Neural Network (GNN) with ReLU activation functions. Our work relies on a recent result in random matrix theory by Jeong, Li, Plan, and Yilmaz arXiv:2001.10631. .