Provable Compressed Sensing with Generative Priors via Langevin Dynamics

Thanh V. Nguyen, Gauri Jagatap, Chinmay Hegde

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. Here, we assume an 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. In this paper, 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.

Introduction

In the field of inverse problems, compressed sensing seeks to recover a high-dimensional signal—such as a high-resolution image—from a limited set of low-dimensional, potentially noisy linear measurements. Because the problem is inherently underdetermined, success relies on the use of "priors," or mathematical assumptions about the signal's underlying structure. Traditionally, these priors assumed sparsity in a fixed basis (like wavelets). However, recent advances have shifted toward using pre-trained deep generative models (e.g., GANs or VAEs) as priors, which can capture much more complex data distributions.

The standard recovery method involves searching the latent space of the generator to find a vector that, when passed through the network, minimizes the reconstruction error. While Gradient Descent (GD) is the tool of choice for this search, it faces a significant hurdle: the loss landscape of deep neural networks is highly non-convex. Consequently, GD often becomes trapped in local minima, necessitating multiple random restarts to find a globally optimal solution. This paper addresses this gap by proposing a recovery framework with provable global convergence guarantees.

Methodology: From Optimization to Sampling

To overcome the limitations of standard gradient descent, this research reframes signal recovery as a Bayesian sampling problem. Rather than seeking a single point via pure optimization, the authors employ Stochastic Gradient Langevin Dynamics (SGLD).

SGLD modifies the standard gradient update rule by injecting a carefully scaled amount of Gaussian noise at each iteration. This noise serves a critical purpose: it allows the algorithm to "hop" out of local minima and saddle points that would otherwise stall a deterministic gradient descent process. Mathematically, this acts as an Euler discretization of a continuous-time diffusion process, effectively sampling from a Gibbs distribution where the energy function corresponds to the reconstruction loss.

To provide rigorous guarantees, the authors introduce CS-SGLD. This variant incorporates a Metropolis-Hastings accept/reject step to ensure the latent vector remains within a bounded domain. By applying conductance analysis from Markov Chain Monte Carlo (MCMC) theory, the authors prove that this noisy process converges to the true underlying signal in finite time.

Theoretical Contributions

A primary contribution of this work is the introduction of the "Strong Smoothness" condition for generative networks. The authors demonstrate that feed-forward networks satisfy this property if they utilize strictly increasing, continuously differentiable activation functions (such as ELU or sigmoid) and maintain non-decreasing layer sizes.

Under these conditions, the paper establishes the first finite-time polynomial convergence guarantee for compressed sensing with generative priors. Furthermore, the theory confirms that the number of measurements required for successful recovery scales linearly with the latent dimension of the generator, rather than the ambient dimension of the signal. This aligns with the information-theoretic optimal bounds for compressed sensing.

Empirical Results

The authors validated their theoretical findings using standard benchmarks, including the MNIST and CIFAR-10 datasets. They trained DCGAN generators to serve as the generative priors and compared SGLD against standard GD.

  • Performance: On MNIST (at 20% measurements) and CIFAR-10 (at 30% measurements), SGLD consistently achieved lower Mean Squared Error (MSE) than standard GD.
  • Efficiency in Search: While standard GD implementations typically require approximately 10 random restarts to avoid poor local minima, SGLD achieved superior and more consistent results in a single run. The injected Langevin noise naturally navigated the non-convex landscape, eliminating the need for the computationally expensive restart strategy.
  • ReLU Networks: Although the formal proof for strong smoothness requires strictly increasing activations, empirical tests showed that standard ReLU-based GANs still exhibit this property in practice, suggesting the method's broad applicability.

Limitations and Future Work

While SGLD provides a robust theoretical foundation, it is not without limitations. The current theoretical convergence rate is polynomial, which is slower than the logarithmic rates seen in some local optimization methods. Additionally, the formal proof does not yet cover the non-differentiable points of ReLU activations, though empirical evidence is promising. Future research will focus on tightening these convergence bounds and extending the rigorous proofs to a wider variety of network architectures and activation functions.

Conclusion

By bridging the gap between MCMC sampling and deep generative priors, this work provides a provable path forward for signal recovery in non-convex landscapes. The transition from deterministic optimization to stochastic dynamics not only offers theoretical peace of mind but also yields practical benefits by making signal recovery more robust and less dependent on heuristic initialization strategies.

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. Here, we assume an 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. In this paper, 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},
}
Figure