# Robust Compressed Sensing using Generative Models

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

## Built on by (most cited first, 30 of 33)

- [Solving Inverse Problems in Medical Imaging with Score-Based Generative Models](https://mlsanity.com/paper/2111.08005/) (2021)
- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Deblurring via Stochastic Refinement](https://mlsanity.com/paper/2112.02475/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [A Theoretical Justification for Image Inpainting using Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2302.01217/) (2023)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Adaptive Compressed Sensing with Diffusion-Based Posterior Sampling](https://mlsanity.com/paper/2407.08256/) (2024)
- [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)
- [Robust Imitation Learning from Corrupted Demonstrations](https://mlsanity.com/paper/2201.12594/) (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)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Optimization for Amortized Inverse Problems](https://mlsanity.com/paper/2210.13983/) (2022)
- [Beyond Independent Measurements: General Compressed Sensing with GNN Application](https://mlsanity.com/paper/2111.00327/) (2021)
- [Over-the-Air Design of GAN Training for mmWave MIMO Channel Estimation](https://mlsanity.com/paper/2205.12445/) (2022)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Block Sparse Bayesian Learning: A Diversified Scheme](https://mlsanity.com/paper/2402.04646/) (2024)
- [Score-Based Variational Inference for Inverse Problems](https://mlsanity.com/paper/2410.05646/) (2024)
- [How many measurements are enough? Bayesian recovery in inverse problems with general distributions](https://mlsanity.com/paper/2505.10630/) (2025)
- [Image Restoration via Diffusion Models with Dynamic Resolution](https://mlsanity.com/paper/2605.14267/) (2026)
- [Latent Space Imaging](https://mlsanity.com/paper/2407.07052/) (2024)
- [A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptions](https://mlsanity.com/paper/2306.04756/) (2023)
- [Compressed Sensing of Generative Sparse-latent (GSL) Signals](https://mlsanity.com/paper/2310.15119/) (2023)
- [Chasing Better Deep Image Priors between Over- and Under-parameterization](https://mlsanity.com/paper/2410.24187/) (2024)
- [Sparse Bayesian Generative Modeling for Compressive Sensing](https://mlsanity.com/paper/2411.09483/) (2024)
- [Real-Time Network Traffic Forecasting with Missing Data: A Generative Model Approach](https://mlsanity.com/paper/2506.09647/) (2025)

## Abstract (arXiv)

The goal of compressed sensing is to estimate a high dimensional vector from an underdetermined system of noisy linear equations. In analogy to classical compressed sensing, here we assume a generative model as a prior, that is, we assume the vector is represented by a deep generative model G: ℝk rightarrow ℝn. Classical recovery approaches such as empirical risk minimization (ERM) are guaranteed to succeed when the measurement matrix is sub-Gaussian. However, when the measurement matrix and measurements are heavy-tailed or have outliers, recovery may fail dramatically. In this paper we propose an algorithm inspired by the Median-of-Means (MOM). Our algorithm guarantees recovery for heavy-tailed data, even in the presence of outliers. Theoretically, our results show our novel MOM-based algorithm enjoys the same sample complexity guarantees as ERM under sub-Gaussian assumptions. Our experiments validate both aspects of our claims: other algorithms are indeed fragile and fail under heavy-tailed and/or corrupted data, while our approach exhibits the predicted robustness.