Taihui<EMAIL_ADDRESS>Zhong<EMAIL_ADDRESS>Hengyue
<EMAIL_ADDRESS>Le<EMAIL_ADDRESS>Hengkang<EMAIL_ADDRESS>Ju<EMAIL_ADDRESS>Department of Computer Science and Engineering
University of Minnesota
Minnesota, USA Department of Electrical and Computer Engineering
University of Minnesota
Minnesota, USA Self-Validation: Early Stopping for SIDGPs

# Self-Validation: Early Stopping for Single-Instance Deep Generative Priors

###### Abstract

Recent works have shown the surprising effectiveness of deep generative models
in solving numerous image reconstruction (IR) tasks, _even without training
data_. We call these models, such as deep image prior and deep decoder,
collectively as _single-instance deep generative priors_ (SIDGPs). The
successes, however, often hinge on appropriate early stopping (ES), which by
far has largely been handled in an ad-hoc manner. In this paper, we propose
the first principled method for ES when applying SIDGPs to IR, taking
advantage of the typical bell trend of the reconstruction quality. In
particular, our method is based on collaborative training and _self-
validation_ : the primal reconstruction process is monitored by a deep
autoencoder, which is trained online with the historic reconstructed images
and used to validate the reconstruction quality constantly. Experimentally, on
several IR problems and different SIDGPs, our self-validation method is able
to reliably detect near-peak performance and signal good ES points. Our code
is available at https://sun-umn.github.io/Self-Validation/.

##  1 Introduction

Validation-based ES is one of the most reliable strategies for controlling
generalization errors in supervised learning, especially with potentially
overspecified models such as in gradient boosting and modern DNNs [Zhang et
al.(2005)Zhang, Yu, et al., Prechelt(1998), Goodfellow et al.(2016)Goodfellow,
Bengio, and Courville]. Beyond supervised learning, ES often remains critical
to learning success, but there are no principled ways—universal as validation
for supervised learning—to decide when to stop. In this paper, we make the
first step toward filling in the gap, and focus on solving IR, a central
family of inverse problems, using _training-free deep generative models_.

List of Acronyms (alphabetic order)
---
AE | Autoencoder
CNN | convolutional neural network
DD | deep decoder
DGP | deep generative prior
DIP | deep image prior
DL | deep learning
DNN | deep neural network
ES | early stopping
IR | image reconstruction
MIDGP | multi-instance DGP
OPT | optimization
PG | PSNR gap
SG | SSIM gap
SIDGP | single-instance DGP
SIREN | sinusoidal representation network

IR entails estimating an image of interest, denoted as $x$, from a measurement
$y=f\pqty{x}$, where $f$ models the measurement process. This model covers
classical image processing tasks such as image denoising, superresolution,
inpainting, deblurring, and modern computational imaging problems such as
MRI/CT reconstruction [Epstein(2007)] and phase retrieval [Shechtman et
al.(2015)Shechtman, Eldar, Cohen, Chapman, Miao, and Segev, Tayal et
al.(2020)Tayal, Lai, Kumar, and Sun]. In this paper, _we assume that $f$ is
known_. Classical approaches normally formulate IR as a regularized data
fitting problem (Ref. problem (1)) and solve it via iterative optimization
algorithms [Parikh and Boyd(2014)]. Recently, DL-based methods have been
developed to either directly approximate the inverse mapping $f^{-1}$, or
enhance classical optimization algorithms for solving problem (1) by
integrating pretrained or trainable DNN modules (e.g., plug-and-play or
network unrolling; see the recent survey [Ongie et al.(2020)Ongie, Jalal,
Metzler, Baraniuk, Dimakis, and Willett]). But, they invariably require
extensive and representative training data. In this paper, we focus on an
emerging lightweight approach _that requires no extra training data_ : the
target $x$ is directly modeled via DNNs.

$\displaystyle\min_{x}\;\ell\pqty{y,f\pqty{x}}+\lambda
R\pqty{x}\;\;\ell\text{: fitting loss},\;R\text{:
regularization},\;\lambda\text{: regularization parameter}$ (1)

Figure 1: Illustration of the overfitting issue of DIP and DD on image
denoising with Gaussian noise (noise level: $\sigma=0.18$; pixel values
normalized to $[0,1]$). The reconstruction quality (as measured by both PSNR
and SSIM) typically follows a skewed bell curve: before the peak only the
clean image content is recovered, but after the peak noise starts to kick in.
Note that DD is not free from overfitting when the network is increasingly
over-parametrized (indicated by the number following “DD-” in the legend).

Single-instance deep generative priors Many deep generative models can be used
for modeling image collections [Goodfellow et al.(2016)Goodfellow, Bengio, and
Courville, Part III]. For modeling single images, two families of models stand
out: 1) _structural models_ 111Some authors call this _untrained DNN
models/priors_ ; see [Qayyum et al.(2021)Qayyum, Ilahi, Shamshad, Boussaid,
Bennamoun, and Qadir]. But this may be confused with SIDGPs with prefixed but
frozen $G$ (e.g., random) as in [Bora et al.(2017)Bora, Jalal, Price, and
Dimakis, Hand et al.(2018)Hand, Leong, and Voroninski]. : the image is modeled
as $x\approx G_{\theta}\pqty{z}$. Here, $z$ is a fixed or trainable seed/code,
and $G$ is a trainable DNN—often taken as CNN to bias toward structures in
natural images—parameterized by $\theta$. DIP [Ulyanov et al.(2018)Ulyanov,
Vedaldi, and Lempitsky] and DD [Heckel and Hand(2018)] are two exemplars in
this category, and they only differ in the choice of architecture for $G$. A
variant [Pan et al.(2020)Pan, Zhan, Dai, Lin, Loy, and Luo] allows
initializing $G$ with a pretrained model. These models should be contrasted
with _multi-instance DGPs_ (MIDGPs, of which GAN inversion [Zhu et
al.(2016)Zhu, Krähenbühl, Shechtman, and Efros, Bau et al.(2019)Bau, Zhu,
Wulff, Peebles, Strobelt, Zhou, and Torralba] is a special case), where $G$ is
pretrained and frozen but $z$ is trainable. Although MIDGPs have also been
used to tackle IR problems [Bora et al.(2017)Bora, Jalal, Price, and Dimakis,
Hand et al.(2018)Hand, Leong, and Voroninski], pretraining $G$ requires
massive training sets that can cover the target domains. Thus, MIDGPs are not
suitable for single-image settings222See [Leong and Sakla(2019)] that tries to
bridge the two regimes though. . 2) _functional models_ : the (discrete) image
$x$ is modeled as the collection of uniform-grid samples, i.e.,
discretization, from an underlying _continuous_ function $\overline{x}$
supported on a bounded region in $\mathbb{R}^{2}$ (sometimes higher
dimensions)333In a sense, this is inverting the discretization process in
typical image formation. Also, the idea of modeling continuous functions
directly is popular in DL for solving PDEs [Weinan(2020)]. . Now
$\overline{x}$ is parameterized as a DNN $\overline{x}_{\theta}$, i.e.,
$x=\mathcal{S}\pqty{\overline{x}_{\theta}}$ where $\mathcal{S}$ denotes the
sampling process. Note that if $\overline{x}$ can be learned, in principle one
can obtain arbitrary resolutions for the discrete version $x$—attractive for
computer vision/graphics applications. These models are called implicit neural
representation or coordinate-based multilayer perceptron (MLP) in the
literature, of which sinusoidal representation networks (SIRENs, [Sitzmann et
al.(2020)Sitzmann, Martel, Bergman, Lindell, and Wetzstein]) and MLP with
Fourier features [Tancik et al.(2020)Tancik, Srinivasan, Mildenhall,
Fridovich-Keil, Raghavan, Singhal, Ramamoorthi, Barron, and Ng] are two
representative models.

We categorize all these single-image models into the family of SIDGPs.
Substituting any of the SIDGPs into problem (1) and removing the explicit
regularization term $R$, we can now solve IR problems by DL:

$\displaystyle\textbf{structural
OPT}:\;\min_{\theta}\;\ell\pqty{y,f\pqty{G_{\theta}\pqty{z}}}\quad\text{or}\quad\textbf{functional
OPT}:\;\min_{\theta}\;\ell\pqty{y,f\pqty{\mathcal{S}\pqty{\overline{x}_{\theta}}}}.$
(2)

This simple approach is surprisingly effective in solving numerous IR
problems, ranging from classical image restoration [Ulyanov et
al.(2018)Ulyanov, Vedaldi, and Lempitsky, Heckel and Hand(2018)], to advanced
computational imaging problems [Bora et al.(2017)Bora, Jalal, Price, and
Dimakis, Hand et al.(2018)Hand, Leong, and Voroninski, Gandelsman et
al.(2019)Gandelsman, Shocher, and Irani, Ren et al.(2020)Ren, Zhang, Wang, Hu,
and Zuo, Williams et al.(2019)Williams, Schneider, Silva, Zorin, Bruna, and
Panozzo, Sitzmann et al.(2020)Sitzmann, Martel, Bergman, Lindell, and
Wetzstein, Tancik et al.(2020)Tancik, Srinivasan, Mildenhall, Fridovich-Keil,
Raghavan, Singhal, Ramamoorthi, Barron, and Ng, Darestani and Heckel(2020)],
and even beyond [Ravula and Dimakis(2019), Michelashvili and Wolf(2019)]; see
the recent survey [Qayyum et al.(2021)Qayyum, Ilahi, Shamshad, Boussaid,
Bennamoun, and Qadir].

