Compressed Sensing using Generative Models

Ashish Bora; Ajil Jalal; Eric Price; Alexandros G. Dimakis

Source-linked AI summary

Compressed Sensing using Generative Models

Ashish Bora, Ajil Jalal, Eric Price, Alexandros G. Dimakis

arXiv:1703.03208v1Mar 9, 2017stat.MLcs.ITcs.LG

TL;DR

Compressed sensing seeks recovery from noisy, underdetermined measurements, traditionally using sparsity as the structural prior. This paper instead optimizes over the range of a generative model and establishes recovery guarantees for that setting. The authors conclude that generative models can enable substantially fewer measurements than standard sparsity-based methods.

Problem
Compressed sensing must recover vectors from noisy, underdetermined measurements, but standard results generally represent structure through sparsity in a chosen basis.
Method
The paper uses a pretrained generative model and gradient descent to find a representation whose generated sample matches the observed measurements, with guarantees based on S-REC.
Results
Theorems and experiments show reconstruction becomes close to the optimum within the generator range after relatively few measurements.
Takeaways & Limitations
Generative models can represent data distributions more concisely than standard sparsity models and support compressed sensing with significantly fewer measurements.
Takeaways & Limitations
The guarantees assume bounded representation norms and, for the stated neural-network result, architectures with piecewise-linear nonlinearities having at most two pieces.

Abstract

from arXiv · show

The goal of compressed sensing is to estimate a vector from an underdetermined system of noisy linear measurements, by making use of prior knowledge on the structure of vectors in the relevant domain. For almost all results in this literature, the structure is represented by sparsity in a well-chosen basis. We show how to achieve guarantees similar to standard compressed sensing but without employing sparsity at all. Instead, we suppose that vectors lie near the range of a generative model $G: \mathbb{R}^k \to \mathbb{R}^n$. Our main theorem is that, if $G$ is $L$-Lipschitz, then roughly $O(k \log L)$ random Gaussian measurements suffice for an $\ell_2/\ell_2$ recovery guarantee. We demonstrate our results using generative models from published variational autoencoder and generative adversarial networks. Our method can use $5$-$10$x fewer measurements than Lasso for the same accuracy.

1 Introduction

Compressed sensing traditionally relies on sparsity to recover vectors from noisy, underdetermined measurements, whereas this paper uses the range of a generative model as the structural prior. It develops theoretical guarantees and reports empirical reconstruction advantages over Lasso.

Motivation: Underdetermined noisy measurements require structural assumptions, traditionally sparsity in a known basis, for recovery.Compressed sensing has applications including tomography, CT, rapid MRI, neuronal spike recovery, and single-pixel cameras.
Motivation: Generative models replace sparsity by mapping a low-dimensional representation z ∈ R^k into high-dimensional samples G(z) ∈ R^n.The paper uses pretrained variational autoencoders and generative adversarial networks as priors.
Approach: Gradient descent optimizes z so that G(z) has small measurement error, producing the reconstruction G(ẑ).The objective is nonconvex, but the authors empirically find gradient descent works well.
Theory: The S-REC generalizes REC to generator ranges and yields recovery close to the closest point in the range when optimization finds a good approximate solution.The error bound includes representation error, measurement noise, and optimization tolerance ϵ.
Theory: O(kd log n) Gaussian measurements suffice for d-layer ReLU networks, while general L-Lipschitz generators require approximately O(k log L) measurements.Typical neural networks have L ≤ n^O(d), recovering the same O(kd log n) scaling for common activation functions.
Scope: The theory imposes bounded representation norm and additive δ conditions, which the paper describes as mild because their dependence is logarithmic.The authors suggest r = n^O(d) and δ = 1/n^O(d), losing only constant factors.
Theory: The guarantees extend beyond Gaussian matrices to matrices with subgaussian entries or fast-JL constructions.The proof uses the distributional Johnson–Lindenstrauss property.

2 Our Algorithm

The algorithm searches in the generator’s low-dimensional representation space for a sample whose measurements match the observations. Differentiability enables backpropagation and gradient-based optimization, with G(ẑ) used as the reconstruction.

Problem setup: The sensing model observes y = Ax* + η, where A is the measurement matrix and η is noise.The task is to recover x̂ close to the unknown x*.
Generator: A generative model maps a low-dimensional representation z ∈ R^k to a high-dimensional sample G(z) ∈ R^n.The model also specifies a distribution P_Z from which representations can be sampled.
Optimization: The method minimizes measurement loss(z) so that the generated vector matches the observed measurements.The optimization is performed with respect to the representation z rather than directly over the signal.
Optimization: For differentiable generators, backpropagation supplies gradients for standard optimizers, and termination at ẑ yields reconstruction G(ẑ).Measurement error is ||AG(ẑ) − y||_2, while reconstruction error is ||G(ẑ) − x*||_2.

3 Related Work

Related work covers generator-based projection with full observations, structured partial-observation tasks, invertible convolutional networks, and measurement complexity for smooth manifolds. The paper distinguishes its generator ranges from smooth manifolds because of ReLUs and self-intersections.

Generator-based reconstruction: Prior projection methods optimize in a generator’s representation space when the full image is known, corresponding to an identity measurement matrix.Reported approaches use SGD with stochastic clipping or logistic measurement loss.
Structured observations: Inpainting and super-resolution treat structured partial observations as linear measurements of missing pixels or local spatial averages.Prior methods for these tasks use generative models or other super-resolution approaches.
Other related work: Related work connects model-based compressed sensing with invertibility of convolutional neural networks.
Theoretical connections: Measurement complexity for smooth manifolds is analogous to the paper’s S-REC, but generator ranges can be nonsmooth because of ReLUs and can contain self-intersections.Prior recovery results were extended to unions of two manifolds.

4 Theoretical Results

The paper replaces sparsity-based recovery conditions with S-REC, a set-based condition applicable to generative-model ranges. Random Gaussian measurements satisfy this condition for broad neural-network generators, yielding recovery guarantees when combined with measurement norm preservation.

Set-Restricted Eigenvalue Condition: S-REC generalizes REC from approximately sparse vectors to differences between vectors in an arbitrary set S.This enables applying the condition when S is the range of a generative model.
Set-Restricted Eigenvalue Condition: The additive slack δ accommodates general Lipschitz generators by tolerating small-scale deviations that increase recovery error by O(δ).Without slack, guaranteeing the condition across arbitrarily many local regions is not possible.
Random measurements: Random Gaussian matrices satisfy S-REC with high probability for generator outputs, including bounded Lipschitz models and neural networks.For neural networks, the stated probability is 1−e^−Ω(α^2m).
Random measurements: For d-layer neural networks with piecewise-linear activations, the analysis establishes S-REC guarantees without requiring bounds on network weight magnitudes.The network assumptions include linear transformations followed by pointwise nonlinearities, with at most two pieces per nonlinearity.
Recovery guarantee: S-REC together with norm preservation implies that approximate measurement-error minimization over the generator range recovers a vector close to the unknown signal.The resulting error includes the best approximation error in the generator range, measurement noise, and an optimization term.

5 Models

The experiments evaluate the approach with a VAE and a GAN on two image datasets, using regularized latent optimization and comparisons against sparse-recovery baselines. Figure 1 reports per-pixel reconstruction error as the number of measurements varies.

Experimental setup: The experiments use two image datasets and two generative-model types: a VAE and a GAN.The authors present this setup as evidence that the approach can work across multiple models and datasets.
Experimental setup: The optimization adds a regularizer L(z) to encourage exploration in regions preferred by the corresponding generative model.Both models use isotropic Gaussian priors on z, motivating a regularizer based on ∥z∥2.
Experimental setup: Figure 1 plots per-pixel reconstruction error against the number of measurements and shows 95% confidence intervals with vertical bars.The figure compares the proposed algorithm with baseline methods.
MNIST with VAE: The MNIST experiment trains a VAE with a 20-dimensional representation on 28 × 28 binary digit images.Lasso on pixel values serves as the sparse-recovery baseline.
CelebA with DCGAN: The CelebA experiment trains a DCGAN with a 100-dimensional input on 64 × 64 RGB celebrity images.Additional baselines use Lasso with 2D-DCT and 2D-DB1 wavelet representations.

6.1 Reconstruction from Gaussian measurements

Using random Gaussian measurements and held-out test images, the generative-model algorithm achieves low reconstruction error with fewer measurements than Lasso, but its performance eventually saturates because outputs remain in the generator range.

6.1 Reconstruction from Gaussian measurements: Random Gaussian measurements and reconstruction error are evaluated on held-out test images, with Lasso using DCT and wavelet bases as baselines.The measurement matrix has IID Gaussian entries, and reconstruction error is ||x_hat − x*||_2.
6.1 Reconstruction from Gaussian measurements: 25 measurements for the generative-model algorithm match Lasso’s performance with 400 measurements on MNIST.The paper reports that the algorithm reaches low errors with far fewer measurements.
6.1 Reconstruction from Gaussian measurements: After 100 measurements on MNIST, the generative-model algorithm saturates; Lasso eventually surpasses it after more than 500 measurements.The saturation is attributed to the algorithm’s outputs being constrained to the generator range.
6.1 Reconstruction from Gaussian measurements: 500 measurements produce reasonable celebA reconstructions with the generative-model algorithm, while baseline outputs are described as quite blurry.The comparison uses a 12,288-dimensional image vector and includes Lasso with DCT and wavelet bases.
6.1 Reconstruction from Gaussian measurements: More than 5,000 measurements let Lasso obtain a better celebA reconstruction, while the generative-model algorithm is expected to benefit from a representation dimension k > 100.The paper again attributes the high-measurement limitation to saturation and anticipates stronger performance from a more powerful generator.

6.2 Super-resolution

The algorithm applies compressed-sensing recovery to super-resolution by treating pooled low-resolution pixels as linear measurements, producing detailed reconstructions on held-out images.

