Compressed Sensing with Deep Image Prior and Learned Regularization
Authors: Dave Van Veen
Ajil Jalal
Mahdi Soltanolkotabi
Eric Price
Sriram Vishwanath
Alexandros G. Dimakis
Venue:  (2020)
Keywords: compressed sensing
sparsity
inverse problems

Abstract: We propose a novel method for compressed sensing recovery using
untrained deep generative models. Our method is based on the recently
proposed Deep Image Prior (DIP), wherein the convolutional weights of
the network are optimized to match the observed measurements. We show
that this approach can be applied to solve any differentiable linear inverse
problem, outperforming previous unlearned methods. Unlike various learned approaches based on generative models, our method does not require pre-training over large datasets. We further introduce a novel learned regularization technique, which incorporates prior information on the network weights. This reduces reconstruction error, especially for noisy measurements. Finally we prove that, using the DIP optimization approach, moderately overparameterized single-layer networks trained can perfectly fit any signal despite the nonconvex nature of the fitting problem. This theoretical result provides justification for early stopping.

Under review as a conference paper at ICLR 2020
COMPRESSED SENSING WITH DEEP IMAGE PRIOR AND LEARNED REGULARIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We propose novel method for compressed sensing recovery using untrained deep generative models. Our method based on the recently proposed Deep Image Prior (DIP), wherein the convolutional weights of the network are optimized to match the observed mcasurements. We show that this approach can be applicd to solve any differentiable linear inverse problem, outperforming previous unlcarned methods. Unlike various learned approaches based on generative models, our method does not require pre-training over large datasets. We further introduce novel learned regularization technique, which incorporates prior information on the network weights. This reduces reconstruction error, especially for noisy mea- surements. Finally we prove that, using the DIP optimization approach, moder- ately overparameterized single-layer networks trained can perfectly fit any signal despite the nonconvex nature of the fitting problem. This theoretical result pro- vides justification for early stopping.
INTRODUCTION
We consider the well-studied compressed sensing problem of recovering an unknown signal x* Rn by observing set of noisy measurements y Ih of the form
y Ax + 77.
(1)
Here A E Rmmx is known measurement matrix, typically generated with random independent Gaussian entries. Since the number of measurements m is smaller than the dimension n of the unknown vector z", this is an under-determined system of noisy linear equations and hence ill-posed. There are many solutions, and some structure must be assumed on x² to have any hope recovery. Pioneering research (Donoho) 2006; Candès et al., 2006; Candes & Tao 2005) established that if x² assumed to be sparse in a known basis, small number of measurements will be provably sufficient to recover the unknown vector in polynomial time using methods such as Lasso (Tibshirani 1996).
Sparsity approaches have proven successful, but more complex models with additional structure have been recently proposed such model-based compressive sensing (Baraniuk al., 2010) and manifold models (Hegde et al., 20088 Heede & Baraniuk] 2012] Efttkhari & Wakin (2015). Bora al. (2017) showed that deep generative models can be used excellent priors for images. They also showed that backpropagation can be used to solve the signal recovery problem by performing gradient descent in the generative latent space. This method enabled image generation with signif- icantly fewer measurements compared to Lasso for a given reconstruction error. Compressed sens- ing using deep generative models was further improved in very recent work (Tripathi et al. 2018 Grover & Ermon, 201 8a Kabkab et al. 2018 Shah & Hegdel 2018 Fletcher & Rangan 2017 Asim let al. 2018). Additionally theoretical analysis of the nonconvex gradient descent algorithm (Bora al. 2017 was proposed by Hand & Voroninski (017) under some assumptions on the generative
model.
Inspired by these impressive benefits of deep generative models, we chose to investigate the appli- cation of such methods for medical imaging, a canonical application of compressive sensing. A significant problem, however, is that all these previous methods require the existence of pre-trained models. While this has been achieved for various types of images, e.g. human faces of CelebA (Liu al. 2015) via DCGAN (Radford al. 2015). it remains significantly more challenging for med-

---

Under review as a conference paper at ICLR 2020
ical images (Wolterink et al. 2017 Schlegl al. 2017: Instead of addressing this problem in generative models, we found an easier way to circumvent it.
Nie et al. 2017 Schlemper et al. 2017
Surprising recent work by Ulyanov et al. (2017) proposed Deep Image Prior (DIP), which uses un- trained convolutional neural networks. In Daseb schemes, a convolutional neural network gen- erator (e.g. DCGAN) is initialized with random weights; these weights are subsequently optimized to make the network produce an output as close to the target image as possible. This procedure is unlearned, using no prior information from other images. The prior enforced only by the fixed convolutional structure of the generator network.
Generators used for DIP are typically wver-parameterized, i.e. the number of network weights is much larger compared to the oulput dimension. For this reason DIP has empirically been found to overfit to noise if run for too many iterations (Ulyanov et al.) 2017). In this paper we theoretically prove that this phenomenon occurs with gradient descent and justify the use of early stopping and other regularization methods.
Our Contributions:
In Section we propose DIP for compressed sensing (CS-DIP). Our basic method is as fol- lows. Initialize DCGAN generator with random weights; use gradient descent to optimize these weights such that the network produces an output which agrees with the observed measurements as much as possible. This unlearned method can be improved with novel learned regularization technique, which regularizes the DCGAN weights throughout the optimization process.
In Section 4 we theoretically prove that DIP will fit any signal to zero error with gradient descent. Our result is established for network with a single hidden layer and sufficient constant fraction wver-parametrization. While it is expected that over-parametrized neural networks can fit any signal, the fact that gradient descent can provably solve this non- convex problem interesting and provides theoretical justification for early stopping.
Section 5 we empirically show that CS-DIP outperforms previous unlearned methods in many cases. While pre-trained or "learned" methods frequently perform better (Bora ct al. 2017). we have the advantage of not requiring a generative model trained over large datasets. As such, we can apply our method to various medical imaging datasets for which data acquisition is expensive and generative models are difficult to train.
2 BACKGROUND
2.1 COMPRESSED SENSING: CLASSICAL AND UNLEARNED APPROACHES
classical assumption made in compressed sensing is that the vector x² is k-sparse in some basis such wavelet or discrete cosine transform (DCT). Finding the sparsest solution mined linear system of equations is NP-hard in general: however, the matrix A satisfies conditions such as the Restricted Eigenvalue Condition (REC) Restricted Isometry Property (RIP) (Can- des et al. 2006 Bickel et al., 2009 Donoho 2006 Tibshirani] 1996), then x" can be recovered in polynomial time via convex relaxations (Tropp) 2006) or iterative methods. There is extensive compressed sensing literature regarding assumptions on A, numerous recovery algorithms, and vari- ations of RIP and REC (Bickel et 2009 Negahban al. 2009 Agarwal et al. 2010; Bach al.,
underdeter-
2012
Loh & Wainwright 2011))
Compressed sensing methods have found many applications in imaging, for example the single-pixt camera (SPC) (Duarte et al. 2008). Medical tomographic applications include x-ray radiography. microwave imaging, magnetic resonance imaging (MRI) (Winters et al., 20100; Chen et al. 2008 Lustig et al., 2007). Obtaining measurements for medical imaging can be costly, time-consuming and in some cases dangerous to the patient (Qaisar et al.) 2013). As such, an important goal is to reduce the number of measurements while maintaining good reconstruction quality.
Aside from the classical use of sparsity, recent work has used other priors to solve linear inverse problems. Plug-and-play priors /Venkatakrishnan et al. 2013 Chan et al.) 2017) and Regularization by Denoising (Romano et al. (017)) have shown how image denoisers can be used to solve general linear inverse problems. A key example of this is BM3D-AMP, which applies Block-Matching
2

---

