# Survey on Modeling Intensity Function of Hawkes Process Using Neural Models

Jayesh Malaviya
Computer Science and Engineering
IIT Gandhinagar

<EMAIL_ADDRESS>

###### Abstract

The event sequence of many diverse systems is represented as a sequence of
discrete events in a continuous space. Examples of such an event sequence are
earthquake aftershock events, financial transactions, e-commerce transactions,
social network activity of a user, and the user’s web search pattern. Finding
such an intricate pattern helps discover which event will occur in the future
and when it will occur. A Hawkes process is a mathematical tool used for
modeling such time series discrete events. Traditionally, the Hawkes process
uses a critical component for modeling data as an intensity function with a
parameterized kernel function. The Hawkes process’s intensity function
involves two components: the background intensity and the effect of events’
history. However, such parameterized assumption can not capture future event
characteristics using past events data precisely due to bias in modeling
kernel function. This paper explores the recent advancement using novel deep
learning-based methods to model kernel function to remove such parametrized
kernel function. In the end, we will give potential future research directions
to improve modeling using the Hawkes process.

##  1 Introduction

Collections of random data points in some space, such as time or location
modeled as point processes. The point processes give the statistical language
for describing the timing and properties of the events. We can fit many
problems in this set of point processes with a range of application domains.
Like in finance, a process can represent a sell or a buy transaction in the
stock market that influences future prices. In geophysics, the process can be
an earthquake that is implying the likelihood of a future earthquake in the
vicinity. In social media analytics, the process can be over a period of a
time user action, each of that has a number of properties like user influence,
connectivity with the neighboring network, and the topic of interest in the
community. Hawkes processes are one of the point processes, and especially
useful for modeling discrete, inter-dependent events over continuous time
[1,2].

Some times we can directly observe the diffusion of information via retweets
in case of twitter, but there exist other diffusion processes that can not be
observed clearly like offline word-of-mouth diffusion, or propagating of
information over emails and different online platforms. One way for modeling
such an information diffusion process is by self-exciting processes. In these
processes, we are seeing the probability of seeing a new event increases due
to previous events.

Many events are by default correlated in the surrounding, viz. a single or
multiple events can cause or stop the future event from occurring. Papers in
this domain are mainly interested in learning the distribution of such time-
series events and various events’ properties. If we can concretely model the
correlation among these events, we can predict the future event or set of
events using the history of future events’ events and timing. An example of
such correlation among events can be found in many applied domains. Every
patient has a sequence of a doctors visit, laboratory tests, diagnoses, and
medications in medical events. By learning from past patients sequence data,
we can predict a new patient’s future events from their past events. In
e-commerce, a user has a sequence of online purchase transactions, and by
modeling such a sequence, we can learn the consumers’ purchase patterns. In
social network data, the user actions are previous posts, likes, comments, and
messages, and from that, we can predict future activities of the users [1, 4].

This paper’s primary motivation is despite being much traditional literature
on time series data modeling using the Hawkes process using many different
kernel functions empirically tested for specific applications. Still, they
can’t generalize well and suffer from the problem of the curse of model
misspecification. To tackle that, recently, people started exploring deep
learning-based kernel function modeling techniques to avoid many parametric
assumptions about intensity function and showing useful improvements in the
future event prediction and efficiently handling high dimensional time series
compared to traditional approaches.

###  1.1 Motivation for the survey

Hawkes process is traditionally used to predict future events or event
causality detection. These two closely match machine learning objectives, viz.
models prediction accuracy and interpretability [Choi et al., 2016].
Traditionally till recently, people were using a manually specified parametric
kernel function to model Hawkes processes. Recently, people started exploring
deep neural models for modeling the Hawkes process’s intensity function to
remove the curse of model misspecification. More recent neural models call it
neural Hawkes process as the term used in [Du et al., 2016; Mei and Eisner,
2017], which removes the need for explicit parametric intensity function. Du
et al. also showed that the classical Hawkes process models with parametric
intensity function are good at interpretability on understanding the learning
process and event causality.

In contrast, the neural Hawkes process gives high accuracy in predicting
future events and time. In the subsequent section, we will review the more
recent work along these threads. As this is still an emerging area, there are
fewer papers available for the neural Hawkes process. Nevertheless, current
curiosity in top Machine Learning conferences like ICML, Neurips, etc. about
this topic shows a great scope of improvement in this line by leveraging deep
learning techniques to predict future events and interpretability of causal
relationships better.

##  2 Preliminary

In this section we will describe basic definitions and terminology used in
modeling Hawkes process.

#### Definition 1 (Point Process [1])

Let $(\omega,F,P)$ be a probability space. A point process on $R^{+}$ is a
sequence of non-negative random variables
$\left\\{t_{i}\right\\}_{i=1,2,\dots}$ , such that for all i, $t_{i}\leq
t_{i+1}$.

#### Definition 2 (Interarrival time [1])

Consider a temporal point process $\left\\{t_{i}\right\\}_{i=1,2,\dots}$ ,
Define $W_{i}=t_{i}-t_{i-1}$ with the convention $t_{0}=0$. The sequence
$\left\\{W_{i}\right\\}_{i=1,2,\dots}$ is called the interarrival times.

#### Definition 3 (Counting Process [1])

A counting process associated with the temporal point process
$\left\\{t_{i}\right\\}_{i=1,2,\dots}$ represented as $N_{t}$ or $N(t)$ is a
random function defined on time $t\geq 0$ , taking values in $Z^{+}$ , that
counts the number of occurrences up to and including time $t$, i.e.

$N_{t}=\sum_{i=1,2,\dots}1_{t_{i}\leq t}$

#### Definition 4 (Intensity of point process [1])

The intensity of a point process is defined as,

$\lambda(t)=\lim_{h->0^{+}}\frac{P(N(t,t+h]>0)}{h}$

$N(t,t+h]$ indicate the count of the number of events in an interval of length
h. $\lambda(t)$ intuitively measures the rate at which the events occur.

A fundamental model for modeling sequence data is the Poisson process, which
assumes that the events arriving independently of other events. In a typical
homogeneous Poisson process, we take that the intensity function is constant
$\lambda(t)=\lambda$ . However, in a non-homogeneous Poisson process, event
probability t varies with time t. Still, it is independent of another process.
In a Hawkes process (Hawkes, 1971; Liniger, 2009), they incorporated that the
past events can temporarily raise future event probability. They assume that
this self-excitation is positive, additive over the past events, and
exponentially decaying with time.

#### Definition 5 (Hawkes process [2, 1])

Let $\left\\{N_{t}\right\\}_{t>0}$ be a counting process with associated
history $H_{t},t\geq 0$. The point process is said to be a Hawkes process if
the conditional intensity function $\lambda(t|H_{t})$ takes the form,

$\lambda(t|H_{t})=\lambda_{0}(t)+\sum_{i:t>T_{i}}\phi(t-T_{i})$

where $T_{i}<t$ are all the event time having occurred before current time t,
and which contribute to the event intensity at time t.
$\lambda_{0}(t):R\mapsto R_{+}$ is a deterministic base intensity function,
and $\phi:R\mapsto R_{+}$ is called the memory kernel, normally kernel is
stocastic and depend on the past events throuth the kernel function.

##  3 Traditional Hawkes process likelihood and Kernel functions

The process is described via a conditional intensity function
$\lambda(t|H_{t})$ [1, 6], which is intensity function at time t conditioned
on history of event $H_{t}=\left\\{t_{i}\right\\}_{t_{i}<t}$ upto time t,

$\lambda(t|H_{t})=\lim_{\Delta\mapsto
0}\frac{P(one\>event\>occur\>in[t,t+\Delta)|H_{t})}{\Delta}$

If conditional intensity function is specified then, the probability density
function of the next event time $t+1$, given the past event times
$\left\\{t_{1},t_{2},\dots t_{i}\right\\}$ is [1, 6] calculated as,

$P(t_{i+1}|t_{1},t_{2},\dots,t_{i})=\lambda(t_{i+1}|H_{i+1})\,exp\left\\{-\int_{t_{i}}^{t_{i+1}}\lambda(t|H_{t})dt\right\\}$