The overfitting issue There is a caveat to all the claimed successes:
overfitting. In practice, we have $y\approx f\pqty{x}$ instead of
$y=f\pqty{x}$ due to various kinds of measurement noise and model
misspecification, and the DNN used in (2) is also often (substantially)
overparametrized. So when the objective in Eq. 2 is globally optimized, the
final reconstruction $G_{\theta}\pqty{z}$ or
$\mathcal{S}\pqty{\overline{x}_{\theta}}$ may account for the noise and model
errors, alongside the desired image content. This overfitting phenomenon has
indeed been observed empirically on all SIDGPs when noise is present. Fig. 1
shows the typical reconstruction quality of DIP and DD for image denoising
(Gaussian noise) over iterations. Note the iconic skewed bell curves here: the
reconstruction quality initially monotonically climbs to a peak level—noise
effect is almost invisible during this period, and then monotonically degrades
where the noise effect gradually kicks in until everything is fit by the
overparametrized models. Also, when the level of overparametrization grows,
overfitting becomes more serious (Fig. 1 (b) for DD). The overfitting
phenomenon has also been partly justified theoretically: despite the typical
nonconvexity of the objectives in Eq. 2, global optimization is feasible and
happens with high probability [Jagatap and Hegde(2019), Heckel and
Soltanolkotabi(2019)]. But it is a curse here.

Prior work on mitigating overfitting Several lines of methods have been
developed to remove the overfitting. DD [Heckel and Hand(2018)] proposes to
control the network size for structural models, and shows that overfitting is
largely suppressed when the network is suitably parameterized. However,
choosing the right level of parameterization for an unknown image with unknown
complexity is no easy task, and underparameterization can apparently hurt the
performance, as acknowledged by [Heckel and Hand(2018)]. So in practice people
still tend to use overparametrization and counter overfitting with ES [Heckel
and Soltanolkotabi(2020)]; see Fig. 1 (b). The second line adds
regularization. [Sun(2020), Sun et al.(2021)Sun, Latorre, Sanchez, and Cevher]
plug in total-variation or other denoising regularizers, and [Cheng et
al.(2019)Cheng, Gadelha, Maji, and Sheldon] appends weight-decay and runs SGD
with Langevin dynamics (i.e., with additional noise) [Welling and Teh(2011)].
But their evaluations are limited to denoising with low Gaussian noise; our
experiments in Fig. 3 show that overfitting still exists when the noise level
is higher. The third line explicitly models the noise in the objective, so
that hopefully both the image $x$ and the noise are exactly recovered when the
objective is globally optimized. [You et al.(2020)You, Zhu, Qu, and Ma]
implements such an idea for additive sparse corruption. The overfitting is
gone, but it is unclear how to generalize the algorithm, which is delicately
designed for sparse corruption only, to other types of noise.

Our contribution In this paper, we take a different route, and capitalize on
overfitting instead of suppressing or even killing it. Specifically, we leave
the problem formulation (2) as is, and propose a reliable method for detecting
near-peak performance, which is _first of its kind_ and also 1) effective:
empirically, our method detects near-peak performance measured in both PSNR
and SSIM; 2) fast: our method performs ES once a near-peak performance is
detected—which is often early in the optimization process (see Fig. 1),
whereas the above mitigating strategies push the peak performance to the final
iterations; 3) versatile: the only assumption that our method relies on is the
performance curve (either PSNR or SSIM) is (skewed) bell-shaped. This seems to
hold for the various structural and functional models, tasks, noise types that
we experiment with; see Section 3.

After the initial submission, we became aware of two new works [Shi et
al.(2021)Shi, Mettes, Maji, and Snoek, Jo et al.(2021)Jo, Chun, and Choi] that
also perform ES. [Shi et al.(2021)Shi, Mettes, Maji, and Snoek] proposes an ES
criterion based on a blurriness-to-sharpness ratio for natural images, but it
only works for the modified DIP and DD they propose, not the original and
other SIDGPs. [Jo et al.(2021)Jo, Chun, and Choi] focuses on Gaussian noise,
and designs an elegant Gaussian-specific regularized objective to monitor
progress and decide ES. Compared to our approach, both methods are limited in
versatility. We defer a detailed comparison with them to future work.

##  2 Early stopping via self-validation

Figure 2: (left) The MSE curves of learning a natural image vs learning random
noise by DIP. DIP fits the natural image much faster than noise. This induces
the typical bell-shaped reconstruction quality curves (as shown in Fig. 1 and
(right) here) when fitting noisy images using DIP; (right) The PSNR curve vs
our online AE reconstruction error curve when fitting a noisy image with DIP.
The peak of the PSNR curve is well aligned with the valley of the AE error
curve. So by detecting the valley of the latter curve, we are able to detect
near-peak points of the former—corresponding to reconstructed images of near-
peak quality.

In this section, we describe our detection method taking structural SIDGPs as
an example; this can be easily adapted for functional SIDGPs.

Bell curves: the why and the bad When $y=f\pqty{x}$, solving the structural
OPT in (2) with an overparameterized CNN $G_{\theta}$ using gradient descent
has disparate behaviors on natural images vs pure noise: the term
$G_{\theta}\pqty{z}$ fits natural images much more rapidly than fitting pure
noise. This is illustrated in Fig. 2 (left) and has been highlighted in
numerous places [Heckel and Hand(2018), Heckel and Soltanolkotabi(2019)]; it
can be explained by the strong bias of convolutional operations toward natural
image structures, which are low-frequency dominant, during the early learning
stage [Heckel and Hand(2018), Heckel and Soltanolkotabi(2019)]. When $y\approx
f\pqty{x}$, e.g., the measurement is noisy, intuitively $G_{\theta}\pqty{z}$
would quickly fit the image content with little noise initially, and then
gradually fit more noise until reaching the full capacity. This induces the
skewed bell curves as shown in Fig. 1 and Fig. 2 (right). Of course, this
argument is handwavy and the fitting effect might not be decomposable into
that of image content and noise separately for complicated $f$’s and noise
types (it has been rigorously established for simple cases, e.g., [Heckel and
Soltanolkotabi(2019)]). Nonetheless, the bell-shaped performance curves are
also observed for nonlinear $f$’s with complex noise types, e.g., [Bostan et
al.(2020)Bostan, Heckel, Chen, Kellman, and Waller, Lawrence et
al.(2020)Lawrence, Bramherzig, Li, Eickenberg, and Gabrié], as well as
functional models as we show in Fig. 6. The downside is overfitting, if no
suitable ES is performed. Recent methods that mitigate the overfitting issue
defer the performance peak until the final convergence and work only in
limited scenarios.

Bell curves: the good Here we do not try to alter the bell curves but turn
them into our favor, as explained below. In practice, we do not directly
observe these curves, as they depend on the groundtruth $x$. Let
$\left\\{\theta_{k}\right\\}$ denote the iterate sequence and
$\left\\{x_{k}\right\\}$ the corresponding reconstruction sequence, i.e.,
$x_{k}=G_{\theta_{k}}\pqty{z}$. We only observe $\left\\{x_{k}\right\\}$ and
$\left\\{\theta_{k}\right\\}$ directly, and we know that there exists a
$k^{*}\in\mathbb{N}$ so that the subsequence $\left\\{x_{k}\right\\}_{k\leq
k^{*}}$ has increasingly better quality and contains very little noise.

Our first technical idea is constructing a quality oracle by training an AE

$\displaystyle\min_{w,v}\;\sum_{i=1}^{n}\ell_{\mathrm{AE}}\pqty{s_{i},d_{v}\circ
e_{w}\pqty{s_{i}}}\quad e_{w}\text{: encoder DNN}\quad d_{v}\text{: decoder
DNN},$ (3)

where $\left\\{s_{i}\right\\}_{i\leq n}$ is a given training set. AEs are now
a seminal tool for manifold learning and nonlinear dimension reduction
[Goodfellow et al.(2016)Goodfellow, Bengio, and Courville, Chap. 14]. When
$\left\\{s_{i}\right\\}_{i\leq n}$ is sampled from a low-dimensional manifold,
after training we expect that $s\approx d_{v}\circ e_{w}\pqty{s}$ for any $s$
from the same manifold and $s\not\approx d_{v}\circ e_{w}\pqty{s}$ otherwise.
This implies that we can use the AE reconstruction loss
$\ell_{\mathrm{AE}}\pqty{s,d_{v}\circ e_{w}\pqty{s}}$ as a proxy to tell if a
novel data point $s$ comes from the training manifold. Thus, if the training
set $\left\\{s_{i}\right\\}_{i\leq n}$ consists of images very close to $x$,
we can use $\ell_{\mathrm{AE}}\pqty{s,d_{v}\circ e_{w}\pqty{s}}$ to score the
reconstruction quality of any $s$: higher the loss, lower the quality, and
vice versa. If we apply this ideal AE to $\left\\{x_{k}\right\\}$, the AE loss
curve will have an inverted bell shape, where the valley corresponds to the
quality peak. So we can detect the peak of the quality curve by detecting the
valley of the AE loss curve.