Under review as a conference paper at ICLR 2020
and 3D filtering (BM3D) denoiser to an Approximate Message Passing (D-AMP) algorithm (Met- zler et al. 2016 2015). AMP has also been applicd to linear models in other contexts (Schniter et al. 2016). Another related algorithm is TVAL3 (Zang et al. 2013 Li et al. 2009) which leverages aug- mented Lagrangian multipliers to achieve impressive performance on compressed sensing problems. In many different settings, we compare algorithm these prior methods: BM3D-AMP, TVAL3,
and Lasso.
2.2 COMPRESSED SENSING: LEARNED APPROACHES
While sparsity in some chosen basis is well-established, recent work has shown better empirical performance when neural networks are used (Bora al. 2017). This success is attributed to the fact that neural networks are capable of learning image priors from very large datasets (Goodfellow) ct al. 2014 Kingma& & Welling, 2013). There is significant recent work on solving linear inverse problems using various learned techniques, e.g. recurrent generative models (Mardani et al. 2017b) and auto-regressive models (Dave et al. 2018). Additionally approximate message passing (AMP) has been extended to a learned setting by Metzler et al. (2017).
Bora et al. 2017)) is the closest to our set-up. In this work the authors assume that the unknown signal is in the range of pre-trained generative model such as generative adversarial network (GAN) (Goodfellow et al.] 2014) or variational autoencoder (VAE) (Kingma & Welling 2013). The recovery of the unknown signal is obtained via gradient descent in the latent space by searching for a signal that satisfies the measurements. This can be directly applied for linear inverse problems and more generally to any differentiable measurement process. Recent work has built upon these methods using new optimization techniques (Chang et al. (017). uncertainty autoencoders (Grover Ermon 2018b), and other approaches (Dhar et al., 2018 Kabkab al.] 2018 Mixon & Villar Pandit et al. [2019] Rusu et 2018) Hand et al. 2018). The key point is that all this prior work
requires pre-trained generative models, contrast to CS-DIP. Finally, there is significant ongoing
work to understand DIP and develop related approaches (Heckel et al. 2018 Dittmer et al. 2018).
PROPOSED ALGORITHM
Let x² E Rn be the signal that we are trying to reconstruct, Rmxn be the measurement matrix, and n E Ihm be independent noise. Given the measurement matrix A and the observations y = Ax + 77, we wish to reconstruct an & that close to x²"
A generative model is deterministic function G(z; w): R+ + R" which takes as input seed z E R² and is parameterized by "weights" w E IRd, producing an output G(z; w) E I" These models have shown excellent performance generating real-life signals such as images (Goodfellow et al. 2014: Kingma & Welling, 2013) and audio Van Den Oord et al.] (016). We investigate deep convolutional generative models, special case in which the model architecture has multiple cascaded layers of convolutional filters (Krizhevsky et al., 2012).. In this paper we apply a DC- GAN (Radford et al. 2015)) model and restrict the signals be images.
3.1 COMPRESSED SENSING WITH DEEP IMAGE PRIOR (CS-DIP)
Our approach to find a set of weights for the convolutional network such that the measurement matrix applied to the network output, i.e. AG(2; w). matches the measurements y we are given.
Hence we initialize an untrained network G(2; w) with some fixed z and solve the following:
w = arg min |yy AG(2;w)]1'
(2)
w
This is, of course, non-convex problem because G(2; w) is complex feed-forward neural network. Still we can use gradient-base optimizers for any generative model and measurement process that is differentiable. Generator networks such as DCGAN are biased toward smooth, natural images due to their convolutional structure; thus the network structure alone provides a good prior for reconstructing images in problems such inpainting and denoising (Ulyanov et al., 2017). Our finding is that this applies to general linear measurement processes. Furthermore, our method also directly applies to any differentiable forward operator A. We restrict solution to lie in the span
3

---