where the exponential term in the right-hand side represents the probability
that no events occur in $[t_{i};t_{i+1})$. The probability density function to
observe an event sequence $\left\\{t_{i}\right\\}_{i=1}^{n}$ is [1, 6]
calculated as,

$P(\left\\{t_{i}\right\\}_{i=1}^{n})=\prod_{i=1}^{n}\lambda(t_{i}|H_{t_{i}})\,exp\left\\{-\int_{0}^{T}\lambda(t|H_{t})dt\right\\}$

Detailed proof for the above equations is available in [1].

#### Conditional intensity functions of point processes

  * •

Poisson Process (Kingman 1992): As discussed above, the Poisson process has a
constant intensity function and no event history effect on current events.

  * •

Reinforced Poisson processes (Pemantle 2007; Shen et al. 2014): the model
captures the ’rich-get-richer’ phenomenon defined by a compact intensity
function, which is lately used for predicting popularity (Shen et al. 2014).

  * •

Hawkes process (Hawkes 1971): Hawkes process incorporates constant background
intensity with kernel function for modeling the event’s history, and it is a
self-excitation process. It received wide recognition lately in analysing the
social network data (Zhou, Zha, and Song 2013a), viral diffusion(Yang and Zha
2013) etc.

  * •

Reactive point process (Ertekin, Rudin, and Mc- Cormick 2015): It can be
thought of as a generalization of the Hawkes process. It generally combines a
self-inhibiting term in the Hawkes process to account for inhibiting effects
from past events.

  * •

Self-correcting process (Isham and Westcott 1979): In this background, part
increases steadily, while it is reduced by a constant $e^{-\alpha}<1$ every
time a new event appears.

Above is table 1 of the conditional intensity functions of various point
processes in their general form. In that, it is shown background intensity
component and event history effect component separately.

Table 1: Conditional intensity functions of point processes [4] Model | Background | History event effect
---|---|---
Poisson process | $\mu(t)$ | 0
Reinforced poisson process | 0 | $\gamma(t)\sum_{t_{i}<t}\delta(t_{i}-t)$
Hawkes process | $\mu(t)$ | $\sum_{t_{i}<t}\gamma(t,t_{i})$
Reactive point process | $\mu(t)$ | $\sum_{t_{i}<t}\gamma_{1}(t,t_{i})-\sum_{t_{i}<t}\gamma_{2}(t,t_{i})$
Self-correcting process | 0 | $exp(\mu t-\sum_{t_{i}<t}\gamma(t,t_{i}))$

Note: $\delta(t)$ is Dirac function, $\gamma(t,t_{i})$ is time-decaying kernel
and $\mu(t)$ can be constant or time-varying function.

###  3.1 Problems

The real-world pattern can not correctly model using the Hawkes process using
the assumption for intensity function like assumption about function is
positive is violated if a current event inhibits future events rather than
excite. For example, Softdrink consumption inhibits alcohol consumption.
Another assumption of additivity is infringed in past events that are not
additive, i.e., the 100th advertisement may not help much compared to the
first advertisement to increase the purchase rate and even decrease the
purchase. The third assumption of exponential decrease with respect to time is
violated when a prior event has a very delayed effect, so it may increase
sharply just before decaying.

Another critical problem with the classical Hawkes process is complexity as to
generalize the model well, we usually pick complex kernel function, which will
lead to the intractable likelihood function due to the integral of a kernel
function. However, many numerical approximation algorithms are available to
compute integral but generally deteriorate the model’s accuracy and
computationally very difficult to train for high dimensional time series.

Another problem is missing data in the observed sequences, which generally
requires a more robust model than the traditional Hawkes process. Manier time,
even if a particular domain Hawkes model might be appropriate, it is still
hard to apply when sequences of events are partially observed. Real datasets
sometimes systematically exclude some types of events, i.e., offline
purchases, which may influence future events.

##  4 Neural Models for Hawkes process

After investing in different forms of conditional intensity functions[11, 12,
13], the authors in [3] observed that different forms of dependency structures
exist among past events and future events. With this crucial insight, they
found that to learn general representation for approximating the latent
dependency among the event’s history is essential for predicting future event
time and the type of event.

In subsequent sections, we will explore various deep learning techniques to
model the Hawkes process’s conditional intensity function. In Table 2, Neural
Model-Based Methods with Implementation Code are provided for exploration
purposes.

###  4.1 RMTPP: Embedding Event History to Vector [3]

A recurrent neural network (RNN) with sigmoid activation units can capable of
simulating a universal Turing machine [22], which can use to perform complex
computations. RNN has shown promising results in the sequence modeling task.
For example, in NLP, the recurrent neural network has an excellent result for
predicting future sequence and sequence to sequence translations[23]. It has
been used in discrete time series data prediction[24, 25, 26] for a long time.

In this paper, the author proposes the Recurrent marked temporal point process
to the model type of the event, which is event marker and event timing
simultaneously. Their approach’s main idea is to use RNN in place of modeling
intensity function by assuming it a complex non-linear function; an RNN can
automatically learn the relationship between past events and future events and
their influences. RMTPP is the first attempt to incorporate a deep model into
the temporal point process, and results show improvement over traditional
methods. RMTPP can also scale to millions of events and get better predictions
compared to parameterized methods.

Input for the RNN in this approach is the occurrence timing of the event
$t_{j}$ and the type of the event $y_{j}$, the pair $(t_{j},y_{j})$ and then
RNN unrolled up to the event $(j+1)^{th}$ event. The embedding $h_{j-1}$
represents the past events influence memory where both timing and type of
event are captured. The neural model updates $h_{j-1}$ to $h_{j}$ by
considering the effect of the event $(t_{j},y_{j})$. With this, we can now
represent the conditional intensity of $j^{th}$ event as a $h_{j}$ since it
represents the history of influence till $j^{th}$ event,

$f^{*}(t_{j+1})=f(t_{j+1}|H_{t})=f(t_{j+1}|h_{j})=f(d_{j+1}|h_{j})$

where $d_{j+1}=t_{j+1}-t_{j}$. So now we can predict next events timing
$\hat{t}_{j+1}$ and event type $\hat{y}_{j+1}$, that is depend on the $h_{j}$.

The advantage of this method is it can now capture a hidden representation of
event history in $h_{j}$ that captures a more general form of event
representations concerning time without being relay on the parameterized
assumption in case of intensity function $\lambda(t|H_{t})$.

The disadvantage of this approach is that we lose model interpretation and
causal relationships among the events.

###  4.2 NHP: A Neurally Self-Modulating Multivariate Point Process [5]

In this paper author modeled a sequence of discrete events in continuous time
by a novel ideal of continuous-time LSTM. Like before, each event type k has
its intensity $\lambda_{k}(t)$, which varies with time and jumps
discontinuously when each new event occurs and, in the end, drifts
continuously towards baseline intensity. In this continuous-time LSTM, we have
hidden state vector $h(t)\in(-1,1)^{D}$, which depends on a vector $c(t)\in
R^{D}$ of the memory cell. This model is different from traditional discrete-
time LSTM(Hochreiter and Schmidhuber, 1997; Graves, 2012) in the continuous
interval following an event, and each memory cell c exponentially decays at
some rate $\delta$ towards some steady-state value $\bar{c}$,

At each time t > 0, we obtain the intensity $\lambda_{k}(t)$ by
$\lambda_{k}(t)=f_{k}(W_{k}^{t}h(t))$, where
$h(t)=o_{i}\odot(2\sigma(2c(t))-1)$ for $t\in(t_{i-1},t_{i}]$, defines how the
hidden states $h(t)$ are continually obtained from the memory cells $c(t)$ as
the cells decay. This basically says that on the interval $(t_{i-1},t_{i}]$,
after occurrence of $i-1$ event till $i^{th}$ event occur at time $t_{i}$ ,
the $h(t)$ define in above equation determines the intensity function
$\lambda_{k}(t)=f_{k}(W_{k}^{t}h(t))$.

