In classical compressed sensing, recovering a high-dimensional signal $x \in \mathbb{R}^n$ from a small number of linear measurements $y = Ax$ relies on the assumption of sparsity. If a signal has only $s$ non-zero entries in some basis, it can be perfectly reconstructed using $O(s \log(n/s))$ measurements.
However, real-world data structures—such as natural images or complex physical signals—are rarely just sparse in a fixed coordinate basis. Instead, they tend to lie on intricate, non-linear, low-dimensional manifolds.
This realization motivated a paradigm shift: replacing traditional sparsity constraints with generative priors. Instead of assuming a signal is sparse, we assume it lies within the range of a pre-trained deep generative model (like a GAN or VAE) $G: \mathbb{R}^k \to \mathbb{R}^n$, where the latent dimension $k$ is much smaller than the ambient dimension $n$. The core intuition of this approach is that the number of measurements required for successful recovery should depend on the intrinsic dimensionality of the data manifold ($k$) rather than the ambient space ($n$) or an arbitrary sparsity count.
The Latent Dimension Advantage
The foundational framework for this paradigm was established by Ashish Bora et al. in Compressed Sensing using Generative Models. They demonstrated that constraining the reconstruction search to the range of a generative model allows for high-fidelity signal recovery using significantly fewer measurements than standard methods like Lasso.
To understand why this works, consider the geometry of the problem. In traditional compressed sensing, the measurement matrix $A$ must preserve the lengths of all $s$-sparse vectors—a property known as the Restricted Isometry Property (RIP). With a generative prior, the measurement matrix only needs to preserve the structure of the manifold mapped out by $G$.
The authors proved that if $G$ is an $L$-Lipschitz continuous function, the number of random Gaussian measurements needed to guarantee robust recovery scales as:
$$m = O(k \log L)$$
This logarithmic dependence on the Lipschitz constant $L$ means that even if the generative network is deep and highly expressive, the required sample size is primarily driven by the latent dimension $k$. As highlighted in a comprehensive survey by Jonathan Scarlett et al. in Theoretical Perspectives on Deep Learning Methods in Inverse Problems, leveraging these compressed representations pushes sample complexity near information-theoretic limits.
This principle holds true across diverse network architectures. For instance, Ben Adcock et al. developed a non-asymptotic Bayesian framework in How many measurements are enough? Bayesian recovery in inverse problems with general distributions, confirming that the minimum sampling rate for stable Bayesian recovery scales log-linearly with the latent dimension. Even when utilizing untrained neural network priors, as explored by Gauri Jagatap et al. in Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors, the measurement requirement is dictated by the network's internal parameter complexity rather than the total dimensionality of the ambient signal space.
Robustness to Non-Linearity and Noise
Real-world sensing systems are rarely perfectly linear. Signals are frequently subjected to non-linear transformations, quantization, or heavy-tailed noise. Generative priors offer remarkable resilience against these corruptions because the low-dimensional manifold acts as a powerful regularizer, preventing the reconstruction from fitting arbitrary noise.
Phase Retrieval and Single Index Models
In phase retrieval, we only observe the magnitudes of our measurements, discarding the phase information. Traditional sparsity-based phase retrieval often requires a quadratic number of measurements relative to the sparsity level. However, Rakib Hyder et al. showed in Alternating Phase Projected Gradient Descent with Generative Priors for Solving Compressive Phase Retrieval that by constraining the search space to a generative model's latent space, one can accurately reconstruct images from highly undersampled data.
Furthermore, Zhaoqiang Liu et al. demonstrated in Misspecified Phase Retrieval with Generative Priors that this recovery achieves a linear dependence on the latent dimension $k$, even when the exact non-linear function generating the data is unknown or misspecified.
Generalized Lasso and Heavy Tails
This capability extends to broader non-linear observation models. In The Generalized Lasso with Nonlinear Observations and Generative Priors, Zhaoqiang Liu et al. proved that the sensing cost for recovering signals from arbitrary non-linear observations remains strictly proportional to the latent dimensionality.
Even when the data is plagued by non-Gaussian, heavy-tailed noise, the structural constraint of the manifold keeps the optimization bounded. As shown by Xiaohan Wei et al. in On the statistical rate of nonlinear recovery in generative models with heavy-tailed data, efficient high-dimensional recovery remains viable because the heavy-tailed perturbations cannot easily pull the solution off the tightly constrained generative manifold.
Smoothing the Optimization Landscape
One major theoretical hurdle of using deep generative models as priors is non-convexity. Optimizing a loss function through the layers of a deep neural network typically introduces a highly non-convex landscape filled with treacherous local minima. Why, then, do simple gradient-based methods work so well in practice?
The answer lies in the architectural properties of the generative networks themselves. PAul HAnd et al. provided global convergence guarantees in Global Guarantees for Blind Demodulation with Generative Priors. They proved that for sufficiently expansive random neural networks, the optimization landscape becomes remarkably well-behaved, effectively eliminating spurious local minima.
When dealing with more complex or rugged landscapes, alternative optimization strategies can bypass these hurdles entirely. Thanh V. Nguyen et al. demonstrated in Provable Compressed Sensing with Generative Priors via Langevin Dynamics that injecting controlled thermal noise via Stochastic Gradient Langevin Dynamics (SGLD) allows the optimizer to naturally escape local minima, providing finite-time polynomial convergence guarantees without requiring multiple random restarts.
From Instance-Specific to Uniform Recovery
Early theoretical guarantees for generative compressed sensing were largely non-uniform, meaning that a randomly generated sensing matrix $A$ would successfully recover a specific signal with high probability. However, practical imaging hardware requires a uniform guarantee: a single, fixed measurement matrix $A$ must be capable of recovering any signal that lies within the range of the generative prior.
To bridge this gap, Junren Chen et al. introduced a unified framework in A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing. By developing advanced concentration inequalities and Lipschitz approximation techniques, they proved that uniform recovery under non-linear observations is achievable with a sample complexity that scales linearly with the latent dimension:
$$m = \tilde{O}\left(\frac{k}{\epsilon^2}\right)$$
This matches the sample efficiency of non-uniform methods, providing a rigorous foundation for building reliable physical sensing devices.
This uniform embedding property is remarkably resilient. Zhaoqiang Liu et al. extended these uniform guarantees to extreme sensing environments in Uniform Recovery Guarantees for Quantized Corrupted Sensing Using Structured or Generative Priors, proving that a single sensing matrix can uniformly recover any signal and corruption pair even when the measurements are coarsely quantized to a few bits. By shifting our perspective from counting non-zero coefficients to mapping low-dimensional continuous manifolds, generative priors allow us to reconstruct the complex world around us with unprecedented efficiency.
Key Foundational Work
Alternating Phase Projected Gradient Descent with Generative Priors for Solving Compressive Phase Retrieval (2019) — contributed 2 concept elements to this direction.
Compressed Sensing using Generative Models (2017) — contributed 2 concept elements to this direction.
Global Guarantees for Blind Demodulation with Generative Priors (2019) — contributed 2 concept elements to this direction.