But it is unclear how to ensure that $\left\\{s_{i}\right\\}_{i\leq n}$ be
uniformly close to $x$. Our second technical idea is exploiting the
monotonicity of reconstruction quality in $\left\\{x_{k}\right\\}_{k\leq
k^{*}}$ and $\left\\{x_{k}\right\\}_{k\geq k^{*}}$ to train a sequence of AEs.
We take a consecutive length-$n$ subsequence of $\left\\{x_{k}\right\\}_{k\leq
k^{*}}$ to train an AE each time, and test the next reconstructed image
against the resulting AE. Although the quality of any initial training set can
be low, resulting in poor AEs, it improves over time and culminates when
getting near the $x_{k^{*}}$. Similarly, afterward, the quality gradually
degrades. Away from the peak $x_{k^{*}}$, the quality of $x_{k}$’s changes
rapidly over iterations, and so we expect high AE loss, regardless of the
quality of the AE training set. In contrast, around $x_{k^{*}}$ all $x_{k}$’s
are of high quality, leading to near-ideal AEs and low AE losses. Thus, even
after the practical modification, we expect an inverted bell shape in the AE
loss curve, and alignment of the quality peak with the loss valley again, as
confirmed in Fig. 2 (right).

Algorithm 1 Structural OPT with ES for IR

0: $y,f,\ell,\ell_{\mathrm{AE}}$, $G$, $\theta^{(0)}$ (of Eq. 2), $w^{(0)}$,
$v^{(0)}$ (of Eq. 3), $k=0$, window size $n$, patience number $p$

1: while not stopped do

2: update $\theta$ via one iterative step on Eq. 2 to obtain $\theta^{(k+1)}$
and $x^{(k+1)}$

3: update $w,v$ via one iterative step on Eq. 3 using
$\left\\{x_{i}\right\\}_{i=k-n+1}^{k}$ to obtain $w^{(k+1)},v^{(k+1)}$

4: calculate the reconstruction loss
$\ell_{\mathrm{AE}}(x^{(k+1)},d_{v^{(k+1)}}\circ e_{w^{(k+1)}}(x^{(k+1)}))$

5: if no improvement in the reconstruction loss in $p$ consecutive iterations
then

6: early stop and exit

7: end if

8: $k=k+1$

9: end while

9: the reconstructed image $x^{(k-p+1)}$

Our method: ES by self-validation We now only need to detect the valley of the
AE loss curve due to the blessed alignment discussed above. To sum up our
algorithm: we train the structural OPT and an AE side-by-side, feed the most
recent $n$ reconstructed images to train the AE, and then test the next image
for AE loss. We make two additional modifications for better efficiency: 1)
the AE is updated only once per new training set instead of being greedily
trained, i.e., an online learning setting. This helps to substantially cut
down the learning cost and save hyperparameters while remaining effective; and
2) to ensure the AEs learn the most compact representations, we borrow the
idea of IRMAE [Jing et al.(2020)Jing, Zbontar, et al.] and add several
trainable linear layers in the AEs before feeding the hidden code to the
decoder. Our whole algorithmic pipeline is summarized in Algorithm 1.

##  3 Experiments

Setup We experiment with $3$ SIDGPs (DIP
444https://github.com/DmitryUlyanov/deep-image-prior,
DD555https://github.com/reinhardh/supplement_deep_decoder,
SIREN666https://vsitzmann.github.io/siren/) and $4$ IR problems (image
denoising, inpainting, MRI reconstruction, and image regression). Unless
stated otherwise, we work with their default DNN architectures, optimizers,
and hyperparameters. We fix the window size $n=256$, and the patience number
$p=500$ for denoising and inpainting and $p=200$ for MRI reconstruction and
image regression. For training the collaborative AEs, ADAM is used with a
learning rate $10^{-3}$. To assess the IR quality, we use both PSNR [Chan et
al.(2005)Chan, Ho, and Nikolova] and SSIM [Wang et al.(2004)Wang, Bovik,
Sheikh, and Simoncelli]. To evaluate our detection performance, we use ES-PG
which is the absolute difference between the detected and the true peak PSNRs;
similarly for ES-SG. Sometimes we also report BASELINE-PG which measures the
difference between the peak and the final overfitting PSNRs; similarly for
BASELINE-SG. For most small-scale experiments, we repeat all experiments $3$
times and report means and standard deviations. All omitted details and
experimental results can be found in the Appendix.

Figure 3: DIP+AE for image denoising. Each columns represents a distinct noise
type, and the 1st row contains the PGs, and 2nd in SGs. The _L_ and _H_ in the
horizontal annotations indicate low and high noise levels, respectively.

Image denoising The power of DIP and DD was initially only demonstrated on
Gaussian denoising. Here, to make the evaluation more thorough, we also
experiment with denoising impulse, shot, and speckle noise, on a standard
image denoising dataset777http://www.cs.tut.fi/f̃oi/GCF-
BM3D/index.html#ref_results ($9$ images). For each of the $4$ noise types, we
test a low and a high noise level, respectively. The mean squares error (MSE)
is used for Gaussian, shot, and speckle noise, while the $\ell_{1}$ loss is
used for impulse noise. To obtain the final degraded results, we run DIP for
$150$K iterations.

The denoising results are measured in terms of the gap metrics are summarized
in Fig. 3. Note that our typical detection gap is $\leq 1$ measured in ES-PG,
and $\leq 0.1$ measured in ES-SG. If DIP just runs without ES, the degradation
of quality is severe, as indicated by both BASELINE-PG and BASELINE-SG.
Evidently, our DIP+AE can save the computation and the reconstruction quality,
and return an estimate with near-peak performance for almost all images, noise
types, and noise levels that we test. The Baboon image is an outlier. It
contains substantial high-frequency textures, and actually the peak PSNR/SSIM
itself is also much worse compared to other images. We suspect that dealing
with similar kinds of images can be challenging for DIP and DD and our
detection method, which warrants future study.

Figure 4: DIP+AE on IN-100. 1st row: ES-PGs; 2nd row: ES-SGs.

We further test our method on $100$ randomly selected images from ImageNet
[Russakovsky et al.(2015)Russakovsky, Deng, Su, Krause, Satheesh, Ma, Huang,
Karpathy, Khosla, Bernstein, Berg, and Fei-Fei], denoted as IN-100. We follow
the same evaluation protocol as above, except that we only experiment a medium
noise level and we do not estimate the means and standard deviations; the
results are reported in Fig. 4. It is easy to see that the ES-PGs are
concentrated around $1$ and the ES-GSs are concentrated around $0.1$,
consistent with our observation on the small-scale dataset above.

Table 1: DIP+AE, DIP+TV, and SGLD on Gaussian denoising. The best PSNRs are colored as red; the best SSIMs are colored as blue. | PSNR $\uparrow$ | SSIM $\uparrow$
---|---|---
DIP+AE | DIP+TV | SGLD | DIP+AE | DIP+TV | SGLD
House |  |  30.824(0.236)
---
| 18.866(0.093)
---
| 21.800(2.430)
---
|  0.834 (0.008)
---
| 0.174 (0.006)
---
| 0.495 (0.152)
---
Peppers |  |  26.471 (0.249)
---
| 19.000 (0.004)
---
| 20.516 (0.263)
---
|  0.688 (0.008)
---
| 0.238 (0.001)
---
| 0.453 (0.017)
---
Lena |  |  27.462 (0.602)
---
| 18.961 (0.028)
---
| 20.217 (0.808)
---
|  0.744 (0.003)
---
| 0.253 (0.001)
---
| 0.447 (0.051)
---
Baboon |  |  19.453 (0.251)
---
| 18.416 (0.024)
---
| 19.111 (0.091)
---
|  0.335 (0.008)
---
| 0.467 (0.0)
---
| 0.572 (0.003)
---
F16 |  |  27.644 (0.114)
---
| 19.183 (0.122)
---
| 20.431 (0.091)
---
|  0.818 (0.005)
---
| 0.248 (0.005)
---
| 0.457 (0.008)
---
Kodak1 |  |  24.455 (0.111)
---
| 18.688 (0.088)
---
| 19.555 (0.049)
---
|  0.649 (0.006)
---
| 0.409 (0.006)
---
| 0.528 (0.003)
---
Kodak2 |  |  26.886 (0.218)
---
| 19.535 (0.160)
---
| 20.569 (0.629)
---
|  0.677 (0.006)
---
| 0.243 (0.014)
---
| 0.430 (0.046)
---
Kodak3 |  |  27.894 (0.311)
---
| 18.904 (0.181)
---
| 19.921 (0.194)
---
|  0.761 (0.002)
---
| 0.187 (0.008)
---
| 0.379 (0.012)
---
Kodak12 |  |  28.269 (0.239)
---
| 18.998 (0.183)
---
| 19.974 (0.240)
---
|  0.727 (0.003)
---
| 0.193 (0.011)
---
| 0.391 (0.015)
---

We compare DIP+AE with three other competing methods that try to eliminate
overfitting, i.e., DIP+TV [Sun(2020), Sun et al.(2021)Sun, Latorre, Sanchez,
and Cevher] and SGLD [Welling and Teh(2011)] on Gaussian denoising, and DOP
[You et al.(2020)You, Zhu, Qu, and Ma] on removing sparse corruptions. We take
a medium noise level. All these methods claim to eliminate the overfitting
altogether, and so we directly compare the detected PSNRs (SSIMs) by our
method and the final PSNRs returned by their methods at the final convergence.
The results are tabulated in Table 1 and Table 2, respectively. It seems that
1) DIP+TV and SGLD do not quite eliminate overfitting when different images
and noise levels (noise levels used in the respective papers are relatively
low) than they experimented with are used; and 2) our detection method, i.e.,
DIP+AE, returns far better reconstruction than DIP+TV and SGLD (except on
Baboon), and comparable results to DOP on sparse corruptions (in our
experiments, we do not add any perturbations to the input random noise of
DOP).