This paper is different from the previous on RMTPP because the RMTPP uses
standard discrete-time LSTM cell without decaying like in NHP, so they encode
intervals between past events in terms of numerical input the LSTM. Another is
they use only one intensity function $\lambda(t)$, and it at the end, it
merely decay towards 0 exponentially between two events, whereas in NHP, more
modular mode creates separate intensity function $\lambda_{k}(t)$. They each
allow complex and non-monotonic dynamics towards non zero steady-state
intensity. Another main difference is in RMTPP. They assume inherently that
event type y and event time t are conditionally independent given history h,
and they are finding different distribution for them, and their model can not
avoid the positive probability of extermination at all times. Lastly, they
taking exponential function, and therefore the effect of their hidden unit of
RNN is multiplicative, whereas in this paper, the function is softplus, so
here they are getting additive effect inspired by classical Hawkes process. As
per the author in NHP, additivity helps capture independent causes, and at the
same time, hidden units in NHP can capture complex joint causes.

###  4.3 Fully Neural Network based Model for General Temporal Point Processes
[6]

In the past literature[3, 5], RNN based models usually assume some specific
functional forms for the time course of the intensity function of a temporal
point process, i.e., exponentially increasing or decreasing with time since
most recent events. However, such an assumption limits the expressibility of
the model. So in this paper, the author proposes an exciting ideal of RNN
based model. They remove the assumption of the time course of intensity
function and represent it as a generic way with a cumulative hazard function.
In this paper, the first model intensity functions integral using a
feedforward neural network and then obtain it as a derivative. With this
approach, we can evaluate the exact log-likelihood function, which otherwise
we have to use a numerical approximation algorithm and computationally
expensive.

###  4.4 Self-Attentive Hawkes Process [7]

In this paper, the author examines the use of the self-attention mechanism in
the Hawkes process by proposing a Self-Attentive Hawkes Process (SAHP). First,
they apply self-attention to estimate the influence of the history of events
on the next event by computing its probability. As self-attention relies on
positional embeddings of the input for taking into account the events’ order,
traditional embedding methods are used on sinusoidal functions for shifting
their position by a constant shifting phase, which if used for sequences would
ignore the original time interval between events. This paper removes this
limitation by proposing a novel idea of a time-shifted positional embedding
method where they assume time interval as a phase shift of sinusoidal
functions. This attention-based model is more interpretable compared to
previous RNN based models as the learned attention weight vector can be used
to reveal the contributions of one type of event in another kind of event
happening and their causal relationships.

###  4.5 Transformer Hawkes Process [8]

Sequential event data often contain complicated long-term and short-term
temporal dependencies. Previously studied literature on neural models with the
Hawkes process fails to simultaneously capture both these types of
dependencies and eventually give an unreliable prediction on future events and
timestamps.

Figure 1: Illustration of dependency computation between the last event (the
red triangle) and its history (the blue circles). RNN based NHP models
dependencies through recursion. THP directly and adaptively models the event’s
dependencies on its history. Convolution-based models enforce static
dependency patterns [8].

In this paper author target this issue with the help of the Transformer Hawkes
Process (THP) model, which uses the self-attention mechanism for capturing the
long-term dependencies and, at the same time, computationally very efficient
compared to previous models. Experiments of the paper on various datasets
suggest that THP gives better likelihood and event prediction than existing
methods by a good margin.

The main component of the THP model is the self-attention module, which,
unlike RNN, discards recurrent structures (figure 1). However, this model
still needs to be aware of the temporal information of input, which is the
event time. Here, they are using trigonometric functions to define a temporal
encoding for each timestamp $t_{j}$. Here, the self-attention mechanism model
can directly select events whose occurrence time is at any distance from the
current time. Whereas in RNN based models encoding of event history is
sequential via a hidden unit representation of the events, i.e., the state
$t_{j}$ depends on state $t_{j-1}$, which in turn depends on $t_{t-2}$ and so
on. This encoding is weak, and RNN may fail to learn relevant information for
any random event $t_{k}$, hidden unit for any event $t_{j}$ where $j\geq k$
will be inferior.

The limitation of previous RNN based models (figure 1) is the need to feed
data sequentially, and because of that, it can not train parallelly. This
limits RNN to train for large scale data. Recently CNN based models (Oord et
al., 2016) [27] are also proposed to capture long term dependency in
sequential data. But the limitation of that model is that these models are
inherently enforced to capture many unnecessary dependencies.

They experimented with model sensitivity to the number of model parameters and
tested on the Retweet dataset and found that THP is not sensitive to its
number of parameters. The THP model outperforms RNN based models with very few
parameters. In their experiments, they showed that NHP with about 1000k
parameters matches the performance of the time-series event sequence (TSES)
model with about 2000k parameters. So THP is efficient in both model size and
training time.

Table 2: Neural Model Based Methods with Implementation Code Neural Model Based Methods |  Code
---|---
RMTPP: Embedding Event History to Vector [3] |  https://github.com/musically-ut/tf_rmtpp
NHP: A Neurally Self-Modulating Multivariate Point Process [5] |  https://github.com/xiao03/nh
Fully Neural Network based Model for General Temporal Point Processes [6] |  https://github.com/omitakahiro/NeuralNetworkPointProcess
Self-Attentive Hawkes Process [7] |  https://github.com/QiangAIResearcher/sahp_repo
Transformer Hawkes Process [8] |  https://github.com/SimiaoZuo/Transformer-Hawkes-Process

##  5 Future Scope

Deep learning-based conditional intensity modeling has opened a new research
thread in the temporal point process domain. Still, at the same time, it
compromises the interpretability of the model, and eventually, it makes it
challenging to deal with the causality of events. The problem of predicting
the distribution of events in case of missing sequence data or partially
observed sequence still requires efforts to improve results. It is interesting
to embed these neural models into reinforcement learning to discover the
causal relationship among events and learn a global policy. Causality
analysis, in the case of asynchronous events using an attention-based model,
is interesting to explore. The joint distribution of the event marker and
event time can be more informative than assume it to be independent.

## Acknowledgement

I thank Professor Anirban Dasgupta, Department of Computer Science and
Engineering IIT Gandhinagar, for guidance on the Hawkes process topic and
useful discussion. I would also like to thank Rachit Chhaya, Ph.D. Scholar at
the Department of Computer Science and Engineering IIT Gandhinagar, for
providing valuable feedback of the work during writing.

## References

[1] Rizoiu, Marian-Andrei, Young Lee, Swapnil Mishra, and Lexing Xie. "A
tutorial on hawkes processes for events in social media." arXiv preprint
arXiv:1708.06401 (2017).

[2] Hawkes, Alan G. "Spectra of some self-exciting and mutually exciting point
processes." Biometrika 58, no. 1 (1971): 83-90.

[3] Du, Nan, Hanjun Dai, Rakshit Trivedi, Utkarsh Upadhyay, Manuel Gomez-
Rodriguez, and Le Song. "Recurrent marked temporal point processes: Embedding
event history to vector." In Proceedings of the 22nd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, pp. 1555-1564. 2016.

[4] Xiao, Shuai, Junchi Yan, Xiaokang Yang, Hongyuan Zha, and Stephen M. Chu.
"Modeling the intensity function of point process via recurrent neural
networkss." In Proceedings of the Thirty-First AAAI Conference on Artificial
Intelligence, pp. 1597-1603. 2017.

[5] Mei, Hongyuan, and Jason M. Eisner. "The neural hawkes process: A neurally
self-modulating multivariate point process." In Advances in Neural Information
Processing Systems, pp. 6754-6764. 2017.

[6] Omi, Takahiro, and Kazuyuki Aihara. "Fully neural network based model for
general temporal point processes." In Advances in Neural Information
Processing Systems, pp. 2122-2132. 2019.

[7] Zhang, Qiang, Aldo Lipani, Omer Kirnap, and Emine Yilmaz. "Self-Attentive
Hawkes Process." ICML, 2020.

[8] Zuo, Simiao, Haoming Jiang, Zichong Li, Tuo Zhao, and Hongyuan Zha.
"Transformer Hawkes Process." ICML 2020.

[9] E. Choi, M. T. Bahadori, J. Sun, J. Kulas, A. Schuetz, and W. Stewart.
Retain: An interpretable predictive model for healthcare using reverse time
attention mechanism. In NIPS, pages 3504–3512, 2016.

[10] A.G Hawkes. Hawkes processes and their applications to finance: a review.
Quantitative Finance, 18(2):193–198, 2018.

[11] K. Cho, B. van Merrienboer, D. Bahdanau, and Y. Bengio. On the properties
of neural machine translation: Encoder-decoder approaches. CoRR,
abs/1409.1259, 2014.

