On the Power of Compressed Sensing with Generative Models

Akshay Kamath, Eric Price, Sushrut KarmalkarICML 2020 · OpenReview

Overview

This paper establishes the fundamental theoretical limits of compressed sensing when using generative models (like GANs or VAEs) instead of traditional sparsity. The authors prove that existing measurement bounds are mathematically optimal and demonstrate that generative models are a strict generalization of sparsity by constructing a simple neural network that perfectly represents all $k$-sparse signals.

The Problem: Sparsity vs. Generative Models

In classical compressed sensing, the goal is to recover a high-dimensional signal $x \in \mathbb{R}^n$ from a small number of linear measurements $y = Ax$, where $m \ll n$. Traditionally, this is possible only if $x$ is "sparse" (contains mostly zeros).

Recently, the field has shifted toward using generative models $G: \mathbb{R}^k \to \mathbb{R}^n$ to define signal "structure." Instead of assuming $x$ is sparse, researchers assume $x$ lies in the range of a pre-trained neural network. A landmark 2017 paper by Bora et al. showed that if $G$ is $L$-Lipschitz, one can recover $x$ using $O(k \log(Lr/\delta))$ measurements.

However, two major questions remained unresolved:

  1. Is this bound tight? Can we achieve recovery with fewer measurements, or is this the absolute physical limit?
  2. How does this relate to classical sparsity? Is a generative model truly a "richer" representation, or just a different one?

Methodology

The authors employ two distinct theoretical approaches to answer these questions:

1. Communication Complexity for Lower Bounds To prove the measurement bound is tight, the authors use a reduction from the "Augmented Indexing" problem in communication complexity. They construct a "well-separated" set of points within the range of a Lipschitz generative model. They show that if an algorithm could recover the signal with fewer measurements than the predicted bound, it would effectively be solving a communication problem with fewer bits than theoretically possible.

2. Constructive Neural Network Design To bridge the gap between generative models and sparsity, the authors explicitly design a ReLU-based neural network. They utilize specialized "gadgets"—groups of neurons designed to activate only within specific angular ranges in polar coordinates.

Neural network gadget designed to represent sparse signals

These gadgets allow the network to create a mapping where the output can perfectly represent any $k$-sparse vector.

Angular activation regions for the neural network gadgets
(Note: As a theoretical paper focused on proving fundamental limits and existence theorems, no empirical datasets like MNIST or CelebA were used. The "data" consists of mathematical objects: Lipschitz functions and $k$-sparse vector spaces.)

Key Insights

  • The Necessity of the Error Term ($\delta$): In classical sparse recovery, exact recovery is sometimes achievable. This paper highlights a fundamental difference: for Lipschitz generative models, an additive error $\delta$ is unavoidable if you want to use fewer than $n$ measurements. The complexity of the problem is inextricably linked to how precisely you want to recover the signal.
  • Generative Models > Sparsity: The authors prove that generative models are a strict generalization of sparsity. By showing that a 2-layer ReLU network can represent the set of all $k$-sparse vectors, they demonstrate that any theoretical guarantee for generative models automatically applies to traditional compressed sensing.
  • Tightness of the Bora et al. Bound: The paper confirms that the $O(k \log(Lr/\delta))$ bound isn't just a limitation of current algorithms—it is a fundamental information-theoretic limit. No matter how clever the recovery algorithm, one cannot beat this scaling for general Lipschitz models.

Key Results

  • Optimal Lower Bound: The authors prove that for any $L$-Lipschitz generative model, the number of measurements $m$ must be at least $\Omega(k \log(Lr/\delta))$. This perfectly matches the known upper bound, closing the theoretical gap.
  • Sparsity Representation: They show that a ReLU network with just 2 hidden layers and $O(n)$ activations per layer can have a range that is precisely the set of all $k$-sparse vectors.
  • Non-Uniform Recovery: Their lower bound holds even for "non-uniform" recovery, a more relaxed setting where the measurement matrix $A$ only needs to work for most signals rather than all of them.

Limitations and Future Work

  • Computational vs. Information-Theoretic Limits: While this paper proves how many measurements are needed, it doesn't solve the problem of how to efficiently find the signal. Recovery in generative models usually involves solving a non-convex optimization problem, which can be prone to local minima.
  • Specific Architectures: The lower bound applies to the broad class of $L$-Lipschitz functions. Future work could investigate if more specific architectural constraints (like those found in actual GANs or Invertible Neural Networks) allow for even better bounds.
  • Construction Complexity: While the authors show a 2-layer network can represent sparsity, the Lipschitz constant of such a network might be very high. There is a trade-off between the "width" of the network and its Lipschitz smoothness that remains to be fully explored.

Summary updated

Abstract

The goal of compressed sensing is to learn a structured signal $x$ from a limited number of noisy linear measurements $y \approx Ax$. In traditional compressed sensing, “structure” is represented b...
BibTeX
@inproceedings{kamath2020power,
  author = {Akshay Kamath and Eric Price and Sushrut Karmalkar},
  title = {{On the Power of Compressed Sensing with Generative Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=M2X_-aTUBD},
}
Figure