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.
== After reading authors' response ==
The 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"
== Original review ==
The 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.
This particular paper adds the following to the DIP idea:
(1) it adds a total-variation (TV) semi-norm regularization term,
(2) it adds a weighted Tikhonov/ridge-regression style regularization term, with learned weight-matrix, and some overall lambda_L hyper-parameter,
(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.
They provide some numerical experiments to demonstrate the performance of their approach.
== I have some high-level criticism of the approach (things that cannot be fixed):
-- 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.
-- 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.
On 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.
== Some major comments (things that *can* be addressed)
-- 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.
-- 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. 
-- 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.
-- 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.
-- 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!).
== Summary of my opinion ==
I 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.
Overall, I lean toward weak reject, as I think the regularization parts of the paper would benefit from a major revision of the paper.
== Minor comments ==
- 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.
- 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.
- 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.
- 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.
- Thm 4.1: 
-- "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?
-- 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.
-- "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!
- Table 1: for with and without LR, did you have a TV term for both?
- 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.
- In bibliography, capitalize acronyms like "admm", "amp", "mri", etc.