[12] D. Daley and D. Vere-Jones. An introduction to the theory of point
processes: volume II general theory and structure, Springer, 2007.

[13] N. Du, M. Farajtabar, A. Ahmed, A. J. Smola, and L. Song. Dirichlet-
hawkes processes with applications to clustering continuous-time document
streams. In KDD , ACM, 2015.

[14] Kingman, J. F. C., Poisson processes. volume 3\. Oxford university press,
1992.

[15] Pemantle, Robin. "A survey of random processes with reinforcement."
Probability surveys 4 (2007): 1-79.

[16] Shen, Hua-Wei, Dashun Wang, Chaoming Song, and Albert-László Barabási.
"Modeling and predicting popularity dynamics via reinforced poisson
processes.", In AAAI 2014.

[17] Zhou, Ke, Hongyuan Zha, and Le Song. "Learning triggering kernels for
multi-dimensional hawkes processes." In International Conference on Machine
Learning, pp. 1301-1309. 2013.

[18] Zhou, Ke, Hongyuan Zha, and Le Song. "Learning social infectivity in
sparse low-rank networks using multi-dimensional hawkes processes." In
Artificial Intelligence and Statistics, pp. 641-649. 2013.

[19] Yang, Shuang-Hong, and Hongyuan Zha. "Mixture of mutually exciting
processes for viral diffusion." In International Conference on Machine
Learning, pp. 1-9. 2013.

[20] Ertekin, Şeyda, Cynthia Rudin, and Tyler H. McCormick. "Reactive point
processes: A new approach to predicting power failures in underground
electrical systems." The Annals of Applied Statistics 9, no. 1 (2015):
122-144.

[21] Isham, Valerie, and Mark Westcott. "A self-correcting point process."
Stochastic processes and their applications 8, no. 3 (1979): 335-347.

[22] H. T. Siegelmann and E. D. Sontag. Turing computability with neural nets.
Applied Mathematics Letters, 4:77–80, 1991.

[23] Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. "Sequence to sequence
learning with neural networks." In Advances in neural information processing
systems, pp. 3104-3112. 2014.

[24] H. Min, X. Jiahui, X. Shiguo, and Y. Fuliang. Prediction of chaotic time
series based on the recurrent predictor neural network. IEEE Transactions on
Signal Processing, 52:3409–3416, 2004.

[25] C. Xindi, Z. Nian, V. Ganesh K., and W. I. Donald C. Time series
prediction with recurrent neural networks trained by a hybrid psoˆaA¸Sea
algorithm. Neurocomputing, 70:2342–2353, 2007.

[26] C. Rohitash and Z. Mengjie. Cooperative coevolution of elman recurrent
neural networks for chaotic time series prediction. Neurocomputing,
86:116–123, 2012.

[27] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image
recognition. In Proceedings of the IEEE conference on computer vision and
pattern recognition, pp. 770–778, 2016.


# Zero-shot Image Restoration via Diffusion Inversion

###### Abstract

Recently, various methods have been proposed to solve Image Restoration (IR)
tasks using a pre-trained diffusion models leading to state-of-the-art
performance. A common characteristic among these approaches is that they alter
the diffusion sampling process in order to satisfy the consistency with the
corrupted input image. However, this choice has recently been shown to be sub-
optimal and may cause the generated image to deviate from the data manifold.
We propose to address this limitation through a novel IR method that not only
leverages the power of diffusion but also guarantees that the sample
generation path always lies on the data manifold. One choice that satisfies
this requirement is not to modify the reverse sampling , i.e., not to alter
all the intermediate latents, once an initial noise is sampled. This is
ultimately equivalent to casting the IR task as an optimization problem in the
space of the diffusion input noise. To mitigate the substantial computational
cost associated with inverting a fully unrolled diffusion model, we leverage
the inherent capability of these models to skip ahead in the forward diffusion
process using arbitrary large time steps. We experimentally validate our
method on several image restoration tasks. Our method SHRED achieves state of
the art results on multiple zero-shot IR benchmarks especially in terms of
image quality quantified using FID.

##  1 Introduction

Recent advances in the field of generative learning due to diffusion models
(ho2020denoising; song2019generative) and better architecture choices
(stylegan3; zhang2022styleswin) have led to models capable of generating
detailed high-resolution images. In addition to their data generation
capabilities, these models also provide a smooth representation of the learned
data distribution, which can be used for various applications, such as image
restoration. Indeed, different approaches (kawar2022denoising;
lugmayr2022repaint; wang2022zero) have emerged to solve inverse problems using
pretrained diffusion models. Those approaches start from a random noise vector
as the diffusion input and recursively alter the diffusion sampling process in
order to guarantee the data fidelity. After each diffusion reverse step, a
projection-based measurement consistency step is added to ensure the
consistency with the corrupted image. chung2022improving shows that this
procedure may cause the generated image to step outside the data manifold
during the iterative denoising process.

In this work, we devise a new zero-shot image restoration method that we call
in short SHRED (zero-SHot image REstoration via Diffusion inversion) which, by
construction, ensures that the sample generation path always lies on the data
manifold. To this end, we opt for a simple yet effective strategy: we do not
alter the reverse sampling , i.e., all the intermediate latents, once an
initial noise is sampled. More specifically, SHRED use a pre-trained Denoising
Diffusion Implicit Models (DDIM) (song2020denoising) and exploits the existing
deterministic correspondence between noise and images in DDIMs by casting the
inverse restoration problem as a latent estimation problem, i.e., where the
latent variable is the input noise to the diffusion model.Given a degraded
image, the pre-trained generative model allows us to retrieve the optimal
initial noise that, when applying the reverse diffusion sampling, generates
the closest clean image under the learnt image distribution. Since SHRED is an
optimization method that works by iteratively optimizing the initial noise,
multiple forward passes of the diffusion process are required which can be
computationally expensive. A single forward pass of a standard diffusion model
(with 1000 steps) takes in the order of minutes on a typical modern GPU. Thus,
a direct implementation of the optimization procedure in the case of the
Diffusion model as a black box would be computationally demanding and
ultimately impractical. To mitigate the substantial computational cost
associated with inverting a fully unrolled diffusion model, we leverage the
inherent capability of these models to skip ahead in the forward diffusion
process using arbitrary large time steps. Thanks to the non-Markovian marginal
distributions used in DDIM, our method introduces a hyperparameter $\delta t$
that can be used to prioritize either image quality or computational cost. We
show that by optimizing for the best initial noise that corresponds to the
unknown restored image, our method is able to achieve competitive image
performance across a wide range of image restoration tasks both in the blind
and non-blind setting. Our main contributions can be summarized as:

  1. 1.

We are the first to cast the IR task as a latent optimization problem in the
context of diffusion models where only the initial noise is optimized. This
design choice does not alter the intermediate diffusion latents and thus
provides more guarantees that the generated images lies in the in-distribution
manifold.

  2. 2.

We leverage the capabilty of DDIM to skip ahead in the forward diffusion
process by arbitrary time steps and propose an efficient and practical
diffusion model inversion in the context of image restoration.

  3. 3.

We achieve competitive results on both CelebA and ImageNet for different IR
tasks including image inpainting, super-resolution, compressed sensing and
blind deconvolution.

Figure 1: Image inpainting with SHRED. We show the flow during one iteration
of our optimization scheme of initial noise $x_{T}$. The dashed and single
line arrows denote the reverse and forward diffusion processes respectively.
We optimize the inpainting error $\mathcal{L}_{IR}$ only with respect to the
initial noise $x_{T}$. In our notation, $x_{0|t}$ is our intermediate estimate
of $x_{0}$ given $x_{t}$. The top and bottom row images show $x_{t}$ and
$x_{0|t}$ for different values of $t$ respectively. The reconstruction of
$x_{0|t}$ allows us to skip time steps and make the generation process and the
gradient back-propagation much more efficient.

##  2 Related Work

Methods for inverse problems have a long and rich literature spanning more
than 50 years (bates1986image). Within this field, we review methods that
relate to our approach in terms of their ability to be repurposed (see plug-
and-play methods), of using unfolded models (deep unfolding methods), of using
a pre-trained diffusion model (zero-shot approaches).