Table 2: DOP vs. DIP+AE on removing sparse corruptions Metrics | Models | House | Peppers | Lena | Baboon | F16 | Kodak1 | Kodak2 | Kodak3 | Kodak12
---|---|---|---|---|---|---|---|---|---|---
PSNR $\uparrow$ | DOP | 35.148 | 28.635 | 30.592 | 21.051 | 28.918 | 25.006 | 29.516 | 30.098 | 29.694
DIP+AE | 38.343 | 27.724 | 30.768 | 19.476 | 28.253 | 24.954 | 29.812 | 30.220 | 30.883
SSIM $\uparrow$ | DOP | 0.914 | 0.753 | 0.831 | 0.578 | 0.869 | 0.690 | 0.766 | 0.843 | 0.803
DIP+AE | 0.954 | 0.783 | 0.845 | 0.377 | 0.892 | 0.723 | 0.785 | 0.861 | 0.844
Iteration $\downarrow$ | DOP | 149740 | 149469 | 141000 | 37000 | 149370 | 147096 | 145595 | 148666 | 141390
DIP+AE | 3425 | 1405 | 1638 | 360 | 1524 | 1322 | 1038 | 1112 | 1522
Figure 5: Results for MRI reconstruction. (left) The solid vertical lines
indicate the peak performance iterate while the dash vertical lines are ES
iterate detected by our method. (right) Visualizations for Sample 6 (1st row)
and Sample 9 (2nd row).

We further compare our method with a group of baseline methods based on no-
reference image quality metrics: the classical BRISQUE [Mittal et
al.(2012a)Mittal, Moorthy, and Bovik] and NIQE [Mittal et al.(2012b)Mittal,
Soundararajan, and Bovik], and a state-of-the-art, NIMA (both technical
quality and aesthetic assessment) [Talebi and Milanfar(2018)] which is based
on pretrained DNNs. We experiment with medium noise level across all four
noise types with DIP, run DIP until the final convergence (i.e., overfitting),
and then select the highest quality one from among all the intermediate
reconstructions according to each of the three metrics, respectively.
Performance gaps on medium Gaussian and impluse noise are presented in Table
3, on shot noise and speckle noise presented in Table 9 in the Appendix. Told
from Table 3 and Table 9, our method is a clear winner: in most cases, our
method has the smallest gaps. Moreover, while our detection gaps are uniformly
small (with rare outliers), the three baseline methods can frequently lead to
intolerably large gaps.

Table 3: The performance gaps of BRISQUE [Mittal et al.(2012a)Mittal, Moorthy, and Bovik], NIQE [Mittal et al.(2012b)Mittal, Soundararajan, and Bovik], NIMA [Talebi and Milanfar(2018)], and DIP+AE on Gaussian and impulse noises. For NIMA, we report both technical quality assessment (the number before “/”) and aesthetic assessment (the number after “/”). The best PSNR gaps are colored as red; the best SSIM gaps are colored as blue. | Gaussian noise | Impulse noise
---|---|---
| Gap in PSNR $\downarrow$ | Gap in SSIM $\downarrow$ | Gap in PSNR $\downarrow$ | Gap in SSIM $\downarrow$
| BRISQUE | NIQE | NIMA | DIP+AE | BRISQUE | NIQE | NIMA | DIP+AE | BRISQUE | NIQE | NIMA | DIP+AE | BRISQUE | NIQE | NIMA | DIP+AE
House | 10.961 | 10.961 | 12.906/3.361 | 1.057 | 0.408 | 0.408 | 0.659/0.122 | 0.015 | 25.227 | 9.886 | 25.227/21.403 | 5.832 | 0.835 | 0.052 | 0.835/0.344 | 0.005
Peppers | 3.715 | 5.053 | 4.893/5.204 | 0.603 | 0.271 | 0.341 | 0.334/0.345 | 0.006 | 12.872 | 2.296 | 2.117/9.701 | 0.305 | 0.404 | 0.013 | 0.012/0.198 | 0.012
Lena | 4.681 | 7.194 | 10.180/1.581 | 0.845 | 0.260 | 0.397 | 0.537/0.054 | 0.008 | 2.374 | 6.204 | 15.646/12.674 | 0.231 | 0.011 | 0.039 | 0.376/0.209 | 0.002
Baboon | 0.247 | 0.694 | 1.375/3.450 | 2.583 | 0.008 | 0.014 | 0.174/0.416 | 0.304 | 7.092 | 1.312 | 1.157/12.707 | 1.426 | 0.224 | 0.013 | 0.153/0.462 | 0.231
F16 | 6.236 | 8.128 | 1.336/3.991 | 0.850 | 0.429 | 0.530 | 0.036/0.088 | 0.023 | 14.180 | 5.505 | 8.621/9.372 | 0.495 | 0.369 | 0.036 | 0.111/0.135 | 0.006
Kodak1 | 2.558 | 3.158 | 6.723/19.546 | 0.520 | 0.069 | 0.103 | 0.275/0.626 | 0.029 | 5.913 | 0.232 | 11.791/10.366 | 0.538 | 0.142 | 0.007 | 0.410/0.584 | 0.048
Kodak2 | 6.959 | 6.855 | 9.094/0.143 | 0.353 | 0.361 | 0.365 | 0.516/0.004 | 0.007 | 18.575 | 0.312 | 13.870/9.657 | 0.429 | 0.741 | 0.014 | 0.304/0.127 | 0.026
Kodak3 | 2.029 | 7.686 | 19.834/19.716 | 0.574 | 0.152 | 0.475 | 0.731/0.624 | 0.005 | 16.867 | 8.769 | 13.217/2.031 | 1.959 | 0.351 | 0.077 | 0.180/0.005 | 0.046
Kodak12 | 7.066 | 8.093 | 6.436/3.075 | 0.788 | 0.419 | 0.456 | 0.384/0.178 | 0.007 | 16.781 | 1.785 | 9.139/2.685 | 1.068 | 0.817 | 0.003 | 0.087/0.008 | 0.048

MRI reconstruction We now test our detection method on MRI reconstruction, a
classical medical IR problem involving a nontrivial linear $f$. Specifically,
the model is $y=f(x)+\xi=\mathcal{F}\pqty{x}+\xi$, where $\mathcal{F}$ is the
subsampled Fourier operator and $\xi$ models the noise encountered in
practical MRI imaging. Here, we take $8$-fold undersampling and choose to
parametrize $x$ using a DD, inspired by the recent work [Heckel and
Soltanolkotabi(2020)]. Due to the heavy overparametrization of DD, [Heckel and
Soltanolkotabi(2020)] needs to choose an appropriate ES to produce quality
reconstruction. We report the performance in Fig. 5 (results for all randomly
selected samples can be found in the Appendix). Our method is able to signal
stopping points that are reasonably close to the peak points, which also yield
reasonably faithful reconstruction.

Figure 6: Results for image regression.

Image regression Now we turn to SIREN [Sitzmann et al.(2020)Sitzmann, Martel,
Bergman, Lindell, and Wetzstein], a recent functional SIDGP model that is
designed to facilitate the learning of functions with significant high-
frequency components. We consider a simple task from the original task, image
regression, but add in some Gaussian noise. Mathematically, the
$y=x+\varepsilon$, where $\varepsilon\sim_{iid}\mathcal{N}\pqty{0,0.196}$, and
we are to fit $y$ by performing functional OPT listed in Eq. 2. Clearly, when
the MLP used in SIREN is sufficiently overparamterized, the noise will also be
learned. We test our detection method on this using the same $9$-image dataset
as in denoising. From Fig. 6, we can see again that our method is capable of
reliably detecting near-peak performance measured by either ES-PG or ES-SG,
much better than without implementing any ES.

Ablation studies

Figure 7: Ablation study for the sensitivity of the detection performance with
respect to the patience number $p$ and window size $n$.

There are two crucial parameters—the window size $n$ and the patience number
$p$—dictating the performance of our detection method. Here, we evaluate the
sensitivity of the performance to $n$ and $p$ on two settings: 1) fix $n=256$,
and vary $p$ in $\\{100,300,500,700,900\\}$; 2) fix $p=500$, and vary $n$ in
$\\{32,64,128,256,512\\}$. We again use the $9$-image dataset, simulate
medium-level Gaussian noise, and adopt DIP. For simplicity, we only report the
gaps averaged over all images. Fig. 7 summarizes the results. Two
observations: 1) our detection method is relatively insensitive to the two
parameters; 2) large $p$ and $n$ seem to benefit the performance more. To be
sure, we need $p$ to be at least reasonably large so that our detection will
not be trapped by local spikes. However, larger $n$ requires better GPU
resources to hold and compute with the data. In addition, we also explore the
influence of the learing rates—for SIDGP and AE, respectively—on the
performance. For this, we again consider medium Gaussian noise with DIP, and
freeze $n=256$ and $p=500$. We fix one of the two learning rates while
changing the other, and present the results in Table 4. We observe that
despite different learning rates lead to slightly different levels of
performance, the variation is not significant, in view that our typical ES-PG
is less than $1$, and typical ES-SG less than $0.1$ in our previous
evaluation.

Table 4: The impacts of different learning rates.  Learning Rate | (vary) DIP + (fixed $.001$) AE | (fixed $.01$) DIP + (vary) AE
---|---|---
ES-PG $\downarrow$ | ES-SG $\downarrow$ | ES-PG $\downarrow$ | ES-SG $\downarrow$
0.01 | 0.756 (0.629) | 0.044 (0.093) | 0.814 (0.623) | 0.043 (0.090)
0.001 | 0.593 (0.497) | 0.043 (0.085) | 0.713 (0.628) | 0.045 (0.098)
0.0001 | 1.073 (0.984) | 0.074 (0.118) | 1.216 (1.036) | 0.071 (0.098)

