Compressed Sensing using Generative Models

By Ashish Bora, Ajil Jalal, Eric Price, A. Dimakis. 2017

934 citations recorded by the source corpus.

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 : ℝk → ℝn. Our main theorem is that, if G is L-Lipschitz, then roughly O(k log L) random Gaussian measurements suffice for an l2/l2 recovery guarantee. We demonstrate our results using generative models from published variational autoencoder and generative adversarial networks. Our method can use 5-10x fewer measurements than Lasso for the same accuracy.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, Generative Models

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

In Generative Models

Citations in the corpus

GAN Inversion: A Survey (2021, background): “[138] propose to solve (37) using back-propagation and standard gradient-based optimization.”
The Robust Manifold Defense: Adversarial Training using Generative Models (2017, methodology): “We use the compressed sensing inversion method [7] instead: Given an input image x and a classiﬁer C , do not feed the image directly as an input to the classiﬁer, but rather treat it as noisy measurements of another true image x true in the range of a (pre-trained) generator G ( z ).”
PULSE: Self-Supervised Photo Upsampling via Latent Space Exploration of Generative Models (2020, background): “Indeed, this is how the previously mentioned work [5] attempts to address this issue.”
PacGAN: The Power of Two Samples in Generative Adversarial Networks (2017, background): “…over a family of all measurable functions; ( b ) the population expectation; and ( c ) the 0-1 loss function of the form: The ﬁrst assumption allows us to bypass the speciﬁc architecture of the discriminator used, which is common when analyzing neural network based discriminators (e.g. [7, 8]).”
CausalGAN: Learning Causal Implicit Generative Models with Adversarial Training (2017, background): “Another application of generative models is in compressed sensing: Authors in [6] give compressed sensing guarantees for recovering a vector, if the data lies close to the output of a generative model, such as a trained GAN.”
ClusterGAN : Latent Space Clustering in Generative Adversarial Networks (2018, methodology): “Unfortunately, no such inference mechanism exists in GANs, let alone the possibility of clustering in the latent space.”
Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation (2020, positive): “, 2014)) and then using the resulting image models to regularize problems such as compressed sensing (Bora et al., 2017; Hand & Voroninski, 2018; Huang et al., 2018), denoising (Heckel et al.”
Detecting Overfitting of Deep Generative Networks via Latent Recovery (2019, methodology): “SGD (successful recovery requiring approximately 50 iterations as opposed to 500 in [5, 18]).”
Prior Image-Constrained Reconstruction using Style-Based Generative Models (2021, positive): “It must be noted that certain assumptions in the theoretical analysis, such as the validity of a useful S-REC for non-Gaussian sensing matrices, and obtaining near-optimal approximations to Eq.”
Intermediate Layer Optimization for Inverse Problems using Deep Generative Models (2021, methodology): “The CSGM framework (Bora et al., 2017) used gradient descent to minimize the measurement mean squared error (MSE) and showed good empirical performance for numerous inverse problems including inpainting and compressed sensing with random Gaussian measurements using DC-GAN.”
DiffBIR: Towards Blind Image Restoration with Generative Diffusion Prior (2023, background): “Earlier works [2, 9, 36, 39] mainly concentrate on searching a latent code within a pre-trained GAN’s latent space.”
Inverting Deep Generative models, One layer at a time (2019, background): “Previous work focuses on the `2 norm that works slowly with gradient descent [4, 15].”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, background): “Most importantly, in contrast to [3, 2], we provide a global analysis of the nonconvex empirical risk objective function and constructively exhibit a descent direction at every point outside a neighborhood of the desired solution and a negative scalar multiple of it.”
When and How Can Deep Generative Models be Inverted? (2020, methodology): “A common and simple approach is to draw a random vector z and iteratively update it using gradient descent, opting to minimize Equation 1 [28, 5].”
GAN-Based Projector for Faster Recovery With Convergence Guarantees in Linear Inverse Problems (2019, methodology): “We compare the performance of our algorithm on MNIST and CelebA with other GAN-prior solvers ([4, 33]) and sparsity-based methods, Lasso with discrete cosine transform (DCT) basis [34] and total variation minimization method (TVAL3) [21] for linear inverse problems, namely compressed sensing (CS), s”
CNN-Based Projected Gradient Descent for Consistent CT Image Reconstruction (2017, background): “Similarly, in [31], the inverse problem is solved over a set parameterised by a generative model.”
MimicGAN: Robust Projection onto Image Manifolds with Corruption Mimicking (2019, methodology): “Subsequently, several efforts have pursued solving inverse problems us-ing PGD, for example compressive recovery [13], [52], and deblurring [8].”
Denoising Diffusion Restoration Models (2022, background): “Structures learned by generative models have been applied to various inverse problems and often outperform data-independent structural constraints such as sparsity (Bora et al., 2017).”
Solving Linear Inverse Problems Using Gan Priors: An Algorithm with Provable Guarantees (2018, methodology): “where δ is inversely proportional to the number of measurements m [17].”