Supervised approaches  Supervised methods use explicit pairs of a degraded
image and its corresponding restored counterpart for model training. For
example, in the case of diffusion models, SR3 (saharia2022image) trains a
conditional diffusion model with synthetic low-/high-resolution image pairs as
the training data to solve super-resolution problems. The same idea is also
extended to other IR tasks (saharia2022palette). whang2022deblurring addresses
image deblurring by obtaining an initial reconstruction via a deterministic
predictor and then by training a diffusion model to predict the residual
error. Such methods are by definition not applicable to other image
degradations and capture undesired biases stemming for the pairws data
collection.

Zero-shot approaches  Recently, methods that can be repurposed to different
inverse problems have been called _zero-shot_. song2019generative proposes a
method based on guiding the reverse diffusion process with the unmasked region
to solve inpainting in a zero-shot manner. song2021solving proposes the use of
gradient guidance to solve inverse problems in the context of medical imaging.
choi2021ilvr applies low-frequency guidance from a reference image to solve
super-resolution. RePaint (lugmayr2022repaint) solves the inpainting problem
by guiding the diffusion process with the unmasked region. To condition the
generation process, the reverse diffusion iterations are altered by sampling
the unmasked regions using the given image information. DDRM
(kawar2022denoising) proposes an inverse problem solver based on posterior
sampling by introducing a variational inference objective for learning the
posterior distribution of the inverse problem. It uses SVD to decompose the
degradation operators which can be computational expensive when dealing with
high-dimensional matrices. DDNM (wang2022zero) proposes a zero-shot framework
for IR tasks based on the range-null space decomposition. The method works by
refining only the null-space contents during the reverse diffusion process,to
satisfy both data consistency and realness. chung2022improving argues that
relying on an iterative procedure consisting of reverse diffusion steps and a
projection-based consistency step runs the risk of stepping outside of the
data manifold, a risk they mitigate using an additional correction term.

##  3 Background

###  3.1 Denoising Diffusion Probabilistic Models

Denoising Diffusion Probabilistic Models (DDPM) (ho2020denoising) leverage
diffusion processes in order to generate high quality image samples. The aim
is to reverse the forward diffusion process that maps images to noise, either
by relying on a stochastic iterative denoising process or by learning the
explicit dynamics of the reverse process, e.g., through an ODE
(song2020denoising). More precisely the forward diffusion process maps an
image $x_{0}\sim p(x)$ to a zero-mean Gaussian
$x_{T}\sim\mathcal{N}(0,\mathbf{I})$ by generating intermediate images $x_{t}$
for $t\in(0,T]$ which are progressively noisier versions of $x_{0}$. DDPM
(ho2020denoising) adopts a Markovian diffusion process, where $x_{t}$ only
depends on $x_{t-1}$. Given a non-increasing sequence $\alpha_{1:T}\in(0,1]$,
the joint and marginal distributions of the forward diffusion process are
described by

$\displaystyle q(x_{1:T}|x_{0})$
$\displaystyle=\prod_{t=1}^{T}q(x_{t}|x_{t-1}),\text{ where
}q(x_{t}|x_{t-1})=\mathcal{N}\Bigg{(}\sqrt{\alpha_{t}}x_{t-1},\Big{(}1-\alpha_{t}\Big{)}\mathbf{I}\Bigg{)},$
(1)

which implies that we can sample $x_{t}$ simply by conditioning on $x_{0}$
with $\bar{\alpha}_{t}=\prod_{s\leq t}\alpha_{s}$ via

$\displaystyle q(x_{t}|x_{0})$
$\displaystyle=\mathcal{N}\Big{(}\sqrt{\bar{\alpha}_{t}}x_{0},(1-\bar{\alpha}_{t})\mathbf{I}\Big{)}.$
(2)

To invert the forward process, one can train a model $\epsilon_{\theta}$ to
minimize the objective

$\displaystyle\min_{\theta}~{}$
$\displaystyle~{}\mathbb{E}_{t\sim\mathcal{U}(0,1);x_{0}\sim
q(x);\epsilon\sim\mathcal{N}(0,\mathbf{I})}\Big{[}\|\epsilon-\epsilon_{\theta}(\sqrt{\bar{\alpha}_{t}}x_{0}+\sqrt{1-\bar{\alpha}_{t}}\epsilon,t)\|^{2}\Big{]}.$
(3)

Image samples $\hat{x}_{0}$ given the initial noise $x_{T}$, are obtained by
iterating for $t\in[1,T]$ the denoising update

$\displaystyle
x_{t-1}=\nicefrac{{1}}{{\sqrt{\alpha_{t}}}}(x_{t}-\epsilon_{\theta}(x_{t},t)\times\nicefrac{{(1-\alpha_{t})}}{{\sqrt{1-\bar{\alpha_{t}}}}})+\sigma_{t}z,$
(4)

with $z\sim\mathcal{N}(0,\mathbf{I})$, and
$\sigma_{t}^{2}=\frac{1-\bar{\alpha}_{t-1}}{1-\bar{\alpha}_{t}}(1-\alpha_{t})$.

song2020denoising point out that the quality of generated images highly
depends on the total number of denoising steps $T$. Thus, the inference loop
using Eq. 4 becomes computationally expensive. To reduce the computational
cost, they propose a Denoising Diffusion Implicit Model (DDIM)
(song2020denoising), which foregoes the Markovian assumption in favor of a
diffusion process
$q(x_{1:T}|x_{0})~{}=~{}q(x_{T}|x_{0})\prod_{t=2}^{T}q(x_{t-1}|x_{t},x_{0})$
where
$q(x_{T}|x_{0})=\mathcal{N}\Big{(}\sqrt{\bar{\alpha}_{T}}x_{0},(1-\bar{\alpha}_{T})\mathbf{I}\Big{)}$
and

$\displaystyle q(x_{t-1}|x_{t},x_{0})$
$\displaystyle=\mathcal{N}\Big{(}\sqrt{\bar{\alpha}_{t-1}}x_{0}+\sqrt{1-\bar{\alpha}_{t-1}-\sigma_{t}^{2}}.\nicefrac{{(x_{t}-\sqrt{\bar{\alpha}_{t}}x_{0})}}{{\sqrt{1-\bar{\alpha}_{t}}}},\sigma_{t}^{2}\mathbf{I}\Big{)}.$
(5)

When $\sigma_{t}=0$ for all $t$, the diffusion process is fully deterministic.
This means that when we start from the same noisy sample $x_{T}$ we obtain the
same generated image sample. Given $x_{t}$, one can first predict the denoised
observation $\hat{x}_{0}$, which is a prediction of $x_{0}$ given $x_{t}$

$\displaystyle\hat{x}_{0}$
$\displaystyle=\nicefrac{{(x_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon_{\theta}(x_{t},t))}}{{\sqrt{\bar{\alpha}_{t}}}}.$
(6)

then we can predict $x_{t-1}$ from $x_{t}$ and $\hat{x}_{0}$ using Eq. 5 by
setting $\sigma_{t}=0$

$x_{t-1}&=\sqrt{\bar{\alpha}_{t-1}}\hat{x}_{0}+\sqrt{1-\bar{\alpha}_{t-1}}{\hat{\omega}}$
(7)

with
$\hat{\omega}=\frac{x_{t}-\sqrt{\bar{\alpha}_{t}}\hat{x}_{0}}{\sqrt{1-\bar{\alpha}_{t}}}$
a direction pointing to $x_{t}$.

song2020denoising shows that this formulation allows DDIM to use fewer time
steps at inference by directly predicting $x_{t-k}$ with $k>1$ which results
in a more computationally efficient process using

$x_{t-k}&=\sqrt{\bar{\alpha}_{t-k}}\hat{x}_{0}+\sqrt{1-\bar{\alpha}_{t-k}}{\hat{\omega}}.$
(8)

##  4 Image Restoration via SHRED

() Original

() Reconstructed (PSNR=$44.10\pm 1.06$ )

() Original

() Reconstructed (PSNR=$42.43\pm 0.67$)

Figure 2:  Inversion results using our optimization scheme on samples from
both CelebA and ImageNet validation datasets. The PSNR mean and standard
deviation are computed over 10 runs.