## Acknowledgement

Zhong Zhuang, Hengkang Wang, and Ju Sun are partly supported by NSF CMMI
2038403. The authors acknowledge the Minnesota Supercomputing Institute (MSI)
at the University of Minnesota for providing resources that contributed to the
research results reported within this paper.

## References

  * [Almansa et al.(2007)Almansa, Ballester, Caselles, and Haro] A. Almansa, C. Ballester, V. Caselles, and G. Haro.  A TV based restoration model with local constraints.  _Journal of Scientific Computing_ , 34(3):209–236, oct 2007.  10.1007/s10915-007-9160-x.
  * [Bau et al.(2019)Bau, Zhu, Wulff, Peebles, Strobelt, Zhou, and Torralba] David Bau, Jun-Yan Zhu, Jonas Wulff, William Peebles, Hendrik Strobelt, Bolei Zhou, and Antonio Torralba.  Seeing what a gan cannot generate.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 4502–4511, 2019.
  * [Bora et al.(2017)Bora, Jalal, Price, and Dimakis] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis.  Compressed sensing using generative models.  In _International Conference on Machine Learning_ , pages 537–546. PMLR, 2017.
  * [Bostan et al.(2020)Bostan, Heckel, Chen, Kellman, and Waller] Emrah Bostan, Reinhard Heckel, Michael Chen, Michael Kellman, and Laura Waller.  Deep phase decoder: self-calibrating phase microscopy with an untrained deep neural network.  _Optica_ , 7(6):559–562, 2020.
  * [Chan et al.(2005)Chan, Ho, and Nikolova] Raymond H Chan, Chung-Wa Ho, and Mila Nikolova.  Salt-and-pepper noise removal by median-type noise detectors and detail-preserving regularization.  _IEEE Transactions on image processing_ , 14(10):1479–1485, 2005.
  * [Cheng et al.(2019)Cheng, Gadelha, Maji, and Sheldon] Zezhou Cheng, Matheus Gadelha, Subhransu Maji, and Daniel Sheldon.  A bayesian perspective on the deep image prior.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5443–5451, 2019.
  * [Darestani and Heckel(2020)] MZ Darestani and R Heckel.  Accelerated mri with un-trained neural networks.  _arXiv preprint arXiv:2007.02471_ , 2020.
  * [Epstein(2007)] Charles L Epstein.  _Introduction to the mathematics of medical imaging_.  SIAM, 2007.
  * [Gandelsman et al.(2019)Gandelsman, Shocher, and Irani] Yosef Gandelsman, Assaf Shocher, and Michal Irani.  " double-dip": Unsupervised image decomposition via coupled deep-image-priors.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11026–11035, 2019.
  * [Goodfellow et al.(2016)Goodfellow, Bengio, and Courville] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * [Hand et al.(2018)Hand, Leong, and Voroninski] Paul Hand, Oscar Leong, and Vladislav Voroninski.  Phase retrieval under a generative prior.  _arXiv preprint arXiv:1807.04261_ , 2018.
  * [Heckel and Hand(2018)] Reinhard Heckel and Paul Hand.  Deep decoder: Concise image representations from untrained non-convolutional networks.  In _International Conference on Learning Representations_ , 2018.
  * [Heckel and Soltanolkotabi(2019)] Reinhard Heckel and Mahdi Soltanolkotabi.  Denoising and regularization via exploiting the structural bias of convolutional generators.  _arXiv preprint arXiv:1910.14634_ , 2019.
  * [Heckel and Soltanolkotabi(2020)] Reinhard Heckel and Mahdi Soltanolkotabi.  Compressive sensing with un-trained neural networks: Gradient descent finds a smooth approximation.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 4149–4158. PMLR, 13–18 Jul 2020.  URL http://proceedings.mlr.press/v119/heckel20a.html.
  * [Hendrycks and Dietterich(2018)] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  In _International Conference on Learning Representations_ , 2018.
  * [Jagatap and Hegde(2019)] Gauri Jagatap and Chinmay Hegde.  Algorithmic guarantees for inverse imaging with untrained network priors.  _arXiv preprint arXiv:1906.08763_ , 2019.
  * [Jing et al.(2020)Jing, Zbontar, et al.] Li Jing, Jure Zbontar, et al.  Implicit rank-minimizing autoencoder.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * [Jo et al.(2021)Jo, Chun, and Choi] Yeonsik Jo, Se Young Chun, and Jonghyun Choi.  Rethinking deep image prior for denoising.  _arXiv:2108.12841_ , August 2021.
  * [Lanza et al.(2018)Lanza, Morigi, Sciacchitano, and Sgallari] Alessandro Lanza, Serena Morigi, Federica Sciacchitano, and Fiorella Sgallari.  Whiteness constraints in a unified variational framework for image restoration.  _Journal of Mathematical Imaging and Vision_ , 60(9):1503–1526, sep 2018.  10.1007/s10851-018-0845-6.
  * [Lawrence et al.(2020)Lawrence, Bramherzig, Li, Eickenberg, and Gabrié] Hannah Lawrence, David Bramherzig, Henry Li, Michael Eickenberg, and Marylou Gabrié.  Phase retrieval with holography and untrained priors: Tackling the challenges of low-photon nanoscale imaging.  _arXiv preprint arXiv:2012.07386_ , 2020.
  * [Leong and Sakla(2019)] Oscar Leong and Wesam Sakla.  Low shot learning with untrained neural networks for imaging inverse problems.  _arXiv preprint arXiv:1910.10797_ , 2019.
  * [Michelashvili and Wolf(2019)] Michael Michelashvili and Lior Wolf.  Audio denoising with deep network priors.  _arXiv preprint arXiv:1904.07612_ , 2019.
  * [Mittal et al.(2012a)Mittal, Moorthy, and Bovik] Anish Mittal, Anush Krishna Moorthy, and Alan Conrad Bovik.  No-reference image quality assessment in the spatial domain.  _IEEE Transactions on image processing_ , 21(12):4695–4708, 2012a.
  * [Mittal et al.(2012b)Mittal, Soundararajan, and Bovik] Anish Mittal, Rajiv Soundararajan, and Alan C Bovik.  Making a “completely blind” image quality analyzer.  _IEEE Signal processing letters_ , 20(3):209–212, 2012b.
  * [Ongie et al.(2020)Ongie, Jalal, Metzler, Baraniuk, Dimakis, and Willett] Gregory Ongie, Ajil Jalal, Christopher A Metzler, Richard G Baraniuk, Alexandros G Dimakis, and Rebecca Willett.  Deep learning techniques for inverse problems in imaging.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):39–56, 2020.
  * [Pan et al.(2020)Pan, Zhan, Dai, Lin, Loy, and Luo] Xingang Pan, Xiaohang Zhan, Bo Dai, Dahua Lin, Chen Change Loy, and Ping Luo.  Exploiting deep generative prior for versatile image restoration and manipulation.  In _European Conference on Computer Vision_ , pages 262–277. Springer, 2020.
  * [Parikh and Boyd(2014)] Neal Parikh and Stephen Boyd.  Proximal algorithms.  _Foundations and Trends in optimization_ , 1(3):127–239, 2014.
  * [Prechelt(1998)] Lutz Prechelt.  Early stopping-but when?  In _Neural Networks: Tricks of the trade_ , pages 55–69. Springer, 1998.
  * [Qayyum et al.(2021)Qayyum, Ilahi, Shamshad, Boussaid, Bennamoun, and Qadir] Adnan Qayyum, Inaam Ilahi, Fahad Shamshad, Farid Boussaid, Mohammed Bennamoun, and Junaid Qadir.  Untrained neural network priors for inverse imaging problems: A survey.  2021\.
  * [Ravula and Dimakis(2019)] Sriram Ravula and Alexandros G Dimakis.  One-dimensional deep image prior for time series inverse problems.  _arXiv preprint arXiv:1904.08594_ , 2019.
  * [Ren et al.(2020)Ren, Zhang, Wang, Hu, and Zuo] Dongwei Ren, Kai Zhang, Qilong Wang, Qinghua Hu, and Wangmeng Zuo.  Neural blind deconvolution using deep priors.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3341–3350, 2020.
  * [Russakovsky et al.(2015)Russakovsky, Deng, Su, Krause, Satheesh, Ma, Huang, Karpathy, Khosla, Bernstein, Berg, and Fei-Fei] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3):211–252, 2015.  10.1007/s11263-015-0816-y.
  * [Shechtman et al.(2015)Shechtman, Eldar, Cohen, Chapman, Miao, and Segev] Yoav Shechtman, Yonina C Eldar, Oren Cohen, Henry Nicholas Chapman, Jianwei Miao, and Mordechai Segev.  Phase retrieval with application to optical imaging: a contemporary overview.  _IEEE signal processing magazine_ , 32(3):87–109, 2015.
  * [Shi et al.(2021)Shi, Mettes, Maji, and Snoek] Zenglin Shi, Pascal Mettes, Subhransu Maji, and Cees G. M. Snoek.  On measuring and controlling the spectral bias of the deep image prior.  _arXiv:2107.01125_ , July 2021.
  * [Sitzmann et al.(2020)Sitzmann, Martel, Bergman, Lindell, and Wetzstein] Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein.  Implicit neural representations with periodic activation functions.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * [Sun(2020)] Zhaodong Sun.  Solving inverse problems with hybrid deep image priors: the challenge of preventing overfitting.  _arXiv preprint arXiv:2011.01748_ , 2020.
  * [Sun et al.(2021)Sun, Latorre, Sanchez, and Cevher] Zhaodong Sun, Fabian Latorre, Thomas Sanchez, and Volkan Cevher.  A plug-and-play deep image prior.  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 8103–8107. IEEE, 2021.
  * [Talebi and Milanfar(2018)] Hossein Talebi and Peyman Milanfar.  Nima: Neural image assessment.  _IEEE Transactions on Image Processing_ , 27(8):3998–4011, 2018.
  * [Tancik et al.(2020)Tancik, Srinivasan, Mildenhall, Fridovich-Keil, Raghavan, Singhal, Ramamoorthi, Barron, and Ng] Matthew Tancik, Pratul P. Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan T. Barron, and Ren Ng.  Fourier features let networks learn high frequency functions in low dimensional domains.  _NeurIPS_ , 2020.
  * [Tayal et al.(2020)Tayal, Lai, Kumar, and Sun] Kshitij Tayal, Chieh-Hsin Lai, Vipin Kumar, and Ju Sun.  Inverse problems, deep learning, and symmetry breaking.  _arXiv:2003.09077_ , March 2020.
  * [Ulyanov et al.(2018)Ulyanov, Vedaldi, and Lempitsky] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Deep image prior.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 9446–9454, 2018.
  * [Wang et al.(2004)Wang, Bovik, Sheikh, and Simoncelli] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli.  Image quality assessment: from error visibility to structural similarity.  _IEEE transactions on image processing_ , 13(4):600–612, 2004.
  * [Weinan(2020)] E Weinan.  Machine learning and computational mathematics.  _arXiv preprint arXiv:2009.14596_ , 2020.
  * [Welling and Teh(2011)] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688. Citeseer, 2011.
  * [Williams et al.(2019)Williams, Schneider, Silva, Zorin, Bruna, and Panozzo] Francis Williams, Teseo Schneider, Claudio Silva, Denis Zorin, Joan Bruna, and Daniele Panozzo.  Deep geometric prior for surface reconstruction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10130–10139, 2019.
  * [You et al.(2020)You, Zhu, Qu, and Ma] Chong You, Zhihui Zhu, Qing Qu, and Yi Ma.  Robust recovery via implicit bias of discrepant learning rates for double over-parameterization.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 17733–17744. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/cd42c963390a9cd025d007dacfa99351-Paper.pdf.
  * [Zhang et al.(2005)Zhang, Yu, et al.] Tong Zhang, Bin Yu, et al.  Boosting with early stopping: Convergence and consistency.  _The Annals of Statistics_ , 33(4):1538–1579, 2005.
  * [Zhu et al.(2016)Zhu, Krähenbühl, Shechtman, and Efros] Jun-Yan Zhu, Philipp Krähenbühl, Eli Shechtman, and Alexei A Efros.  Generative visual manipulation on the natural image manifold.  In _European conference on computer vision_ , pages 597–613. Springer, 2016.

##  Appendix A Additional experimental details

In this section, we provide experimental details omitted in the main body of
the paper.

  * •

_Noise settings_. We simulate $4$ different types of noise and $3$ intensity
levels for each noise type, as detailed below. The generation algorithms
follow those of ImageNet-C [Hendrycks and Dietterich(2018)]
888https://github.com/hendrycks/robustness.

    * –

Gaussian noise: $0$ mean additive Gaussian noise with variance $0.12$, $0.18$,
and $0.26$ for low, medium, and high noise levels, respectively;

    * –

Impulse noise: i.e., salt-and-pepper noise, replacing each pixel with
probability $p\in[0,1]$ into white or black pixel with half chance each. Low,
medium, and high noise levels correspond to $p=0.3,0.5,0.7$, respectively;

    * –

Shot noise: i.e., pixel-wise independent Poisson noise. For each pixel
$x\in[0,1]$, the noisy pixel is Poisson distributed with rate $\lambda x$,
where $\lambda$ is $25,12,5$ for low, medium, and high noise levels,
respectively.

    * –

Speckle noise: for each pixel $x\in[0,1]$, the noisy pixel is
$x\pqty{1+\varepsilon}$, where $\varepsilon$ is 0-mean Gaussian with a
variance level $0.20$, $0.35$, $0.45$ for low, medium, and high noise levels,
respectively.

  * •

_Network architecture_. Our AE is based on deep CNNs. The exact architecture
is depicted in Table 5.

Table 5: The network architecture of AE.

