Provable Compressed Sensing With Generative Priors via Langevin Dynamics

Thanh V. Nguyen, Gauri Jagatap, Chinmay Hegde

TL;DR

This paper tackles the problem of compressed sensing using deep generative models as priors. Because neural networks are highly non-convex, standard gradient descent often gets stuck in local minima during signal recovery; to fix this, the authors propose using Stochastic Gradient Langevin Dynamics (SGLD). They provide the first finite-time polynomial convergence guarantees for this approach and empirically demonstrate that it outperforms standard gradient descent by naturally escaping bad local minima without the need for multiple random restarts.

What Problem Does This Paper Address?

In inverse problems like compressed sensing, the goal is to recover a high-dimensional signal (like an image) from a small number of low-dimensional, potentially noisy linear measurements. Because this problem is mathematically ill-posed, researchers rely on "priors"—assumptions about the structure of the signal.

Recently, pre-trained deep generative models (like GANs or VAEs) have become incredibly popular and effective priors. The standard way to recover the signal is to run gradient descent (GD) on the latent space of the generator to find the latent vector that best matches the measurements. However, there is a major theoretical gap: neural networks are highly non-convex. Standard GD lacks global convergence guarantees and, in practice, often requires many random restarts to avoid getting trapped in local minima or saddle points. This paper seeks to bridge that gap by developing an algorithm with provable, global convergence guarantees for signal recovery.

Methods

Instead of treating signal recovery as a pure optimization problem, the authors reframe it as a sampling problem. They replace standard gradient descent with Stochastic Gradient Langevin Dynamics (SGLD).

SGLD modifies the standard gradient descent update rule by injecting a carefully scaled amount of Gaussian noise at each step. Intuitively, this acts as an Euler discretization of a continuous-time diffusion process. By adding this noise, the algorithm effectively samples from a Gibbs distribution where the "energy function" is the reconstruction loss.

To make the math work, the authors introduce CS-SGLD, a variant that includes a Metropolis-Hastings accept/reject step to ensure the latent vector stays within a bounded domain. They then use conductance analysis from Markov Chain Monte Carlo (MCMC) literature to prove that this noisy gradient process will eventually converge to the true underlying signal.

Datasets

The paper's primary focus is theoretical, but the authors validate their claims empirically using:

  • MNIST (handwritten digits)
  • CIFAR-10 (natural images)

Both datasets were used to train standard DCGAN generators to serve as the generative priors for the compressed sensing tasks.

Key Insights and Ideas

  • Noise is a Feature, Not a Bug: By framing the recovery as a Bayesian sampling problem via SGLD, the injected noise allows the algorithm to naturally escape the non-convex traps (local minima) inherent in deep generator landscapes.
  • The "Strong Smoothness" Condition: The authors introduce a new, relaxed mathematical condition for generative networks called "strong smoothness." They prove that feed-forward networks with strictly increasing, continuously differentiable activations (like ELU or sigmoid) and non-decreasing layer sizes satisfy this property.
  • Theory Meets Practice for ReLU: While their rigorous proof for strong smoothness requires strictly increasing activations, the authors empirically demonstrate that standard ReLU-based GANs still exhibit this strong smoothness property in practice.
  • Optimal Measurement Complexity: The theory proves that the number of measurements required for successful recovery scales linearly with the latent dimension of the generator, rather than the massive ambient dimension of the image. This matches the optimal theoretical bounds for compressed sensing.

Key Results

  • Theoretical Guarantee: The paper establishes the first finite-time convergence guarantee for compressed sensing with generative priors using a stochastic gradient-like method. They prove that CS-SGLD converges to the true signal in a polynomial number of iterations.
  • Empirical Superiority: On MNIST (using 20% measurements) and CIFAR-10 (using 30% measurements), SGLD achieved lower Mean Squared Error (MSE) than standard GD.
  • No Restarts Needed: Standard GD implementations for this task typically require ~10 random restarts to find a good solution. SGLD achieved better, more consistent reconstructions in a single run because the Langevin noise naturally pushes the optimization trajectory out of bad local minima.

Limitations and Future Work

  • Slow Convergence Rate: While SGLD is guaranteed to converge, the theoretical rate is polynomial. This can be slow compared to the logarithmic convergence of other methods (like linearized ADMM), though those faster methods only guarantee convergence to a neighborhood of the true signal, not the exact signal. Improving the theoretical convergence rate of CS-SGLD is a key future direction.
  • Activation Function Constraints: The formal proof of the "strong smoothness" condition does not currently cover ReLU networks (since ReLU is not strictly increasing/continuously differentiable). Extending the rigorous proof to ReLU remains an open problem.
  • Bounded Domain Assumption: The theoretical analysis requires the latent vector to be restricted to a bounded Euclidean ball via a Metropolis-Hastings step. While common in theory, the authors note this step isn't actually necessary for empirical success.

Summary updated

Abstract

Deep generative models have emerged as a powerful class of priors for signals in various inverse problems such as compressed sensing, phase retrieval and super-resolution. In this work, we consider the compressed sensing problem and assume the unknown signal to lie in the range of some pre-trained generative model. A popular approach for signal recovery is via gradient descent in the low-dimensional latent space. While gradient descent has achieved good empirical performance, its theoretical behavior is not well understood. We introduce the use of stochastic gradient Langevin dynamics (SGLD) for compressed sensing with a generative prior. Under mild assumptions on the generative model, we prove the convergence of SGLD to the true signal. We also demonstrate competitive empirical performance to standard gradient descent.
BibTeX
@article{nguyen2022provable,
  author = {Thanh V. Nguyen and Gauri Jagatap and Chinmay Hegde},
  title = {{Provable Compressed Sensing With Generative Priors via Langevin Dynamics}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=TStIsvxwp9},
}

Loading related content...

Figure