Compressed Sensing using Generative Models

Abstract

The goal of compressed sensing is to estimate a vector from an underdetermined system of noisy linear measurements, by making use of prior knowledge on the structure of vectors in the relevant domain. For almost all results in this literature, the structure is represented by sparsity in a well-chosen basis. We show how to achieve guarantees similar to standard compressed sensing but without employing sparsity at all. Instead, we suppose that vectors lie near the range of a generative model $G:{\mathbb{R}}^k\to {\mathbb{R}}^n$. Our main theorem is that, if $G$ is $L$-Lipschitz, then roughly $O(k\log L)$ random Gaussian measurements suffice for an ${\ell }_2/{\ell }_2$ recovery guarantee. We demonstrate our results using generative models from published variational autoencoder and generative adversarial networks. Our method can use $5$-$10$x fewer measurements than Lasso for the same accuracy.

References in corpus (4)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Fast global convergence of gradient methods for high-dimensional statistical recovery

Cited by in corpus (91)

• Spectral DiffuserCam: lensless snapshot hyperspectral imaging with a spectral filter array
• Deep Decoder: Concise Image Representations from Untrained Non-convolutional Networks
• Solving Inverse Problems With Deep Neural Networks -- Robustness Included?
• Learning to Optimize: A Primer and A Benchmark
• Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors
• Measuring Robustness in Deep Learning Based Compressive Sensing
• Recent Advances in Imaging Around Corners
• Robust Compressed Sensing MRI with Deep Generative Priors
• Generative Models for Low-Rank Video Representation and Reconstruction
• Recovering compressed images for automatic crack segmentation using generative models
• Deep Neural Networks with Trainable Activations and Controlled Lipschitz Constant
• Solving Inverse Problems by Joint Posterior Maximization with Autoencoding Prior
• Solving Inverse Problems with Hybrid Deep Image Priors: the challenge of preventing overfitting
• Using latent space regression to analyze and leverage compositionality in GANs
• An Unsupervised Reconstruction Method For Low-Dose CT Using Deep Generative Regularization Prior
• DeepFlow: History Matching in the Space of Deep Generative Models
• Learning Space Partitions for Nearest Neighbor Search
• Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation
• Fast Compressive Sensing Recovery Using Generative Models with Structured Latent Variables
• Neumann Networks for Inverse Problems in Imaging
• CoIL: Coordinate-based Internal Learning for Imaging Inverse Problems
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
• Optimal Transport driven CycleGAN for Unsupervised Learning in Inverse Problems
• Bayesian Inference with Generative Adversarial Network Priors
• SGD Learns One-Layer Networks in WGANs
• Globally Injective ReLU Networks
• Self-Validation: Early Stopping for Single-Instance Deep Generative Priors
• Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie
• Coresets for Classification -- Simplified and Strengthened
• Lower Bounds for Compressed Sensing with Generative Models
• The Generalized Lasso with Nonlinear Observations and Generative Priors
• Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applications
• Invert and Defend: Model-based Approximate Inversion of Generative Adversarial Networks for Secure Inference
• Learning-based Support Estimation in Sublinear Time
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
• Variational Inference for Computational Imaging Inverse Problems
• When and How Can Deep Generative Models be Inverted?
• Co-VeGAN: Complex-Valued Generative Adversarial Network for Compressive Sensing MR Image Reconstruction
• Solving Inverse Problems by Joint Posterior Maximization with a VAE Prior
• An Overview on the Application of Graph Neural Networks in Wireless Networks
• Quantum Algorithms for the Pathwise Lasso
• Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis
• Prior Image-Constrained Reconstruction using Style-Based Generative Models
• Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
• Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal Statistical Rate and Global Landscape Analysis
• Inference in Multi-Layer Networks with Matrix-Valued Unknowns
• Surfing: Iterative optimization over incrementally trained deep networks
• RODE-Net: Learning Ordinary Differential Equations with Randomness from Data
• Constant-Expansion Suffices for Compressed Sensing with Generative Priors
• Parallel and Flexible Sampling from Autoregressive Models via Langevin Dynamics
• Learning-Augmented $k$-means Clustering
• Subspace Embeddings Under Nonlinear Transformations
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors
• Image Restoration from Parametric Transformations using Generative Models
• Bayesian Reasoning with Trained Neural Networks
• Learning Generative Models of Structured Signals from Their Superposition Using GANs with Application to Denoising and Demixing
• Scalable Deep Compressive Sensing
• Deep Decomposition Learning for Inverse Imaging Problems
• On the convergence of group-sparse autoencoders
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Learning Illumination Patterns for Coded Diffraction Phase Retrieval
• High Dimensional Linear Regression using Lattice Basis Reduction
• Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models
• Solving inverse problems via auto-encoders
• Alternating Phase Projected Gradient Descent with Generative Priors for Solving Compressive Phase Retrieval
• The Nonconvex Geometry of Linear Inverse Problems
• A Projectional Ansatz to Reconstruction
• Bayesian Imaging With Data-Driven Priors Encoded by Neural Networks: Theory, Methods, and Algorithms
• Universal Joint Approximation of Manifolds and Densities by Simple Injective Flows
• Image De-Quantization Using Generative Models as Priors
• Learning Generative Prior with Latent Space Sparsity Constraints
• Generator Surgery for Compressed Sensing
• Deep generative demixing: Recovering Lipschitz signals from noisy subgaussian mixtures
• Provably Convergent Algorithms for Solving Inverse Problems Using Generative Models
• Data Summarization via Bilevel Optimization
• OpenICS: Open Image Compressive Sensing Toolbox and Benchmark
• Model-Aware Regularization For Learning Approaches To Inverse Problems
• Tree Search Network for Sparse Regression
• Solving Inverse Problems with Conditional-GAN Prior via Fast Network-Projected Gradient Descent
• Beyond Independent Measurements: General Compressed Sensing with GNN Application
• Generative Tomography Reconstruction
• Solving Inverse Problems for Spectral Energy Distributions with Deep Generative Networks
• Non-Convex Compressed Sensing with Training Data
• SUREMap: Predicting Uncertainty in CNN-based Image Reconstruction Using Stein's Unbiased Risk Estimate
• Compressed Sensing via Measurement-Conditional Generative Models
• Perceptual Image Restoration with High-Quality Priori and Degradation Learning
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors
• Fine-grained Action Segmentation using the Semi-Supervised Action GAN
• Class-Specific Blind Deconvolutional Phase Retrieval Under a Generative Prior
• Compressive Learning of Generative Networks
• Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension