Compressed Sensing using Generative Models

Ashish Bora 1 Ajil Jalal 2 Eric Price 1 Alexandros G. Dimakis 2

Abstract of the unknown vector x⇤ . We need to assume that the un-

known vector is “natural,” or “simple,” in some application-
The goal of compressed sensing is to estimate a dependent way.
vector from an underdetermined system of noisy
linear measurements, by making use of prior The most common structural assumption is that the vec-
knowledge on the structure of vectors in the rel- tor x⇤ is k-sparse in some known basis (or approximately
evant domain. For almost all results in this lit- k-sparse). Finding the sparsest solution to an underdeter-
erature, the structure is represented by sparsity mined system of linear equations is NP-hard, but still con-
in a well-chosen basis. We show how to achieve vex optimization can provably recover the true sparse vec-
guarantees similar to standard compressed sens- tor x⇤ if the matrix A satisfies conditions such as the Re-
ing but without employing sparsity at all. In- stricted Isometry Property (RIP) or the related Restricted
stead, we suppose that vectors lie near the range Eigenvalue Condition (REC) (Tibshirani, 1996; Candes
of a generative model G : Rk ! Rn . Our main et al., 2006; Donoho, 2006; Bickel et al., 2009). The prob-
theorem is that, if G is L-Lipschitz, then roughly lem is also called high-dimensional sparse linear regression
O(k log L) random Gaussian measurements suf- and there is vast literature on establishing conditions for
fice for an `2 /`2 recovery guarantee. We demon- different recovery algorithms, different assumptions on the
strate our results using generative models from design of A and generalizations of RIP and REC for other
published variational autoencoder and generative structures, see e.g. (Bickel et al., 2009; Negahban et al.,
adversarial networks. Our method can use 5-10x 2009; Agarwal et al., 2010; Loh & Wainwright, 2011; Bach
fewer measurements than Lasso for the same ac- et al., 2012).
curacy. This significant interest is justified since a large number of
applications can be expressed as recovering an unknown
vector from noisy linear measurements. For example,
1. Introduction many tomography problems can be expressed in this frame-
work: x⇤ is the unknown true tomographic image and the
Compressive or compressed sensing is the problem of re- linear measurements are obtained by x-ray or other physi-
constructing an unknown vector x⇤ 2 Rn after observing cal sensing system that produces sums or more general lin-
m < n linear measurements of its entries, possibly with ear projections of the unknown pixels. Compressed sens-
added noise: ing has been studied extensively for medical applications
y = Ax⇤ + ⌘, including computed tomography (CT) (Chen et al., 2008),
rapid MRI (Lustig et al., 2007) and neuronal spike train
where A 2 Rm⇥n is called the measurement matrix and recovery (Hegde et al., 2009). Another impressive appli-
⌘ 2 Rm is noise. Even without noise, this is an under- cation is the “single pixel camera” (Duarte et al., 2008),
determined system of linear equations, so recovery is im- where digital micro-mirrors provide linear combinations to
possible unless we make an assumption on the structure a single pixel sensor that then uses compressed sensing re-
Code for experiments in the paper can be found at: construction algorithms to reconstruct an image. These re-
[Link] 1 University sults have been extended by combining sparsity with addi-
of Texas at Austin, Department of Computer Science tional structural assumptions (Baraniuk et al., 2010; Hegde
2
University of Texas at Austin, Department of Electrical et al., 2015), and by generalizations such as translating
and Computer Engineering. Correspondence to: Ashish Bora
<[Link]@[Link]>, Ajil Jalal <ajiljalal@[Link]>, sparse vectors into low-rank matrices (Negahban et al.,
Eric Price <ecprice@[Link]>, Alexandros G. Dimakis 2009; Bach et al., 2012; Foygel & Mackey, 2014). These
<dimakis@[Link]>. results can improve performance when the structural as-
sumptions fit the sensed signals. Other works perform “dic-
Proceedings of the 34 th International Conference on Machine tionary learning,” seeking overcomplete bases where the
Learning, Sydney, Australia, PMLR 70, 2017. Copyright 2017
by the author(s). data is more sparse (see (Chen & Needell, 2016) and refer-
 Compressed Sensing using Generative Models

ences therein). with 1 e ⌦(m)

probability,
In this paper instead of relying on sparsity, we use struc- kG(b
z) x⇤ k2  6 min kG(z ⇤ ) x⇤ k2 + 3k⌘k2 + 2✏.
ture from a generative model. Recently, several neural z ⇤ 2Rk
network based generative models such as variational auto-
encoders (VAEs) (Kingma & Welling, 2013) and genera- In the error bound above, the first two terms are the mini-
tive adversarial networks (GANs) (Goodfellow et al., 2014) mum possible error of any vector in the range of the genera-
have found success at modeling data distributions. In these tor and the norm of the noise; these are necessary for such a
models, the generative part learns a mapping from a low technique, and have direct analogs in standard compressed
dimensional representation space z 2 Rk to the high di- sensing guarantees. The third term ✏ comes from gradient
mensional sample space G(z) 2 Rn . While training, this descent not necessarily converging to the global optimum;
mapping is encouraged to produce vectors that resemble empirically, ✏ does seem to converge to zero, and one can
the vectors in the training dataset. We can therefore use check post-observation that this is small by computing the
any pre-trained generator to approximately capture the no- upper bound ky AG(b z )k2 .
tion of a vector being “natural” in our domain: the genera- While the above is restricted to ReLU-based neural net-
tor defines a probability distribution over vectors in sample works, we also show similar results for arbitrary L-
space and tries to assign higher probability to more likely Lipschitz generative models, for m ⇡ O(k log L). Typi-
vectors, for the dataset it has been trained on. We expect cal neural networks have poly(n)-bounded weights in each
that vectors “natural” to our domain will be close to some layer, so L  nO(d) , giving for any activation, the same
point in the support of this distribution, i.e., in the range of O(kd log n) sample complexity as for ReLU networks.
G.
Theorem 1.2. Let G : Rk ! Rn be an L-Lipschitz func-
Our Contributions: We present an algorithm that uses tion. Let A 2 Rm⇥n be a random Gaussian matrix for
generative models for compressed sensing. Our algorithm m = O(k log Lr ), scaled so Ai,j ⇠ N (0, 1/m). For any
simply uses gradient descent to optimize the representation x⇤ 2 Rn and any observation y = Ax⇤ + ⌘, let zb minimize
z 2 Rk such that the corresponding image G(z) has small ky AG(z)k2 to within additive ✏ of the optimum over
measurement error kAG(z) yk22 . While this is a noncon- vectors with kb
z k2  r. Then with 1 e ⌦(m) probability,
vex objective to optimize, we empirically find that gradient
descent works well, and the results can significantly out- z ) x⇤ k2  6 min kG(z ⇤ ) x⇤ k2 +3k⌘k2 +2✏+2 .
kG(b
z ⇤ 2Rk
perform Lasso with relatively few measurements. kz ⇤ k2 r

We obtain theoretical results showing that, as long as gra-

dient descent finds a good approximate solution to our ob- The downside is two minor technical conditions: we only
jective, our output G(z) will be almost as close to the true optimize over representations z with kzk bounded by r, and
x⇤ as the closest possible point in the range of G. our error gains an additive term. Since the dependence
on these parameters is log(rL/ ), and L is something like
The proof is based on a generalization of the Re- nO(d) , we may set r = nO(d) and = 1/nO(d) while only
stricted Eigenvalue Condition (REC) that we call the Set- losing constant factors, making these conditions very mild.
Restricted Eigenvalue Condition (S-REC). Our main the- In fact, generative models normally have the coordinates
orem is that if a measurement matrix satisfies the S-REC p of
z be independent uniform or Gaussian, so kzk ⇡ k ⌧
for the range of a given generator G, then the measure- nd , and apconstant signal-to-noise ratio would have k⌘k2 ⇡
ment error minimization optimum is close to the true x⇤ . kx⇤ k ⇡ n 1/nd .
Furthermore, we show that random Gaussian measurement
matrices satisfy the S-REC condition with high probabil- We remark that, while these theorems are stated in terms
ity for large classes of generators. Specifically, for d-layer of Gaussian matrices, the proofs only involve the distri-
neural networks such as VAEs and GANs, we show that butional Johnson-Lindenstrauss property of such matrices.
O(kd log n) Gaussian measurements suffice to guarantee Hence the same results hold for matrices with subgaussian
good reconstruction with high probability. One result, for entries or fast-JL matrices (Ailon & Chazelle, 2009).
ReLU-based networks, is the following:
2. Our Algorithm
Theorem 1.1. Let G : Rk ! Rn be a generative
All norms are 2-norms unless specified otherwise.
model from a d-layer neural network using ReLU activa-
tions. Let A 2 Rm⇥n be a random Gaussian matrix for Let x⇤ 2 Rn be the vector we wish to sense. Let A 2
m = O(kd log n), scaled so Ai,j ⇠ N (0, 1/m). For any Rm⇥n be the measurement matrix and ⌘ 2 Rm be the noise
x⇤ 2 Rn and any observation y = Ax⇤ + ⌘, let zb minimize vector. We observe the measurements y = Ax⇤ + ⌘. Given
ky AG(z)k2 to within additive ✏ of the optimum. Then y and A, our task is to find a reconstruction x̂ close to x⇤ .
 Compressed Sensing using Generative Models

A generative model is given by a deterministic function We also take note of the related work of (Gilbert et al.,
G : Rk ! Rn , and a distribution PZ over z 2 Rk . To 2017) that connects model-based compressed sensing
generate a sample from the generator, we can draw z ⇠ PZ with the invertibility of Convolutional Neural Networks,
and the sample then is G(z). Typically, we have k ⌧ n, Bayesian compressed sensing (Ji et al., 2008) and compres-
i.e. the generative model maps from a low dimensional rep- sive sensing using Gaussian mixture models (Yang et al.,
resentation space to a high dimensional sample space. 2014).
Our approach is to find a vector in representation space A related result appears in (Baraniuk & Wakin, 2009),
such that the corresponding vector in the sample space which studies the measurement complexity of an RIP con-
matches the observed measurements. We thus define the dition for smooth manifolds. This is analogous to our
objective to be S-REC for the range of G, but the range of G is nei-
ther smooth (because of ReLUs) nor a manifold (because
loss(z) = kAG(z) yk2 (1) of self-intersection). Their recovery result was extended
By using any optimization procedure, we can minimize in (Hegde & Baraniuk, 2012) to unions of two manifolds.
loss(z) with respect to z. In particular, if the generative
model G is differentiable, we can evaluate the gradients 4. Theoretical Results
of the loss with respect to z using backpropagation and use
standard gradient based optimizers. If the optimization pro- We begin with a brief review of the Restricted Eigenvalue
cedure terminates at ẑ, our reconstruction for x⇤ is G(ẑ). Condition (REC) in standard compressed sensing. The
We define the measurement error to be kAG(ẑ) yk2 and REC is a sufficient condition on A for robust recovery to
the reconstruction error to be kG(ẑ) x⇤ k2 . be possible. The REC essentially requires that all “approx-
imately sparse” vectors are far from the nullspace of the
matrix A. More specifically, A satisfies REC for a constant
3. Related Work > 0 if for all approximately sparse vectors x,
Several recent lines of work explore generative models for kAxk kxk. (2)
reconstruction. The first line of work attempts to project
an image on to the representation space of the genera- It can be shown that this condition is sufficient for recovery
tor. These works assume full knowledge of the image, of sparse vectors using Lasso. If one examines the struc-
and are special cases of the linear measurements frame- ture of Lasso recovery proofs, a key property that is used is
work where the measurement matrix A is identity. Excel- that the difference of any two sparse vectors is also approx-
lent reconstruction results with SGD in the representation imately sparse (for sparsity up to 2k). This is a coincidence
space to find an image in the generator range have been that is particular to sparsity. By contrast, the difference of
reported by (Lipton & Tripathi, 2017) with stochastic clip- two vectors “natural” to our domain may not itself be natu-
ping and (Creswell & Bharath, 2016) with logistic mea- ral. The condition we need is that the difference of any two
surement loss. A different approach is introduced in (Du- natural vectors is far from the nullspace of A.
moulin et al., 2016) and (Donahue et al., 2016). In their
method, a recognition network that maps from the sam- We propose a generalized version of the REC for a set
ple space vector x to the representation space vector z is S ✓ Rn of vectors, the Set-Restricted Eigenvalue Con-
learned jointly with the generator in an adversarial setting. dition (S-REC):
Definition 1. Let S ✓ Rn . For some parameters >
A second line of work explores reconstruction with struc-
0, 0, a matrix A 2 Rm⇥n is said to satisfy the
tured partial observations. The inpainting problem consists
S-REC(S, , ) if 8 x1 , x2 2 S,
of predicting the values of missing pixels given a part of
the image. This is a special case of linear measurements kA(x1 x2 )k kx1 x2 k .
where each measurement corresponds to an observed pixel.
The use of generative models for this task has been stud-
There are two main differences between the S-REC and the
ied in (Yeh et al., 2016), where the objective is taken to be
standard REC in compressed sensing. First, the condition
a sum of L1 error in measurements and a perceptual loss
applies to differences of vectors in an arbitrary set S of
term given by the discriminator. Super-resolution is a re-
“natural” vectors, rather than just the set of approximately
lated task that attempts to increase the resolution of an im-
k-sparse vectors in some basis. This will let us apply the
age. We can view the observations as local spatial averages
definition to S being the range of a generative model.
of the unknown higher resolution image and hence cast this
as another special case of linear measurements. For prior Second, we allow an additive slack term . This is neces-
work on super-resolution see e.g. (Yang et al., 2010; Dong sary for us to achieve the S-REC when S is the output of
et al., 2016; Kim et al., 2016) and references therein. general Lipschitz functions. Without it, the S-REC depends
 Compressed Sensing using Generative Models

on the behavior of S at arbitrarily small scales. Since there piecewise linear with at most two pieces. The popular
are arbitrarily many such local regions, one cannot guar- ReLU or LeakyReLU non-linearities satisfy this assump-
antee the existence of an A that works for all these local tion. We do not make any other assumption, and in par-
regions. Fortunately, as we shall see, poor behavior at a ticular, the magnitude of the weights in the network do not
small scale will only increase our error by O( ). affect our guarantee.
The S-REC definition requires that for any two vectors in Lemma 4.2. Let G : Rk ! Rn be a d-layer neural net-
S, if they are significantly different (so the right hand side work, where each layer is a linear transformation followed
is large), then the corresponding measurements should also by a pointwise non-linearity. Suppose there are at most c
be significantly different (left hand side). Hence we can nodes per layer, and the non-linearities are piecewise lin-
hope to approximate the unknown vector from the mea- ear with at most two pieces, and let
surements, if the measurement matrix satisfies the S-REC. ✓ ◆
1
m=⌦ kd log c
But how can we find such a matrix? To answer this, we ↵2
present two lemmas showing that random Gaussian matri-
for some ↵ < 1. Then a random matrix A 2
ces of relatively few measurements m satisfy the S-REC for
Rm⇥n with IID entries Aij ⇠ N (0, m1
) satisfies the
the outputs of large and practically useful classes of gener- ⌦(↵2 m)
ative models G : Rk ! Rn . S-REC(G(R ), 1 ↵, 0) with 1 e
k
probability.

In the first lemma, we assume that the generative model To show Theorems 1.1 and 1.2, we just need to show that
G(·) is L-Lipschitz, i.e., 8 z1 , z2 2 Rk , we have the S-REC implies good recovery. In order to make our
error guarantee relative to `2 error in the image space Rn ,
kG(z1 ) G(z2 )k  Lkz1 z2 k. rather than in the measurement space Rm , we also need
that A preserves norms with high probability (Cohen et al.,
Note that state of the art neural network architectures
2009). Fortunately, Gaussian matrices (or other distribu-
with linear layers, (transposed) convolutions, max-pooling,
tional JL matrices) satisfy this property.
residual connections, and all popular non-linearities satisfy
this assumption. In Lemma 8.5 in the Appendix we give a Lemma 4.3. Let A 2 Rm⇥n by drawn from a distribution
simple bound on L in terms of parameters of the network; that (1) satisfies the S-REC(S, , ) with probability 1 p
for typical networks this is nO(d) . We also require the input and (2) has for every fixed x 2 Rn , kAxk  2kxk with
z to the generator to have bounded norm. Since generative probability 1 p.
models such as VAEs and GANs typically assume their in- For any x⇤ 2 Rn and noise ⌘, let y = Ax⇤ + ⌘. Let x
b
put z is drawn with independent uniform or Gaussian in- approximately minimize ky Axk over x 2 S, i.e.,
puts, this only prunes an exponentially unlikely fraction of
the possible outputs. ky xk  min ky
Ab Axk + ✏.
x2S
Lemma 4.1. Let G : R ! R be L-Lipschitz. Let
k n
Then,
k k
B (r) = {z | z 2 R , kzk  r} ✓ ◆
4 1
kb
x x⇤ k  + 1 min kx⇤ xk + (2k⌘k + ✏ + )
be an L2 -norm ball in R . For ↵ < 1, if
k x2S

✓ ◆ with probability 1 2p.

k Lr
m=⌦ log ,
↵2 Combining Lemma 4.1, Lemma 4.2, and Lemma 4.3 gives
Theorems 1.1 and 1.2. In our setting, S is the range of the
then a random matrix A 2 R with IID entries such that
m⇥n
generator, and x
b in the theorem above is the reconstruction
Aij ⇠ N 0, m 1
satisfies the S-REC(G(B k (r)), 1 ↵, )
2 z ) returned by our algorithm.
G(b
with 1 e ⌦(↵ m) probability.

All proofs, including this one, are deferred to Appendix A. 5. Models

Note that even though we proved the lemma for an L2 ball, In this section we describe the generative models used in
the same technique works for any compact set. our experiments. We used two image datasets and two dif-
ferent generative model types (a VAE and a GAN). This
For our second lemma, we assume that the generative
provides some evidence that our approach can work with
model is a neural network such that each layer is a com-
many types of models and datasets.
position of a linear transformation followed by a pointwise
non-linearity. Many common generative models have such In our experiments, we found that it was helpful to add a
architectures. We also assume that all non-linearities are regularization term L(z) to the objective to encourage the
 Compressed Sensing using Generative Models
5ecRnVtructLRn errRr (per pLxel)

5ecRnsWrucWLRn errRr (per pLxel)

0.12 0.35
LaVVR LDssR (DC7)
0.10 VA( 0.30 LDssR (WDveleW)
VA(+5eg DCGA1
0.25
0.08 DCGA1+5eg
0.20
0.06
0.15
0.04
0.10
0.02
0.05
0.00 0.00
100

200

300
400
500

750
10

25

50

10000
1000

2500

5000
7500
100

200

500
20

50
1umEer Rf meaVurementV
1umber Rf meDsuremenWs
(a) Results on MNIST (b) Results on celebA

Figure 1. We compare the performance of our algorithm with baselines. We show a plot of per pixel reconstruction error as we vary the
number of measurements. The vertical bars indicate 95% confidence intervals.

optimization to explore more in the regions that are pre- 5.2. CelebA with DCGAN
ferred by the respective generative models (see compari-
CelebA is a dataset of more than 200, 000 face images
son to unregularized versions in Fig. 1). Thus the objective
of celebrities (Liu et al., 2015). The input images were
function we use for minimization is
cropped to a 64 ⇥ 64 RGB image, giving 64 ⇥ 64 ⇥ 3 =
kAG(z) yk2 + L(z). 12288 inputs per image. Each pixel value was scaled so
that all values are between [ 1, 1]. We trained a DCGAN
Both VAE and GAN typically imposes an isotropic Gaus- (Radford et al., 2015; Kim, 2017) on this dataset. We set
sian prior on z. Thus kzk2 is proportional to the negative the input dimension k = 100 and use a standard normal dis-
log-likelihood under this prior. Accordingly, we use the tribution. The architecture follows that of (Radford et al.,
following regularizer: 2015). The model was trained by one update to the discrim-
inator and two updates to the generator per cycle. Each up-
L(z) = kzk2 , (3) date used the Adam optimizer (Kingma & Ba, 2014) with
minibatch size 64, learning rate 0.0002 and 1 = 0.5. We
where measures the relative importance of the prior as use = 0.001 in Eqn. (3).
compared to the measurement error. For baselines, we perform sparse recovery using Lasso on
the images in two domains: (a) 2D Discrete Cosine Trans-
5.1. MNIST with VAE form (2D-DCT) and (b) 2D Daubechies-1 Wavelet Trans-
The MNIST dataset consists of about 60, 000 images of form (2D-DB1). While we provide Gaussian measure-
handwritten digits, where each image is of size 28⇥28 (Le- ments of the original pixel values, the L1 penalty is on ei-
Cun et al., 1998). Each pixel value is either 0 (background) ther the DCT coefficients or the DB1 coefficients of each
or 1 (foreground). No pre-processing was performed. We color channel of an image. For all experiments, we set the
trained VAE on this dataset. The input to the VAE is a vec- shrinkage parameter to be 0.1 and 0.00001 respectively for
torized binary image of input dimension 784. We set the 2D-DCT, and 2D-DB1.
size of the representation space k = 20. The recognition
network is a fully connected 784 500 500 20 network. 6. Experiments and Results
The generator is also fully connected with the architecture
20 500 500 784. We train the VAE using the Adam 6.1. Reconstruction from Gaussian measurements
optimizer (Kingma & Ba, 2014) with a mini-batch size 100 We take A to be a random matrix with IID Gaussian entries
and a learning rate of 0.001. We use = 0.1 in Eqn. (3). with zero mean and standard deviation of 1/m. Each entry
The digit images are reasonably sparse in the pixel space. of noise vector ⌘ is also an IID Gaussian random variable.
Thus, as a baseline, we use the pixel values directly for We compare performance of different sensing algorithms
sparse recovery using Lasso. We set shrinkage parameter qualitatively and quantitatively. For quantitative compari-
to be 0.1 for all the experiments. son, we use the reconstruction error = kx̂ x⇤ k2 , where x̂
 Compressed Sensing using Generative Models

is an estimate of x⇤ returned by the algorithm. In all cases, measurement matrix may not satisfy the S-REC condition
we report the results on a held out test set, unseen by the (with good constants and ), and consequently, our theo-
generative model at training time. rems may not be applicable.
MNIST: The p standard deviation of the noise vector is MNIST: We construct a low resolution image by spatial
set such that E[k⌘k2 ] = 0.1. We use Adam opti- 2 ⇥ 2 pooling with a stride of 2 to produce a 14 ⇥ 14 image.
mizer (Kingma & Ba, 2014), with a learning rate of 0.01. These measurements are used to reconstruct the original
We do 10 random restarts with 1000 steps per restart and 28 ⇥ 28 image. Fig. 2b shows reconstructions produced
pick the reconstruction with best measurement error. by our algorithm on images from a held out test set. We
observe sharp reconstructions which closely match the fine
In Fig. 1a, we show the reconstruction error as we change
structure in the ground truth.
the number of measurements both for Lasso and our algo-
rithm. We observe that our algorithm is able to get low celebA: We construct a low resolution image by spatial 4⇥
errors with far fewer measurements. For example, our 4 pooling with a stride of 4 to produce a 16 ⇥ 16 image.
algorithm’s performance with 25 measurements matches These measurements are used to reconstruct the original
Lasso’s performance with 400 measurements. Fig. 2a 64 ⇥ 64 image. In Fig. 4 we show results on images from a
shows sample reconstructions by Lasso and our algorithm. held out test set. We see that our algorithm is able to fill in
the details to match the original image.
However, our algorithm is limited since its output is con-
strained to be in the range of the generator. After 100
measurements, our algorithm’s performance saturates, and 6.3. Understanding sources of error
additional measurements give no additional performance. Although better than baselines, our method still admits
Since Lasso has no such limitation, it eventually surpasses some error. This error can be decomposed into three com-
our algorithm, but this takes more than 500 measurements ponents: (a) Representation error: the unknown image is
of the 784-dimensional vector. We expect that a more far from the range of the generator (b) Measurement error:
powerful generative model with representation dimension The finite set of random measurements do not contain all
k > 20 can make better use of additional measurements. the information about the unknown image (c) Optimization
celebA: The p standard deviation of the noise vector is error: The optimization procedure did not find the best z.
set such that E[k⌘k2 ] = 0.01. We use Adam opti- In this section we present some experiments that suggest
mizer (Kingma & Ba, 2014), with a learning rate of 0.1. that the representation error is the dominant term. In our
We do 2 random restarts with 500 update steps per restart first experiment, we ensure that the representation error is
and pick the reconstruction with best measurement error. zero, and try to minimize the sum of other two errors. In
In Fig. 1b, we show the reconstruction error as we change this setting, we observe that the reconstructions are almost
the number of measurements both for Lasso and our algo- perfect. In the second experiment, we ensure that the mea-
rithm. In Fig. 3 we show sample reconstructions by Lasso surement error is zero, and try to minimize the sum of other
and our algorithm. We observe that our algorithm is able two. Here, we observe that the total error obtained is very
to produce reasonable reconstructions with as few as 500 close to the total error in our reconstruction experiments
measurements, while the output of the baseline algorithms (Sec. 6.1).
is quite blurry. Similar to the results on MNIST, if we con-
tinue to give more measurements, our algorithm saturates, 6.3.1. S ENSING IMAGES FROM RANGE OF GENERATOR
and for more than 5000 measurements, Lasso gets a better Our first approach is to sense an image that is in the range
reconstruction. We again expect that a more powerful gen- of the generator. More concretely, we sample a z ⇤ from
erative model with k > 100 would perform better in the PZ . Then we pass it through the generator to get x⇤ =
high-measurement regime. G(z ⇤ ). Now, we pretend that this is a real image and try to
sense that. This method eliminates the representation error
6.2. Super-resolution and allows us to check if our gradient based optimization
procedure is able to find z ⇤ by minimizing the objective.
Super-resolution is the task of constructing a high resolu-
tion image from a low resolution version of the same im- In Fig. 6a and Fig. 6b, we show the reconstruction error for
age. This problem can be thought of as special case of images in the range of the generators trained on MNIST
our general framework of linear measurements, where the and celebA datasets respectively. We see that we get almost
measurements correspond to local spatial averages of the perfect reconstruction with very few measurements. This
pixel values. Thus, we try to use our recovery algorithm suggests that objective is being properly minimized and we
to perform this task with measurement matrix A tailored indeed get ẑ close to z ⇤ . i.e. the sum of optimization error
to give only the relevant observations. We note that this and the measurement error is small in the absence of the
 Compressed Sensing using Generative Models

(a) We show original images (top row) and reconstructions by (b) We show original images (top row), low resolution version
Lasso (middle row) and our algorithm (bottom row). of original images (middle row) and reconstructions (last row).

Figure 2. Results on MNIST. Reconstruction with 100 measurements (left) and Super-resolution (right)
OrLgLnDO
LDsso (DCT)
LDsso (WDveOeW)
DCGAN

Figure 3. Reconstruction results on celebA with m = 500 measurements (of n = 12288 dimensional vector). We show original images
(top row), and reconstructions by Lasso with DCT basis (second row), Lasso with wavelet basis (third row), and our algorithm (last row).
OriginDO
BOurreG
DCGAN

Figure 4. Super-resolution results on celebA. Top row has the original images. Second row shows the low resolution (4x smaller) version
of the original image. Last row shows the images produced by our algorithm.
OriginDO
DCGAN

Figure 5. Results on the representation error experiments on celebA. Top row shows original images and the bottom row shows closest
images found in the range of the generator.
 Compressed Sensing using Generative Models
5eFRnstruFtiRn errRr (per pixel)

5eFRnstruFtiRn errRr (per pixel)

0.07 0.20
)rRm test set )rRm test set
0.06 )rRm generatRr )rRm generatRr
0.15
0.05

0.04
0.10
0.03

0.02
0.05
0.01

0.00 0.00
100

200

300
400
500

750
10

25

50

1000

2500
100

200

500
20

50
1umber Rf measurements
1umber Rf measurements
(a) Results on MNIST (b) Results on celebA

Figure 6. Reconstruction error for images in the range of the generator. The vertical bars indicate 95% confidence intervals.

tation error of 0.005. The recovered images are shown in

Fig. 7. In contrast, with only 100 Gaussian measurements,
we get a per pixel reconstruction error of about 0.009. On
the celebA dataset, we get average per pixel representation
error of 0.020. The recovered images are shown in Fig. 5.
Figure 7. Results on the representation error experiments on In contrast, with only 500 Gaussian measurements, we get
MNIST. Top row shows original images and the bottom row a per pixel reconstruction error of about 0.028.
shows closest images found in the range of the generator.
This suggests that the representation error is the major com-
representation error. ponent of the total error, and thus a more flexible generative
model can help reduce it on both datasets.
6.3.2. Q UANTIFYING REPRESENTATION ERROR
We saw that in absence of the representation error, the over- 7. Conclusion
all error is small. However from Fig. 1, we know that the
overall error is still non-zero. So, in this experiment, we We demonstrate how to perform compressed sensing us-
seek to quantify the representation error, i.e., how far are ing generative models from neural nets. These models can
the real images from the range of the generator? represent data distributions more concisely than standard
sparsity models, while their differentiability allows for fast
From the previous experiment, we know that the ẑ recov- signal reconstruction. This will allow compressed sensing
ered by our algorithm is close to z ⇤ , the best possible value, applications to make significantly fewer measurements.
if the image being sensed is in the range of the generator.
Based on this, we make an assumption that this property is Our theorems and experiments both suggest that, after rel-
also true for real images. With this assumption, we get an atively few measurements, the signal reconstruction gets
estimate to the representation error as follows: We sample close to the optimal within the range of the generator. To
real images from the test set. Then we use the full image in reach the full potential of this technique, one should use
our algorithm, i.e., our measurement matrix A is identity. larger generative models as the number of measurements
This eliminates the measurement error. Using these mea- increase. Whether this can be expressed more concisely
surements, we get the reconstructed image G(ẑ) through than by training multiple independent generative models of
our algorithm. The estimated representation error is then different sizes is an open question.
kG(ẑ) x⇤ k2 . We repeat this procedure several times over Generative models are an active area of research with ongo-
randomly sampled images from our dataset and report av- ing rapid improvements. Because our framework applies to
erage representation error values. The task of finding the general generative models, this improvement will immedi-
closest image in the range of the generator has been stud- ately yield better reconstructions with fewer measurements.
ied in prior work (Creswell & Bharath, 2016; Dumoulin We also believe that one could also use the performance of
et al., 2016; Donahue et al., 2016). generative models for our task as one benchmark for the
On the MNIST dataset, we get average per pixel represen- quality of different models.
 Compressed Sensing using Generative Models

Acknowledgements Creswell, Antonia and Bharath, Anil Anthony. Inverting

the generator of a generative adversarial network. arXiv
We would like to thank Philipp Krähenbühl for helpful dis- preprint arXiv:1611.05644, 2016.
cussions. This research has been supported by NSF Grants
CCF 1344364, 1407278, 1422549, 1618689, ARO YIP Donahue, Jeff, Krähenbühl, Philipp, and Darrell,
W911NF-14-1-0258, and the William Hartwig fellowship. Trevor. Adversarial feature learning. arXiv preprint
arXiv:1605.09782, 2016.
References Dong, Chao, Loy, Chen Change, He, Kaiming, and Tang,
Agarwal, Alekh, Negahban, Sahand, and Wainwright, Mar- Xiaoou. Image super-resolution using deep convolu-
tin J. Fast global convergence rates of gradient methods tional networks. IEEE transactions on pattern analysis
for high-dimensional statistical recovery. In Advances and machine intelligence, 38(2):295–307, 2016.
in Neural Information Processing Systems, pp. 37–45,
Donoho, David L. Compressed sensing. IEEE Transac-
2010.
tions on information theory, 52(4):1289–1306, 2006.
Ailon, Nir and Chazelle, Bernard. The fast johnson– Duarte, Marco F, Davenport, Mark A, Takbar, Dharmpal,
lindenstrauss transform and approximate nearest neigh- Laska, Jason N, Sun, Ting, Kelly, Kevin F, and Baraniuk,
bors. SIAM Journal on Computing, 39(1):302–322, Richard G. Single-pixel imaging via compressive sam-
2009. pling. IEEE signal processing magazine, 25(2):83–91,
2008.
Bach, Francis, Jenatton, Rodolphe, Mairal, Julien, Obozin-
ski, Guillaume, et al. Optimization with sparsity- Dumoulin, Vincent, Belghazi, Ishmael, Poole, Ben, Lamb,
inducing penalties. Foundations and Trends R in Ma- Alex, Arjovsky, Martin, Mastropietro, Olivier, and
chine Learning, 4(1):1–106, 2012. Courville, Aaron. Adversarially learned inference. arXiv
preprint arXiv:1606.00704, 2016.
Baraniuk, Richard G and Wakin, Michael B. Random pro-
jections of smooth manifolds. Foundations of computa- Foygel, Rina and Mackey, Lester. Corrupted sensing:
tional mathematics, 9(1):51–77, 2009. Novel guarantees for separating structured signals. IEEE
Transactions on Information Theory, 60(2):1223–1247,
Baraniuk, Richard G, Cevher, Volkan, Duarte, Marco F, 2014.
and Hegde, Chinmay. Model-based compressive sens-
ing. IEEE Transactions on Information Theory, 56(4): Gilbert, Anna C, Zhang, Yi, Lee, Kibok, Zhang, Yuting,
1982–2001, 2010. and Lee, Honglak. Towards understanding the invert-
ibility of convolutional neural networks. arXiv preprint
Bickel, Peter J, Ritov, Ya’acov, and Tsybakov, Alexan- arXiv:1705.08664, 2017.
dre B. Simultaneous analysis of lasso and dantzig se-
Goodfellow, Ian, Pouget-Abadie, Jean, Mirza, Mehdi, Xu,
lector. The Annals of Statistics, pp. 1705–1732, 2009.
Bing, Warde-Farley, David, Ozair, Sherjil, Courville,
Candes, Emmanuel J, Romberg, Justin K, and Tao, Ter- Aaron, and Bengio, Yoshua. Generative adversarial nets.
ence. Stable signal recovery from incomplete and in- In Advances in neural information processing systems,
accurate measurements. Communications on pure and pp. 2672–2680, 2014.
applied mathematics, 59(8):1207–1223, 2006. Hegde, Chinmay and Baraniuk, Richard G. Signal recov-
ery on incoherent manifolds. IEEE Transactions on In-
Chen, Guang-Hong, Tang, Jie, and Leng, Shuai. Prior im- formation Theory, 58(12):7204–7214, 2012.
age constrained compressed sensing (piccs): a method
to accurately reconstruct dynamic ct images from highly Hegde, Chinmay, Duarte, Marco F, and Cevher, Volkan.
undersampled projection data sets. Medical physics, 35 Compressive sensing recovery of spike trains using a
(2):660–663, 2008. structured sparsity model. In SPARS’09-Signal Process-
ing with Adaptive Sparse Structured Representations,
Chen, Guangliang and Needell, Deanna. Compressed sens- 2009.
ing and dictionary learning. Proceedings of Symposia in
Applied Mathematics, 73, 2016. Hegde, Chinmay, Indyk, Piotr, and Schmidt, Ludwig. A
nearly-linear time framework for graph-structured spar-
Cohen, A., Dahmen, W., and DeVore, R. Compressed sens- sity. In Proceedings of the 32nd International Con-
ing and best k-term approximation. J. Amer. Math. Soc, ference on Machine Learning (ICML-15), pp. 928–937,
22(1):211–231, 2009. 2015.
 Compressed Sensing using Generative Models

Ji, Shihao, Xue, Ya, and Carin, Lawrence. Bayesian com- Tibshirani, Robert. Regression shrinkage and selection via
pressive sensing. IEEE Transactions on Signal Process- the lasso. Journal of the Royal Statistical Society. Series
ing, 56(6):2346–2356, 2008. B (Methodological), pp. 267–288, 1996.
Kim, Jiwon, Kwon Lee, Jung, and Mu Lee, Kyoung. Ac- Vershynin, Roman. Introduction to the non-asymptotic
curate image super-resolution using very deep convolu- analysis of random matrices. arXiv preprint
tional networks. In Proceedings of the IEEE Conference arXiv:1011.3027, 2010.
on Computer Vision and Pattern Recognition, pp. 1646–
1654, 2016. Yang, Jianbo, Yuan, Xin, Liao, Xuejun, Llull, Patrick,
Brady, David J, Sapiro, Guillermo, and Carin, Lawrence.
Kim, Taehoon. A tensorflow implementation of “deep Video compressive sensing using gaussian mixture mod-
convolutional generative adversarial networks”. els. IEEE Transactions on Image Processing, 23(11):
[Link] 4863–4878, 2014.
2017.
Yang, Jianchao, Wright, John, Huang, Thomas S, and Ma,
Kingma, Diederik and Ba, Jimmy. Adam: A Yi. Image super-resolution via sparse representation.
method for stochastic optimization. arXiv preprint IEEE transactions on image processing, 19(11):2861–
arXiv:1412.6980, 2014. 2873, 2010.
Kingma, Diederik P and Welling, Max. Auto-encoding
Yeh, Raymond, Chen, Chen, Lim, Teck Yian, Hasegawa-
variational bayes. arXiv preprint arXiv:1312.6114,
Johnson, Mark, and Do, Minh N. Semantic image in-
2013.
painting with perceptual and contextual losses. arXiv
LeCun, Yann, Bottou, Léon, Bengio, Yoshua, and Haffner, preprint arXiv:1607.07539, 2016.
Patrick. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–
2324, 1998.
Lipton, Zachary C and Tripathi, Subarna. Precise recovery
of latent vectors from generative adversarial networks.
arXiv preprint arXiv:1702.04782, 2017.
Liu, Ziwei, Luo, Ping, Wang, Xiaogang, and Tang, Xiaoou.
Deep learning face attributes in the wild. In Proceedings
of the IEEE International Conference on Computer Vi-
sion, pp. 3730–3738, 2015.
Loh, Po-Ling and Wainwright, Martin J. High-dimensional
regression with noisy and missing data: Provable guar-
antees with non-convexity. In Advances in Neural Infor-
mation Processing Systems, pp. 2726–2734, 2011.
Lustig, Michael, Donoho, David, and Pauly, John M.
Sparse mri: The application of compressed sensing for
rapid mr imaging. Magnetic resonance in medicine, 58
(6):1182–1195, 2007.
Matoušek, Jiřı́. Lectures on discrete geometry, volume 212.
Springer Science & Business Media, 2002.
Negahban, Sahand, Yu, Bin, Wainwright, Martin J, and
Ravikumar, Pradeep K. A unified framework for high-
dimensional analysis of m-estimators with decompos-
able regularizers. In Advances in Neural Information
Processing Systems, pp. 1348–1356, 2009.
Radford, Alec, Metz, Luke, and Chintala, Soumith. Un-
supervised representation learning with deep convolu-
tional generative adversarial networks. arXiv preprint
arXiv:1511.06434, 2015.