6.2 Super-resolution: Super-resolution is formulated as linear measurement recovery using a measurement matrix that records local spatial averages.The matrix is tailored to retain only the relevant observations, although it may not satisfy the S-REC condition.
6.2 Super-resolution: 2 × 2 pooling creates 14 × 14 measurements for reconstructing 28 × 28 MNIST images, yielding sharp reconstructions that closely match ground-truth fine structure.The evaluation uses images from a held-out test set.
6.2 Super-resolution: 4 × 4 pooling creates 16 × 16 measurements for reconstructing 64 × 64 celebA images, and the algorithm fills in details to match the original images.The results are shown on a held-out test set.

6.3 Understanding sources of error

Experiments separate representation, measurement, and optimization error, indicating that representation error is the dominant component of total reconstruction error on MNIST and celebA.

6.3 Understanding sources of error: The paper identifies representation, measurement, and optimization error as three sources of reconstruction error.Representation error reflects distance from the generator range; measurement error reflects incomplete sensing; optimization error reflects failure to find the best latent code.
6.3 Understanding sources of error: Experiments isolate representation error from the other two terms by placing images in the generator range or eliminating measurement error with full observations.These experiments are designed to assess which error component dominates.
6.3.1 Sensing images from the range of the generator: Images generated from latent codes achieve almost perfect reconstruction with very few measurements, indicating small combined measurement and optimization error when representation error is absent.The result is reported for generators trained on MNIST and celebA.
6.3 Understanding sources of error: The average per-pixel representation error is 0.005 on MNIST and 0.020 on celebA under full-image observations.The corresponding Gaussian-measurement reconstruction errors are about 0.009 with 100 measurements on MNIST and 0.028 with 500 measurements on celebA.
6.3 Understanding sources of error: The experiments suggest that representation error is the major component of total error, so more flexible generative models could reduce overall error on both datasets.The paper presents this as an experimental suggestion rather than a universal guarantee.

7 Conclusion

The paper demonstrates compressed sensing with neural generative models and argues that their compact data representations and differentiability support reconstruction from fewer measurements. It concludes that larger or improved generators are important as measurement counts increase.

7 Conclusion: Generative models from neural networks can represent data distributions more concisely than standard sparsity models and support differentiable signal reconstruction.The paper presents this as a route to using significantly fewer measurements in compressed-sensing applications.
7 Conclusion: Theorems and experiments suggest that reconstruction approaches the best possible point in the generator range after relatively few measurements.The conclusion distinguishes optimality within the generator range from unrestricted recovery.
7 Conclusion: Larger generative models are needed to realize the technique’s full potential as the number of measurements increases.The paper leaves open whether varying model size can be handled more concisely than training multiple independent generators.
7 Conclusion: Because the framework applies to general generative models, improvements in those models are expected to yield better reconstructions with fewer measurements.The authors also propose using performance on this task as a benchmark for generative-model quality.

8 Appendix A

Appendix A establishes that random Gaussian measurements preserve the geometry of a generative model’s range sufficiently for recovery, with measurement requirements controlled by latent dimension, Lipschitzness, and approximation scale.

8 Appendix A: The proof approximates G(B^k(r)) using nested epsilon nets whose radii decrease geometrically.The construction uses δ_i = δ_0/2^i and maps latent-space nets through the Lipschitz generator.
8 Appendix A: The telescoping decomposition expresses any point as a net representative plus successive differences and a final approximation error.Each difference belongs to a finite set of pairwise net differences, enabling a union-bound argument.
8 Appendix A: A random Gaussian matrix satisfies S-REC on G(B^k(r)) with probability 1 − e^−Ω(α^2m).The guarantee applies to an L-Lipschitz generator and preserves pairwise geometry up to the stated parameters.
8 Appendix A: For piecewise-linear d-layer networks with at most c nodes per layer, the generator range is a union of c^d k-faces.Within each input partition, the network is linear; a union bound then yields S-REC on the full range with probability 1 − e^−Ω(α^2m).
8 Appendix A: The generator’s Lipschitz constant is bounded by L = (Mcw_max)^d when each layer has at most c nodes, weights bounded by w_max, and nonlinearities are M-Lipschitz.The bound follows by composing the Lipschitz constants of the d layers.

9 Appendix B

Appendix B evaluates reconstruction under increasing noise and varying measurement counts, comparing the generative-model method with Lasso and end-to-end learned alternatives on MNIST and celebA.

9 Appendix B: Figure 8 plots per-pixel reconstruction error against noise level and displays 95% confidence intervals.The horizontal variable is the noise magnitude E[∥η∥2].
9 Appendix B: The generative-model algorithm has more noise tolerance than Lasso on both MNIST and celebA.The comparison fixes measurement counts at 500 for MNIST and 2500 for celebA before increasing the noise level.
9 Appendix B: End-to-end learned models are evaluated on MNIST with 10, 20, and 30 noiseless measurements using either fixed-random or learned measurement matrices.The learned measurement matrix is jointly optimized in one of the two approaches.
9 Appendix B: Reconstruction figures compare ground truth, Lasso, and the proposed algorithm on MNIST and celebA.The celebA comparisons include Lasso using DCT and wavelet bases.