Signal Recovery with Non-Expansive Generative Network Priors

Jorio CocolaNeurIPS 2022

This paper, originally presented at NeurIPS 2022, bridges a critical gap between deep learning theory and practice in the realm of compressed sensing. By introducing a novel mathematical condition, the author proves that high-dimensional signals can be successfully recovered from compressed measurements using generative models—even when those models feature "contractive" or non-expansive layers.

The Challenge of Generative Priors in Compressed Sensing

In compressed sensing, the objective is to reconstruct a high-dimensional signal (such as an image) from a relatively small number of linear measurements. Traditionally, researchers relied on the assumption that signals were "sparse" to make this reconstruction mathematically feasible. More recently, a powerful alternative has emerged: assuming the signal lies within the range of a pre-trained generative model, such as a Generative Adversarial Network (GAN) or a Variational Autoencoder (VAE).

However, early mathematical guarantees for this "generative prior" approach came with a significant limitation: they required the generative network to be strictly expansive. This meant every layer had to be wider than the preceding one. In practice, state-of-the-art architectures like StyleGAN frequently employ contractive layers where the dimensionality decreases. This paper addresses a major open question: Can we still guarantee signal recovery if the generative network is non-expansive or contractive?

Methodology and the R2WDC Innovation

The paper tackles this problem using a combination of high-dimensional probability and non-convex optimization analysis.

1. The Optimization Algorithm

The author employs a standard Subgradient Descent method. Because ReLU activation functions introduce non-smoothness into the loss function, the analysis relies on "Clarke subdifferentials." A critical feature of the proposed algorithm is a "negation step"—if the loss at $-x$ is lower than at $x$, the algorithm jumps to $-x$. This mechanism allows the solver to escape a known spurious local minimum that frequently traps gradient-based approaches in these types of problems.

2. Range Restricted Weight Distribution Condition (R2WDC)

The core theoretical breakthrough of the paper is the introduction of the Range Restricted Weight Distribution Condition (R2WDC). Previous mathematical proofs relied on the standard Weight Distribution Condition (WDC), which required weight matrices to behave like near-isometries across the entire space.

R2WDC relaxes this strict requirement. It mandates "nice" near-isometric behavior only on the specific subset of the space that the previous layers of the network can actually reach (its "range").

3. Theoretical Framework

The author proves that random Gaussian networks satisfy this new R2WDC with high probability, even when layers are contractive. The primary requirement is that layer widths must be at least proportional to the input dimension, up to polynomial factors of the network's depth.

Key Insights and Broad Applicability

  • Weakening the Requirements: The pivotal insight of this work is realizing that a weight matrix does not need to be well-behaved everywhere—only where the data actually lives. By restricting the condition to the range of the previous layer, the mathematics finally accommodate the "bottlenecks" common in real-world neural networks.
  • Polynomial vs. Exponential Bounds: Previous attempts to analyze non-expansive networks resulted in error bounds or measurement requirements that grew exponentially with the depth of the network ($d$). This paper successfully achieves bounds that are polynomial in $d$, making the theory vastly more applicable to deep architectures.
  • Beyond Compressed Sensing: The utility of R2WDC extends beyond basic compressed sensing. The author demonstrates that it can provide the first recovery guarantees for non-expansive priors in several other complex domains, including Phase Retrieval (recovering signals from magnitude-only measurements), Denoising, and Spiked Matrix Recovery.

Key Results

The theoretical framework yields several strong guarantees for signal recovery:

  1. Optimal Measurement Complexity: The paper proves that a signal can be recovered using $m = \Omega(k \cdot \text{poly}(d))$ measurements (where $k$ is the latent dimension). This is information-theoretically optimal up to the polynomial depth factor and logarithmic terms.
  2. Noise Robustness: The reconstruction error is bounded by $O(\sqrt{k/m} \|\eta\|_2)$, where $\eta$ represents the measurement noise. This demonstrates a clear "denoising effect," where increasing the number of measurements $m$ directly suppresses the impact of noise.
  3. Global Convergence: Despite the objective function being non-convex, the paper proves that the subgradient descent algorithm will reliably enter a region of local convergence and eventually reach an estimate close to the true underlying signal.

Limitations and Future Work

While a significant theoretical step forward, the paper notes a few limitations that pave the way for future research:

  • Gaussian Assumption: The proofs currently rely on the assumption that network weights are independent and identically distributed (i.i.d.) Gaussian variables ($W_i \sim N(0, 1/n_i)$). Real-world trained weights are highly structured and non-Gaussian.
  • Lack of Biases: The model assumes a simplified network structure: $G(x) = \text{ReLU}(W_d \dots \text{ReLU}(W_1 x))$. Most practical networks include bias terms ($Wx + b$), which are not yet covered by this specific theory.
  • Sharpness of Depth Bounds: The author acknowledges that the polynomial dependence on depth (which reaches $d^{90}$ in some constants) is likely an artifact of the proof technique and is much higher than what is observed empirically. Future work will need to aim for tighter mathematical constants.

Summary updated

BibTeX
@inproceedings{cocola2022signal,
  author = {Jorio Cocola},
  title = {{Signal Recovery with Non-Expansive Generative Network Priors}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
}
Figure