Convolutional Neural Networks (CNNs) have emerged as highly successful tools for image generation, recovery, and restoration. This success is often attributed to large amounts of training data. However, recent experimental findings challenge this view and instead suggest that a major contributing factor to this success is that convolutional networks impose strong prior assumptions about natural images. A surprising experiment that highlights this architectural bias towards natural images is that one can remove noise and corruptions from a natural image without using any training data, by simply fitting (via gradient descent) a randomly initialized, over-parameterized convolutional generator to the single corrupted image. While this over-parameterized network can fit the corrupted image perfectly, surprisingly after a few iterations of gradient descent one obtains the uncorrupted image. This intriguing phenomenon enables state-of-the-art CNN-based denoising and regularization of linear inverse problems such as compressive sensing. In this paper, we take a step towards demystifying this experimental phenomenon by attributing this effect to particular architectural choices of convolutional networks, namely convolutions with fixed interpolating filters. We then formally characterize the dynamics of fitting a two-layer convolutional generator to a noisy signal and prove that early-stopped gradient descent denoises/regularizes. This result relies on showing that convolutional generators fit the structured part of an image significantly faster than the corrupted portion.
This paper studies the situation in which a two-layer CNN with RELU nonlinearity is fit to a single image and the observation that it is able to fit a "natural" image in fewer iterations than a "noisy" image. Theorems on the convergence of this fitting are discussed and proven in the appendices. Intermediate results study the convergence of fitting a linear model to an image plus noise and fitting a single-layer CNN. Denoising is demonstrated on two images with additive white Gaussian noise and the approach under study is shown to provide a better signal-to-noise ratio than BM3D, another untrained denoising approach. The main result is that the use of upsampling via a fixed interpolation filter provides an inductive bias towards "natural" images.
The bibliography does a good job of positioning this paper within the recent set of articles exploring the curious behavior of fitting a CNN to a single image. The problem is interesting, timely, and surprising. The analysis does provide some insight into what is going on.
But, the paper would do well to embrace the Fourier domain and first discuss what is meant by "natural images" and "noise" in terms of their frequency content. In particular, something like Simoncelli and Olshausen (2001) could be used as a description of the spectra of natural images. Additive white Gaussian noise has a flat spectrum, which is never mentioned in the paper. Thus, the theoretical result mainly highlights the fact that natural images have a low-pass spectrum, while white noise has a flat spectrum, and CNNs using interpolation also have a low-pass spectrum in some sense. This makes sense from a frequency perspective, because interpolation increases the sampling rate of a signal without changing its frequency content, i.e., it adds high frequencies with no energy. 
The "trigonometric basis" used in the paper, which consists of sines and cosines at each frequency, could be more cleanly described as a basis of complex exponentials, i.e., the Fourier basis, which doesn't require partitioning the basis into a cosine half and a sine half. The discussion of triangular and Gaussian smoothing functions has been very well explored in the signal processing literature discussing windowing functions and their Fourier transforms, e.g., Harris (1978). I don't think Figure 3 showing some sinusoids is necessary.
The main body of the paper goes into the 10th page, but the appendices make up another 18 pages. The main body of the paper does not include any of the proofs of the provided theorems. This seems rather excessive.
Harris, F. J. (1978). On the use of windows for harmonic analysis with the discrete Fourier transform. Proceedings of the IEEE, 66(1), 51-83.
Simoncelli, E. P., & Olshausen, B. A. (2001). Natural image statistics and neural representation. Annual review of neuroscience, 24(1), 1193-1216.
Minor comments:
Several citations are in the wrong form (\citet instead of \citep) throughout the paper.
There is a link to a figure in the appendix that is broken on page 5
In figure 7, one one set of y-axis labels is shown, but it appears that each subplot uses an independent y-axis, just without labels. Please plot them all on the same y-axis.
Similarly, figures 1, 4, and 6 show similar things on different y-axes when they could be plotted at the same scale on the y-axis to make them more easily comparable visually. 
Typos: "over-paramtrized" and "spacial" both on page 1.
After discussion:
The authors have addressed my concerns, so I am changing my decision from Weak Reject to Weak Accept.