Nets |  Layers |  Parameters
---|---|---
Encoder net |  Conv2d 1 |  (3, 32, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Conv2d |  (32, 64, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Conv2d |  (64, 128, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Conv2d |  (128, 128, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Conv2d |  (128, 128, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Conv2d |  (128, 128, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Conv2d |  (128, 1, 3, 2, 1, False)
Batch norm, ReLU |  N/A
Linear net 3 |  Linear 2 |  (16, 16, False)
Linear |  (16, 16, False)
Linear |  (16, 16, False)
Linear |  (16, 16, False)
Decoder net 3 |  Upsample |  bilinear
Conv2d |  (1, 128, 3, 1, 1, False)
Batch norm, ReLU |  N/A
Upsample |  bilinear
Conv2d |  (128, 128, 3, 1, 1, False)
Batch norm, ReLU |  N/A
Upsample |  bilinear
Conv2d |  (128, 128, 3, 1, 1, False)
Batch norm, ReLU |  N/A
Upsample |  bilinear
Conv2d |  (128, 128, 3, 1, 1, False)
Batch norm, ReLU |  N/A
Upsample |  bilinear
Conv2d |  (128, 64, 3, 1, 1, False)
Batch norm, ReLU |  N/A
Upsample |  bilinear
Conv2d |  (64, 32, 3, 1, 1, False)
Batch norm, ReLU |  N/A
Upsample |  bilinear
Conv2d |  (32, 3, 3, 1, 1, False)
Batch norm, Sigmoid |  N/A

  * 1

The parameters for Conv2d layers: (in_channels, out_channels, kernel_size,
stride, padding, bias).

  * 2

The parameters for Linear layers: (in_features, out_features, bias).

  * 3

Tensors are reshaped properly to suit the input dimensions.

##  Appendix B Additional experimental results

###  B.1 Image denoising

Besides DIP, we also verify our methods on DD. As we alluded to in Section 1,
although the original DD paper proposes underparameterization as a strategy to
tame overfitting, in practice it is tricky to implement and
underparameterization can produce inferior results, see, e.g., Fig. 1 (right).
Thus, people (including the DD authors in their later papers, e.g., [Heckel
and Soltanolkotabi(2020)]) tend to still use overparametrized DD. Empirically,
overparametrized DDs behave very similarly to DIPs. Since in Fig. 3 we have
validated our detection method extensively on DIP with $4$ noise types of both
low and high noise levels, here we only focus on Gaussian noise with medium
noise level. Here, we set all the network width as $512$, which is typically
used in practice. The learning rate is set to $0.001$ here for good numerical
stability. Other experimental settings are identical to those of DIP in
Section 3.

The denoising results are summarized in Fig. 8. One can observe that in most
cases, the detection gap is $\leq 1$ in terms of ES-PG, and $\leq 0.1$ in
terms of ES-SG. However, if we run DD without ES, the overfitting issue is
dreadful: most of BASELINE-PGs are $\geq 6$ and BASELINE-SGs are $\geq 0.4$.
These denoising results reaffirm the effectiveness and generality of our
method.

Figure 8: DD+AE for image denoising. (left) The performance measured in PGs.
(right) The performance measured in SGs.

Moreover, Fig. 9 visualizes the reconstruction results of both DIP+AE and DOP.
Fig. 9 (left) shows that both DIP+AE and DOP attain similar performance in
terms of PSNR while DIP+AE requires far fewer iterations and stops very early.
Fig. 9 (right) confirms that visually they also lead to similar reconstruction
qualities, as there is almost no perceivable difference.

Figure 9: DIP+AE vs DOP. (left) The solid lines and dash lines respectively
show the restoration performance for DOP and DIP+AE. (right) Visualizations
for Kodak2 (first row) and Kodak3 (second row).

###  B.2 MRI reconstruction

Here we provide the results for the complete set of random MRI samples that we
experiment with. For the notations, _ES_ indicates the reconstruction quality
detected by our method, _Peak_ denotes the peak quality that DD can achieve,
and _Overfitting_ is the final reconstruction quality without ES.

Table 6: The experimental results of MRI reconstruction.  |  | Sample 1 | Sample 2 | Sample 4 | Sample 6 | Sample 9 | Sample 10 | Sample 16
---|---|---|---|---|---|---|---|---
PSNR $\uparrow$ | ES |  | 29.837 (0.176)
---
| 30.077 (0.231)
---
| 27.419 (0.250)
---
| 28.799 (0.111)
---
| 33.395 (0.158)
---
| 27.907 (0.124)
---
| 28.602 (0.217)
---
Peak |  | 31.792 (0.295)
---
| 31.700 (0.185)
---
| 28.465 (0.282)
---
| 29.855 (0.081)
---
| 34.444 (0.265)
---
| 28.816 (0.107)
---
| 30.494 (0.381)
---
Overfitting |  | 27.182 (0.379)
---
| 26.710 (0.449)
---
| 23.934 (0.072)
---
| 25.631 (0.191)
---
| 31.053 (0.061)
---
| 25.545 (0.182)
---
| 24.806 (0.232)
---
SSIM $\uparrow$ | ES |  | 0.602 (0.002)
---
| 0.609 (0.000)
---
| 0.611 (0.003)
---
| 0.612 (0.005)
---
| 0.669 (0.002)
---
| 0.620 (0.008)
---
| 0.646 (0.005)
---
Peak |  | 0.642 (0.006)
---
| 0.643 (0.004)
---
| 0.658 (0.003)
---
| 0.637 (0.014)
---
| 0.689 (0.008)
---
| 0.644 (0.004)
---
| 0.671 (0.003)
---
Overfitting |  | 0.562 (0.002)
---
| 0.571 (0.002)
---
| 0.568 (0.005)
---
| 0.507 (0.012)
---
| 0.591 (0.009)
---
| 0.554 (0.004)
---
| 0.553 (0.005)
---

As can be seen from Table 6, for all experimental samples, _ES_ and _Peak_
yield close performance in terms of both PSNR and SSIM, which indicates that
our method can reliably detect the near-peak performance. On the other hand,
the performance (both PSNR and SSIM) of _ES_ is uniformly better than that of
_overfitting_ , often by a considerable margin, further confirming the
effectiveness of our method.

###  B.3 Image inpainting

Image inpainting is another common IR task that SIDGPs have excelled in and
hence popularly evaluated on; see, e.g., the DIP paper [Ulyanov et
al.(2018)Ulyanov, Vedaldi, and Lempitsky]. In this task, a clean image $x_{0}$
is contaminated by additive Gaussian noise $\varepsilon$, and then only
partially observed to yield the observation $y=(x_{0}+\varepsilon)\odot m$,
where $m\in\\{0,1\\}^{H\times W}$ is a binary mask and $\odot$ denotes the
Hadamard pointwise product. Here both $y$ and $m$ are known, and the goal is
to reconstruct $x_{0}$. We consider the natural formulation

$E(x)=\norm{(x-y)\odot m}_{2}^{2}.$ (4)

We parametrize $x$ using the DIP model. The mask $m$ is generated according to
an iid Bernoulli model, with a rate of $50\%$, i.e., $50\%$ of pixels not
observed in expectation. The noise $\varepsilon$ is set to the medium level.

We also compare the performance of our method (DIP+AE) with the two competing
methods: DIP+TV [Sun(2020), Sun et al.(2021)Sun, Latorre, Sanchez, and Cevher]
and SGLD [Cheng et al.(2019)Cheng, Gadelha, Maji, and Sheldon]. To ensure
convergence, we run 60K and 200K iterations for DIP+TV and SGLD, respectively,
and report their final results. We repeat all experiments $3$ times and obtain
the mean and standard deviation for each instance.

Table 7 summarizes the results. Our method significantly outperforms the other
two in terms of both PSNR and SSIM. It should be noted that here we test a
medium noise level, rather than the very low noise levels experimented with in
the DIP+TV and SGLD papers. Although in their original papers overfitting
seems to be gone, here we see a strike-back with a different noise level. So
the two competing methods are at best sensitive to hyperparameters, which are
tricky to set.

Table 7: DIP+AE, DIP+TA, and SGLD for image inpainting. The best PSNRs are colored as red; the best SSIMs are colored as blue. | PSNR $\uparrow$ | SSIM $\uparrow$
---|---|---
DIP+AE | DIP+TV | SGLD | DIP+AE | DIP+TV | SGLD
Barbara |  |  21.878 (0.101)
---
| 17.790 (0.024)
---
| 15.326 (0.062)
---
|  0.522 (0.010)
---
| 0.259 (0.000)
---
| 0.259 (0.003)
---
Boat |  |  23.268 (0.445)
---
| 18.071 (0.040)
---
| 15.211 (0.020)
---
|  0.534 (0.010)
---
| 0.259 (0.001)
---
| 0.227 (0.001)
---
House |  |  28.883 (0.300)
---
| 18.362 (0.022)
---
| 15.566 (0.059)
---
|  0.767 (0.025)
---
| 0.157 (0.000)
---
| 0.171 (0.002)
---
Lena |  |  25.052 (0.246)
---
| 18.264 (0.040)
---
| 15.481 (0.084)
---
|  0.644 (0.004)
---
| 0.218 (0.001)
---
| 0.204 (0.003)
---
Peppers |  |  26.251 (0.187)
---
| 18.400 (0.022)
---
| 15.610 (0.036)
---
|  0.738 (0.016)
---
| 0.203 (0.000)
---
| 0.199 (0.001)
---
C.man |  |  26.194 (0.423)
---
| 18.571 (0.049)
---
| 15.861 (0.031)
---
|  0.732 (0.009)
---
| 0.204 (0.001)
---
| 0.215 (0.001)
---
Couple |  |  22.619 (0.154)
---
| 18.115 (0.007)
---
| 15.313 (0.062)
---
|  0.512 (0.011)
---
| 0.280 (0.000)
---
| 0.241 (0.002)
---
Finger |  |  21.396 (0.119)
---
| 17.714 (0.024)
---
| 15.150 (0.027)
---
|  0.795 (0.003)
---
| 0.601 (0.000)
---
| 0.490 (0.001)
---
Hill |  |  24.216 (0.254)
---
| 18.274 (0.017)
---
| 15.514 (0.107)
---
|  0.518 (0.009)
---
| 0.242 (0.000)
---
| 0.214 (0.003)
---
Man |  |  23.687 (0.302)
---
| 18.159 (0.022)
---
| 15.394 (0.109)
---
|  0.532 (0.007)
---
| 0.252 (0.001)
---
| 0.222 (0.004)
---
Montage |  |  27.290 (0.282)
---
| 19.005 (0.022)
---
| 16.334 (0.017)
---
|  0.799 (0.007)
---
| 0.193 (0.000)
---
| 0.221 (0.001)
---

###  B.4 Performance on clean images

For SIDGPs, when there is no noise, the target clean image is a global
optimizer to Eq. 2. So there is no overfitting issue in these scenarios, and
ES is not strictly necessary. But, in practice, one does not know if noise is
present apriori, and finite termination has to be made. In this section, we
experiment with “denoising” _clean_ images with DIP. The setup is exactly as
that of our typical denoising, except that here we do not report the PSNR gap,
as whenever one makes a stop after finite iterations, the theoretical PNSR gap
is infinity. We report the absolute PSNR detected by our method instead; for
most applications, PNSR greater than $30$ is good enough for practical
purposes.

The AE error curve tends to fluctuate when the quality is already high. To
improve the detection performance, we find that comparing running average to
determine ES points performs better than the stopping criterion described in
Algorithm 1. We use this slightly modified version here; we leave reconciling
the two versions as future work—we suspect that this modified version will
likely improve our previous detection performance.

Table 8 shows the preliminary results. Except for the challenging case Baboon,
the PSNR scores are near $30$ or above. So our method is performing reasonable
detection. We suspect using more advanced smoothing techniques such that
Gaussian smoothing can suppress the fluctuation better and hence lead to
better performance; we leave this as future work.

Table 8: Performance of DIP+AE on denoising clean images. |  PSNR $\uparrow$ |  SSIM $\uparrow$
---|---|---
House |  |  36.569
---
|  0.921
---
Peppers |  |  30.407
---
|  0.797
---
Lena |  |  31.927
---
|  0.857
---
Baboon |  |  20.186
---
|  0.423
---
F16 |  |  33.065
---
|  0.911
---
Kodak1 |  |  29.243
---
|  0.852
---
Kodak2 |  |  31.064
---
|  0.826
---
Kodak3 |  |  30.155
---
|  0.861
---
Kodak12 |  |  31.757
---
|  0.851
---
Table 9: The performance gaps of BRISQUE [Mittal et al.(2012a)Mittal, Moorthy, and Bovik], NIQE [Mittal et al.(2012b)Mittal, Soundararajan, and Bovik], NIMA [Talebi and Milanfar(2018)], and DIP+AE on shot and speckle noises. For NIMA, we report both technical quality assessment (the number before “/”) and aesthetic assessment (the number after “/”). The best PSNR gaps are colored as red; the best SSIM gaps are colored as blue. | Shot noise | Speckle noise
---|---|---
| Gap in PSNR $\downarrow$ | Gap in SSIM $\downarrow$ | Gap in PSNR $\downarrow$ | Gap in SSIM $\downarrow$
| BRISQUE | NIQE | NIMA | DIP+AE | BRISQUE | NIQE | NIMA | DIP+AE | BRISQUE | NIQE | NIMA | DIP+AE | BRISQUE | NIQE | NIMA | DIP+AE
House | 6.713 | 8.629 | 10.873/0.662 | 0.294 | 0.389 | 0.491 | 0.598/0.024 | 0.002 | 9.848 | 8.970 | 12.879/1.394 | 1.847 | 0.457 | 0.424 | 0.591/0.027 | 0.010
Peppers | 5.538 | 5.975 | 1.863/6.013 | 0.417 | 0.267 | 0.289 | 0.128/0.295 | 0.018 | 6.414 | 6.085 | 8.987/4.861 | 0.311 | 0.233 | 0.227 | 0.316/0.193 | 0.011
Lena | 7.976 | 6.191 | 9.697/1.545 | 1.281 | 0.448 | 0.375 | 0.516/0.075 | 0.020 | 8.797 | 5.133 | 9.352/0.912 | 0.445 | 0.402 | 0.240 | 0.436/0.039 | 0.013
Baboon | 0.508 | 0.562 | 2.767/3.061 | 1.920 | 0.026 | 0.009 | 0.391/0.404 | 0.284 | 0.387 | 1.507 | 1.178/2.063 | 2.318 | 0.027 | 0.053 | 0.144/0.231 | 0.314
F16 | 5.329 | 8.448 | 0.938/6.404 | 1.016 | 0.403 | 0.555 | 0.011/0.168 | 0.013 | 6.760 | 7.136 | 0.418/7.757 | 0.418 | 0.488 | 0.498 | 0.001/0.229 | 0.021
Kodak1 | 3.099 | 3.741 | 3.287/5.387 | 0.953 | 0.086 | 0.118 | 0.321/0.485 | 0.059 | 1.363 | 4.332 | 3.215/6.871 | 0.719 | 0.013 | 0.106 | 0.258/0.556 | 0.056
Kodak2 | 15.693 | 9.055 | 10.208/1.071 | 0.154 | 0.433 | 0.269 | 0.435/0.025 | 0.006 | 9.755 | 7.921 | 8.169/0.634 | 0.340 | 0.272 | 0.177 | 0.158/0.013 | 0.013
Kodak3 | 8.429 | 8.546 | 2.501/21.796 | 0.895 | 0.429 | 0.427 | 0.092/0.619 | 0.006 | 6.484 | 6.509 | 13.457/13.130 | 1.183 | 0.236 | 0.239 | 0.584/0.263 | 0.016
Kodak12 | 6.009 | 8.941 | 6.746/20.054 | 2.118 | 0.401 | 0.490 | 0.422/0.704 | 0.021 | 8.545 | 8.204 | 5.398/0.703 | 0.562 | 0.459 | 0.450 | 0.343/0.011 | 0.010

###  B.5 Bell-shape examples under different learning rate

As we shown in Table 4, our ES detection method is stable in terms of
different learning rates of DIP. Here we further demonstrate that the bell-
shape of PSNR curve of DIP is holds under different learning rates. We
randomly select two images—F16 and Peppers—and visualize their PSNR curves
under different learning rates {0.01, 0.001, 0.0001} in Fig. 10. We can
observe that different rates would perturb the curves but would not distort
the overall bell shape.

Figure 10: The PSNR curves of DIP under different learning rates. (left) the
PSNR curves for F16; (right) the PSNR curves for Peppers.

###  B.6 Analysis of failure mode

To qualitatively understand the failing cases, we select $3$ positive images
that enjoy consistent good detection and $3$ negative images that see
consistent failure, and visualize their Fourier spectra in Figs. 11 and 12.
For better visualization, we take the $x\mapsto\log(1+x)$ transform of the
Fourier magnitudes, as is commonly done in image processing. Visually, the
positive examples can be well characterized as being piecewise smooth, and the
negative ones invariably contain fine details that correspond to high
frequency components. Indeed, the positive spectra are concentrated in the
low-frequency bands, whereas the negative spectra are much more scattered into
high-frequency bands. We leave a more quantitative analysis of this as future
work.

Figure 11: Positive images and their spectra. Figure 12: Negative images and
their spectra.

###  B.7 ES criterion based on other principles?

During the peer review, one reviewer kindly pointed to us the possibility of
formulating ES criteria based on the _whiteness_ or _discrepancy_ principles
in image denoising [Lanza et al.(2018)Lanza, Morigi, Sciacchitano, and
Sgallari, Almansa et al.(2007)Almansa, Ballester, Caselles, and Haro]. In this
section, we briefly discuss the possibility of implementing them. We want to
quickly remind that we target practical denoising, and so assume very little
knowledge about noise types, levels, or whatsoever. Particularly, the noise
level $\sigma^{2}$ is unknown to us and possibly also hard to estimate due to
the generality we strive for. Also, to avoid confusion, we will switch our
notations slightly here.

Let $\mathbf{X}\in\mathbb{R}^{n\times n}$ be the target image, and
$\mathbf{Y}=f\pqty{\mathbf{X}}+\mathbf{W}$ be the noisy measurement, where
$\mathbf{W}\in\mathbb{R}^{n\times n}$ is white noise with variance level
$\sigma^{2}<+\infty$, i.e.

  * •

$\mathbb{E}\,w_{ij}=0$ and
$\mathbb{E}\,w_{ij}^{2}=\sigma^{2}\quad\forall\;i,j$;

  * •

any pair of distinct elements in $\mathbf{W}$ are _uncorrelated_ : for two
different (in location) elements $w,w^{\prime}$ of $\mathbf{W}$,
$\mathbb{E}\left[(w-\mathbb{E}\,w)(w^{\prime}-\mathbb{E}\,w^{\prime})\right]=0\Longrightarrow\mathbb{E}\left[ww^{\prime}\right]=0$
(the implication uses the 1st property).

The 2nd property has an interesting implication:

$\displaystyle\mathbb{E}\left[\mathbf{W}\star\mathbf{W}\right]=n^{2}\sigma^{2}\delta_{n\times
n}=\begin{bmatrix}n^{2}\sigma^{2}&\mathbf{0}^{\intercal}_{n-1}\\\
\mathbf{0}_{n-1}&\mathbf{0}_{(n-1)\times(n-1)}\end{bmatrix},$ (5)

where $\star$ denotes the 2D cross-correlation (for convenience, we assume the
circular version), and $\delta_{n\times n}$ is the 2D delta function (we
assume the top-left corner corresponds to no-shift alignment). Denote our
estimated image as $\widehat{\mathbf{X}}$. If we have perfect recovery, then

$\displaystyle\mathbf{Y}-f\pqty{\widehat{\mathbf{X}}}=\mathbf{Y}-f\pqty{\mathbf{X}}=\mathbf{W},$
(6)

and so

$\displaystyle\mathbb{E}\left[\pqty{\mathbf{Y}-f\pqty{\widehat{\mathbf{X}}}}\star\pqty{\mathbf{Y}-f\pqty{\widehat{\mathbf{X}}}}\right]=\mathbb{E}\left[\mathbf{W}\star\mathbf{W}\right]=n^{2}\sigma^{2}\delta_{n\times
n}.$ (7)

This is the _whiteness principle_ in [Lanza et al.(2018)Lanza, Morigi,
Sciacchitano, and Sgallari]999Our presentation here does not use the discrete-
time stochastic process language as in the original paper—which seems overly
technical than necessary, but they are equivalent.: in particular, except for
the top-left corner, all other elements should be zero.

In practice, we are not able to take the expectation as we only observe one
realization. But note that except for the perfectly aligned case which
produces $n^{2}\sigma^{2}$, each element of
$\frac{1}{n^{2}}\mathbf{W}\star\mathbf{W}$ can be approximated by
$\mathcal{N}\pqty{0,\frac{\sigma^{4}}{n^{2}}}$ due to central limit theorem
when $n^{2}$ is large—this is valid for images. So typical element of
$\mathbf{W}\star\mathbf{W}$ should lie in the range

$\displaystyle[-cn\sigma^{2},cn\sigma^{2}],$ (8)

where $c>1$ is a large enough constant, say $5$.

This is explicitly used as a constraint in [Lanza et al.(2018)Lanza, Morigi,
Sciacchitano, and Sgallari] to improve image restoration quality. If the
variance level $\sigma^{2}$ is known, we may be able to use distance to this
set as a measure of image quality. However, for our applications, we do not
assume known $\sigma^{2}$, and also the constant $c$ chosen can impact the
result also.

A more reasonable metric for us would be the quantity

$\displaystyle\norm{(\mathbf{W}\star\mathbf{W})_{-0}},$ (9)

i.e., the norm of the $\mathbf{W}\star\mathbf{W}$ with the top-left corner
removed, which ideally should be as sufficiently small. To be more explicit,

$\displaystyle\norm{\pqty{\pqty{\mathbf{Y}-f\pqty{\widehat{\mathbf{X}}}}\star\pqty{\mathbf{Y}-f\pqty{\widehat{\mathbf{X}}}}}_{-0}}.$
(10)

But obviously the minimum is achieved when we overfit the noisy image
$\mathbf{Y}$.

The _discrepancy principle_ (or local constraint) in [Almansa et
al.(2007)Almansa, Ballester, Caselles, and Haro] is a refinement to the
obvious constraint

$\displaystyle\frac{1}{n^{2}}\norm{f\pqty{\widehat{\mathbf{X}}}-\mathbf{Y}}_{F}^{2}\leq\sigma^{2}$
(11)

for a good estimate $\widehat{\mathbf{X}}$ to satisfy. This only enforces that
_globally_ the noise level of the residual matches the known noise level, but
does not ensure _uniformly_. To ensure the latter, a natural idea is to
enforce the noise level consistently everywhere locally:

$\displaystyle
G\ast\pqty{f\pqty{\widehat{\mathbf{X}}}-\mathbf{Y}}^{2}_{i,j}\leq\sigma^{2}\quad\forall\;i,j.$
(12)

Here, $G$ is a Gaussian filter of appropriate size, and the left side of the
equality is the (Gaussian) weighted mean variance around the pixel location
$(i,j)$.

Similar to the situation for the whiteness principle, if the variance level
$\sigma^{2}$ is known, we may also use the distance to this set as a metric to
measure the reconstruction quality. When $\sigma^{2}$ is unknown, it is
unclear how to make easy modification to do this, unlike the case of the
whiteness principle above.