In this section, we introduce the general setting of inverse problems that we
aim to solve and how generative models can be used to address the ambiguities
associated with this class of image restoration tasks. We then present our
zero-shot image restoration algorithm SHRED.

###  4.1 An Unbiased Formulation

Image restoration (IR) can be cast as a Maximum a Posteriori (MAP)
optimization problem (Zhang2020PlugandPlayIR)

$\displaystyle\hat{x}=\operatorname*{argmax}_{x\in\mathbb{R}^{N_{x}\times
M_{x}}}\log p(y|x)+\log p(x),$ (9)

where $\hat{x}\in\mathbb{R}^{N_{x}\times M_{x}}$ is the restored image and
$y\in\mathbb{R}^{N_{y}\times M_{y}}$ is the degraded image, and where $p(y|x)$
is the so-called likelihood and $p(x)$ the prior distribution. Linear inverse
problems describe IR tasks with linear degradation operators
$H:\mathbb{R}^{N_{x}\times M_{x}}\rightarrow\mathbb{R}^{N_{y}\times M_{y}}$
and often consider zero-mean additive noise $\eta$, such that the observed
degraded image $y$ can be written as

$y=H(x)+\eta.$ (10)

IR tasks such as image inpainting, denoising and super-resolution can all be
described using specific choices of $H$ and $\eta$. For instance, if we
vectorize the image $x$ and the output of the operator $H$, we can describe
image inpainting via a pixel projection operator $H(x)_{i}=x_{k[i]}$, where
$i=1,\dots,N_{y}\times M_{y}$, $k$ is a permutation of $N_{x}\times
M_{x}>N_{y}\times M_{y}$ indices, and $\eta=0$. The associated $H$ and $\eta$
for each image restoration task111A more accurate denomination of the
operators used in the linear image restoration problems should be _affine_
rather than linear. Nonetheless, we follow the terminology used in the
literature for simplicity. considered in this paper are provided in the
supplementary material. By applying the desired observation model to the MAP
formulation, one can aim to recover $\hat{x}$ given $y$ by using

$\hat{x}=\operatorname*{argmin}_{x\in\mathbb{R}^{N_{x}\times
M_{x}}}\|y-H(x)\|+\lambda\mathcal{R}(x),$ (11)

where $\|.\|$ is often a norm that depends on the nature of the noise $\eta$,
e.g., a zero-mean Gaussian noise $\eta$ induces a squared $L_{2}$ norm,
$\mathcal{R}$ is a term corresponding to the prior, and $\lambda>0$ is a
coefficient that regulates the interplay between the likelihood and the prior.

In plug-and-play methods (Zhang2020PlugandPlayIR) the prior $\mathcal{R}$ is
obtained through a pre-training that aims at denoising the images $x$.
However, using the prior $p(x)$ also captures the bias of the specific dataset
used for pre-training. Since we do not know where the prior will be used, we
argue that a bias could impact negatively the restoration process. Thus, we
propose to employ a formulation that implicitly assumes a uniform prior on the
domain $\Omega\subset\mathbb{R}^{N_{x}\times M_{x}}$ of valid reconstructions,
i.e.,
$\mathcal{R}(x)=-\log(p_{\mathcal{U}}(x))=-\log(\text{const}\cdot\mathbf{1}_{\Omega}(x))$,
where $\mathbf{1}_{\Omega}(x)$ is $1$ for $x$ in the support $\Omega$ and $0$
otherwise. This choice of $\mathcal{R}(x)$ is equivalent to considering an
unbiased prior over the support of the data distribution and results in the
following formulation

$\hat{x}=\arg\min_{x\in\Omega}\|y-H(x)\|.$ (12)

To ensure that $x\in\Omega$, we parameterize $x$ via the initial noise of a
pre-trained diffusion model. In the next section, we present our approach to
infer the initial noise such that the generated image minimizes Eq. 12.

###  4.2 An Efficient Diffusion Inversion

Algorithm 1 SHRED: Image Restoration via DDIM inversion

0: Degraded image $y$, step size $\delta t$, learning rate $\alpha$

0: Restored image $\hat{x_{0}}$

1: Initialize $x_{T}$ with random from $\mathcal{N}(0,1)$. If blind,
initialize $H_{\theta}$.

2: for $k:1\rightarrow N$ do

3: Initialize t = T

4: while t > 0 do

5:
$\hat{x}_{0|t}=(x_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon_{\theta}(x_{t},t))/\sqrt{\bar{\alpha}_{t}}$

6: $x_{t-{\delta t}}=\sqrt{\bar{\alpha}_{t-{\delta
t}}}\hat{x}_{0|t}+\sqrt{1-\bar{\alpha}_{t-{\delta
t}}}.\frac{x_{t}-\sqrt{\bar{\alpha}_{t}}\hat{x}_{0|t}}{\sqrt{1-\bar{\alpha}_{t}}}$

7: t = t - $\delta t$

8: end while

9: if BLIND then

10:
$x^{k+1}_{T}=x^{k}_{T}-\alpha\nabla_{x_{T}}\mathcal{L}_{IR}(x^{k}_{T},H_{\theta^{k}})$

11:
$\theta^{k+1}=\theta^{k}-\alpha\nabla_{\theta}\mathcal{L}_{IR}(x^{k}_{T},H_{\theta^{k}})$

12: else

13: $x^{k+1}_{T}=x^{k}_{T}-\alpha\nabla_{x_{T}}\mathcal{L}_{IR}(x^{k}_{T})$

14: end if

15: end for

16: Return the restored image $\hat{x}_{0}$

In this work, we adopt DDIM as our pre-trained generative process and we adopt
a fully deterministic diffusion process ($\sigma_{t}=0$). We propose a new
iterative inversion process, which we summarize in Algorithm 1. We adopt an
optimization-based iterative procedure to solve Eq. 12. In contrast to
kawar2022denoising; wang2022zero; lugmayr2022repaint, we explicitly use the
correspondence between image samples $x_{0}$ and their associated latent
vector $x_{T}$. SHRED starts from an initial noise instance
$x_{T}^{0}\sim\mathcal{N}(0,\mathbf{I})$ and at the end of each iteration $k$,
we update $x_{T}^{k}$. At each iteration, we first predict $\hat{x}_{0|t}$
from $x_{t}$ using the pre-trained DDIM model $\epsilon_{\theta}$.

$\displaystyle\hat{x}_{0|t}$
$\displaystyle=\frac{x_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon_{\theta}(x_{t},t)}{\sqrt{\bar{\alpha}_{t}}}.$
(13)

Rather than denoising $x_{T}$ iteratively for all the steps used in the pre-
training, we make larger steps by using intermediate estimates of
$\hat{x}_{0|t}$. We define a hyper-parameter $\delta t$ that controls the
number of denoising steps and we can directly jump to estimate $x_{t-{\delta
t}}$ from $\hat{x}_{0|t}$ and $x_{t}$ using

$x_{t-{\delta t}}=\sqrt{\bar{\alpha}_{t-{\delta
t}}}\hat{x}_{0|t}+\sqrt{1-\bar{\alpha}_{t-{\delta
t}}}.\frac{x_{t}-\sqrt{\bar{\alpha}_{t}}\hat{x}_{0|t}}{\sqrt{1-\bar{\alpha}_{t}}}.$
(14)

Higher step size $\delta t$ allows us to favor speed while a lower one will
favor fidelity. This iterative procedure results in an estimate of $x_{0}$
that is differentiable in $x_{T}$. We denote by $f$ the mapping between
$x_{T}$ and $x_{t}$. The estimate $x_{0}=f(x_{T})$ is used to update $x_{T}$
such that it minimizes the image restoration loss. Our method supports both
non-blind and blind image degradation.

Non-blind case In the non-blind case, $H$ is supposed to be known, the
restoration loss becomes

$\mathcal{L}_{IR}(x_{T})=\|y-H(f(x_{T}))\|$ (15)

Given an initial noise $x^{0}_{T}$, the optimization iteration is simply
derived as the following

$x^{k+1}_{T}=x^{k}_{T}-\alpha\nabla_{x_{T}}\mathcal{L}_{IR}(x^{k}_{T})$ (16)

where $\alpha$ is the learning rate.

Blind case In the blind case, $H$ is unknown and can be approximated by a
parametric function $H_{\theta}$, the restoration loss becomes