Under review as a conference paper at ICLR 2020
of convolutional neural network. If sufficient number of measurements is given, obtain an output such that x x G(2; w").
untrained generative model and optimizes over the network weights w. In contrast previous methods, such as that of Bora al. (2017). use a trained model and optimize over the latent 2-space, solving =" arg min; AG(2; w)ll. We instead initialize random with Gaussian i.i.d. entries and keep this fixed throughout the optimization process.
Note that this method
In our algorithm leverage the well-established total variation regularization (Rudin et al. 1992 Wang et al. 2008 Liu et al. 2018). denoted as (Z; We also propose an additional learned regularization technique, LR( w); note that without this technique, i.e. when Ar. our method is completely unlearned. Lastly we use early stopping, phenomena that will be analyzed theoretically in Section
Thus the final optimization problem becomes
w = arg minlly - WG( + R(w; AT, At).
The regularization term contains hyperparameters Ay and X5. for total variation and learned regular- ization: R(w; Àr, Ar.) = XrTV( (L. Next we discuss this Lf(w) term.
3.2 LEARNED REGULARIZATION
Without learned regularization CS-DIP relies only on linear measurements taken from one unknown image. We now introduce novel method which leverages a small amount of training data to opti- mize regularization. In this case training data refers to measurements from additional ground truth of similar type, e.g. other x-ray images.
To leverage this additional information, we pose Eqn. 3 tion problem and propose a novel prior on the weights the generative model. This prior then acts regularization term, penalizing the model toward an optimal set of weights w".
Maximum a Posteriori (MAP) estima-
For set of weights w Rd, we model the likelihood of the measurements y = Ax, y E R", and the prior on the weights w Gaussian distributions given by
AG( (2; w)ll |1y
exp
cxp (-2 (w - -1)² E -)TEE- W-1(ww (w (b)
2dr
p(ylw)=
p(w)
V /2TT\L))) )
12
where μ E dRd and E E Iddd
In this setting we want to find a set weights w* that maximizes the posterior on w given y,, i.e.,
w arg max p( = min |Iv AG(22; de (w 1) x-1 (w n)) (4)
w
This gives us the learned regularization term
LR(w) = (w - - x-1 (w 14)
(5)
where the coefficient \ in Eqn. Acontrols the strength of the prior.
Our motivation for assuming Gaussian distribution on the weights is to build upon the proven success E2 regularization, which also makes this assumption. Notice that when = 0 and laxa; this regularization term is equivalent to lz-regularization. Thus this method can be thought of as an adaptive version standard weight decay. Further, because the network weights are initialized Gaussian i..d., assumed the optimized weights would also be Gaussian. Previous work has shown evidence that the convolutional weights in a trained network do indeed follow a Gaussian distribution (Ma al. 2018).
4

---

Under review as a conference paper at ICLR 2020
3.2.1 LEARNING THE PRIOR PARAMETERS
In the previous section, we introduced the learned regularization term LR(w) defined in Eqn. However we have not yet learned values for parameters (μ, Σ) that incorporate prior knowledge of the network weights. We now propose way to estimate these parameters.
Assume we have set of measurements Sy = {311 131,,2.... y2. .Q4 } from Q different images Sx (2, ... ,TQ, each obtained with a different measurement matrix A. For each measurement Ug: 2 E [1,2, ..., Q), we run CS-DIP to solve the optimization problem in Eqn. 3 and obtain an optimal set of weights W [wi, w5; ... w²) Note that when optimizing for the weights W*, we only have access to the measurements Sy, not the ground truth Sx.
The number weights
deep networks tends to be very large. As such, learning a distribution over each weight, i.e. estimating μ E R and Σ E Rdxd becomes intractable. We instead use a layer-wise approach: with network layers, we have μ RR and Σ E RRXL, Thus each weight within layer 1 E {1, .... L) is modeled according the same (u,, Σn) distribution. For simplicity we assume Σnj = i o j. i.c. that network weights are independent across layers. The process of estimating statisties (j,, Σ) from W* is described in Algorithm 1 of the appendix.
We use this learned (n., Σ) in the regularization term LR(w) from Eqn. 5 for reconstructing mea- surements of images. We refer to this technique learned regularization. While this may seem analogous to batch normalization (Toffe & Szegedy] 2015), note that we only use (1,, Σ) to penalize the fo-m of the weights and do not normalize the layer outputs themselves.
3.2.2 DISCUSSION OF LEARNED REGULARIZATIO
The proposed CS-DIP does not require training if no learned regularization is used, i.c. if Y 0 in Eqn. [3] This means that CS-DIP can be applied only with measurements from a single image and no prior information of similar images in a dataset.
Our next idea, learned regularization, utilizes small amount of prior information, requiring access to measurements from small number of similar images (roughly 5 - 10). In contrast, other pre- trained models such as that Bora et al. (2017) require access to ground truth from a massive number of similar images (tens of thousands for CelebA). If such a large dataset is available, and a good generative model can be trained on that dataset, we expect that pre-trained models would outperform our method. Our approach is instead more suitable for reconstructing problems where large amounts of data or good generative models are not readily available.
THEORETICAL RESULTS
In this section we provide theoretical evidence highlight the importance of early stopping for DIP- based approaches. Here we focus on denoising a noisy signal y E R by optimizing over network weights. This problem takes the form:
min ((w) = 1y G(2; w1
(6)
This is special instance of Eqn. 2 with the measurement matrix A = I corresponding to denoising. We focus on generators consisting of single hidden-layer ReLU network with k inputs, d hidden units, and n outputs. Using w = (W, V) the generator model in this case is given by G(2; W) V Re)U(W=).
where: = & is the input, W _ the input-to-hidden weights, and V Ruxdd the hidden- to-output weights. We assume V is fixed at random and train over W using gradient descent. With these formulations in place, we are now ready state our theoretical result.
Theorem 4.1. Consider fitting a generator of the form W + G(2; W. V) = =V ReLU (Wz) to a signal y R with z E R$ W dddk V E Baxd and ReLU(z) max(0,2). Furthermore, assume V is a random matrix with ii.d NO, v²) entries with v ddn weight matrix Wo selected at random with i...d. ((,0 entries, run gradient descent updates of the form Wr W1+1 = W,- - V 7/L(WW on the loss
|ell || Starting from an initial
L(W)= 2 |IV ReLU ReLU(W2)) -11².
5

---

Under review as a conference paper at ICLR 2020
with step size r7
where nj S 1. Assuming that Sn
lvll 4m+d
d Cn,
with C a fixed numerical constant, then
1j V (W+2) v|1 53 8(4n + d)
1ly1
holds for all with probability at least 1 - 5c- m/2 - 4/2 2 e-122
c 4d
Our theoretical result shows that after many iterative updates, gradient descent will solve this non- convex optimization problem and fit any signal y, if the generator network sufficiently wide. This occurs as soon as the number of hidden units d exceeds the signal size n. by constant factor. In our theorem we have focused on the case where the measurement matrix is the identity (A I). We note however that our theorem directly applies to many compressed sensing measurement matrices, in particular any matrix obtained by subsampling the rows of an orthonormal matrix (e.g. sub- sampling a Fourier matrix). This is possible as for any such matrix, AV has the same distribution as a Gaussian matrix with i.d. entries. Therefore, our thcorem directly applies in this setting by replacing V with AV. This result demonstrates that early stopping is necessary for DIP-based methods to be successful; otherwise the network can fit any signal, including one that is noisy.
Our proof builds on theoretical ideas from Oymak & Soltanolkotabi (2019) which provide general framework for establishing global convergence guarantees for overparameterized nonlinear learning problems based on various properties of the Jacobian mapping along the gradient descent trajectory. Related literature can be found in Du et al. (2018); Oymak & Soltanolkotabi (2018). We combine tools from empirical process theory, random matrix theory, and matrix algebra to show that, starting from a random initialization, the Jacobian mapping across all iterates has favorable properties with high probability, hence facilitating convergence global optima.
EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Measurements: We evaluate our algorithm using two different measurements processes, i.e. matri- Rmxn, First set the entries of A to be Gaussian i.i.d. such that A ~ (O, =. Recall m is the number of measurements, and n is the number of pixels in the ground truth image. This measurement process is standard practice in compressed sensing literature; hence we use on each dataset. Additionally we use Fourier measurement process common in MRI applications (Mardani
al. 2018 2017a Hammernik et al. 2018 Lehtinen al. 2018 Lustig et al. 2008).
Datasets: We use our algorithm to reconstruct both grayscale and RGB images. For grayscale we use the first 100 images the test set of MNIST (LeCun et al. [998) and also 60 random images from the Shenzhen Chest X-Ray Dataset (Jaeger et al.) (2014). downsampling 512x512 crop to 256x256 pixels. For RGB we use retinopathy images from the STARE dataset (Hoover et al. 2000) with 512x512 12 crops downsized to 128x128 pixels.
Table 1: Evaluating the benefits of learned regularization (LR) x-ray images with varying levels of noise and number of measurements. Table values are percent decrease in error, e.g. at o = and = 500, L.R reduces MSE by 9.9%. The term o corresponds variance of the noise vector y Eqn. i.e. each entry of r) is drawn independently No0, m tends to provide greater benefit with noisy signals and with fewer measurements.
a2 These results indicate that LR
Measurements, m
500
1000
2000
4000
8000
0
9.9%
2.9%
0.2%
2.0%
0.6%
10
11.6%
4.6%
4.5%
2.4%
1.0%
100
14.9%
19.2%
5.0%
3.9%
2.8%
1000
37.4%
30.6%
19.8%
3.0%
6.2%

---

Under review as a conference paper at ICLR 2020
0.30
0.005
Ours
Ours +
0.25
BMSD-AMP
Reconstruction Error
Lasso-Dr DCT
Reconstructin Entrr
0.004
TVAL3
Lassp DCT
0.003
0.15
0.002
0.10
0.001
0.05
0.000
1000
2000
4000
8000
0.00
50
100
200
Number Measurements
(a) MSE Chest X-ray (65536 pixels)
(b) MSE MNIST (784 pixels)
Figure I: Per-pixel reconstruction error (MSE) vs. number of measurements. Vertical bars indicate 95% confidence intervals. BM3D-AMP frequently fails to converge for fewer than 4000 measure- ments on x-ray images, as denoted by error values far above the vertical axis.
Baselines: We compare our algorithm to state-of-the thethe-arrrrt art unlearned methods such as BM3D- AMP (Metzler al., 2016 2015). TVAL3 (Li] 2011 Li al. 2009 Zhang al.. (013), and Lasso in DCT basis (Ahmed et al. 1974). We also evaluated the performance of Lasso in a Daubechies wavelet basis (Daubechies) 1988 Wasilewski 2010) but found this performed worse than Lasso
DCT on all datasets. Thus hereon we refer to Lasso DCT as "Lasso" and do not include results of Lasso Wavelet.
Metrics: To quantitatively evaluate the performance of our algorithm, we use per-pixel mean- squared етror (MSE) between the reconstruction å and true image x", i.e. ||8-=-1| Note that because these pixels are over the range [-1, 1], it's possible for MSE to be greater than 1.
Implementation: To find set of weights w* that minimize Equ. 3 we use PyTorch (Paszke al.] 2017) with a DCGAN architecture. For baselines BM3D-AMP and TVAL3, we use the repositories provided by the authors Metzler et (2018) and eL respectively. For baseline reconstructions |
Lasso, use scikit-leam (Pedregosa et al. 101 Section the appendix provides further details on our experimental procedures, c.g. choosing hyperparameters. The supplementary material also contains our code repository for these experiments.
5.2
EXPERIMENTAL RESULTS
5.2. RESULTS: LEARNED REGULARIZATION
We first evaluate the benefits of learned regularization by comparing algorithm with and without learned regularization, i.c. \₁, = 100 and X 0, respectively. The latter setting is an unlearned method, as we are not leveraging (μ,, Σ) from specific dataset. In the former setting (n, Σ) from particular set of x-ray images; we then evaluate different set of x-ray images. We compare these two settings with varying noise and across different number of measurements.
first learn
Our results in Table [ show that learned regularization does indeed provide benefit. This bene- fit tends to increase with more noise or fewer measurements. Thus we can infer that assuming a learned Gaussian distribution over weights is useful, especially when the original signal is noisy or significantly compressed.
5.2.2 RESULTS: UNLEARNED CS-DIP
For the remainder of this section, we evaluate our algorithm in the noiseless case without learned regularization, i.e. when 7 in Eqn. D and λ 0 in Eqn. Hence CS-DIP is completely unlearned; as such, we compare it to other of unlearned algorithms on various datasets and with different measurement matrices.
7

---

Under review as a conference paper at ICLR 2020
Diiginal
Ou
TUALS
Luase
(a) Reconstructions Chest X-ray
(b) Reconstructions MNIST
Figure 2: Reconstruction results x-ray images for m 2000 measurements (of 65536 pixels) and MNIST for m = 75 measurements (of 784 pixels). From top to bottom row: original image, reconstructions by algorithm, then reconstructions by baselines BM3D-AMP, TVAL3, and Lasso. For x-ray images the number of mcasurements obtained are 3% the number of pixels (i.e. m .03), for which BM3D-AMP often fails converge.
MNIST: In Figure Tb we plot reconstruction with varying number of measurements of 784. This demonstrates that our algorithm outperforms baselines almost all cases. Figure 2b shows reconstructions for 75 measurements, while remaining reconstructions
the appendix.
Chest X-Rays: In Figure la we plot reconstruction error with varying number of measurements m of n 65536. Figure 2a shows reconstructions for 2000 measurements; remaining reconstructions are in the appendix. On this dataset we outperform all baselines except BM3D-AMP for higher m. However for lower m, c.g. when the ratio < 3%. BM3D-AMP often doesn't converge. This finding seems to support the work of Metzler et al. (2015): BM3D-AMP performs well on higher m, e.g. m7 Z 10%, but recovery lower sampling rates is not demonstrated.
n
Retinopathy: We plot reconstruction error with varying number of measurements m of n 49152 in FagureBajof the appendix. On this RGB dataset we quantitatively outperform all baselines except BM3D-AMP on higher m; however, even at these higher m, patches of green and purple pixels corrupt the image reconstructions as seen in Figure TO Similar to x-ray for lower m, BM3D-AMP often fails to produce anything sensible. All retinopathy reconstructions are located in the appendix.
All previous experiments used measurement matrix A containing Gaussian i.i.d. entries. We now consider the case where the measurement matrix is subsampled Fourier matrix, as discussed in Section of the appendix. Our algorithm outperforms baselines on the x-ray dataset, shown in the appendix Figure 3b
Fourier Measurement Process:
Additional Experiments, Appendix Figure 4a we compare our algorithm against the learned approach of [Bora et al. (2017). In Figure 4b we compare our algorithm against baselines in the presence of noise, i.e. when 17 * Eqn. the x-ray dataset in Table
We also demonstrate runtimes for all algorithms on
CONCLUSION
We demonstrate how Deep Image Prior (DIP) can be generalized to solve any differenniable linear inverse problem. We further propose a learned regularization method which, with a small amount of prior information, reduces reconstruction emor for noisy compressed measurements. Lastly prove that the DIP optimization technique can fit any signal given a sufficiently wide single-layer network. This provides theoretical justification for regularization methods such early stopping.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alekh Agarwal, Sahand Negahban, and Martin J Wainwright. Fast global convergence rates of gradient methods for high-dimensional statistical recovery. In Advances in Neural Information Processing Systems, pp. 37-45, 2010.
Nasir Ahmed, T- Natarajan, and Kamisetty R Rao. Discrete cosine transform. IEEE transactions on Computers, 100(1):90-93, 1974.
Muhammad Asim, Fahad Shamshad, and Ali Ahmed. Solving invorsss using deep generative priors. CoRR, abs/1802.04077 2018. URL htRl:tttt.//arxv..or///////////
04073
Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et al. Optimization with sparsity-inducing penalties. Foundations and Trends in Machine Learning, 4(1):1-106, 2012.
Richard G Baraniuk, Volkan Cevher, Marco F Duarte, and Chinmay Hegde. Model-based compres- sive sensing. IEEE Transactions on Information Theory, 1684):1982-2001, 2010.
Peter J Bickel, Yaacov Ritov, Alexandre B Tsybakov, et al. Simultancous analysis of lasso and dantzig selector. The Annals Statistics, (7()) 37(4):1705-17333 2009.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros Dimakis. Compressed sensing using genera- tive models. arXiv preprini 1703,032700020 2017.
Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, 51(12):220-44215 2005.
Emmanuel Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-55 2006.
Exact signal
Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59(8): 1223, 2006.
Stanley Chan, Xiran Wang, and Omar A Elgendy. Plug-and-play admm for image restoration: Fixed-point convergence and applications. IEEE Transactions on Computational Imaging, 3(1): 84-98, 2017.
Jen-Hao Rick Chang, Chun-Liang Li, Barnabás Péczos, B. V. K. Vijaya Kumar, and Aswin C. Sankaranarayanan. One network to solve them all solving linear inverse problems using deep projection models. CoRR, abs/1 703.09912, 2017.
Guang-Hong Chen, Jie Tang, and Shuai Leng. Prior image constrained compressed sensing (pices): method accurately reconstruct dynamic ct images from highly undersampled projection data sets. Medical physics, 35(2):660-66) 2008.
Ingrid Daubechies. Orthonormal bases of compactly supported wavelets. Communications on pure and applied mathematics, 41(7):909- 996, 1988.
Akshat Dave, Anil Kumar Vadathya, Ramana Subramanyam, Rahul Baburajan, and Kaushik Mitra. Solving inverse computational imaging problems using deep pixel-level prior. arXiv preprint 1rXiv:/802.0000 09850, 2018.
Manik Dhar, Aditya Grover, and Stefano Ermon. Modeling sparse deviations for compressed sensing using generative models. arXiv preprint 1xXx:1807700442.. 2018.
Soren Dittmer, Tobias Kluth, Peter Maass, and Daniel Otero Baguer. Regularization by architecture: A deep prior approach for inverse problems. arXiv preprint arXiv:1812.03388,, 2018.
David L Donoho. Compressed sensing. IEEE Transactions on info theory, 52(4):1289-1300 2006.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint 18000218,, 2018

---

Under review as a conference paper at ICLR 2020
Marco F Duarte, Mark A Davenport, Dharmpal Takhar, Jason N Laska, Ting Sun, Kevin F Kelly, and Richard G Baraniuk. Single-pixel imaging via compressive sampling. IEEE signal processing magazine, 25(2):83-91, 2008.
Armin Eftekhari and Michael Wakin. New analysis of manifold embeddings and signal recovery from compressive measurements. Applied and Compulational Harmonic Analysis, 39(1)677119, 2015.
Ender M Eksioglu and A Korhan Tane. Denoising amp for mri reconstruction: Bm3d-amp-mri. SIAM Journal on Imaging Sciences, 1 113)22090-2109, 2018.
Alyson K Fletcher and Sundeep Rangan. Inference in deep networks in high dimensions. arXiv
preprint arXiv:1706.0653 2017.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair,
Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NeurIPS, pp. 2672-2680, 2014.
Aditya Grover and Stefano Ermon. Amortized variational compressive sensing. ICLR Workshop, 2018a.
Aditya Grover and Stefano Ermon. Uncertainty autoencoders: Learning compressed representations via variational information maximization. arXiv preprint arXiv: 2b.
Kerstin Hammernik, Teresa Klatzer, Erich Kobler, Michael P Recht, Daniel K Sodickson, Thomas Pock, and Florian Knoll. Learning a variational network for reconstruction of accelerated mri data. Magnetic resonance in medicine, 79(6):3055-330 -0771 2018.
Paul Hand and Vladislav Voroninski. Global guarantees for enforcing deep generative priors by empirical risk. arXiv preprint arXiv: 2017.
Paul Hand, Oscar Leong, and Vlad Voroninski. Phase retrieval under generative prior. In Advances in Neural Information Processing Systems, pp. 9154-9164, 2018.
Reinhard Heckel, Wen Huang, Paul Hand, and Vladislav Voroninski. Deep denoising: Rate-optimal recovery of structured signals with a deep prior. arXiv preprint arXiv: 088555 2018.
Chinmay Hegde and Richard G Baraniuk. Signal recovery on incoherent manifolds. IEEE Transac- tions on Information Theory, 58(12);7204-7144 2012.
Chinmay Hegde, Michael Wakin, and Richard Baraniuk. Random projections for manifold learning. In Advances neural information processing systems, pp. 641-648, 2008
AD Hoover, Valentina Kouznetsova, and Michael Goldbaum. Locating blood vessels in retinal im- ages by piecewise threshold probing of matched filter response. IEEE Transactions Medical imaging, 1933):00--210, 2000.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015.
Stefan Jaeger, Sema Candemir, Sameer Antani, Yi-Xiáng J Wáng, Pu-Xuan Lu, and George Thoma. Two public chest x-ray datasets for computer-aided screening of pulmonary diseases. Quantitative imaging in medicine and surgery, 4(6):475, 2014.
Maya Kabkab, Pouya Samangouei, and Rama Chellappa. Task-aware compressed sensing with generative adversarial networks. arXiv preprint /80.00/802.0/284 2018.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. preprint arXiv: 2013.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
10

---

Under review as a conference paper at ICLR 2020
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 96(11):2278-2333 1998.
Jaakko Lehtinen, Jacob Munkberg, Jon Hasselgren, Samuli Laine, Tero Karras, Miika Ait- tala, and Timo Aila. Noise2noise: Learning image restoration without clean data. preprint arXiv:1803.04189 2018.
Chengbo Li. Compressive sensing for 3d data processing tasks: applications, models and algorithms. Technical report, Rice University, 2011.
Chengbo Li, Wotao Yin, and Yin Zhang. Tval3: Tv minimization by augmented lagrangian and al-
ternating direction algorithms. https: //wp:: caam. rice. edu/ itt.ee.eeeuoopptiimiiiiioooo.o
TVAL3/
Chengbo Li, Wotao Yin, and Yin Zhang. Users guide for tval3: Tv minimization by augmented lagrangian and alternating direction algorithms. CAAM report, 20(46-47):4, 2009.
Jiaming Liu, Yu Sun, Xiaojian Xu, and Ulugbek Kamilov. Image restoration using total variation regularized deep image prior. arXiv preprint arXiv: 1810..2864, 2018.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), 2015.
Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. In NeurlPS, pp. 2726-2734, 2011.
Michael Lustig, David Donoho, and John M Pauly. Sparse mri: The application of compressed
sensing for rapid mr imaging. Magnetic resonance in medicine, 58(6):1182-11 11921199, 2007.
Michael Lustig, David L Donoho, Juan M Santos, and John M Pauly. Compressed sensing mri. IEEE signal processing magazine, 25(2):72-82) 2008.
Fangehang Ma, Ulas Ayaz, and Sertac Karaman. Invertibility of convolutional generative networks from partial measurements. Advances Neural Information Processing Systems, pp. 9628- 9637, 2018.
Morteza Mardani, Enhao Gong, Joseph Cheng, Shreyas Vasanawala, Greg Zaharchuk, Marcus Alley, Neil Thakur, Song Han, William Dally, John M Pauly, et al. Deep generative adversarial networks for compressed sensing automates mri. arXiv preprint arXiv: wo0/ 1705.00051 2017a
Morteza Mardani, Hatef Monajemi, Vardan Papyan, Shreyas Vasanawala, David Donoho, and John Pauly. Recurrent generative adversarial networks for proximal learning and automated compres- sive image recovery. arXiv preprint arXiv:1711.10000 2017b.
Morteza Mardani, Qingyun Sun, Shreyas Vasawanala, Vardan Papyan, Hatef Monajemi, John Pauly, and David Donoho. Neural proximal gradient descent for compressive imaging. arXiv preprint arXiv:1806.0 03966, 2018.
Chris Metzler, Ali Mousavi, and Richard Baraniuk. Learned d-amp: Principled neural network based compressive image recovery. In NeurlPS, pp. 1772-1783, 2017.
Chris Metzler al. D-amp toolbox. httppe://giicubb.cm//rieeee 2018.
Christopher A Metzler, Arian Maleki, and Richard G Baraniuk. Bm3d-amp: A new image recov- ery algorithm based on bm3d denoising. In Image Processing (ICIP), 2015 IEEE International Conference on, pp. 3116-3120. IEEE, 2015.
Christopher A Metzler, Arian Maleki, and Richard G Baraniuk. From denoising to compressed sensing. IEEE Transactions on Information Theory, 62(9)5511--114, 2016.
Dustin G Mixon and Soledad Villar. Sunlayer: Stable denoising with generative networks. arXiv preprint arXiv: 1003.08033.093 2018
11

---

Under review as a conference paper at ICLR 2020
Sahand Negahban, Bin Yu, Martin J Wainwright, and Pradeep K Ravikumar. A unified framework for high- nigh-dimensional analysis of m-estimators with decomposable regularizers. In Advances in Neural Information Processing Systems, pp. 1348-1355 2009.
Dong Nie, Roger Trullo, Jun Lian, Caroline Petitjean, Su Ruan, Qian Wang, and Dinggang Shen. Medical image synthesis with context-aware generative adversarial networks. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 417-425.
Springer, 2017.
Roberto Imbuzeiro Oliveira. The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties. arXiv preprint arXiv: 1312. 2013.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterrized nonlinear learning: Gradient descent takes the shortest path? 12 2018. URL
Samet Oymak and Mahdi Soltanolkotabi. 'Towrrds moderate overparametterization:: global conver- gence guarantees for training shallow neural networks. arXiv preprint wwXiv:/902.044 2019.
Parthe Pandit, Mojtaba Sahraee, Sundeep Rangan, and Alyson K Fletcher. Asymptotics of map inference deep networks. arXiv preprint arXiv:190..01293, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. Open Review, 2017.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Saad Qaisar, Rana Muhammad Bilal, Wafa Iqbal, Muqaddas Naureen, and Sungyoung Lee, Com- pressive sensing: From theory to applications. Journal of Communications and networks, 15(5): 2013.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.064:5 2015.
Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regularization by denoising (red). SIAM Journal on Imaging Sciences,
2017.
Leonid Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-26) 1992.
Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin- dero, and Raia Hadsell. Meta-learning with latent embedding optimization. arXiv preprint 1rXiv:1807.055 2018.
Thomas Schlegl, Philipp Seebück, Sebastian M Waldstein, Ursula Schmidt-Erfurth, and Georg Langs. Unsupervised anomaly detection with generative adversarial networks to guide marker discovery. In International Conference on Information Processing in Medical Imaging, pp. 146- 157. Springer, 2017.
Jo Schlemper, Jose Caballero, Joseph V Hajnal, Anthony N Price, and Daniel Rueckert. deep cas- cade of convolutional neural networks for dynamic mr image reconstruction. IEEE transactions on Medical Imaging, 37(2):991550 2017.
Philip Schniter, Sundeep Rangan, and Alyson Fletcher. Vector approximate message passing for IEEE, 2016.
the generalized linear model. In ACSSC, pp.
Viraj Shah and Chinmay Hegde. Solving linear inverse problems using gan priors: An algorithm with provable guarantees. arXiv preprint arXiv:1802.084000 2018
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), pp. 267-288, 1996.
12

---

Under review as a conference paper at ICLR 2020
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26- 31, 2012.
Subarna Tripathi, Zachary C Lipton, and Truong Q Nguyen. Correction by projection: Denoising images with generative adversarial networks. arXiv preprint urXiv:1803.044477 2018.
Joel A Tropp. Just relax: Convex programming methods for identifying sparse signals in noise.
IEEE transactions on information theory, 52(3):1030-1053 2006.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. arXiv preprint 17X1::1111.10225. 2017.
Aaron Van Den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint
2016.
Singanallur V Venkatakrishhan, Charles A Bouman, and Brendt Wohlberg. Plug-and-play priors for model based reconstruction. In GlobalSIP, 2013 IEEE, pp. 945-948. IEEE, 2013.
Yilun Wang, Junfeng Yang, Wotao Yin, and Yin Zhang. A new altemattng minimization algorithm for total variation image reconstruction. SIAM Journal on Imaging Sciences, 1(3):248- 2008
F Wasilewski. Pywavelets: Discrete wavelet transform in python, 2010.
David W Winters, Barry D Van Veen, and Susan C Hagness. A sparsity regularization approach to the electromagnetic inverse scattering problem. IEEE transactions on antennas and propagation, 58(1):145-154, 2010.
Jelmer M Wolterink, Tim Leiner, Max A Viergever, and Ivana lggum. Generative adversarial net- works for noise reduction in low-dose ct. IEEE transactions on medical imaging, 36(12):2536- 2545, 2017.
Jian Zhang, Shaohui Liu, Ruiqin Xiong, Siwei Ma, and Debin Zhao. Improved total variation based image compressive sensing recovery by nonlocal regularization. In Circuits and Systems (ISCAS), 2013 IEEE International Symposium on, pp. 2836-2839. IEEE, 2013.
13

---

Under review as a conference paper at ICLR 2020
A ADDITIONAL EXPERIMENTS DETAILS, AND INSIGHTS
Hyperparameters: Our algorithm CS-DIP implemented in Py PyTorch using the RMSProp opti- mizer (Tieleman & Hinton 2012) with learning rate 10-3, momentum 0.9, and 1000 update steps for every set of measurements. These parameters are the same across all datasets. We initialize one random measurement matrix A for each image in all experiments. Further we the TV hyperpa- rameter 'y = 0.01, and found that high frequency components of the image were not reconstructed as sharply with Xy 0.
Dataset-specific design choices: On larger images such as x-ray (n 65536) and retinopathy (n 49152), we found no difference using random restarts of the initial seed 2. However for smaller vectors such as MNIST (n = 784), restarts did provide some benefit. As such our experiments utilize random restarts for MNIST and one initial seed (no restarts) for x-ray and retinopathy images. For choosing hyperparameter Xr. in Eqn. we used standard grid search and selected the best one. We used a similar grid search procedure for choosing dataset-specific hyperparameters baseline algorithms BM3D-AMP, TVAL3, and Lasso.
Learned Regularization: For learned regularization, 10 x-ray images are used to learn μ and Σ. The results then evaluated, i.e. averaged over x², 50 additional x-ray images.
Network Architecture: Our network has depth 7 and uses convolutional layers with ReLU activa- tions. The initial seed in Eqn. is initialized with random Gaussian i.i.d. entries and then held fixed as we optimize over network weights w. We found negligible difference when varying the dimension of (within reason), this only affects the number of channels in the network's first layer. Hence we set the dimension of = to be 128, a standard choice for DCGAN architectures.
Stopping Criterion:
We stop after 1000 iterations in all experiments. We did not optimize this hyperparameter, so admittedly there could be room for improvement. We further note that the "Error vs. Iterations" curve of CS-DIP with RMSProp did not monotonically decrease for some learning rates, even though еттоr gradually decreased in all cases. As such we implemented stopping condition which chooses the reconstruction with least error over the last 20 iterations. Note choose this reconstruction based off measurement loss and do not look at the ground truth image.
The measurements are obtained by sampling Fourier coefficients along radial lines as demonstrated in Figure [3 For a 2D image and set of indices Ω the measurements
Fourier Sampling:
we receive are given by B(i.j) F(xx) (z))( (i,j) E Z2 where J is the 2D Fourier transform. We choose 52 to be indices along radial lines, shown in Figure 13 of the appendix; this choice of Ω is common in literature (Candès et al. 2006) and MRI applications (Mardani et al., 201 70 Lustig et al. 2008 Eksioglu & Tane (2018). While Fourier subsampling is common in MRI applications, we use it here on images of x-rays simply to demonstrate that our algorithm performs well with different measurement processes.
We compare our algorithm to baselines on the x-ray dataset for {3, 5, 10, 20} radial lines in the Fourier domain, which corresponds to (381, 634, 1260, 2500} Fourier coefficients, respectively. We plot reconstruction eтror with varying number of Fourier coefficients in Figure 3b outperforming baselines. Reconstructions be found in Figure
Table 2: Runtime (seconds) for each algorithm with varying number of measurements. Note that our algorithm was run NVIDIA GTX 1080-Ti GPU, while baselines only leverage CPU. Thus our goal here is not compare runtimes; instead we demonstrate that our algorithm can run in reasonable amount of time, which is an issue with other DIP methods.
Algorithm CS-
1000
2000
4000
8000
15.6
17.1
20.4
29.9
BM3D-AMP
51.1
54.0
67.8
71.2
TVAL3
13.8
22.1
31.9
56.7
Lasso DCT
27.1
33.0
52.2
96.4
14

---

Under review as a conference paper at ICLR 2020
0.010
0.012
Ours AMM Lasso
Ours
Reconstruction Error
0.008
BM3D-AMP
TVAL3
Reconstruction
0.008
0.006
0.006
0.004
0.004
0.002
0.002
0.000
500
1000
2000
400
8000
0.000
500
1000
1500
2000
2500
Number of Measurements
Number Fourier Coefficients
(a) MSE Retinopathy (RGB) with Gaussian mea-
(b) MSE - Chest X-ray with Fourier measurements
surements
Figure 3: Per-pixel reconstruction eπror (MSE) vs. number of measurements. Vertical bars indi-
cate 95% confidence intervals. Unfortunately an RGB version of TVAL3 does not currently exist,
although related TV algorithms such as FTVd perform similar denoising tasks (Wang et al. 2008).
Ours
Ours m-2000
TVAL3 m,200
0.25
Reconstruction Error
Recontinction Eiror
020
0.009
0:15
0.006
0.10
0.004
0.00
10
100
200
500
1000
Number of Measurements
o²
(a) Reconstruction error (MSE) on MNIST varying number of measurements. As expected, the trained algorithm of Bora et al. (CSGM) outper- forms our method for fewer measurements; how- ever, CSGM saturates after measurements, its output is constrained to the range the generator. This saturation is discussed in Bora et al., Section 1.
(b) Reconstruction enror (MSE) on x-ray images for varying amounts of noise: number of mea- surements m fixed at 2000. The term o² corre- sponds to variance of the noise vector in y Ax + i.c. i.c. each entry of 17 drawn independently N(0, <²). Other baselines have far above the vertical axis are thus not visible in this plot.
Figure 4
Algorithm Estimate (μ, M) for distribution of optimal network weights W
Input: Set of optimal weights W = [w], ...... w obtained from L-layer DCGAN run over Q images; number of samples S; number of iterations T. Output: Mean vector E I:;; covariance matrix _
1: for /. 1 T do
2: Sample uniformly from (1...., Q}
3:
for = 1 L {for each layer) do Get v E R a vector of S uniformly sampled weights from the 4 layer of wg
4:
5:
[] t T where M,[1, :| is the 1th row of matrix M, E L.x8
6:
[e[ <- S U/
7:
end for
8: Σ, + 3 Mf - uelaa
9: end for
T Pt
10: / + T
11: Σ Σi=1 Σx
15

---

Under review as a conference paper at ICLR 2020
B PROOF OF SECTION 4 THEORETICAL JUSTIFICATION FOR EARLY STOPPING
In this section we prove our theoretical result in Theorem 4. We begin with summary of some notations we use throughout in Section[B1] Next, we state some preliminary calculations in Section B.2
Then, we state few key lemmas Section B.3 with the proofs deferred to Appendix Finally, complete the proof of Theorem 4. in Section B.4
B.1 NOTATION
In this section we gather some notation used throughout the proofs. We use 6(2) =ReLU(2) max(0, 2) with (z) = I[220)- For two matrices/vectors, and of the same size we use y to denote the entrywise Hadamard product of these two matrices/vectors. We also use x & y to denote their Kronecker product. For two matrices B E guxd: and C' Rnxd,
the Khatrio-Rar Rao product as the matrix A = B C Raxdjda with rows A given by A, = B, & C. For a matrix M Rmxn we vect(M) Rm to denote vector obtained by aggregating the rows of the matrix M into a vector, i.e. vect(M) = [M M₂
Mn For a matrix we use (X) and ||]]| denotes the minimum singular value and spectral norm of X. Similarly, for symetric matrix M we use (M) to denote its smallest eigenvalue.
B.2 PRELIMINARIES
In this section carryout some simple calculations yielding simple formulas for the gradient and Jacobian mappings. We begin by noting we can rewrite the gradient descent iterations in the form
vect (W++1) = vect (W+) - ryvect (VL (W+)).
Here,
vect (VL(W-)) =
where
J (W) dvect (W) f(W) and
is the Jacobian mapping associated to the network and
(W) o (V6(22)) y.
the misfit residual vector. Note that
Ovect (W) oT à (Wz)= = [o (w 2) T.
v (ww x) xt
u (ww 2) xT
(u ø' (Wx))² xT
Thus
J (W) = (Vdiag (o((W=))) (12"),
This in turn yields
I JW (W)- (Vdiag (ø' (W))) diag (d(W2)) V (l=][2117]
= || Vdiag (o' (W=) @ o' (Wz)) Fr
(8)
B.3 LEMMAS FOR CONTROLLING THE SPECTRUM OF THE JACOBIAN AND INITIAL MISFIT
In this section we state a few lemmas concerning the spectral properties of the Jacobian mapping, its perturbation and initial misfit of the model with the proofs deferred to Appendix
16

---

Under review as a conference paper at ICLR 2020
Lemma B.1 (Minimum singular value of the Jacobian initialization). Let V Baxd and W Rdxk be random matrices with i.dd. N0 v²) and ( 1) entries and define the Jacobian mapping I ((W) = (Vdiag (Wz))) * (1=²). Then as long as 2 3828m,
1 v/ mmin (J(W))
2
holds with probability at least 1 -e
Lemma B.2 (Perturbation lemma). Let V E Raxd be matrix with i.idd NN v²) entries, W e Bd and define the Jacobian mapping I (W) = (Vdiag (ø' (W2))) * (1=²). Also let Wo be matrix with i...d. (( 1) entries. Then.
d 3 (2dR)3
([T(W) J(W)ll & v ||]||
2/n+
(2dR) log
holds for all W Baa obeying IW - Woll s R with probability least - -12 (24R)
Lemma B.3 (Spectral norm of the Jacobian). Let V Roxd be a matrix with i.i.d. NN v²) entries,
W E Rdxk, and define the Jacobian mapping J (W) = (V (Vdigg ( (Wz))) (1z²). Then,
[J(WI S (vd+ + 2/T) ||=||
holds for all W Ba with probability at least 1 cn/2
Lemma B.4 (Initial misfit). Let V E goxd be matrix with i.i.d. N(O, entries with Also let W E Baakk be matrix with i.i.d. (0, 1) entries. Then Van
(W=) vll S 11yll,
holds with probability at least - n/2
nn/ - dd/2
B.4 PROOF THEOREM
Consider nonlinear least-squares optimization problem of the form
min L()) :- [1((0) - 2 GERP
with IP R and y RR. Suppose the Jacobian mapping associated with f obeys the following three assumptions.
Assumption 1. Fix point 0g. We have that mmin (J 2 20.
Assumption 2. Let || || denote norm that is dominated by the Euclidean norm i.e. ||@] < ||||| holds for all 0 E Rº Fix point 0g and number R 0. For any 0 satisfying ||0 0oll s R, we have that (0,) - [O)]] S a/3.
Assumption 3. For all 0 e IR,, we have that [[]())]] < 8.
Under these assumptions we can state the following theorem from Oymak Soltanolkotabi (2019) Theorem B.5 (Non-smooth Overparameterized Optimization). Given Op E IRP, suppose Assump- tions 7 and hold with
5 [yy - [(0o)]
Then, picking constant learning rate 1j S
1 Tz, all gradient iterations obey the followings
ly - f(0,))l s 5(1 (1--a-)
na? - 11 f(0o)]
(9)
100 - Abll + I1l - (1y-f(0t)) & 1l - f(b)))
(10)
17

---

Under review as a conference paper at ICLR 2020
We shall apply this theorem to the case where the parameter is W and the nonlinear mapping is given by V (Wz) and & = ReLU. All that is needed to be able to apply this theorem is check that the assumptions hold. Per the assumptions of the theorem use
v dn
|=||
To this aim note that using Lemma B. Assumption holds with
|||||
|Bll
4yn n
with probability at least 2e ", Furthermore, by Lemma B.3 Assumption 3 holds with
44n + d
1
V 4n |vll (vd+ [Vd+2vi 22
d
+
||=||
8n
2
with probability at least - en/2 All that remains for applying the theorem above is to verify Assumption holds with high probability
R / 15 Illll
5
V (W=) y/l
In the above we have used Lemma B.4 conclude that Vo (W2) y s 3 |yl| holds with proba-
bility at least 1 em e 4/2, Thus, using Lemma
B.2 all that remains is to show that
|lv|l
2/T+
6 ((dd)) in
1
vdn
3 (2dR)
3
12
holds with R 60/n and with probability at least - e-/22 --4d n The latter is equivalent to
(120)
dsnt
2 1 - c enn2
2/n 6 (120dvm) 8 In
d
vd
(120dd/))
12
which can be rewritten in the form
1
2 d
6 (120)
In d
3(120)
12
which holds as long as d 2 4.3 10" n. Thus with d 2 Cn then Assumptions and 3 holds with
probability least 1 - 5n/2 - 4/2 - e 4d
Thus, Theorem B.5 holds with high probability.
Applying Theorem B.5 completes the proof.
C PROOF OF LEMMAS FOR THE SPECTRAL PROPERTIES OF THE JACOBIAN
C.1 PROOF OF LEMMA B.
We prove the result for v = 1, the general result follows from a simple re-scaling. Define the vectors
at Vio ((we, 2)) E IR",
with Ve the εth column of V. Using equation g we have
I (W) JJ (W) = ||=|| Vdiag (o' (Wz) @ (W(())) VT,
= =|
Σ boso T
=d 1||1
agag
T
(1I)
To bound the minimum eigenvalue we state result from Oliveira (2013)
18

---

Under review as a conference paper at ICLR 2020
Theorem C.1. Assume A Ad R=** are i.idd random positive semidefinite matrices whose coordinates have bounded second moments. Define Σ := [[] (this is an entry-wise expectation) and
Σn Σ t=1
Ap.
Let h (1, +00) be such that v B (u A2u)
S hu Tu for all R".
Then for any E (0,1)
we have
P VUER". R" : L'ENuZ 1 1 1 n 22m
" Eu 21-6
d
We shall apply this theorem with Ae == agaz.. this we need calculate the various parameters in the theorem. We begin with E and note that for ReLU we have
Σ [[,
[[aia]]
E. E (0' ((w, 2)))² Eo-N(o,
= E Em- (ø'(w" ((uz))) 2)) 14n
E [4
2 In-
To calculate h we have
BuT Anu) sv E [)]
B B [[wr=20)] EEao((a.t)) (oTu))]
|ull
3
2 ||ua|1
(1
=ou
(2
=V n² Eu.
Thus we can take V6. Therefore, using Theorem C.1
with 8 = 2e we can conclude that
Amin
Σ
aga
1
4
t=1
holds with probability at least
2e - as long as
2 3528 n.
Plugging this into equation 11 we conclude that with probability at least 1 2e-n 1 Omin (J(W)) 2 /d]l=/]
C.2 PROOF OF LEMMA B.2
We prove the result for v = 1, the general result follows from a simple rescaling. Based on equa-
tion g we have
(J(W) J(W)) (J(W)- - I(W))) |||| Vdiag ((0' (W=) o'(Woz)) (o' +'(W=z))) VT.
19

---

Lemma C.4. Oymak & Soltanolkotabi 2019 Lemma C.3) Let E TR Also ler Wo E Bddx be Under review as a conference paper at ICLR 2020
Thus
[ - J(W)ll s ||=|| diag (o' o' (Woo))
(12)
= ||=||| |Viag (4mw:00) - [[w,=20))]]
- | Vs(woll
(13)
where S(W) 21, d} is the set of indices where W= and Wo have different signs i.e. S(W) = {e sgn(e? + sgn(e) Woz)) and Vs(w) is a submatrix V obtained by pick- ing the columns corresponding to S(W).
To continue further note that by Gordon's 's lemma we have
||vll S vn + /ogg//()/) +t, [
sup
with probability at least 1 12/22 In particular using v we conclude that
sup S
|Vlll s 2y + / 22 log(d/s).
(14)
with probability least e--en/2 To continue further we state a lemma controlling the size of |S(W)] based on the size of the radius R.
Lemma C.2 (sign changes in local neighborhood). Let Wo Rdxk be matrix with i.idd N 1) entries. Also for a matrix W Raxk define S(W) = {E sgn(e? * sgn(e} Wo Then for any IRdck obeying [W - Woll S R
[S(W) < (2 $1
holds with probability least 1-e (adn)
Combining equation 12 clude that
together with equation 14 (using 3 (2dR)3) and Lemma C.2
we con-
d 3 (2dR) 3
(J(W)- - J(wo)l s ||
2 + 6 (2dR)) log
holds with probability at least nn2
(24R)
C.3 PROOF OF LEMMA
To prove this result we utilize two lemmas from Oymak & Soltanolkotabi (2019). In these lemmas we use [u] mm denote the mth smallest entry after sorting entries terms of absolute value.
Lemma C.3. Oymak Soltanolkotabi 2019 Lemma C.2) Given an integer m, suppose
|| - Woll S vm Woz
then
IS(W) < 2m.
matrix with i.d (O. 1) entries. Then, with probability at least -
Wo mn-
m
I
2d
20

---

Under review as a conference paper at ICLR 2020
Combining the latter two lemmas with m [(2dR)
$1
we conclude that when
IW Woll SR
m 3
2d
m
/ m
2d
W62
m
|
(242) 4
then with probability least 1
we have
S(W) S 2m s 2[(2R))
C.4 PROOF OF LEMMA B.3
We prove the result for // = 1, the general result follows from a simple rescaling. Using equation have
J (W) J" (W) = ||==1 diaag (ø o VT
Thus
I| (W)Il S ||=||| di (o'(W2))]
| |[
The proof is complete by using standard concentration results for the spectral norm of a Gaussian matrix that allow to conclude that
II & vd
holds with probability at least n4/2
C.5 PROOF OF LEMMA B.4
By the triangular inequality have
(W2) vll < (W=)) + |lvll
(15)
To continue further let us consider one entry of V (W2) and note that has the same distribution
V (Wz) v o W 2))l g.
where g Rd is random Gaussian vectors with distribution NO, Ta). Thus
I (Wx) 2) ~ v (W I| I < /2nv [@(W=) S /2nw [|
(16)
with probability at least - c n// Furthermore, note that
Wz ||>||
where 7 Rd is random Gaussian vectors with distribution ğ (O( Combining the latter with equation T6 we conclude that
(V&(W2) S 2nndv ||=|| = ||y||,
holds with probability at least nn2 d/2, Combining the latter with equation 15 we conclude that
[Vo(W2) all < 31lll.
holds with probability at least 1
n/2 e-
d/2
21

---

Under review as a conference paper at ICLR 2020
D RECONSTRUCTIONS
Original
3
4
2
Origrnnl
3
4
OUT
803D-AH
YVALS
TVALS
LANO
(a) 25 measurements
(b) measurements
Figure 5: Reconstruction results on MNIST for 25, 50 measurements respectively (of n 784 pixels). From top to bottom row; original image, reconstructions by our algorithm, then reconstruc- tions by baselines BM3D-AMP, TVAL3, and Lasso.
22

---

Under review as a conference paper at ICLR 2020
O'geaa
0
3
4
2
Onges
W
4
2
QuS
0
3
2
OUS
3
4
BR33
3
4
TVAL
3
4
7
(a) 100 measurements
(b) 200 measurements
Figure 6: Reconstruction results on MNIST for m = 100, 200 measurements respectively (of 784 pixels). From top to bottom original image, reconstructions by our algorithm, then reconstructions by baselines BM3D-AMP, TVAL3, and Lasso.
Original
ours
D0050 400
TAALS
TONLY
Luoua
(a) 500 measurements
(b) 1000 measurements
Figure 7: Reconstruction results on x-ray images for m 500, 1000 measurements respectively (of 65536 pixels). From top bottom row: original image, reconstructions by algorithm, then reconstructions by baselines BM3D-AMP, TVAL3, and Lasso.
23

---

Under review as a conference paper at ICLR 2020
PALL
Liso
LAND
(a) 4000 measurements
(b) 8000 measurements
Figure 8: Reconstruction results on x-ray images for 4000, 8000 measurements respectively (of = 65536 pixels). From top to bottom row: original image, reconstructions by our algorithm, then reconstructions by baselines BM3D-AMP, TVAL3, and Lasso.
Dr gnal
LaG3o
(a) 500 measurements
(b) 1000 measurements
Figure 9: Reconstruction results on retinopathy images for m 500, 1000 measurements respec- tively (of 49152 pixels). From top bottom row: original image, reconstructions by our algo- rithm, then reconstructions by baselines BM3D-AMP and Lasso.
24

---

Under review as a conference paper at ICLR 2020
Original
Ours
BM3D-AMP DMP
Lasso
Figure 10: Reconstruction results on retinopathy images for 2000 measurements (of n = 49152 pixels). From top to bottom row: original image, reconstructions by our algorithm, then recon- structions by baselines BM3D-AMP and Lasso. In this case the number of measurements is much smaller than the number of pixels (roughly 4% ratio), for which BM3D-AMP fails to converge, as demonstrated by erroneous green and purple pixels. We recommend viewing in color.
25

---

Under review as a conference paper at ICLR 2020
Original
Ours
BM3D AMP
Lasso
Figure 11: Reconstruction results retinopathy images for 4000 (of 49152 pixels). From top to bottom row: original image, reconstructions by our algorithm, then reconstructions by base- lines BM3D-AMP and Lasso.
26

---

Under review as a conference paper at ICLR 2020
Original
Ours
BM3D AMP
Lasso
Figure 12: Reconstruction results retinopathy images for 8000 (of 49152 pixels). From top to bottom row: original image, reconstructions by our algorithm, then reconstructions by base- lines BM3D-AMP and Lasso.
27

---

Under review as a conference paper at ICLR 2020
Figure 13: A radial sampling pattern of coefficients Q in the Fourier domain. The measurements are obtained by sampling Fourier coefficients along these radial lines.
Original
Ours
BM3D-ANE AMP
TVAL3
Figure 14: Reconstruction results x-ray images for 1260 Fourier coefficients (of n 65536
pixels). From top to bottom row: original image, reconstructions by our algorithm, then reconstruc- tions by baselines BM3D-AMP and TVAL3.
28


Reviews:
[{"review_id": "rJehnPMZ9r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new algorithm for compressed sensing using untrained generative model. To the best of my knowledge, the proposed method is new. The closest method, as stated by the authors, is by Bora et al. (2017). However, Bora et al. (2017) is a pre-trained method and would require access to a large number of samples. This paper, in comparison, only requires access to a small number of samples as it is an untrained generative model. \n\nThe major theoretical contribution is that by running gradient descent, for a network with single hidden layer, the training error will decrease to 0. This provides theoretical justification for early stopping adopted by the authors.\n\nMy complaint to the paper is that the theoretical justification of the generalization ability of the proposed method is missing. The error goes to 0 is not surprising by many existing works, and the authors completely ignore the generalization error analysis of the proposed method.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1eyn6-Pcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "== After reading authors' response ==\n\nThe authors didn't really offer a response. Their new PDF just mentions that their proof for the case $A=I$ can be extended to any orthogonal matrix $A$ (since if $G$ is a iid Gaussian matrix with unit variance, so is $AG$ for any orthogonal matrix $A$).  Hence, I don't change my response, and still support \"weak accept\"\n\n\n== Original review ==\nThe paper proposes an extension to the 2017 \"Deep Image Prior\" (DIP) idea. DIP is a method to use untrained neural nets for compressed sensing, but uses the structure of the neural net to implicitly regularize and constrain the solution (though, as a major result of this paper shows, it doesn't regularize -- it can learn noise). It's an interesting combination of compressed sensing and deep learning.\n\nThis particular paper adds the following to the DIP idea:\n\n(1) it adds a total-variation (TV) semi-norm regularization term,\n\n(2) it adds a weighted Tikhonov/ridge-regression style regularization term, with learned weight-matrix, and some overall lambda_L hyper-parameter,\n\n(3) they provide a theorem, based on a 2019 preprint, that a very simplified version of the unregularized DIP model (1 layer, with one set of weights fixed and assumed drawn Gaussian) can be fully trained by gradient descent, and hence it can overfit to noise, and thus necessarily must be stopped early.\n\nThey provide some numerical experiments to demonstrate the performance of their approach.\n\n\n== I have some high-level criticism of the approach (things that cannot be fixed):\n\n-- The idea of an algorithm that must be stopped early is distasteful to me and perhaps to others as well. It's vague, and it means the model is wrong. It doesn't feel like math, it feels like sorcery. You haven't actually provided a result that says when to stop, or that stopping early at all will help, only that running until convergence is a bad idea.\n\n-- Compressed sensing is a bit old these days, and part of the greatness of CS was what it inspired, even if single-pixel cameras have not overturned the camera industry. But pure CS, with a Gaussian measurement matrix, and noiseless measurements, is quite academic and not applicable to the real-world.  In particular, your method seems to do best when there are a lot of measurements (for low measurement numbers, the Bora et al approach does well, as does TVAL on the MNIST data -- see Fig 1b). The experiments were also noiseless, and they had Gaussian or the Fourier sampling (which is not random, but rather heavily biased toward DC). I'm not that convinced this is useful for medical imaging.\n\n\nOn the plus side, any approach for medical imaging is welcome, even if the connection is a bit academic. The writing was overall good.  Furthermore, the proof of the theorem seems like it combines quite a bit of good math. It wasn't clear if empirical process theory was used in their proof, or if that's from the 2019 result they cite.\n\n\n== Some major comments (things that *can* be addressed)\n\n-- Experimentally, I wasn't convinced that the learned regularization (LR) was useful. Table 1 appears to show it is helpful, but this is just saying that some kind of l2 regularization is useful. I would be convinced if you showed that vanilla Tikhonov regularization is not as helpful as your learned l2 regularization.\n\n-- Furthermore, for the benefit of your LR approach, you did a grid search on the lambda_L parameter to choose the best value. Since you never mentioned trainining/validation/testing data, I assume you did this on the final set of data? In that case, you've tuned your hyperparameter to your testing data, and so I don't find the results that convincing. I think this is a big deal.  Or maybe I don't understand what you've done, because the language \".. and selected the best one\" was unclear what \"best\" meant, e.g., if you look at a residual, or if you use ground-truth data. \n\n-- For both your LR and vanilla Tikhonov, you can try selecting lambda_L based on the residual or other non-oracle method. Standard methods include generalized cross-validation, Morozov’s discrepancy principle, and the unbiased predictive risk estimator method.\n\n-- For the results comparing with Bora et al., how much of your performance advantage was due to the TV term? Please re-do Fig 4b with variants of your method with lambda_T=0, lambda_L=0, and both lambdas=0 added to the plot.\n\n-- The handling of the TV term was not discussed. It seems you fed this into PyTorch and hoped for the best. Actually minimizing the usual isotropic 2D TV is tricky, and there are many optimization papers written about it. It's not differentiable, and if you actually converge, then you usually land at points of non-differentiability, so it cannot just be ignored. Sometimes it is smoothed, or a separable but non-isotropic version is used. I think your response to this point is, \"but we don't actually run the algorithm to convergence\" (since it will overfit), which I still find bizarre (imagine saying that in a paper submitted to an optimization journal!).\n\n== Summary of my opinion ==\n\nI liked the idea, but I think I liked the core idea of DIP more than the extensions that this paper provides. The experiments show enough promising results to make this interesting, but they have not explored the details of the extensions.  The theorem is very complex but quite limited in scope, and maybe would be better as its own (math) result rather than as an add-on to this paper.  The application of CS is a bit limited, and the biggest benefits seem to be in the high-measurement and low or zero-noise case.\n\nOverall, I lean toward weak reject, as I think the regularization parts of the paper would benefit from a major revision of the paper.\n\n\n== Minor comments ==\n\n- In section 3.1, the description of G is confusing. Writing G(z;w): R^k --> R^n is unclear. You mean G(.;w): R^k --> R^n. And calling z a \"seed\" confused me, until I realized you meant this is the \"input\" to the layer.\n\n- statements like \"we use early stopping, a phenomena that will be analyzed theoretically in Section 4\" are misleading, since you don't analyze early stopping at all. You show that your model doesn't regularize, so that it will fit noise (in a special simplified case), so that running to convergence is a bad idea. This doesn't mean you know when to stop.\n\n- Section 3.2, for p(y|w) and p(w), why not just say these are Gaussian and give the parameters?  In the sentence above eq (4), missing a \"log\" before \"posterior\".  The justification for the Gaussian weights (last paragraph on page 4) felt rather weak to me.  Like everyone for the past 60 years, you are adding a l2 regularization term because it's simple and it works fairly well and there are not that many alternatives.\n\n- It took me a while to figure out that Sigma was L x L. The description here was confusing (in section 3.2.1), and it was unclear of Sigma_U was a sub-matrix (and if it was diagonal or a scaled identity) or a scalar.\n\n- Thm 4.1: \n-- \"V is fixed at random\" sounds like it would make a proper probabilist squirm!  The statement of the theorem is that \"... holds ... with probability at least ...\". You mean that this probability is due to the randomness in V?\n\n-- You have a 1-layer network with 2 sets of weights, but in fact fix one set of weights; and it's not compressed sensing but denoising since A=I. I understand that results in this area are hard, but make sure not to oversell your result earlier in the paper, since this limited setting doesn't actually apply to the main problem you're interested in.\n\n-- \"While our proof is for the case of A=I, a similar result can be shown for other measurement matrices.\"  If that's true, then please show it!\n\n- Table 1: for with and without LR, did you have a TV term for both?\n\n- Section 5.2.1, \"thus we can infer that assuming a learned Gaussian distribution over weights is useful.\" No, I don't think this is an appropriate assumption.  Maybe you can infer that shrinking the estimator toward a fixed vector (e.g., 0), and training to find how much to shrink, makes your solution more robust (a bias-variance tradeoff).  In particular, in Table 1, I'd like to see the improvements for one of these entries as a box plot, to see if the improvement is due to controlling bad outliers, or if actually the bulk is really improved.\n\n- In bibliography, capitalize acronyms like \"admm\", \"amp\", \"mri\", etc.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkecZhUFcr", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a deep learning based compressed sensing method, CS-DIP which employs deep image prior algorithm to recovering signals especially for medical images from noisy measurements without pre-learning over large dataset. For further optimization, a learned regularization is leveraged over small training dataset.  Experimental results show that the proposed methods outperformed the others. The theoretical analysis of early stopping is also given. Overall, the writing of this paper is good, the idea is novel and the contribution is sufficient. Here are some of my comments:\n \n1.     The authors claim that CS-DIP is \"unlearned\", which makes me confusing. Although the latent representation $z$ in Eq.(2) is not learned, the weights $w$ is still learned from training over measurements. I think maybe the description is not accurate of saying that the network $G(z;w)$ is unlearned.\n \n2.  It would be better if the authors can compare CS-DIP with more deep-learning based CS methods. However, the proposed method is only compared with three traditional CS recovery method over several datasets. In Figure 4(a), only one deep-learning based method, CSGM, was compared with over MNIST dataset. More comparison should be conducted over all the datasets to demonstrate its efficiency, especially over medical image datasets.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1xHdzo0Fr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes use of the deep image prior (DIP) in compressed sensing. The proposed method, termed CS-DIP, solves the nonlinear regularized least square regression (equation (3)). It is especially beneficial in that it does not require training using a large-scale dataset if the learned regularization is not used. Results of numerical experiments demonstrate empirical superiority of the proposed method on the reconstruction of chest x-ray images as well as on that of the MNIST handwritten digit images.\n\nThe demonstrated empirical efficiency of the proposal is itself interesting. At the same time, the proposal can be regarded as a straightforward combination of compressed sensing and the DIP, so that the main contribution of this paper should be considered rather marginal. I would thus like to recommend \"weak accept\" of this paper.\n\nIn my view the concept of DIP provides a very stimulating working hypothesis which claims that what is important in image reconstruction is not really representation learning but rather an appropriate network architecture. The results of this paper can be regarded as providing an additional empirical support for this working hypothesis. On the other hand, what we have understood in this regard seem quite limited; for example, on the basis of the contents of this paper one cannot determine what network architecture should be used in the proposed CS-DIP framework applied to a specific task. I think that the fact that DIP is still a working hypothesis should be stressed more in this paper. It does not reduce the value of this paper as one providing an empirical support for it.\n\nI think that the theoretical result of this paper, summarized as Theorem 4.1, does not tell us much about CS-DIP. The theorem shows that overfitting occurs even if one uses a single hidden-layer ReLU network. As the authors argue, it would suggest necessity of early stopping in the proposal. On the other hand, I could not find any discussion on early stopping in the experiments: On page 14, lines 22-23, it seems that the theoretical result is not taken into account in deciding the stopping criterion, which would make the significance of the theoretical contribution quite obscure.\n\nPage 4, line 10: a phenomen(a -> on)\nPage 13: The paper by Ulyanov, Vedaldi, and Lempitsky on DIP has been published as a conference paper in the proceedings of CVPR 2018, so that appropriate bibliographic information should be provided.\nPage 16, line 26: On the right-hand side of the equation, the outermost \\phi should not be there.\nPage 17, line 3: 3828 should perhaps read 3528.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a compressed sensing (CS) method which employs deep image prior (DIP) algorithm to recovering signals for images from noisy measurements using untrained deep generative models.  A novel learned regularization technique is also introduced. Experimental results show that the proposed methods outperformed the existing work. The theoretical analysis of early stopping is also given. All reviewers agree that it is novel to combine the deep learning method with compressed sensing. The paper is well written and overall good. However the reviewers also proposed many concerns about method and the experiments, but the authors gave no rebuttal almost no revisions were made on the paper. I would suggest the author to consider the reviewers' concern seriously and resubmit the paper to another conference or journal.
Decision: Reject