$\mathcal{L}_{IR}(x_{T},H_{\theta})=\|y-H_{\theta}(f(x_{T}))\|$ (17)

Given an initial noise $x^{0}_{T}$ and $H_{\theta^{0}}$, the optimization
iteration is simply derived as the following

$x^{k+1}_{T}=x^{k}_{T}-\alpha\nabla_{x_{T}}\mathcal{L}_{IR}(x^{k}_{T},H_{\theta^{k}})$
(18)
$\theta^{k+1}=\theta^{k}-\alpha\nabla_{\theta}\mathcal{L}_{IR}(x^{k}_{T},H_{\theta^{k}})$
(19)

where $\alpha$ is the learning rate.

One might wonder if the proposed fast inversion procedure suffers from local
minima, such that different initial noise samples $x_{T}$ might result in
different estimates of $x_{0}$. We show in Fig. 2 that our inversion method is
stable and is insensitive to the initialization. We use images from both
ImageNet and CelebA and perform denoising without noise (i.e., $H$ is the
identity function and $\eta=0$). As can be observed, the proposed inversion
method is stable.

##  5 Experiments

###  5.1 Image Restoration Tasks

In this work, we showcase our proposed method for different image restoration
tasks. Specifically, we evaluate our method on 4 typical noise-free IR tasks,
including image inpainting, $\times$4, $\times$8, $\times$16 and $\times$32
image super-resolution (SR), blind deconvolution, and compressed sensing (CS)
with a 1% and 5% sampling rates. For our super-resolution experiments, we
adopt a uniform downsampling while we use an anisotropic Gaussian kernel for
blind deconvolution. Our compressed sensing experiments use a uniform pixel
sampling strategy. Lastly, for our inpainting task, we consider a square
centered mask. For each image restoration task, we use the same degradation
operator for all methods. We evaluate our method both on ImageNet
(deng2009imagenet) and CelebA (liu2018large) at 256$\times$256 resolution. We
follow chung2022diffusion; chung2022improving and report the LPIPS
zhang2018unreasonable and FID heusel2017gans values obtained for each
experiment.

###  5.2 Experimental Results

Table 1: LPIPS/FID metrics for different degradation tasks on the CelebA dataset. The best and second best methods are in bold and underlined respectively. Method | Inpainting | SR $\times$8 | SR $\times$16 | SR $\times$32 | Blind Deconv | CR 1% | CR 5%
---|---|---|---|---|---|---|---
DIP ulyanov2018deep | 0.373/125.56 | 0.423/195.74 | 0.507/228.14 | 0.581/267.27 | - | - | -
SelfDeblur ren2020neural | - | - | - | - | 0.667/343.40 | - | -
Repaint lugmayr2022repaint | 0.028/7.82 | - | - | - | - | 0.583/181.57 | 0.389/142.61
DDRM kawar2022denoising | 0.039/8.69 |  0.239/123.54 | 0.385/139.15 | 0.492/149.12 | - | 0.567/162.22 | 0.462/149.79
DDNM wang2022zero |  0.018/6.09 |  0.299/113.76 |  0.376/122.95 |  0.447/143.86 | - |  0.570/179.43 |  0.319/105.06
SHRED |  0.021/6.51 | 0.304/78.84 |  0.325/85.82 |  0.416/110.75 |  0.362/90.28 |  0.558/139.88 |  0.344/85.42
Table 2: LPIPS/FID metrics for different degradation tasks on the ImageNet dataset. The best and second best methods are highlighted in bold and underlined respectively. Method | Inpainting | SR $\times$4 | SR $\times$8 | SR $\times$16 | Blind Deconv | CR 1% | CR 5%
---|---|---|---|---|---|---|---
DIP ulyanov2018deep | 0.175/75.12 | 0.369/114.83 | 0.544/267.31 | 0.738/376.35 | - | - | -
SelfDeblur ren2020neural | - | - | - | - | 0.719/368.94 | - | -
Repaint lugmayr2022repaint | 0.068/7.85 | - | - | - | - | 0.769/338.31 | 0.623/292.17
DDRM kawar2022denoising |  0.042/5.32 |  0.302/75.34 | 0.478/195.82 | 0.578/277.86 | - | 0.784/345.39 |  0.607/295.52
DDNM wang2022zero |  0.056/7.13 |  0.284/70.88 |  0.450/183.64 |  0.582/281.15 | - |  0.700/315.86 |  0.532/276.63
SHRED | 0.063/6.45 | 0.329/ 65.78 |  0.394/152.74 |  0.470/183.11 |  0.467/185.37 |  0.736/295.12 | 0.642/262.17

Our experimental results are summarized in Tables 1 and 2 for CelebA and
ImageNet, respectively. We report the performance of SHRED as well as DIP
(ulyanov2018deep), SelfDeblur (whang2022deblurring), RePaint
(lugmayr2022repaint), DDRM (kawar2022denoising) and DDNM (wang2022zero). We
showcase the versatile nature of SHRED and its ability to restore degraded
images with a higher level of details thanks to its explicit use of the
correspondence property of the underlying pre-trained DDIM song2020denoising
model. We report the performance of super-resolution methods in Tables 1 and 2
for the $\times$8, $\times$16 and $\times$32 upscaling factors on CelebA and
$\times$4, $\times$8 and $\times$16 on ImageNet respectively.

Masked | Repaint | DDRM | DDNM | SHRED | GT
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
Figure 3: Visual results of inpaintings on CelebA.

For both datasets, we observe that our method is ranked first in both LPIPS
and FID. We observe a similar pattern as in our super-resolution experiments
for compressed sensing where SHRED generates more detailed images and achieves
a better FID while being on par or slightly worse in terms of LPIPS.

| Bicubic | DDNM | SHRED
---|---|---|---
$\times 8$ |  |  |
$\times 16$ |  |  |

| Bicubic | DDNM | SHRED
---|---|---|---
$\times 8$ |  |  |
$\times 16$ |  |  |

Figure 4: Visual results of super-resolution with different upsampling
factors.

For the case of blind deconvolution, SHRED largely outperforms SelfDeblur
(whang2022deblurring) both in terms of FID and LPIPS which highlights its
ability to also tackle blind restoration tasks through joint optimization. We
illustrate this in Fig. 6 on two blurred images using a large blur kernel. Due
to the significant blur, SelfDeblur is unable to restore the degraded image.
SHRED on the other hand successfully deblurs the image especially around the
main object in the image. Lastly, in the case of image inpainting SHRED is
ranked second and third on CelebA and ImageNet respectively. On CelebA, SHRED
achieves a comparable FID and LPIPS to DDNM while significantly outperforming
other inpainting methods. We showcase the different considered methods in Fig.
3, where we observe that SHRED is capable of generating highly detailed and
consistent features in the masked regions.

Blurry | SelfDeblur | SHRED | GT
---|---|---|---
|  |  |
|  |  |
Figure 5:  Visual results of blind deconvolution using a random Gaussian
kernel with size $41\times 41$.

|  |  |
---|---|---|---
|  |  |
Figure 6:  Robustness of SHRED to the initial noise $x_{T}$.

|  |  |  |
---|---|---|---|---
|  |  |  |
Figure 7:  A real application of SHRED.

##  6 Ablations Study

###  6.1 Effect of different hyper-parameters

We study the influence of hyper-parameters: the learning rate $\alpha$, the
number of iterations $N$ and the step size $\delta t$, on SHRED performance.
Table 4 shows the effect of varying the step size $\delta t$ on both FID and
the computation time. $\delta t=100$ gives the best trade-off between the
speed and the visual quality. In Table 6, we report the FID values achieved by
SHRED for different learning rates. SHRED acheives competitive FID with the
different learning rates and this shows that it is robust enough to the choice
of learning rate. Table 6 shows SHRED performance for different values of $N$
(the total number of iterations). SHRED needs around $100$ iterations to
achieve the best FID indicating that a limited number of iterations is
sufficient to produce a decent reconstruction. We note that $N$ can be set
automatically using the criteria $\mathcal{L}_{IR}<\epsilon$ . We empirically
observe that tuning on a small set generalizes well in the zero-shot setting.
For all IR tasks, $\delta t=100$ and $\alpha=0.003$ produces competitive
performance.

###  6.2 SHRED Robustness

Robustness to the initial noise We fix the degraded image and we test our
method by varying the initial noise $x_{T}^{0}$. Figure6 shows that SHRED is
robust to the input noise initialization and that for each time it can output
a different plausible solution.
Robustness to real-world degradations We apply our method to the task of old
image enhancement where the images are real and collected from internet
depicting complex and unknown degradation (noise, jpeg artifacts, blur..). The
problem is framed as the mixture of image colorization and super-resolution.
Figure 7 shows SHRED is able to enhance the image quality and that is robust
to the different degradation.

###  6.3 Computational Cost

In Table 4, we report the runtime per image of the different compared methods.
We denote by Naive inversion a similar approach as SHRED that works by
inverting the fully unrolled diffusion model. SHRED is $\times 100$ time
faster than the Naive inversion. Despite being an iterative method, SHRED has
a reasonable runtime making it a practical zero-shot IR method. We note that
the reported speed is using $\delta t=100$ and a further speed boost is
possible by opting for a higher value of $\delta t$ at a small reduction of
the visual quality.

Method | Time[s] |
---|---|---
DIP ulyanov2018deep | 520 |
DDRM kawar2022denoising | 13 |
DDNM wang2022zero | 12 |
Naive Inversion | 5750 |
SHRED | 55 |
Table 3: Runtime (in seconds) comparison of different methods on CelebA per
image on super-resolution. All experiments are conducted on a Geforce GTX 1080
Ti.

Step size ($\delta t$) | 50 | 100 | 200 |
---|---|---|---|---
FID | 6.38 | 6.51 | 8.32 |
Time/Iteration (ms) | 2330 | 1150 | 576 |
Table 4: Effect of the step size $\delta t$ on the visual quality and the
runtime of image inpainting on CelebA.

$\alpha$ | $5\times 10^{-4}$ | $10^{-3}$ | $2.5\times 10^{-3}$ | $5\times 10^{-3}$
---|---|---|---|---
FID | 87.85 | 72.36 | 74.52 | 77.85
Table 5: Effect of the learning rate $\alpha$ on the visual quality SR $\times
16$ on CelebA.

$N$ | 50 | 75 | 100 | 125 | 150
---|---|---|---|---|---
FID | 78.03 | 75.63 | 74.31 | 73.85 | 74.42
Table 6: Effect of the number of iterations $N$ on the visual quality SR
$\times 8$ on CelebA.

##  7 Conclusion

We have introduced SHRED, a zero-shot framework for solving IR tasks by using
pre-trained diffusion generative models as learned priors. Our method exploits
the deterministic correspondence between noise and images in DDIMs by casting
the inverse restoration problem as a latent estimation problem. We demonstrate
the empirical successes of SHRED on various IR problems and datasets.

##  Appendix A Appendix

###  A.1 Implementation Details

In the next sections, we show the implementation details in terms of
degradation operators and training hyper-parameters for every degradation
task.We choose a set of 100 random images from ImageNet 1K and CelebA 1K
datasets with image size $256\times 256$ for validation. For a fair
comparison, we use the same pre-trained denoising models used in wang2022zero
and apply them to all the diffusion-based methods. We use the Adam optimizer
with 400 as the maximum number of iterations for all IR tasks. The step size
$\delta t$ is set to $100$. All experiments are conducted on a Geforce GTX
1080 Ti.

|  |  |  |
---|---|---|---|---
|  |  |  |
|  |  |  |
Figure 8:  An application of SHRED on a non-linear inverse problem (non-
uniform deblurring). The top row shows degraded images with non-uniform blur.
The second row depicts the results of our method. The bottom row shows the
ground truth.

###  A.2 Super-Resolution

For superresolution, we use $\times 4$, $\times 8$, and $\times 16$ uniform
downsampling factors for ImageNet and $\times 8$, $\times 16$, and $\times 32$
uniform downsampling factors for CelebA. During training, we use Adam as our
optimizer with a learning rate of $0.003$ and $70$ iterations. We also add
comparisons with both OID chen2020oid and Chen et al. chen2020enhanced .
Additional visual results are depicted in Fig. 11, Fig. 12 and Fig. 13. While
other methods tend to generate over-smoothed images especially at higher
downsampling factors, our method (SHRED) outputs sharper and more realistic
images. For instance, SHRED is able to generate detailed grass and hair
textures in Fig. 11 and Fig. 12 especially at $\times 16$ upscaling where
other methods fail.

###  A.3 Blind Deconvolution

For Blind Deconvolution, we apply a random anisotropic Gaussian kernel of size
41x41. During training, we use Adam as our optimizer with a learning rate of
$0.003$ and $150$ iterations. Visual results are shown in Fig. 16 and Fig. 17.
Despite the heavy blur, SHRED is able to better deblur the main object present
in the considered image compared to other methods.

###  A.4 Compressed Sensing (CS)

For Compressed Sensing, we randomly subsample $1\%$ and $5\%$ of the total
available pixels. During training, we use Adam as our optimizer with a
learning rate of $0.01$ and $300$ iterations. More visual results are depicted
in Fig. 14 and Fig. 15. SHRED performs better than the other methods at
preserving the identity of the original image especially at the higher
subsampling rates. Indeed, we see in the second and forth rows of Fig. 14 that
other method hallucinate new faces instead of reconstructing the correct one.

###  A.5 Inpainting

For Inpainting, we apply a square mask for CelebA and a text mask for
ImageNet. During training, we use Adam as our optimizer with a learning rate
of $0.01$ and $400$ iterations. We show additional results with different
masks in Fig. 9 and Fig. 10.

Masked | Repaint | DDRM | DDNM | SHRED | GT
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 9: Visual results of inpaintings on CelebA. Masked | Repaint | DDRM | DDNM | SHRED | GT
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 10: Visual results of inpaintings on ImageNet.

|  $\times$8 |  $\times$16 | $\times$32
---|---|---|---
Bicubic |  |  |
DDNM |  |  |
SHRED |  |  |
|  |  |
|  | GT |

|  $\times$4 |  $\times$8 | $\times$16
---|---|---|---
Bicubic |  |  |
DDNM |  |  |
SHRED |  |  |
|  |  |
|  | GT |

Figure 11: Visual results of super-resolution with different upsampling
factors.

|  $\times$8 |  $\times$16 | $\times$32
---|---|---|---
Bicubic |  |  |
DDNM |  |  |
SHRED |  |  |
|  |  |
|  | GT |

|  $\times$4 |  $\times$8 | $\times$16
---|---|---|---
Bicubic |  |  |
DDNM |  |  |
SHRED |  |  |
|  |  |
|  | GT |

Figure 12: Visual results of super-resolution with different upsampling
factors.

|  $\times$8 |  $\times$16 | $\times$32
---|---|---|---
Bicubic |  |  |
DDNM |  |  |
SHRED |  |  |
|  |  |
|  | GT |

|  $\times$4 |  $\times$8 | $\times$16
---|---|---|---
Bicubic |  |  |
DDNM |  |  |
SHRED |  |  |
|  |  |
|  | GT |

Figure 13: Visual results of super-resolution with different upsampling factors. | Masked | Repaint | DDRM | DDNM | SHRED | GT
---|---|---|---|---|---|---
5 % |  |  |  |  |  |
1 % |  |  |  |  |  |
5 % |  |  |  |  |  |
1 % |  |  |  |  |  |
5 % |  |  |  |  |  |
1 % |  |  |  |  |  |
Figure 14: Visual results of CS on CelebA. | Masked | Repaint | DDRM | DDNM | SHRED | GT
---|---|---|---|---|---|---
5 % |  |  |  |  |  |
1 % |  |  |  |  |  |
5 % |  |  |  |  |  |
1 % |  |  |  |  |  |
5 % |  |  |  |  |  |
1 % |  |  |  |  |  |
Figure 15: Visual results of CS on ImageNet. Blurry | SelfDeblur | OID | Chen et al. | SHRED | GT
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 16:  Visual results of blind deconvolution using a random Gaussian kernel with size $41\times 41$ on CelebA. Blurry | SelfDeblur | OID | Chen et al. | SHRED | GT
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 17:  Visual results of blind deconvolution using a random Gaussian
kernel with size $41\times 41$ on ImageNet.