# Delta Keyword Transformer: Bringing Transformers to the Edge through
Dynamically Pruned Multi-Head Self-Attention

Zuzana Jelčicová  Technical University of Denmark; and Demant A/SKongens
Lyngby; and SmørumDenmark2800<EMAIL_ADDRESS>and  Marian Verhelst  MICAS, KU
LeuvenLeuvenBelgium3000<EMAIL_ADDRESS>
(2022)

###### Abstract.

Multi-head self-attention forms the core of Transformer networks. However,
their quadratically growing complexity with respect to the input sequence
length impedes their deployment on resource-constrained edge devices. We
address this challenge by proposing a dynamic pruning method, which exploits
the temporal stability of data across tokens to reduce inference cost. The
threshold-based method only retains significant differences between the
subsequent tokens, effectively reducing the number of multiply-accumulates, as
well as the internal tensor data sizes. The approach is evaluated on the
Google Speech Commands Dataset for keyword spotting, and the performance is
compared against the baseline Keyword Transformer. Our experiments show that
we can reduce $\sim 80\%$ of operations while maintaining the original
$98.4\%$ accuracy. Moreover, a reduction of $\sim 87-94\%$ operations can be
achieved when only degrading the accuracy by 1-4%, speeding up the multi-head
self-attention inference by a factor of $\sim 7.5-16$.

Transformers, delta computations, pruning, compression, keyword spotting, edge
devices

††copyright: rightsretained††journalyear: 2022

##  1\. Introduction

The Transformer architecture (Vaswani et al., 2017) is an emerging type of
neural networks that has already proven to be successful in many different
areas such as natural language processing (Devlin et al., 2019; Liu et al.,
2019b; Brown et al., 2020; Radford et al., 2019), computer vision (Dosovitskiy
et al., 2021; Touvron et al., 2021; Yuan et al., 2021; Neimark et al., 2021),
and speech recognition (Gulati et al., 2020; Chen et al., 2021; Chang et al.,
2021; Liu et al., 2021). Its success lies in the multi-head self-attention
(MHSA), which is a collection of attention mechanisms executed in parallel.
Although Transformers achieve state-of-the-art results, deployment to
resource-constrained devices is challenging due to their large size and
computational complexity that grows quadratically with respect to the sequence
length. Hence, self-attention, despite being extremely efficient and powerful,
can easily become a bottleneck in these models. A widely used compression
technique to reduce the size and computations of DNNs is pruning, that has
been extensively researched throughout the years (Han et al., 2015, 2016;
Frankle and Carbin, 2019; Anwar et al., 2017). An increasing number of works
focusing on MHSA pruning recently emerge. These mainly aim for reducing the
number of attention heads in each Transformer layer (Michel et al., 2019;
Voita et al., 2019; McCarley, 2019), and token pruning (Kim et al., 2021;
Goyal et al., 2020; Kim and Cho, 2021; Wang et al., 2021). Eliminating
attention heads completely to speed up the processing might significantly
impact accuracy. Therefore, token (a vector in the sequence) pruning
represents a more suitable approach, where attention heads are preserved and
only unnecessary tokens within the individual heads are removed. However, most
of the methods above i) require demanding training procedures that hinder
utilizing a single method across various models and applications without
unnecessary overhead, and ii) focus on coarse-grained pruning.
In this work, we further push pruning to finer granularity, where individual
features within tokens are discarded at runtime using a threshold in the MHSA
pipeline. The reduction is based on the comparison of similarities between
corresponding features of subsequent tokens, where only the above-threshold
delta differences are stored and used for performing the multiplications
(MACs). This technique significantly reduces computational complexity during
inference and offers intermediate data compression opportunities. Our method
does not require any training and can, therefore, be used directly in the
existing pre-trained Transformer models. Moreover, no special and expensive
hardware has to be developed as only comparisons are used in the algorithm.
The evaluation is done on a pretrained Keyword Transformer model (KWT) (Berg
et al., 2021) using the Google Speech Commands Dataset (GSCD) (Warden, 2018)
with the focus on the accuracy-complexity trade-off. The results show that the
number of computations can be reduced by $4.2x$ without losing any accuracy,
and $7.5x$ while sacrificing 1% of the baseline accuracy. Furthermore, the
processing of the original MHSA block can be sped up by a factor of $\sim 16$
while still achieving high accuracy of $\sim 95\%$. Therefore, this work
represents the next step to enable efficient inference of Transformers in low-
power edge devices with the tinyML constraints.

##  2\. Related Work

Different approaches have been used to reduce the computational complexity of
the MHSA, such as cross-layer parameter sharing (Lan et al., 2020), trimming
individual weights (Gordon et al., 2020) or removing encoders by distillation
(Sanh et al., 2019; Sun et al., 2019; Liu et al., 2019a; Sun et al., 2020;
Tang et al., 2019). Recent research (Michel et al., 2019; Li et al., 2021;
Voita et al., 2019; McCarley, 2019) demonstrates that some attention heads can
be eliminated without degrading the performance significantly. However, in
order to obtain substantial computational savings and thus inference time
gains, a considerable portion of heads would have to be discarded, inevitably
leading to noticeable accuracy drops.
Other works focus on token pruning instead of removing redundant parameters.
In (Goyal et al., 2020), redundant word-vectors are eliminated, outperforming
previous distillation (Sanh et al., 2019; Sun et al., 2019) and head-pruning
methods (Michel et al., 2019). However, it requires training of a separate
model for each efficiency constraint. This issue is resolved in (Kim and Cho,
2021) by adopting one-shot training that can be used for various inference
scenarios, but the training process is complicated and involves multiple
steps. Cascade pruning on both the tokens and heads is applied in (Wang et
al., 2021), i.e., once a token and/or head is pruned, it is removed in all
following layers. Nonetheless, this approach requires sorting of tokens and
heads depending on their importance dynamically to select the top-k
candidates, which needs specialized hardware. Similar to our work, recently
published (Kim et al., 2021) also adopts a threshold-based pruning approach,
which removes unimportant tokens as the input passes through the Transformer
layers. However, this method requires a three-step training procedure to
obtain a per-layer learned threshold, which again prevents to easily deploy
the technique across a wide range of pre-trained networks. Most of the
previous methods, moreover, only focus on optimizing Transformers for the
natural language processing task.
The idea of threshold-based pruning using delta values for performing
computations has already been explored for other types of DNNs, such as
recurrent (Neil et al., 2017) and convolutional (Habibian et al., 2021) neural
networks. However, incorporating a delta threshold in these networks results
in significant memory overhead, as it requires storing intermediate states and
activations. This issue is eliminated in our Delta Transformer, where almost
no additional resources are required.

##  3\. The Keyword Transformer

The typical Transformer encoder (Vaswani et al., 2017) adopted in KWT consists
of a stack of several identical Transformer blocks. Each Transformer block
comprises of Multi-Head Self-Attention (MHSA), Multi-Layer Perceptron (MLP),
layer normalizations, and residual connections as illustrated in Figure 1. The
key component in Transformers is the MHSA containing several attention
mechanisms (heads) that can attend to different parts of the inputs in
parallel.

Figure 1. A high-level overview of the KWT model along with its dimensions.
Red lines denote the residual connections.

A high-level overview of the KWT model along with its dimensions. Red lines
denote the residual connections.

We base our explanation on the KWT, proposed in (Berg et al., 2021). This
model takes as an input the MFCC spectrogram of T non-overlapping patches
$X_{MFCC}\in R^{T\,x\,F}$, with $t=1,...,T$ and $f=1,...,F$ corresponding to
time windows and frequencies, respectively. This input is first mapped to a
higher dimension $d$ using a linear projection matrix $W_{0}\in R^{F\,x\,d}$
along the frequency dimension, resulting in T tokens of dimension d. These are
then concatenated with a learnable class embedding token $X_{CE}\in
R^{1\,x\,d}$ representing a global feature for the spectrogram. Subsequently,
a learnable positional embedding $X_{PE}\in R^{(T+1)\,x\,d}$ is added to form
a final input to the Transformer encoder:

(1) $\small X=[X_{CE};X_{MFCC}W_{0}]+X_{PE}$

The Transformer encoder multiplies the input $X$ with the projection matrices
$W_{Q},\,W_{K},\,W_{V}\in R^{d\,x\,d}$, producing Query ($Q$), Key ($K$), and
Value ($V$) input embedding matrices:

(2) $\vspace{-0.15cm}\small Q=XW_{Q};\qquad K=XW_{K};\qquad
V=XW_{V}\vspace{0.01cm}$

The matrices are then divided into $k$ attention heads to perform the self-
attention computations in parallel, where each of the heads $i=1,2,..,k$ is
given by:

(3) $\vspace{-0.2cm}\small
head_{i}=attention(Q_{i},K_{i},V_{i})=softmax\left(\frac{Q_{i}(K_{i})^{T}}{\sqrt{d_{h}}}\right)V_{i}$

The MHSA is defined as a concatenation of the attention heads, weighted by a
projection matrix $W_{P}\in R^{kd_{h}\,x\,d}$, where $d_{h}=d/k$:

(4) $\small X_{MHSA}(Q,K,V)=[head_{1},head_{2},...,head_{k}]W_{P}$

The MHSA output is then added to the input $X$ with a residual connection and
passed though the first layer normalization and the MLP block, followed by
another addition of a residual input and second normalization:

(5) $\small X_{LN1}=LN(X_{MHSA}+X);\qquad X_{LN2}=LN(X_{MLP}+X_{LN1})$

This structure is repeated $L$ times, denoting layers, to create an
architecture of stacked Transformer layers.
In the KWT model, the MLP block is a two-layer feed-forward neural network
using a GELU activation function after the first layer. The class embedding
vector is extracted from the output of the last Transformer block to perform
classification.
Three KWT models are proposed in the original work: KWT-1 (607k parameters,
$97.72\%\pm 0.01$ accuracy), KWT-2 (2,394k parameters, $98.21\%\pm 0.06$
accuracy), and KWT-3 (5,361k parameters, $98.54\%\pm 0.17$ accuracy). We
selected KWT-3 for our experiments, as it poses the biggest challenge as well
as potential for compressing and reducing the computational complexity. The
KWT-3 configuration is listed in Table 1.

Table 1. Configuration of the KWT-3 architecture Model | dim $d$ | dim $d_{MLP}$ | heads $k$ | layers $L$ | #params
---|---|---|---|---|---
KWT-3 | 192 | 768 | 3 | 12 | 5,361k

##  4\. KWT model Analysis

The attention mechanism involves MACs of two matrices, resulting in $O(n^{2})$
time and space complexity. However, as all tokens attend to each other, a
certain level of redundancy is expected to be found in the system due to
diffusion of information. Therefore, we analyze the KWT model on the GSCD to
observe the degree of change across the tokens as they pass though the MHSA.
We feed multiple different keywords through the 12-layer KWT and inspect the
MHSA inputs as well as intermediate results within the block. While
considerable correlation across the tokens is expected for the initial input
and intermediate results in the first layer, it is noteworthy to observe such
behavior also in the MHSA of deeper layers, which is in line with cosine
similarity measurements on word-vectors performed in (Goyal et al., 2020).
Correlation is illustrated in Figure 2 showing the input $X$ (top) together
with the difference between subsequent rows of this tensor (bottom), for the
7th layer of a keyword $right$. Figure 3 repeats the same analysis for the
softmax output of layer 7. It is clear that there is a significant amount of
correlation between consecutive tokens, which opens up opportunities for data
compression and/or computational data reuse. For example, $\sim 84\%$ of the
differences between corresponding features of subsequent tokens in $X$ are
smaller than 1% of the dynamic range of $X$ (7th layer). Such a tendency was
observed for all voice-containing input sequences.

Figure 2. Input data to the 7th Transformer layer at the top along with its
delta version at the bottom for keyword right.

Input data to the 7th Transformer layer at the top along with its delta
version at the bottom for keyword right.

Figure 3. Softmax output of the 7th Transformer layer at the top along with
its delta version at the bottom for the keyword $\mathbf{right}$. The figure
illustrates three attention heads.

Softmax output of the 7th Transformer layer at the top along with its delta
version at the bottom for the keyword $\mathbf{right}$. The figure illustrates
three attention heads.

Moreover, when analyzing intermediate tensors from inputs of the
$\\_silence\\_$ class, even larger data redundancy can be observed (Figure 4).
It is clear that fully computing every single token would be a waste of
computational and memory resources.

Figure 4. Input data to the 7th Transformer layer for
$\mathbf{\\_silence\\_}$.

Input data to the 7th Transformer layer for $\mathbf{\\_silence\\_}$.

All these observations demonstrate that the amount of a significant change
across the tokens constitutes only a small portion of the whole. Hence,
introducing a threshold for recomputing could drastically decrease the
computational load and inference time. Furthermore, exploiting sparsity across
the tokens can also offer data compression. Therefore, we propose a delta
algorithm that utilizes a threshold to discard insignificant values, further
described in Section 5.

##  5\. Delta algorithm

The objective of the delta algorithm is to transform a dense matrix-vector
multiplication into a highly-sparse matrix-vector multiplication to reduce
computational complexity and enable data compression, where only non-zero
deltas are stored and used for computations.
The input $X$ always starts with the class embedding vector, followed by the
first input vector. These two vectors (rows of the tensors) will always be
left untouched throughout the complete MHSA pipeline. Every subsequent token
after these will be represented by its delta value. This delta change $\Delta
X(t)$ is calculated as the difference between the current input $X(t)$ and
reference vector $\hat{X}(t-1)$. Only delta differences larger than a
threshold $\theta$ are retained and used to update the reference vector
$\hat{X}(t)$:

(6) $\small\Delta X(t)=\begin{cases}\small X(t)-\hat{X}(t-1)&\small\text{if
$|X(t)-\hat{X}(t-1)|\,>\,\theta$}\\\ \small 0&\small\text{otherwise}\\\
\end{cases}$ (7) $\small\hat{X}(t)=\begin{cases}\small X(t)&\small\text{if
$|X(t)-\hat{X}(t-1)|\,>\,\theta$}\\\
\small\hat{X}(t-1)&\small\text{otherwise}\\\ \end{cases}$

Where the $\hat{X}$ vector is initialized to 0s and updated once the first
token arrives. Figure 5 visualizes this encoding over three tokens with
$\theta=1.0$. The top row represents the first input vector that is left
untouched (no delta algorithm applied). The orange and green colors in
$\hat{X}$ show which values from the current input $X$ are propagated for the
next token. White $\Delta X$ positions denote values of which magnitude equals
to/is below $\theta$ and thus are skipped.

Figure 5. Delta algorithm example across three tokens with threshold
$\mathbf{\theta=1.0}$. The top row corresponds to the first input vector that
is always left untouched (no threshold).

Delta algorithm example across three tokens. The threshold is set to
$\mathbf{\theta=1.0}$.

We apply the delta encoding of data at six different places in the MHSA: layer
input $X$, matrices $K$ and $Q$, scaled $QK^{T}$, softmax output, and the
attention head output. While the computations of delta values are the same
everywhere, the subsequent operations with these deltas differ depending on
whether i) a delta-encoded matrix is multiplied with a regular matrix, ii) two
delta-encoded matrices are multiplied together, or iii) a non-linear $softmax$
function is applied. These three versions are described in the next
subsections.

###  5.1. Delta-regular matrix multiplication

Thanks to the delta representation, only non-zero $\Delta X$ are stored and
used for multiplications as visualized in Figure 6. A weight matrix is denoted
as $W$, and indices for $\Delta xw$ in the result matrix $R$ are excluded for
clarity.

Figure 6. Baseline delta algorithm.

Baseline delta algorithm.

The output $R(t)$ of the tensor operation can hence be computed by
accumulating the result of the previous reference token $R(t-1)$ with the
multiplication results of the weights with the delta values only. The updated
$R(t)$ will then be the new baseline for the upcoming token:

(8) $\small R(t)=\Delta X(t)W+R(t-1)$

With $R(0)$ initialized to 0. These delta multiplications are used in
$XW_{Q}$, $XW_{K}$, $XW_{V}$, $softmaxV$ and
$[head_{1},head_{2},head_{3}]W_{P}$.

###  5.2. Delta-delta matrix multiplication

As a result of the delta encoding, both $Q$ and $K$ will be expressed in their
delta versions, and the multiplications will thus be slightly modified. This
is described below and illustrated in Figure 7 in a general form, with
matrices $A$ and $B$ representing $Q$ and $K^{T}$, respectively.

Figure 7. Delta algorithm for $QK^{T}$ represented with matrices $A$ and $B$.

Delta algorithm for $QK^{T}$ represented with matrices $A$ and $B$.

The multiplication of the first $A$ row with the first $B$ column is done as
usually without using deltas:

(9) $\small r_{00}=a_{00}b_{00}+a_{01}b_{10}+a_{02}b_{20}$

Then, the multiplication of the first $A$ row and second $B$ column exploits
the delta approach in horizontal direction, where the
$a_{00}b_{00}+a_{01}b_{10}+a_{02}b_{20}$ expression can be replaced with
$r_{00}$ from eq. 9 (marked with red):

(10) $\displaystyle\small r_{01}$ $\displaystyle=a_{00}(b_{00}+\Delta
b_{01})+a_{01}(b_{10}+\Delta b_{11})+a_{02}(b_{20}+\Delta b_{21})$
$\displaystyle=a_{00}b_{00}+a_{00}\Delta b_{01}+a_{01}b_{10}+a_{01}\Delta
b_{11}+a_{02}b_{20}+a_{02}\Delta b_{21}$
$\displaystyle=\boldmath{{\color[rgb]{1,0,0}r_{00}}}+a_{00}\Delta
b_{01}+a_{01}\Delta b_{11}+a_{02}\Delta b_{21}$

Similarly, calculating results in the vertical direction for the rows of $A$
and first column of $B$ is given by:

(11) $\displaystyle\small r_{10}$ $\displaystyle=b_{00}(a_{00}+\Delta
a_{10})+b_{10}(a_{01}+\Delta a_{11})+b_{20}(a_{02}+\Delta a_{12})$
$\displaystyle=b_{00}a_{00}+b_{00}\Delta a_{10}+b_{10}a_{01}+b_{10}\Delta
a_{11}+b_{20}a_{02}+b_{20}\Delta a_{12}$
$\displaystyle=\boldmath{{\color[rgb]{1,0,0}r_{00}}}+\Delta
a_{10}b_{00}+\Delta a_{11}b_{10}+\Delta a_{12}b_{20}$

An approach for multiplications for all the other positions is demonstrated on
the second $A$ row and second $B$ column:

(12) $\displaystyle\small r_{11}$
$\displaystyle=({\color[rgb]{0,0,1}a_{00}}+{\color[rgb]{0,0,1}\Delta
a_{10}})({\color[rgb]{0,0,1}b_{00}}+{\color[rgb]{0,0,1}\Delta
b_{01}})+({\color[rgb]{0,1,0}a_{01}}+{\color[rgb]{0,1,0}\Delta
a_{11}})({\color[rgb]{0,1,0}b_{10}}+{\color[rgb]{0,1,0}\Delta b_{11}})$
$\displaystyle+({\color[rgb]{1,.5,0}a_{02}}+{\color[rgb]{1,.5,0}\Delta
a_{12}})({\color[rgb]{1,.5,0}b_{20}}+{\color[rgb]{1,.5,0}\Delta b_{21}})$
$\displaystyle={\color[rgb]{0,0,1}a_{00}b_{00}}+{\color[rgb]{0,0,1}a_{00}\Delta
b_{01}}+{\color[rgb]{0,0,1}\Delta a_{10}b_{00}}+{\color[rgb]{0,0,1}\Delta
a_{10}\Delta b_{01}}$
$\displaystyle+{\color[rgb]{0,1,0}a_{01}b_{10}}+{\color[rgb]{0,1,0}a_{01}\Delta
b_{11}}+{\color[rgb]{0,1,0}\Delta a_{11}b_{10}}+{\color[rgb]{0,1,0}\Delta
a_{11}\Delta b_{11}}$
$\displaystyle+{\color[rgb]{1,.5,0}a_{02}b_{20}}+{\color[rgb]{1,.5,0}a_{02}\Delta
b_{21}}+{\color[rgb]{1,.5,0}\Delta a_{12}b_{20}}+{\color[rgb]{1,.5,0}\Delta
a_{12}\Delta b_{21}}$
$\displaystyle={\color[rgb]{1,0,0}r_{01}}+{\color[rgb]{1,0,0}r_{10}}-{\color[rgb]{1,0,0}r_{00}}+{\color[rgb]{0,0,1}\Delta
a_{10}\Delta b_{01}}+{\color[rgb]{0,1,0}\Delta a_{11}\Delta
b_{11}}+{\color[rgb]{1,.5,0}\Delta a_{12}\Delta b_{21}}$

Where different colors mark each of the three multiplications. Simplifying
parenthesis shows that the expressions not involving any deltas can be
substituted with $r_{00}$. Next, the terms with $\Delta b$ are replaced with
$r_{01}$, while those containing $\Delta a$ with $r_{10}$. Since $r_{00}$,
$r_{01}$, and $r_{10}$ have already been computed in previous timesteps, we
only need to do the (sparse) delta multiplications themselves and subtract the
$r_{00}$ result as it is present in both $r_{01}$ and $r_{10}$. These steps
are then applied to all the other slots as shown in Figure 7.

###  5.3. Delta for softmax

Delta algorithm cannot be directly applied for softmax as this function
introduces a non-linearity to the system:

(13) $\small softmax(r)_{i}=\frac{exp(r_{i})}{\sum_{j}exp(r_{j})}$

We will have to introduce a scaling factor to correct the softmax
computations. As done earlier, we will again start by performing unaltered
processing of the initial row $r_{0}=[r_{00}\,r_{01}\,r_{02}]$ (class
embedding excluded for clarity) with a regular softmax function:

(14) $\small
softmax(r)_{0}=\frac{[exp(r_{00})\,exp(r_{01})\,exp(r_{02})]}{\sum[exp(r_{00})\,exp(r_{01})\,exp(r_{02})]}$

The next row of the scaled input $QK^{T}$ is already expressed with deltas:

(15) $\small r_{1}=[\Delta r_{10}\,\Delta r_{11}\,\Delta r_{12}]$

The $r_{1}$ nominator $NOM_{r_{1}}$ for softmax is thus given by:

(16) $\small NOM_{r_{1}}=[exp(\Delta r_{10})\,exp(\Delta r_{11})\,exp(\Delta
r_{12})]$

While the denominator $DENOM_{r_{1}}$ as:

(17) $\small DENOM_{r_{1}}=\frac{\sum[exp(r_{00}+\Delta
r_{10})\,exp(r_{01}+\Delta r_{11})\,exp(r_{02}+\Delta
r_{12})]}{\sum[exp(r_{00})\,exp(r_{01})\,exp(r_{02})]}$

Finally, a scaling factor for each of the values to correct the softmax result
is:

(18) $\small SF_{r_{1}}=softmax(r)_{1}\,\frac{NOM_{r_{1}}}{DENOM_{r_{1}}}$

###  5.4. Computational savings

To assess the potential computational savings for the Delta KWT, we
differentiate between the two main sublayers: i) MHSA, and ii) MLP. The MLP
block consists of two fully connected layers with weight matrices of
dimensions (192,768) and (768,192), respectively. Without any delta
modification, $\sim$39% of the multiplication of the original KWT can be found
in the MHSA and $\sim$61% in the MLP. Although MLP is the prevailing module in
this specific scenario, its complexity does not grow quadratically with the
input sequence length. Moreover, there are many well-established compression
techniques available, some of them presented in Section 2. Hence, pruning of
the MLP is out of the scope of our work, and it is only stated for
completeness. The MHSA multiplication operations can be further split into
$XW_{K}$, $XW_{Q}$, $XW_{V}$ ($\sim$59.63%), $QK^{T}$ ($\sim$10.25%),
$softmax(QK^{T})V$ ($\sim$10.25%), and final projection with attention heads
$[head_{1},head_{2},head_{3}]W_{P}$ ($\sim$19.88%). The KWT model offers an
optimization in the last layer. As shown in Figure 1, only the class embedding
token is used for the final prediction, making the rest of the tokens within
the sequence unused. This dependency can be tracked up to $QK^{T}$. The MAC
savings in last layer are thus worth $59.64\%$, always making the total
savings at least $4.97\%$ for the whole KWT without losing any accuracy.
Maximum possible computational savings, i.e., cases when only the class
embedding and first vector are computed since all deltas are 0, are stated
below for each of the MHSA parts. For simplicity, all the terms use matrices
$A$ and $B$, and $row$ and $col$ for dimensions.
Savings for $XW_{K}$, $XW_{Q}$, and $XW_{V}$ for each of the first 11 layers
are:

(19) $\small
l_{0-10}=1-\frac{(colA\,x\,2)\,x\,colB\,x\,3}{(colA\,x\,colB\,x\,rowA)\,x\,3}=\sim
97.98\%$

Where $A=(99,192)$ and $B=(192,192)$. Computations for $XW_{Q}$ in the last
layer are expressed as:

(20) $\small
l_{11}=1-\frac{(colA\,x\,2)\,x\,colB\,x\,2+\,colA\,x\,\,colB}{(colA\,x\,colB\,x\,rowA)\,x\,3}=\sim
98.32\%$

Savings for $QK^{T}$:

(21) $\small
l_{0-10}=1-\frac{(colA\,x\,2\,x\,2)\,x\,heads}{(colA\,x\,colB\,x\,rowA)\,x\,heads}=\sim
99.96\%$ (22) $\small
l_{11}=1-\frac{(colA\,x\,2)\,x\,heads}{(colA\,x\,colB\,x\,rowA)\,x\,heads}=\sim
99.98\%$

Where $A=(99,64)$ and $B=(64,99)$. Savings for $softmax(QK^{T})V$:

(23) $\small
l_{0-10}=1-\frac{(colA\,x\,2\,x\,colB)\,x\,heads}{(colA\,x\,colB\,x\,rowA)\,x\,heads}=\sim
97.98\%$ (24) $\small
l_{11}=1-\frac{(colA\,x\,colB)\,x\,heads}{(colA\,x\,colB\,x\,rowA)\,x\,heads}=\sim
98.99\%$

Where $A=(99,99)$ and $B=(99,64)$. Finally, the projection with attention
heads:

(25) $\small
l_{0-10}=1-\frac{(colA\,x\,2)\,x\,colB}{colA\,x\,colB\,x\,rowA}=\sim 97.98\%$
(26) $\small l_{11}=1-\frac{colA\,x\,colB}{colA\,x\,colB\,x\,rowA}=\sim
98.99\%$

Where $A=(99,192)$ and $B=(192,192)$.
Of course, the savings estimated above only hold for the extreme case, which
means that either a) all tokens are perfectly correlated, or b) very large
thresholds are used, resulting in significant accuracy degradation. Section 7
will therefore analyze the complete accuracy-complexity trade-off for real
data sequences.

###  5.5. Resources

The proposed delta approach neither requires expensive hardware nor comes with
a large memory overhead. Only a single token has to be stored as a reference
whenever the delta method is used. The softmax delta version additionally
needs to keep the sum of exp from one timestep to another. In terms of
computations, an additional division is needed when calculating scaling
factors, along with multiplications with scaling factors for features within a
token.
The downside of our method is compute and data irregularity due to the
algorithm’s unstructured pruning. However, there are many techniques proposed
in literature such as (Zhang et al., 2019) on how to handle this challenge.

##  6\. Experimental setup

The GSCD v2 (Warden, 2018) is used to evaluate our method as well as the
original KWT performance. The dataset contains 105,000 1-second audio snippets
of 35 different words sampled at 16 kHz. The model classifies 4,800 keywords
from a test set into one of the 12 categories: ”up”, ”down”, ”left”, ”right”,
”yes”, ”no”, ”on”, ”off”, ”go”, and ”stop”, ”_silence_” and ”_unknown_”.
To assess the impact of the thresholds for the different parts of the MHSA on
accuracy and model complexity, we executed threshold sweeps on a subset of 100
keywords (6-12 words from each category). While the thresholds might be
different for each delta encoding within the MHSA block, they are the same
across every Transformer layer. This means that MHSA in the first layer uses
the same thresholds as MHSAs in other layers. From these sweeps, the
thresholds leading to a Pareto-optimal accuracy-computations trade-off are
used in a full run with all 4,800 keywords. We focused on those configurations
that yielded at least 94% accuracy. Since the thresholds are first determined
on a subset of the complete dataset, it was expected to obtain variations in
the results when performing the test on the full dataset. Additional
finetuning, i.e., threshold adjusting, was done and the results are presented
and discussed in Section 7.

##  7\. Results and Discussion

The Pareto-optimal results evaluated on all 4,800 audio files are shown in
Figure 8, where the delta configurations are provided in the legend. The x-
and the left y-axis show a percentage of executed MACs averaged across the
layers and achieved accuracy, respectively. The second y-axis represents a
speedup factor derived from the amount of MACs. The blue circle corresponds to
the original KWT-3 model that achieves $\sim 98.4\%$ accuracy with 100% MACs.

Figure 8. The results of running the original and the delta version of the KWT
model. X-axis represents MACs, while the left and right y-axis correspond to
the accuracy and speedup, respectively. Each of the red-shaded triangles (and
a square) in the legend is annotated with thresholds used during the
experiment in order: $\mathbf{\theta_{X}}$, $\mathbf{\theta_{Q}}$,
$\mathbf{\theta_{K}}$, $\mathbf{\theta_{QK^{T}}}$,
$\mathbf{\theta_{softmax}}$, and $\mathbf{\theta_{head_{1..k}}}$

The results of running the original as well as the delta version of the KWT
model. X-axis represents MACs, while the left and right y-axis correspond to
the accuracy and speedup, respectively. Each of the red-shaded triangles (and
a square) in the legend is annotated with thresholds used during the
experiment in order: $\mathbf{\theta_{X}}$, $\mathbf{\theta_{Q}}$,
$\mathbf{\theta_{K}}$, $\mathbf{\theta_{QK^{T}}}$,
$\mathbf{\theta_{softmax}}$, and $\mathbf{\theta_{head_{1..k}}}$

Table 2. Percentage of executed MACs averaged across the layers for one instance of each keyword category. The configuration is: $\mathbf{\theta_{X}=0.2}$, $\mathbf{\theta_{Q}=0.2}$, $\mathbf{\theta_{K}=0.2}$, $\mathbf{\theta_{QK^{T}}=0.05}$, $\mathbf{\theta_{softmax}=0.001}$, and $\mathbf{\theta_{head_{1..k}}=0.05}$. Keyword | $\mathbf{XW_{Q,K,V}}$ | $\mathbf{QK^{T}}$ | $\mathbf{softmaxV}$ | $\mathbf{head_{1..k}W_{P}}$ | Total
---|---|---|---|---|---
_silence_ | 3.02 | 0.08 | 2.4 | 2.02 | 2.46
_unknown_ | 35.97 | 7.68 | 26.95 | 16.93 | 28.36
yes | 31.82 | 6.26 | 24.06 | 16.31 | 25.32
no | 36.98 | 8.93 | 25.42 | 14.27 | 28.41
up | 33.48 | 6.28 | 23.64 | 13.32 | 25.68
down | 29.88 | 5.08 | 22.38 | 14.24 | 23.46
left | 38.73 | 10.09 | 26.95 | 16.97 | 30.26
right | 33.52 | 6.68 | 25.65 | 16.55 | 26.59
on | 31.13 | 5.64 | 21.21 | 13.02 | 23.9
off | 39.5 | 10.17 | 26.68 | 15.11 | 30.33
stop | 32.39 | 6.15 | 23.36 | 13.72 | 25.06
go | 33.37 | 6.57 | 23.26 | 14.65 | 25.87

The red and green triangles represent our delta KWT-3 model with regard to
accuracy and speedup, respectively. The inference time gains for the MHSA
range from $\sim 1.05x$ to $\sim 16x$, and there is no accuracy degradation
down to $\sim 23.7\%$ MACs (4.2x speedup). Moreover, some of the
configurations even slightly outperform the original KWT-3 (98.46%, 98.48%,
and 98.42%). Decreasing the accuracy by only 0.1% results in further speedup
of $5x$. Moreover, if the accuracy requirements can be relaxed by 1-4%, the
MHSA inference becomes faster by $7.5-15.7x$, which translates to 86.73-93.65%
of skipped MACs. Table 2 shows the % of executed MHSA operations for one
instance of each keyword category, averaged across the layers. The
configuration (0.2_0.2_0.2_0.05_0.001_0.05) used to obtain the results is
represented with a square in Figure 8. Although the MAC percentage naturally
fluctuates for keywords within the same group, the objective of the table is
to provide a general overview of how much operations are approximately
performed in each of the parts. We can observe that $\sim 60-70\%$ of
$XW_{Q,K,V}$, $90-95\%$ of $QK^{T}$, $73-79\%$ of $softmaxV$, and $83-87\%$ of
$head_{1..k}W_{P}$ are discarded, which sums up to $70-77\%$ of skipped
operations for the entire model. To visualize the savings, Figure 9 shows the
delta values of the input data $X$ and the softmax output of the 7th layer of
a keyword $right$ (same instance as used in Table 2). One special case are the
instances from the $\\_silence\\_$ class, that have the amount of discarded
computations very close to the theoretical maximum defined in Section 5.4.
Figure 10 shows the $\\_silence\\_$ input, for which only a small fraction of
the deltas are non-zero, resulting in $97-99.9\%$ of skipped operations.

(a) Delta inputs

(b) Delta softmax outputs (three attention heads)

Figure 9. Deltas for a) inputs and b) softmax outputs for the 7th Transformer
layer of the keyword $\mathbf{right}$. Black color marks 0s.

Deltas for a) inputs and b) softmax outputs for the 7th Transformer layer of
the keyword $\mathbf{right}$. Black color marks 0s.

Figure 10. Deltas for inputs to the 7th Transformer layer for
$\mathbf{\\_silence\\_}$. Black color marks 0s.

Deltas for inputs to the 7th Transformer layer for $\mathbf{\\_silence\\_}$.
Black color marks 0s.

A potential future improvement involves applying deltas on the input embedding
matrix $V$. Although these cannot be exploited in multiplications with the
softmax output due to the direction of computations (softmax output
compensates for it), it would still contribute to $V$’s data compression.
Future work also explores the most optimal thresholds for each of the layers
individually. This might further optimize the point where the accuracy starts
dropping since a varying number of MACs is executed within each of the 12
layers.

##  8\. Conclusion

This paper introduced a dynamic threshold-based pruning technique that
drastically reduces MAC operations during inference. It was demonstrated on a
keyword spotting task on the GSCD, where $\sim 80\%$ of operations in the MHSA
can be discarded without degrading the accuracy. If the accuracy requirements
can be slightly relaxed, a speedup factor of $\sim 5-16x$ is achieved. Our
method thus helps to considerably decrease the computational complexity and
enable significant data compression. The proposed technique can be exploited
to enable an ultra-low power wake-up word detection front-end, that triggers a
more powerful detector once a keyword is recognized. More generally, this work
represents a stepping stone towards enabling the execution of Transformers on
low-power devices.

## References

  * (1)
  * Anwar et al. (2017) Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. 2017\.  Structured Pruning of Deep Convolutional Neural Networks.  _ACM Journal on Emerging Technologies in Computing Systems (JETC)_ 13, 3 (2017), 1–18.  https://doi.org/10.1145/3005348
  * Berg et al. (2021) Axel Berg, Mark O’Connor, and Miguel Tairum Cruz. 2021\.  Keyword Transformer: A Self-Attention Model for Keyword Spotting. In _Proc. Interspeech 2021_. 4249–4253.  https://doi.org/10.21437/Interspeech.2021-1286
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners. In _Advances in Neural Information Processing Systems, NeurIPS 2020_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 1877–1901.  https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf
  * Chang et al. (2021) Feng-Ju Chang, Martin Radfar, Athanasios Mouchtaris, Brian King, and Siegfried Kunzmann. 2021\.  End-to-End Multi-Channel Transformer for Speech Recognition. In _IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6-11, 2021_. IEEE, 5884–5888.  https://doi.org/10.1109/ICASSP39728.2021.9414123
  * Chen et al. (2021) Xie Chen, Yu Wu, Zhenghao Wang, Shujie Liu, and Jinyu Li. 2021.  Developing Real-Time Streaming Transformer Transducer for Speech Recognition on Large-Scale Dataset. In _IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6-11, 2021_. IEEE, 5904–5908.  https://doi.org/10.1109/ICASSP39728.2021.9413535
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , Jill Burstein, Christy Doran, and Thamar Solorio (Eds.). Association for Computational Linguistics, 4171–4186.  https://doi.org/10.18653/v1/n19-1423
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2021\.  An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In _9th International Conference on Learning Representations, ICLR 2021, Austria, May 3-7, 2021_. OpenReview.net.  https://openreview.net/forum?id=YicbFdNTTy
  * Frankle and Carbin (2019) Jonathan Frankle and Michael Carbin. 2019.  The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.  https://openreview.net/forum?id=rJl-b3RcF7
  * Gordon et al. (2020) Mitchell Gordon, Kevin Duh, and Nicholas Andrews. 2020\.  Compressing BERT: Studying the Effects of Weight Pruning on Transfer Learning. In _Proceedings of the 5th Workshop on Representation Learning for NLP_. Association for Computational Linguistics, Online, 143–155.  https://doi.org/10.18653/v1/2020.repl4nlp-1.18
  * Goyal et al. (2020) Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan T. Chakaravarthy, Yogish Sabharwal, and Ashish Verma. 2020\.  PoWER-BERT: Accelerating BERT Inference via Progressive Word-vector Elimination. In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ _(Proceedings of Machine Learning Research, Vol. 119)_ , Hal Daumé III and Aarti Singh (Eds.). PMLR, 3690–3699.  http://proceedings.mlr.press/v119/goyal20a.html
  * Gulati et al. (2020) Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang. 2020\.  Conformer: Convolution-augmented Transformer for Speech Recognition. In _Interspeech 2020, 21st Annual Conference of the International Speech Communication Association, Virtual Event, Shanghai, China, 25-29 October 2020_ , Helen Meng, Bo Xu, and Thomas Fang Zheng (Eds.). ISCA, 5036–5040.  https://doi.org/10.21437/Interspeech.2020-3015
  * Habibian et al. (2021) Amirhossein Habibian, Davide Abati, Taco S. Cohen, and Babak Ehteshami Bejnordi. 2021.  Skip-Convolutions for Efficient Video Processing. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) 2021, virtual, June 19-25, 2021_. Computer Vision Foundation / IEEE, 2695–2704.  https://openaccess.thecvf.com/content/CVPR2021/html/Habibian_Skip-Convolutions_for_Efficient_Video_Processing_CVPR_2021_paper.html
  * Han et al. (2016) Song Han, Huizi Mao, and William J. Dally. 2016.  Deep Compression: Compressing Deep Neural Network with Pruning, Trained Quantization and Huffman Coding. In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , Yoshua Bengio and Yann LeCun (Eds.).  http://arxiv.org/abs/1510.00149
  * Han et al. (2015) Song Han, Jeff Pool, John Tran, and William Dally. 2015\.  Learning both Weights and Connections for Efficient Neural Network. In _Advances in Neural Information Processing Systems, NeurIPS 2015_ , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (Eds.), Vol. 28. Curran Associates, Inc., 1135–1143.  https://proceedings.neurips.cc/paper/2015/file/ae0eb3eed39d2bcef4622b2499a05fe6-Paper.pdf
  * Kim and Cho (2021) Gyuwan Kim and Kyunghyun Cho. 2021.  Length-Adaptive Transformer: Train Once with Length Drop, Use Anytime with Search. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), August 1-6, 2021_ , Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (Eds.). Association for Computational Linguistics, 6501–6511.  https://doi.org/10.18653/v1/2021.acl-long.508
  * Kim et al. (2021) Sehoon Kim, Sheng Shen, David Thorsley, Amir Gholami, Woosuk Kwon, Joseph Hassoun, and Kurt Keutzer. 2021.  Learned Token Pruning for Transformers.  arXiv:2107.00910 [cs.CL]
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020\.  ALBERT: A Lite BERT for Self-supervised Learning of Language Representations. In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.  https://openreview.net/forum?id=H1eA7AEtvS
  * Li et al. (2021) Jiaoda Li, Ryan Cotterell, and Mrinmaya Sachan. 2021\.  Differentiable Subset Pruning of Transformer Heads.  _Transactions of the Association for Computational Linguistics_ 9 (12 2021), 1442–1459.  https://doi.org/10.1162/tacl_a_00436
  * Liu et al. (2021) Andy T. Liu, Shang-Wen Li, and Hung-yi Lee. 2021.  TERA: Self-Supervised Learning of Transformer Encoder Representation for Speech.  _IEEE ACM Transactions on Audio, Speech, and Language Processing_ 29 (2021), 2351–2366.  https://doi.org/10.1109/TASLP.2021.3095662
  * Liu et al. (2019a) Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao. 2019a.  Improving Multi-Task Deep Neural Networks via Knowledge Distillation for Natural Language Understanding.  _CoRR_ abs/1904.09482 (2019).  arXiv:1904.09482 http://arxiv.org/abs/1904.09482
  * Liu et al. (2019b) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _CoRR_ abs/1907.11692 (2019).  arXiv:1907.11692 http://arxiv.org/abs/1907.11692
  * McCarley (2019) J. S. McCarley. 2019\.  Pruning a BERT-based Question Answering Model.  _CoRR_ abs/1910.06360 (2019).  arXiv:1910.06360 http://arxiv.org/abs/1910.06360
  * Michel et al. (2019) Paul Michel, Omer Levy, and Graham Neubig. 2019.  Are Sixteen Heads Really Better than One?. In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett (Eds.), Vol. 32. Curran Associates, Inc., 14014–14024.  https://proceedings.neurips.cc/paper/2019/hash/2c601ad9d2ff9bc8b282670cdd54f69f-Abstract.html
  * Neil et al. (2017) Daniel Neil, Junhaeng Lee, Tobi Delbrück, and Shih-Chii Liu. 2017.  Delta Networks for Optimized Recurrent Network Computation. In _Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017_ _(Proceedings of Machine Learning Research, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, 2584–2593.  http://proceedings.mlr.press/v70/neil17a.html
  * Neimark et al. (2021) Daniel Neimark, Omri Bar, Maya Zohar, and Dotan Asselmann. 2021\.  Video Transformer Network. In _IEEE/CVF International Conference on Computer Vision Workshops, ICCVW 2021, Montreal, BC, Canada, October 11-17, 2021_. IEEE, 3156–3165.  https://doi.org/10.1109/ICCVW54120.2021.00355
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019\.  Language Models are Unsupervised Multitask Learners.  _OpeanAI blog_ (2019).
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  _CoRR_ abs/1910.01108 (2019).  arXiv:1910.01108 http://arxiv.org/abs/1910.01108
  * Sun et al. (2019) Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. 2019\.  Patient Knowledge Distillation for BERT Model Compression. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (Eds.). Association for Computational Linguistics, 4322–4331.  https://doi.org/10.18653/v1/D19-1441
  * Sun et al. (2020) Zhiqing Sun, Hongkun Yu, Xiaodan Song, Renjie Liu, Yiming Yang, and Denny Zhou. 2020\.  MobileBERT: a Compact Task-Agnostic BERT for Resource-Limited Devices. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (Eds.). Association for Computational Linguistics, 2158–2170.  https://doi.org/10.18653/v1/2020.acl-main.195
  * Tang et al. (2019) Raphael Tang, Yao Lu, Linqing Liu, Lili Mou, Olga Vechtomova, and Jimmy Lin. 2019\.  Distilling Task-Specific Knowledge from BERT into Simple Neural Networks.  _CoRR_ abs/1903.12136 (2019).  arXiv:1903.12136 http://arxiv.org/abs/1903.12136
  * Touvron et al. (2021) Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. 2021.  Training data-efficient image transformers & distillation through attention. In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ _(Proceedings of Machine Learning Research, Vol. 139)_ , Marina Meila and Tong Zhang (Eds.). PMLR, 10347–10357.  http://proceedings.mlr.press/v139/touvron21a.html
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is All you Need. In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, NeurIPS 2017, December 4-9, 2017, Long Beach, CA, USA_ , Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 5998–6008.  https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html
  * Voita et al. (2019) Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. 2019.  Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned. In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers_ , Anna Korhonen, David R. Traum, and Lluís Màrquez (Eds.). Association for Computational Linguistics, 5797–5808.  https://doi.org/10.18653/v1/p19-1580
  * Wang et al. (2021) Hanrui Wang, Zhekai Zhang, and Song Han. 2021.  SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning. In _IEEE International Symposium on High-Performance Computer Architecture, HPCA 2021, Seoul, South Korea, February 27 - March 3, 2021_. IEEE, 97–110.  https://doi.org/10.1109/HPCA51647.2021.00018
  * Warden (2018) Pete Warden. 2018\.  Speech Commands: A Dataset for Limited-Vocabulary Speech Recognition.  _CoRR_ abs/1804.03209 (2018).  arXiv:1804.03209 http://arxiv.org/abs/1804.03209
  * Yuan et al. (2021) Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis E.H. Tay, Jiashi Feng, and Shuicheng Yan. 2021.  Tokens-to-Token ViT: Training Vision Transformers From Scratch on ImageNet. In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_. 558–567.
  * Zhang et al. (2019) Jie-Fang Zhang, Ching-En Lee, Chester Liu, Yakun Sophia Shao, Stephen W. Keckler, and Zhengya Zhang. 2019.  SNAP: A 1.67 - 21.55TOPS/W Sparse Neural Acceleration Processor for Unstructured Sparse Deep Neural Network Inference in 16nm CMOS. In _2019 Symposium on VLSI Circuits, Kyoto, Japan, June 9-14, 2019_. IEEE, C306–C307.  https://doi.org/10.23919/VLSIC.2019.8778193


# Lower bound on spatial asymptotic of parabolic Anderson model with narrow
wedge initial condition

Fei Pu

###### Abstract

Let $\\{u(t\,,x):(t,x)\in(0,\infty)\times{\mathbb{R}}\\}$ be the solution to
parabolic Anderson model with narrow wedge initial condition. Using the
association property of parabolic Anderson model, we establish a lower bound
on spatial asymptotic of the solution:

$\displaystyle\liminf_{R\to\infty}\frac{\max_{|x|\leq R}\left(\log
u(t\,,x)+\frac{x^{2}}{2t}\right)}{(\log
R)^{2/3}}\geq\frac{1}{4}\left(\frac{t}{2}\right)^{1/3},\quad\text{a.s.}$

MSC 2010 subject classification: 60G15, 60F10, 60H15, 60G60
Keywords: parabolic Anderson model, spatial asymptotic, association

##  1 Introduction

Consider the parabolic Anderson model with narrow wedge initial condition

$\displaystyle\begin{cases}\partial_{t}u(t\,,x)=\frac{1}{2}\partial_{x}^{2}u(t\,,x)+u(t\,,x)\,\xi(t\,,x),\\\
u(0)=\delta_{0},\end{cases}$ (1.1)

where $\xi$ denotes the space-time white noise. Conus et al [10] studied the
growth of the tallest peaks of solution to stochastic heat equation. For the
parabolic Anderson model with flat initial data, i.e., $u(0)\equiv 1$, they
showed that there exist positive constants $c_{1}$ and $c_{2}$ such that
almost surely

$\displaystyle c_{1}\leq\liminf_{R\to\infty}\frac{\max_{|x|\leq R}\log
u(t\,,x)}{(\log R)^{2/3}}\leq\limsup_{R\to\infty}\frac{\max_{|x|\leq R}\log
u(t\,,x)}{(\log R)^{2/3}}\leq c_{2},$ (1.2)

(see [10, Theorem 1.3]). Later on, Chen [9] obtained the precise asymptotic
form, that is,

$\displaystyle\lim_{R\to\infty}\frac{\max_{|x|\leq R}\log u(t\,,x)}{(\log
R)^{2/3}}=\frac{3}{4}\left(\frac{2t}{3}\right)^{1/3},\quad\text{a.s.}$

(see [9, Corollary 1.5]).

Huang and Lê [17] have investigated the spatial asymptotic of the stochastic
heat equation with compactly supported initial data. In the case of narrow
wedge initial data, i.e., $u(0)=\delta_{0}$, we see from [17, Theorem 1.4]
that

$\displaystyle\limsup_{R\to\infty}\frac{\max_{|x|\leq R}\left(\log
u(t\,,x)+\frac{x^{2}}{2t}\right)}{(\log
R)^{2/3}}\leq\frac{3}{4}\left(\frac{2t}{3}\right)^{1/3},\quad\text{a.s.}$

A lower bound in [17, Theorem 1.4] is missing and it is conjectured in Huang
and Lê [17] (see [17, Conjecture 1.2 and (1.18)]) that, in the case of narrow
wedge initial data,

$\displaystyle\lim_{R\to\infty}\frac{\max_{|x|\leq R}\left(\log
u(t\,,x)+\frac{x^{2}}{2t}\right)}{(\log
R)^{2/3}}=\frac{3}{4}\left(\frac{2t}{3}\right)^{1/3},\quad\text{a.s.}$

For the flat initial data, Conus et al [10] established the lower bound in
(1.2) using a localization argument. In the situation of the narrow wedge
initial data, this localization procedure does not apply because of some
technical difficulty. We refer to [17, Section 6.2] for detailed explanation
on this. As an attempt to obtain the exact spatial asymptotics for narrow
wedge initial data, Huang and Lê [17] consider a sequence of approximating
solution and use the Gaussian nature of the noise to give some estimate on the
spatial asymptotic of this approximating solution; see [17, Theorem 1.5].

The goal of this paper is to establish a lower bound on the spatial asymptotic
of the parabolic Anderson model with narrow wedge initial data. We have the
following.

######  Theorem 1.1.

Let $\\{u(t\,,x):(t,x)\in{\mathbb{R}}_{+}\times{\mathbb{R}}\\}$ be the
solution to parabolic Anderson model (1.1). For fixed $t>0$, we have almost
surely,

$\displaystyle\liminf_{R\to\infty}\frac{\max_{|x|\leq R}\left(\log
u(t\,,x)+\frac{x^{2}}{2t}\right)}{(\log
R)^{2/3}}\geq\frac{1}{4}\left(\frac{t}{2}\right)^{1/3}.$ (1.3)

Conus et al [10] introduced a coupled process to approximate the solution to
stochastic heat equation. This localization argument implies that the random
variables $u(t\,,x)$ and $u(t\,,y)$ are approximately independent when the
spatial variables $x$ and $y$ are far away, where $u$ denotes the solution to
parabolic Anderson model with flat initial condition. Combined with the
asymptotic behavior of the tail probability of the solution and Borel-
Cantelli’s lemma, it leads to the lower bound in (1.2). Our approach to the
independence structure of the solution to parabolic Anderson model (1.1)
relies on the association property of the solution, which has been proved in
[8]. The association property and boundedness of the density of parabolic
Anderson model (see Proposition 3.1 and Corollary 3.3 below) together lead to
a crucial probability inequality (3.4), which implies that the independence
structure of the solution can be characterized by the asymptotic behavior of
the covariance of the solution, and hence enables us to study the lower bound
on spatial asymptotic of parabolic Anderson model with narrow wedge initial
condition.

We will introduce some basic facts on Malliavin calculus and association in
Section 2. The boundedness of density is proved in Section 3. Finally, we
prove Theorem 1.1 in Section 4.

Let us close the Introduction with a brief description of the notation of this
paper. For every $Z\in L^{k}(\Omega)$, we write $\|Z\|_{k}$ instead of
$(\mathrm{E}[|Z|^{k}])^{1/k}$. Throughout we write “$g_{1}(x)\lesssim
g_{2}(x)$ for all $x\in X$” when there exists a real number $L$ such that
$g_{1}(x)\leq Lg_{2}(x)$ for all $x\in X$. Alternatively, we might write
“$g_{2}(x)\gtrsim g_{1}(x)$ for all $x\in X$.” By “$g_{1}(x)\asymp g_{2}(x)$
for all $x\in X$” we mean that $g_{1}(x)\lesssim g_{2}(x)$ for all $x\in X$
and $g_{2}(x)\lesssim g_{1}(x)$ for all $x\in X$.

##  2 Preliminaries

Following Walsh [22], we interpret the stochastic PDE in the following mild
form:

$\displaystyle
u(t\,,x)=\bm{p}_{t}(x)+\int_{0}^{t}\int_{\mathbb{R}}\bm{p}_{t-s}(x-y)u(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y),$
(2.1)

where

$\bm{p}_{t}(x)=\frac{1}{\sqrt{2\pi
t}}\,\mathrm{e}^{-x^{2}/(2t)}\qquad\text{for all }t>0\text{ and
}x\in{\mathbb{R}}.$

Let

$U(t\,,x):=\frac{u(t\,,x)}{\bm{p}_{t}(x)}\qquad\text{for all $t>0$ and
$x\in{\mathbb{R}}$}.$ (2.2)

By [7, Lemma A.4], $\lim_{t\downarrow 0}U(t\,,x)=1$ in $L^{k}(\Omega)$ for all
$x\in{\mathbb{R}}$ and $k\geq 2$. Therefore, we also define

$U(0\,,x):=1\qquad\text{for all $x\in{\mathbb{R}}$},$

throughout. Amir et al [1, Proposition 1.4] showed that the process
$U(t):=\\{U(t\,,x)\\}_{x\in{\mathbb{R}}}$ is stationary for every $t>0$. The
formulation (2.1) of the stochastic PDE (1.1) can be recast equivalently in
terms of $U$ as follows:

$U(t\,,x)=1+\int_{0}^{t}\int_{\mathbb{R}}\frac{\bm{p}_{t-s}(x-y)\bm{p}_{s}(y)}{\bm{p}_{t}(x)}\,U(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y).$

Because

$\frac{\bm{p}_{t-s}(a)\bm{p}_{s}(b)}{\bm{p}_{t}(a+b)}=\bm{p}_{s(t-s)/t}\left(b-\frac{s}{t}(a+b)\right)\quad\text{for
all $0<s<t$ and $a,b\in{\mathbb{R}}$},$ (2.3)

equation (2.1) can be recast as the following random evolution equation for
$U$:

$\displaystyle
U(t\,,x)=1+\int_{0}^{t}\int_{\mathbb{R}}\bm{p}_{s(t-s)/t}\left(y-\frac{s}{t}x\right)U(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y).$
(2.4)

Chen and Dalang [3, Theorem 2.4] found that there exists a real number
$c_{T,k}>0$ such that for all $(t\,,x)\in(0\,,T]\times{\mathbb{R}}$ and $k\geq
2$,

$\|u(t\,,x)\|_{k}\leq c_{T,k}\,\bm{p}_{t}(x),$

which implies that

$\displaystyle\sup_{(t,x)\in[0,T]\times{\mathbb{R}}}\|U(t\,,x)\|_{k}\leq
c_{T,k}.$ (2.5)

###  2.1 Malliavin calculus

Let $\mathcal{H}=L^{2}({\mathbb{R}}_{+}\times{\mathbb{R}})$. The Gaussian
family $\\{W(h)\\}_{h\in\mathcal{H}}$ formed by the Wiener integrals

$W(h)=\int_{0}^{\infty}\int_{\mathbb{R}}h(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y)$

defines an isonormal Gaussian process on the Hilbert space $\mathcal{H}$. In
this framework we can develop the Malliavin calculus (see Nualart [20]). We
denote by $D$ the derivative operator. Using Clark-Ocone formula (see Chen et
al [6, Proposition 6.3]), we can derive the following Poincaré-type inequality

$|\operatorname{\text{\rm
Cov}}(F\,,G)|\leq\int_{0}^{\infty}\mathrm{d}s\int_{\mathbb{R}}\mathrm{d}y\
\left\|D_{s,y}F\right\|_{2}\left\|D_{s,y}G\right\|_{2}\qquad\text{for all
$F,G\in\mathbb{D}^{1,2}$.}$ (2.6)

(see [7, (2.1]).

The divergence operator $\delta$ is defined as the adjoint of the derivative
operator $D$ as an unbounded operator from $L^{1}(\Omega)$ to
$L^{1}(\Omega;\mathcal{H})$. Denote by ${\rm Dom}\,\delta$ the domain of
$\delta$. For an $\mathcal{H}$-valued random variable $v:\Omega\to\mathcal{H}$
and $F\in\mathbb{D}^{1,1}$, we write

$\displaystyle D_{v}F=\langle DF\,,v\rangle_{\mathcal{H}}.$

The following criterion on the boundedness of the density of random variables
was proved in [2, Proposition 1]; see also [18, Proposition 3.1].

######  Proposition 2.1.

Let $F\in\mathbb{D}^{1,1}$ and $v\in L^{1}(\Omega;\mathcal{H})$ be such that
$D_{v}F\neq 0$ a.s. Assume that $v/D_{v}F\in{\rm Dom}\,\delta$. Then the law
of $F$ has a continuous and bounded density given by

$\displaystyle
f_{F}(a)=\mathrm{E}\left[\bm{1}_{\\{F>a\\}}\delta\left(\frac{v}{D_{v}F}\right)\right],\quad
a\in{\mathbb{R}}$

######  Remark 2.2.

We have the following sufficient conditions for $v/D_{v}F\in{\rm Dom}\,\delta$
in Proposition 2.1:

  * (i)

$F\in\mathbb{D}^{2,p}$ and $(D_{v}F)^{-1}\in L^{q}(\Omega)$,

  * (ii)

$v\in\mathbb{D}^{1,p}(\mathcal{H})$,

for some $p\geq 6$ and $q\geq 4$; see the discussions below Proposition 3.1 of
[18].

According to Chen et al [4, Proposition 5.1], $u(t\,,x)\in\bigcap_{k\geq
2}\mathbb{D}^{1,k}$ for all $t>0$ and $x\in{\mathbb{R}}$. Moreover, by [7,
Lemma 2.1], for every $T>0$ and $k\geq 2$, there exists a real number
$C_{T,k}>0$ such that for $t\in(0\,,T]$ and $x\in{\mathbb{R}}$, and for every
$(s\,,y)\in(0\,,t)\times{\mathbb{R}}$,

$\displaystyle\|D_{s,y}u(t\,,x)\|_{k}\leq
C_{T,k}\,\bm{p}_{t-s}(x-y)\bm{p}_{s}(y),$

which implies that

$\displaystyle\|D_{s,y}U(t\,,x)\|_{k}\leq
C_{T,k}\,\bm{p}_{s(t-s)/t}\left(y-\frac{s}{t}x\right)$ (2.7)

by (2.2) and (2.3).

###  2.2 Association

We recall the association property of solution to parabolic Anderson model. We
refer to [19] for more details on associated random variables. First, let us
recall the definition of association; see Esary et al [12]. A random vector
$X:=(X_{1}\,,\ldots,X_{m})$ is said to be _associated_ if

$\operatorname{\text{\rm Cov}}[h_{1}(X)\,,h_{2}(X)]\geq 0,$ (2.8)

for every pair of functions $h_{1},h_{2}:{\mathbb{R}}^{m}\to{\mathbb{R}}$ that
are nondecreasing in every coordinate and satisfy $h_{1}(X),h_{2}(X)\in
L^{2}(\Omega)$. A random field $\Phi=\\{\Phi(x)\\}_{x\in{\mathbb{R}}^{d}}$ is
_associated_ if $(\Phi(x_{1})\,,\ldots,\Phi(x_{m}))$ is associated for every
$x_{1},\ldots,x_{m}\in{\mathbb{R}}^{d}$.

Chen et al [8] established the association property of solution to stochastic
heat equation; see [8, Theorem A.4]. In particular, it implies that the
solution $\\{u(t\,,x):(t,x)\in(0,\infty)\times{\mathbb{R}}\\}$ to (1.1) is
associated. From the definition of association, we deduce the following.

######  Lemma 2.3.

The process $\\{\log U(t\,,x):(t,x)\in(0,\infty)\times{\mathbb{R}}\\}$ is
associated.

##  3 Boundedness of density

The solution $u(t\,,x)$ to equation (1.1) is strictly positive (see [16] and
[15]) and has a smooth probability density function on $(0,\infty)$ (see [4]).
In this section, we show that this probability density function is bounded.

######  Proposition 3.1.

For fixed $t>0$, the random variable $U(t\,,0)$ has a continuous and bounded
probability density function given by

$\displaystyle
f_{U(t\,,0)}(a)=\mathrm{E}\left[\bm{1}_{\\{U(t\,,0)>a\\}}\delta\left(\frac{v}{D_{v}U(t\,,0)}\right)\right],\quad
a\in(0,\infty)$

where $v$ is chosen as

$\displaystyle
v(r\,,z)=\bm{1}_{\\{0<r<t\\}}\bm{p}_{r(t-r)/t}\left(z\right)U(r\,,z),\quad\text{for
$(r\,,z)\in(0,\infty)\times{\mathbb{R}}$}.$

###### Proof.

We will apply Proposition 2.1 to prove this result. It is clear that the
random variable $U(t\,,0)$ belongs to $\mathbb{D}^{1,1}$. From the choice of
$v$, we have $v\in L^{1}(\Omega;\mathcal{H})$. Moreover, since the Malliavin
derivative $D_{r,z}u(t\,,x)$ is nonnegative almost surely (see [8, (A.4)]) and
$v(r\,,z)$ is strictly positive, we see that

$\displaystyle
D_{v}U(t\,,0)=\int_{0}^{t}\int_{\mathbb{R}}v(r\,,z)D_{r,z}U(t\,,0)\mathrm{d}z\mathrm{d}r$

is strictly positive almost surely. According to Proposition 2.1, we need show
that $v/D_{v}F\in{\rm Dom}\,\delta$, which reduces to show that the conditions
(i) and (ii) in Remark 2.2 are satisfied. In order to check condition (ii) of
Remark 2.2, we use Minkowski’s inequality to see that for all $p\geq 6$,

$\displaystyle\left(\mathrm{E}[\|Dv\|^{p}_{\mathcal{H}^{\otimes
2}}]\right)^{\frac{2}{p}}$
$\displaystyle=\left\|\int_{0}^{t}\mathrm{d}r\int_{\mathbb{R}}\mathrm{d}z\int_{0}^{r}\mathrm{d}r_{1}\int_{\mathbb{R}}\mathrm{d}z_{1}\,\bm{p}^{2}_{r(t-r)/t}\left(z\right)(D_{r_{1},z_{1}}U(r\,,z))^{2}\right\|_{\frac{p}{2}}$
$\displaystyle\leq\int_{0}^{t}\mathrm{d}r\int_{\mathbb{R}}\mathrm{d}z\int_{0}^{r}\mathrm{d}r_{1}\int_{\mathbb{R}}\mathrm{d}z_{1}\,\bm{p}^{2}_{r(t-r)/t}\left(z\right)\left\|(D_{r_{1},z_{1}}U(r\,,z))^{2}\right\|_{\frac{p}{2}}$
$\displaystyle=\int_{0}^{t}\mathrm{d}r\int_{\mathbb{R}}\mathrm{d}z\int_{0}^{r}\mathrm{d}r_{1}\int_{\mathbb{R}}\mathrm{d}z_{1}\,\bm{p}^{2}_{r(t-r)/t}\left(z\right)\left\|D_{r_{1},z_{1}}U(r\,,z)\right\|_{p}^{2}$
$\displaystyle\lesssim\int_{0}^{t}\mathrm{d}r\int_{\mathbb{R}}\mathrm{d}z\int_{0}^{r}\mathrm{d}r_{1}\int_{\mathbb{R}}\mathrm{d}z_{1}\,\bm{p}^{2}_{r(t-r)/t}\left(z\right)\bm{p}^{2}_{r_{1}(r-r_{1})/r}\left(z_{1}-\frac{r_{1}}{r}z\right),$

where the last inequality holds by (2.7). The semigroup property of the heat
kernel yields that

$\displaystyle\left(\mathrm{E}[\|Dv\|^{p}_{\mathcal{H}^{\otimes
2}}]\right)^{\frac{2}{p}}$
$\displaystyle\lesssim\int_{0}^{t}\mathrm{d}r\,\bm{p}_{2r(t-r)/t}\left(0\right)\int_{0}^{r}\mathrm{d}r_{1}\,\bm{p}_{2r_{1}(r-r_{1})/r_{1}}\left(0\right)$
$\displaystyle=\int_{0}^{t}\mathrm{d}r\,\bm{p}_{2r(t-r)/t}\left(0\right)r\int_{0}^{1}\mathrm{d}r_{1}\,\bm{p}_{2r(1-r_{1})}\left(0\right)$
$\displaystyle\asymp\int_{0}^{t}\sqrt{r}\,\bm{p}_{2r(t-r)/t}\left(0\right)\mathrm{d}r<\infty.$

Hence, we have $v\in\mathbb{D}^{1,p}(\mathcal{H})$ for all $p\geq 6$. It is
clear that $U(t\,,0)\in\mathbb{D}^{2,p}$ for all $p\geq 2$. Now it remains to
verify that

$\displaystyle(D_{v}U(t\,,0))^{-1}\in L^{q}(\Omega),\quad\text{for some $q\geq
4$}.$ (3.1)

We will adopt the method in [18, Proposition 5.1] to prove (3.1). Choose
$\alpha\in(\frac{4}{3},2)$. Then we have

$\displaystyle t-\epsilon^{\alpha}\geq\frac{t}{2},\quad\text{for all
$\epsilon\in(0,1\wedge\frac{t}{2})$}.$ (3.2)

For $\epsilon\in(0,1\wedge\frac{t}{2})$, since the Malliavin derivative
$D_{r,z}U(t\,,0)$ is nonnegative almost surely. We have

$\displaystyle
D_{v}U(t\,,0)\geq\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}v(r\,,z)D_{r,z}U(t\,,0)\mathrm{d}z\mathrm{d}r.$

Because the Malliavin derivative of $U(t\,,0)$ satisfies

$\displaystyle
D_{r,z}U(t\,,0)=\bm{p}_{r(t-r)/t}\left(z\right)U(r\,,z)+\int_{r}^{t}\int_{\mathbb{R}}\bm{p}_{s(t-s)/t}\left(y\right)D_{r,z}U(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y)$

for $0<r<t$ and $D_{r,z}U(t\,,0)=0$ for $r\geq t$, we write

$\displaystyle D_{v}U(t\,,0)\geq I_{1}+I_{2},$

where

$\displaystyle I_{1}$
$\displaystyle=\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{r(t-r)/t}\left(z\right)U^{2}(r\,,z)\mathrm{d}z\mathrm{d}r,$
$\displaystyle I_{2}$
$\displaystyle=\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bigg{(}\bm{p}_{r(t-r)/t}\left(z\right)U(r\,,z)\int_{r}^{t}\int_{\mathbb{R}}\bm{p}_{s(t-s)/t}\left(y\right)D_{r,z}U(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y)\bigg{)}\mathrm{d}z\mathrm{d}r.$

Hence, we have for $\epsilon\in(0,1\wedge\frac{t}{2})$

$\displaystyle\mathrm{P}\\{D_{v}U(t\,,0)<\epsilon\\}\leq\mathrm{P}\\{I_{1}<2\epsilon\\}+\mathrm{P}\\{I_{2}|>\epsilon\\}.$
(3.3)

We first estimate $\mathrm{P}\\{I_{1}<2\epsilon\\}$. By Chebyshev’s
inequality, for any $q\geq 2$,

$\displaystyle\mathrm{P}\\{I_{1}<2\epsilon\\}=\mathrm{P}\\{I_{1}^{-1}>(2\epsilon)^{-1}\\}\leq(2\epsilon)^{q}\mathrm{E}\left[\left(\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{r(t-r)/t}\left(z\right)U^{2}(r\,,z)\mathrm{d}z\mathrm{d}r\right)^{-q}\right].$

Set

$\displaystyle m(\epsilon)$
$\displaystyle:=\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{r(t-r)/t}\left(z\right)\mathrm{d}z\mathrm{d}r$
$\displaystyle=\int_{t-\epsilon^{\alpha}}^{t}\bm{p}_{2r(t-r)/t}\left(0\right)\mathrm{d}r\asymp\int_{t-\epsilon^{\alpha}}^{t}\frac{\mathrm{d}r}{\sqrt{t-r}}\qquad\text{because
of \eqref{eq:int}}$ $\displaystyle\asymp\epsilon^{\alpha/2}.$ (3.4)

Since the function $x\to x^{-q}$ is convex, we apply Jensen’s inequality with
respect to the probability measure
$\frac{1}{m(\epsilon)}\bm{p}^{2}_{r(t-r)/t}\left(z\right)\mathrm{d}z\mathrm{d}r$
to write

$\displaystyle\mathrm{E}\left[\left(\frac{1}{m(\epsilon)}\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{r(t-r)/t}\left(z\right)U^{2}(r\,,z)\mathrm{d}z\mathrm{d}r\right)^{-q}\right]$
$\displaystyle\qquad\qquad\qquad\leq\frac{1}{m(\epsilon)}\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{r(t-r)/t}\left(z\right)\mathrm{E}[U^{-2q}(r\,,z)]\mathrm{d}z\mathrm{d}r$
$\displaystyle\qquad\qquad\qquad\lesssim\frac{1}{m(\epsilon)}\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{r(t-r)/t}\left(z\right)\mathrm{d}z\mathrm{d}r=1,$

where the second inequality is due to [18, (72)]; see also [5, Theorem 1.4].
Hence, we obtain that for any $q\geq 2$,

$\displaystyle\mathrm{P}\\{I_{1}<2\epsilon\\}\lesssim\epsilon^{q}m(\epsilon)^{-q}\asymp\epsilon^{(1-\alpha/2)q},$
(3.5)

thanks to (3).

Next, we estimate $\mathrm{P}\\{I_{2}|>\epsilon\\}$. Using stochastic Fubini’s
theorem, we write

$\displaystyle
I_{2}=\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\left[\bm{p}_{s(t-s)/t}\left(y\right)\int^{s}_{t-\epsilon^{\alpha}}\int_{\mathbb{R}}\bm{p}_{r(t-r)/t}\left(z\right)U(r\,,z)D_{r,z}U(s\,,y)\mathrm{d}z\mathrm{d}r\right]\xi(\mathrm{d}s\,\mathrm{d}y).$

By Burkholder’s inequality and Minkowski’s inequality, for any $q\geq 2$,

$\displaystyle\|I_{2}\|_{q}^{2}$
$\displaystyle\lesssim\left\|\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left[\int^{s}_{t-\epsilon^{\alpha}}\int_{\mathbb{R}}\bm{p}_{r(t-r)/t}\left(z\right)U(r\,,z)D_{r,z}U(s\,,y)\mathrm{d}z\mathrm{d}r\right]^{2}\mathrm{d}y\mathrm{d}s\right\|_{\frac{q}{2}}$
$\displaystyle\leq\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left\|\int^{s}_{t-\epsilon^{\alpha}}\int_{\mathbb{R}}\bm{p}_{r(t-r)/t}\left(z\right)U(r\,,z)D_{r,z}U(s\,,y)\mathrm{d}z\mathrm{d}r\right\|_{q}^{2}\mathrm{d}y\mathrm{d}s$
$\displaystyle\leq\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left[\int^{s}_{t-\epsilon^{\alpha}}\int_{\mathbb{R}}\bm{p}_{r(t-r)/t}\left(z\right)\|U(r\,,z)D_{r,z}U(s\,,y)\|_{q}\mathrm{d}z\mathrm{d}r\right]^{2}\mathrm{d}y\mathrm{d}s.$

Using Hölder’s inequality, (2.5) and (2.7), we see that

$\displaystyle\|U(r\,,z)D_{r,z}U(s\,,y)\|_{q}\leq\|U(r\,,z)\|_{2q}\|D_{r,z}U(s\,,y)\|_{2q}\lesssim\bm{p}_{r(s-r)/s}\left(z-\frac{r}{s}y\right).$

Thus, the preceding implies that

$\displaystyle\|I_{2}\|_{q}^{2}$
$\displaystyle\lesssim\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left[\int^{s}_{t-\epsilon^{\alpha}}\int_{\mathbb{R}}\bm{p}_{r(t-r)/t}\left(z\right)\bm{p}_{r(s-r)/s}\left(z-\frac{r}{s}y\right)\mathrm{d}z\mathrm{d}r\right]^{2}\mathrm{d}y\mathrm{d}s$
$\displaystyle=\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left[\int^{s}_{t-\epsilon^{\alpha}}\bm{p}_{[r(t-r)/t]+[r(s-r)/s]}\left(\frac{r}{s}y\right)\mathrm{d}r\right]^{2}\mathrm{d}y\mathrm{d}s$
$\displaystyle=\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left[\int^{s}_{t-\epsilon^{\alpha}}\frac{s}{r}\,\bm{p}_{(s^{2}[r(t-r)/t]+s^{2}[r(s-r)/s])/r^{2}}\left(y\right)\mathrm{d}r\right]^{2}\mathrm{d}y\mathrm{d}s$
(3.6)

where the first equality holds by the semigroup property of heat kernel and
the second equality follows from the following identity

$\displaystyle\bm{p}_{t}(\alpha
x)=\alpha^{-1}\bm{p}_{t/\alpha^{2}}(x)\qquad[t,\alpha>0,x\in{\mathbb{R}}].$
(3.7)

Denote

$\displaystyle\lambda(r)=(s^{2}[r(t-r)/t]+s^{2}[r(s-r)/s])/r^{2}.$

We use the formula

$\bm{p}_{\sigma}(x)\bm{p}_{\tau}(x)=\bm{p}_{\sigma+\tau}(0)\bm{p}_{\sigma\tau/(\sigma+\tau)}(x)\qquad[\sigma,\tau>0,x\in{\mathbb{R}}],$
(3.8)

to derive that

$\displaystyle\int_{t-\epsilon^{\alpha}}^{t}\int_{\mathbb{R}}\bm{p}^{2}_{s(t-s)/t}\left(y\right)\left[\int^{s}_{t-\epsilon^{\alpha}}\frac{s}{r}\,\bm{p}_{\lambda(r)}\left(y\right)\mathrm{d}r\right]^{2}\mathrm{d}y\mathrm{d}s$
$\displaystyle\quad=\int_{t-\epsilon^{\alpha}}^{t}\mathrm{d}s\int_{\mathbb{R}}\mathrm{d}y\,\bm{p}_{2s(t-s)/t}\left(0\right)\bm{p}_{s(t-s)/(2t)}\left(y\right)\int_{[t-\epsilon^{\alpha},s]^{2}}\frac{s\mathrm{d}r_{1}}{r_{1}}\frac{s\mathrm{d}r_{2}}{r_{2}}\,\bm{p}_{\lambda(r_{1})+\lambda(r_{2})}\left(0\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\bm{p}_{\lambda(r_{1})\lambda(r_{2})/(\lambda(r_{1})+\lambda(r_{2}))}\left(y\right)$
$\displaystyle\quad=\int_{t-\epsilon^{\alpha}}^{t}\mathrm{d}s\,\bm{p}_{2s(t-s)/t}\left(0\right)\int_{[t-\epsilon^{\alpha},s]^{2}}\frac{s\mathrm{d}r_{1}}{r_{1}}\frac{s\mathrm{d}r_{2}}{r_{2}}\bm{p}_{\lambda(r_{1})+\lambda(r_{2})}\left(0\right)\bm{p}_{[s(t-s)/(2t)]+[\lambda(r_{1})\lambda(r_{2})/(\lambda(r_{1})+\lambda(r_{2}))]}\left(0\right),$
(3.9)

where we used semigroup property of heat kernel in the second equality. Notice
that

$\displaystyle\bm{p}_{[s(t-s)/(2t)]+[\lambda(r_{1})\lambda(r_{2})/(\lambda(r_{1})+\lambda(r_{2}))]}\left(0\right)\geq\bm{p}_{\lambda(r_{1})\lambda(r_{2})/(\lambda(r_{1})+\lambda(r_{2}))}\left(0\right).$

Thus, in view of (3) and (3), it follows that

$\displaystyle\|I_{2}\|_{q}^{2}$
$\displaystyle\lesssim\int_{t-\epsilon^{\alpha}}^{t}\mathrm{d}s\,\bm{p}_{2s(t-s)/t}\left(0\right)\int_{[t-\epsilon^{\alpha},s]^{2}}\frac{s\mathrm{d}r_{1}}{r_{1}}\frac{s\mathrm{d}r_{2}}{r_{2}}\bm{p}_{\lambda(r_{1})+\lambda(r_{2})}\left(0\right)\bm{p}_{\lambda(r_{1})\lambda(r_{2})/(\lambda(r_{1})+\lambda(r_{2}))}\left(0\right)$
$\displaystyle\asymp\int_{t-\epsilon^{\alpha}}^{t}\mathrm{d}s\,\bm{p}_{2s(t-s)/t}\left(0\right)\left[\int_{t-\epsilon^{\alpha}}^{s}\bm{p}_{\lambda(r)}(0)\frac{s\mathrm{d}r}{r}\right]^{2}.$

Now for all $s\in[t-\epsilon^{\alpha},t]$ and $r\in[t-\epsilon^{\alpha},s]$,
we have $s\in[\frac{t}{2},t]$ and $r\in[\frac{t}{2},t]$; see (3.2). Moreover,
for $s,r\in[\frac{t}{2},t]$, we have

$\displaystyle\lambda(r)\geq s^{2}r(t-r)/(tr^{2})=\frac{s(t-r)}{tr}\gtrsim
t-r.$

Therefore, we conclude that

$\displaystyle\|I_{2}\|_{q}^{2}$
$\displaystyle\lesssim\int_{t-\epsilon^{\alpha}}^{t}\frac{\mathrm{d}s}{\sqrt{t-s}}\left[\int_{t-\epsilon^{\alpha}}^{t}\frac{\mathrm{d}r}{\sqrt{t-r}}\right]^{2}\asymp\epsilon^{\frac{3}{2}\alpha}.$

Hence, by Chebyshev’s inequality, for any $q\geq 2$,

$\displaystyle\mathrm{P}\\{I_{2}|>\epsilon\\}$
$\displaystyle\leq\epsilon^{-q}\mathrm{E}[|I_{2}|^{q}]\lesssim\epsilon^{(\frac{3}{4}\alpha-1)q}.$
(3.10)

Letting $\alpha=\frac{8}{5}$, we deduce from (3.5), (3.10) and (3.3) that for
any $q\geq 2$,

$\displaystyle\mathrm{P}\\{D_{v}U(t\,,0)<\epsilon\\}\lesssim\epsilon^{\frac{q}{5}},$
(3.11)

for $\epsilon\in(0,1\wedge\frac{t}{2})$, where the implicit constant only
depends on $t$ and $q$. The estimate (3.11) ensures that $D_{v}U(t\,,0)$ has
finite negative moments of all orders. This verifies (3.1) and completes the
proof. ∎

######  Remark 3.2.

We refer to [13] and [14] for the asymptotic behavior of the density of
solution to parabolic Anderson model.

######  Corollary 3.3.

For fixed $t>0$ and $x\in{\mathbb{R}}$, the random variable $\log U(t\,,x)$
has a bounded probability density function on ${\mathbb{R}}$.

###### Proof.

By stationary, we assume $x=0$. Denote $X=U(t\,,0)$ and $Y=\log U(t\,,0)$.
Then we have the following relation between the probability density functions
of $X$ and $Y$:

$\displaystyle f_{Y}(y)=f_{X}(\mathrm{e}^{y})\mathrm{e}^{y},\quad\text{for all
$y\in{\mathbb{R}}$}.$ (3.12)

In light of Proposition 3.1,

$\displaystyle
f_{X}(\mathrm{e}^{y})=\mathrm{E}\left[\bm{1}_{\\{U(t\,,0)>\mathrm{e}^{y}\\}}\delta\left(\frac{v}{D_{v}U(t\,,0)}\right)\right]\leq\left\|\delta\left(\frac{v}{D_{v}U(t\,,0)}\right)\right\|_{2}\left(\mathrm{P}\\{U(t\,,0)>\mathrm{e}^{y}\\}\right)^{1/2}$
(3.13)

thanks to the Cauchy-Schwarz’s inequality. According to [11, Theorem 1.11],
there exist positive constants $c_{1},c_{2}$ and $y_{0}$ such that

$\displaystyle\mathrm{P}\\{U(t\,,0)>\mathrm{e}^{y}\\}\leq
c_{1}\mathrm{e}^{-c_{2}y^{3/2}},\quad\text{for all $y\geq y_{0}$}.$ (3.14)

Thus, we see from (3.12), (3.13) and (3.14) that

$\displaystyle\sup_{y\geq y_{0}}f_{Y}(y)<\infty.$

Moreover, since $f_{X}$ is bounded by Proposition 3.1, we see from (3.12) tha
$\sup_{y\leq y_{0}}f_{Y}(y)<\infty$. Therefore, we conclude that the
probability density function $f_{Y}$ is bounded. ∎

######  Corollary 3.4.

Fix $t>0$. There exists a positive constant $K$ such that for all
$x\in{\mathbb{R}}$

$\displaystyle\sup_{a,b\in{\mathbb{R}}}\left(\mathrm{P}\left\\{\log
U(t\,,x)\leq a,\log U(t\,,0)\leq b\right\\}-\mathrm{P}\left\\{\log
U(t\,,x)\leq a\right\\}\mathrm{P}\left\\{\log U(t\,,0)\leq b\right\\}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq
K\left[\operatorname{\text{\rm Cov}}(\log U(t\,,x)\,,\log
U(t\,,0))\right]^{1/3}.$ (3.15)

###### Proof.

Because the process $\\{\log U(t\,,x):(t,x)\in(0,\infty)\times{\mathbb{R}}\\}$
is associated (see Lemma 2.3) and the random variable $\log U(t\,,x)$ has a
bounded probability density function (see Corollary 3.3), the above inequality
follows immediately from [19, (6.2.20)] (see also [19, Theorem 6.2.15]). ∎

##  4 Proof of Theorem 1.1

We prove Theorem 1.1 in this section. First, let us recall a sharp upper tail
estimates for the solution to parabolic Anderson model established in [13].
Let $\\{\mathcal{Z}(t\,,x):(t,x)\in(0,\infty)\times{\mathbb{R}}\\}$ solves

$\displaystyle\begin{cases}\partial_{t}\mathcal{Z}(t\,,x)=\frac{1}{4}\partial_{x}^{2}\mathcal{Z}(t\,,x)+\mathcal{Z}(t\,,x)\,\xi(t\,,x),\\\
\mathcal{Z}(0)=\delta_{0}.\end{cases}$ (4.1)

According to [13, Theorem 2], for fixed $t>0$, there exist $\theta_{0}>0$ and
$C<\infty$ such that for all $\theta>\theta_{0}$,

$\displaystyle\exp\left(-\frac{4}{3}\theta^{3/2}-\theta^{1/2}\log\theta\right)\leq\mathrm{P}\left(\frac{\log\mathcal{Z}(t\,,0)+\frac{t}{12}}{t^{1/3}}\geq\theta\right)\leq\exp\left(-\frac{4}{3}\theta^{3/2}+C\theta^{3/4}\right).$

Notice that the result of [13, Theorem 2] is for $t\in[t_{0},\infty)$ with
$t_{0}>0$. But $t_{0}$ maybe chosen to be any positive value; see the
discussions at the beginning of Section 1.5 of [13]. Hence, we can have the
above estimate for fixed $t>0$. The above estimate implies that for fixed
$t>0$,

$\displaystyle\lim_{\theta\to+\infty}\frac{\log\mathrm{P}\left(\log\mathcal{Z}(t\,,0)+\frac{t}{12}\geq
t^{1/3}\theta\right)}{\theta^{3/2}}=-\frac{4}{3}$

and hence

$\displaystyle\lim_{\theta\to+\infty}\frac{\log\mathrm{P}\left(\log\mathcal{Z}(t\,,0)\geq\theta\right)}{\theta^{3/2}}=-\frac{4}{3\sqrt{t}}.$
(4.2)

The solution to (4.1) satisfies

$\displaystyle\mathcal{Z}(t\,,x)=\bm{p}_{t/2}(x)+\int_{0}^{t}\int_{\mathbb{R}}\bm{p}_{(t-s)/2}(x-y)\mathcal{Z}(s\,,y)\,\xi(\mathrm{d}s\,\mathrm{d}y).$

Using (3.7) and the fact that
$\\{\frac{1}{2}\xi(s/2\,,y/2):(s,y)\in(0,\infty)\times{\mathbb{R}})\\}$ has
the distribution as space-time white noise, it is readily to see that

$\displaystyle\frac{1}{2}\mathcal{Z}(t/2\,,x/2)=\bm{p}_{t}(x)+\int_{0}^{t}\int_{\mathbb{R}}\bm{p}_{t-s}(x-y)\frac{1}{2}\mathcal{Z}(s/2\,,y/2)\,\xi(\mathrm{d}s\,\mathrm{d}y).$

Therefore, we conclude that $\frac{1}{2}\mathcal{Z}(t/2\,,x/2)$ has the
distribution as $u(t\,,x)$ which solves (1.1). By (4.2), we obtain that

$\displaystyle\lim_{\theta\to+\infty}\frac{\log\mathrm{P}\left(\log
U(t\,,0)\geq\theta\right)}{\theta^{3/2}}=-\frac{4}{3}\sqrt{\frac{2}{t}}.$
(4.3)

We next give some estimate on the covariance $\operatorname{\text{\rm
Cov}}(\log U(t\,,x)\,,\log U(t\,,0))$.

######  Lemma 4.1.

For fixed $t>0$, there exists a positive constant $c$ depending on $t$ such
that for all $x\in{\mathbb{R}}$

$\displaystyle\left|\operatorname{\text{\rm Cov}}(\log U(t\,,x)\,,\log
U(t\,,0))\right|\leq\frac{c}{|x|}.$ (4.4)

###### Proof.

Since $U(t\,,x)$ belongs to $\mathbb{D}^{1,2}$ and has finite negative moments
of all orders (see [4]), the random variable $\log U(t\,,x)$ belongs to
$\mathbb{D}^{1,2}$ and we have

$\displaystyle D_{r,z}\log
U(t\,,x)=\bm{1}_{\\{0<r<t\\}}\frac{D_{r,z}U(t\,,x)}{U(t\,,x)}$

(see [8, Lemma 4.3(i)]). Applying the Poincaré inequality (2.6),

$\displaystyle\left|\operatorname{\text{\rm Cov}}(\log U(t\,,x)\,,\log
U(t\,,0))\right|$
$\displaystyle\leq\int_{0}^{t}\int_{\mathbb{R}}\left\|\frac{D_{r,z}U(t\,,x)}{U(t\,,x)}\right\|_{2}\left\|\frac{D_{r,z}U(t\,,0)}{U(t\,,0)}\right\|_{2}\mathrm{d}z\mathrm{d}r$
$\displaystyle\leq\left\|U(t\,,0)^{-1}\right\|^{2}_{4}\int_{0}^{t}\int_{\mathbb{R}}\left\|D_{r,z}U(t\,,x)\right\|_{4}\left\|D_{r,z}U(t\,,0)\right\|_{4}\mathrm{d}z\mathrm{d}r$
$\displaystyle\lesssim\int_{0}^{t}\int_{\mathbb{R}}\bm{p}_{r(t-r)/t}\left(z-\frac{r}{t}x\right)\bm{p}_{r(t-r)/t}\left(z\right)\mathrm{d}z\mathrm{d}r,$

where the second inequality follows from Hölder’s inequality and the third
inequality is due to (2.7). By the semigroup property of heat kernel, it
follows that

$\displaystyle\left|\operatorname{\text{\rm Cov}}(\log U(t\,,x)\,,\log
U(t\,,0))\right|$
$\displaystyle\lesssim\int_{0}^{t}\bm{p}_{2r(t-r)/t}\left(\frac{r}{t}x\right)\mathrm{d}r=t\int_{0}^{1}\bm{p}_{2tr(1-r)}\left(rx\right)\mathrm{d}r$
$\displaystyle\asymp\int_{0}^{1}\mathrm{e}^{-\frac{rx^{2}}{4t(1-r)}}\frac{\mathrm{d}r}{\sqrt{r(1-r)}}.$
(4.5)

Using change of variable,

$\displaystyle\int_{0}^{1/2}\mathrm{e}^{-\frac{rx^{2}}{4t(1-r)}}\frac{\mathrm{d}r}{\sqrt{r(1-r)}}$
$\displaystyle\leq\int_{0}^{1/2}\mathrm{e}^{-\frac{rx^{2}}{4t}}\frac{\mathrm{d}r}{\sqrt{r/2}}$
$\displaystyle\asymp\frac{1}{|x|}\int_{0}^{x^{2}/2}\mathrm{e}^{-\frac{r}{4t}}\frac{\mathrm{d}r}{\sqrt{r}}\leq\frac{1}{|x|}\int_{0}^{\infty}\mathrm{e}^{-\frac{r}{4t}}\frac{\mathrm{d}r}{\sqrt{r}}\asymp\frac{1}{|x|}.$
(4.6)

Similarly,

$\displaystyle\int_{1/2}^{1}\mathrm{e}^{-\frac{rx^{2}}{4t(1-r)}}\frac{\mathrm{d}r}{\sqrt{r(1-r)}}$
$\displaystyle\leq\int_{1/2}^{1}\mathrm{e}^{-\frac{x^{2}}{8t(1-r)}}\frac{\mathrm{d}r}{\sqrt{(1-r)/2}}=\int_{0}^{1/2}\mathrm{e}^{-\frac{x^{2}}{8tr}}\frac{\mathrm{d}r}{\sqrt{r/2}}$
$\displaystyle=|x|\int_{0}^{\frac{1}{2x^{2}}}\mathrm{e}^{-\frac{1}{8tr}}\frac{\mathrm{d}r}{\sqrt{r/2}}\leq|x|\mathrm{e}^{-\frac{x^{2}}{4t}}\int_{0}^{\frac{1}{2x^{2}}}\frac{\mathrm{d}r}{\sqrt{r/2}}\asymp\mathrm{e}^{-\frac{x^{2}}{4t}}.$
(4.7)

We obtain (4.4) from (4), (4) and (4). ∎

We are now ready to prove Theorem 1.1.

###### Proof of Theorem 1.1.

Fix $t>0$. Let $\beta$ be a positive number that is strictly less than
$\frac{1}{8}\sqrt{\frac{t}{2}}$. Choose and fix $a\in(0,\frac{1}{6})$,
$\epsilon\in(0,1)$ such that

$\displaystyle\beta<\frac{a}{\frac{4}{3}\sqrt{\frac{2}{t}}+\epsilon}.$ (4.8)

For this fixed $\epsilon\in(0,1)$, by (4.3), there exists a positive constant
$\tilde{C}$ depending on $\epsilon$ and the fixed $t>0$ such that

$\displaystyle\mathrm{P}\left(\log
U(t\,,0)\geq\theta\right)\geq\mathrm{e}^{-(\frac{4}{3}\sqrt{\frac{2}{t}}+\epsilon)\theta^{3/2}},\quad\text{for
all $\theta\geq\tilde{C}$}.$ (4.9)

Define $x_{j}=2jR/\left\lfloor R^{a}\right\rfloor$ for
$j=1,\ldots,\left\lfloor R^{a}\right\rfloor$. Here the notation $\left\lfloor
x\right\rfloor$ denotes the largest integer which is less than or equal to
$x$. Assume that $R$ is sufficiently large so that $\left\lfloor
R^{a}\right\rfloor\geq R^{a}/2$ and $(\beta\log R)^{2/3}\geq\tilde{C}$, where
$\tilde{C}$ is the constant in (4.9).

By stationarity of $\\{U(t\,,x):x\in{\mathbb{R}}\\}$,

$\displaystyle\mathrm{P}\left\\{\max_{0\leq x\leq 2R}\log
U(t\,,x)\leq(\beta\log R)^{2/3}\right\\}\leq\mathrm{P}\left\\{\max_{1\leq
j\leq\left\lfloor R^{a}\right\rfloor}\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}$ $\displaystyle\qquad=\mathrm{P}\left\\{\max_{1\leq
j\leq\left\lfloor R^{a}\right\rfloor}\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}-\prod_{j=1}^{\left\lfloor
R^{a}\right\rfloor}\mathrm{P}\left\\{\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left(1-\mathrm{P}\left\\{\log
U(t\,,0)>(\beta\log R)^{2/3}\right\\}\right)^{\left\lfloor
R^{a}\right\rfloor}$ (4.10)

Since the process $\\{\log U(t\,,x):x\in{\mathbb{R}}\\}$ is associated (see
Lemma 2.3), by [21, (2.6)],

$\displaystyle\mathrm{P}\left\\{\max_{1\leq j\leq\left\lfloor
R^{a}\right\rfloor}\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}-\prod_{j=1}^{\left\lfloor
R^{a}\right\rfloor}\mathrm{P}\left\\{\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}$ $\displaystyle\qquad\leq\sum_{1\leq j<k\leq\left\lfloor
R^{a}\right\rfloor}\bigg{(}\mathrm{P}\left\\{\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3},\log U(t\,,x_{k})\leq(\beta\log R)^{2/3}\right\\}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad-\mathrm{P}\left\\{\log
U(t\,,x_{j})\leq(\beta\log R)^{2/3}\right\\}\mathrm{P}\left\\{\log
U(t\,,x_{k})\leq(\beta\log 2R)^{2/3}\right\\}\bigg{)}$
$\displaystyle\qquad\lesssim\sum_{1\leq j<k\leq\left\lfloor
R^{a}\right\rfloor}\left[\operatorname{\text{\rm Cov}}(\log
U(t\,,x_{j})\,,\log U(t\,,x_{k}))\right]^{1/3}$
$\displaystyle\qquad\lesssim\sum_{1\leq j<k\leq\left\lfloor
R^{a}\right\rfloor}\frac{1}{|x_{k}-x_{j}|^{1/3}}\asymp R^{(a-1)/3}\sum_{1\leq
j<k\leq\left\lfloor R^{a}\right\rfloor}\frac{1}{|k-j|^{1/3}},$

where the second inequality holds by Corollary 3.4 and stationarity, and the
third inequality holds by Lemma 4.1. Evidently, we have

$\displaystyle\sum_{1\leq j<k\leq\left\lfloor
R^{a}\right\rfloor}\frac{1}{|k-j|^{1/3}}\lesssim R^{\frac{5a}{3}}.$

Hence, we obtain that

$\displaystyle\mathrm{P}\left\\{\max_{1\leq j\leq\left\lfloor
R^{a}\right\rfloor}\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}-\prod_{j=1}^{\left\lfloor
R^{a}\right\rfloor}\mathrm{P}\left\\{\log U(t\,,x_{j})\leq(\beta\log
R)^{2/3}\right\\}\lesssim R^{\frac{1}{3}-2a},$

which together with (4) implies that

$\displaystyle\mathrm{P}\left\\{\max_{0\leq x\leq 2R}\log
U(t\,,x)\leq(\beta\log R)^{2/3}\right\\}$ $\displaystyle\lesssim
R^{\frac{1}{3}-2a}+\left(1-\mathrm{P}\left\\{\log U(t\,,0)>(\beta\log
R)^{2/3}\right\\}\right)^{\left\lfloor R^{a}\right\rfloor}$ $\displaystyle\leq
R^{\frac{1}{3}-2a}+\left(1-\mathrm{e}^{-(\frac{4}{3}\sqrt{\frac{2}{t}}+\epsilon)\beta\log
R}\right)^{\left\lfloor R^{a}\right\rfloor}$ $\displaystyle\leq
R^{\frac{1}{3}-2a}+\mathrm{e}^{-\frac{1}{2}R^{a-\frac{4}{3}(\sqrt{\frac{2}{t}}+\epsilon)\beta}},$

where the second inequality is due to (4.9) and the third inequality follows
from the fact that $1-x\leq\mathrm{e}^{-x}$ for all $x\geq 0$. Since
$\frac{1}{3}-2a<0$ and $a-\frac{4}{3}(\sqrt{\frac{2}{t}}+\epsilon)\beta>0$ by
(4.8), letting $R=2^{n}$, we obtain that

$\displaystyle\sum_{n=1}^{\infty}\mathrm{P}\left\\{\max_{0\leq x\leq
2^{n+1}}\log U(t\,,x)\leq(\beta\log 2^{n})^{2/3}\right\\}<\infty.$

Hence, by Borel-Cantelli’s lemma, we have almost surely,

$\displaystyle\liminf_{n\to\infty}\frac{\max_{0\leq x\leq 2^{n+1}}\log
U(t\,,x)}{(\log 2^{n})^{2/3}}\geq\beta^{2/3}.$

Since the quantity $\max_{0\leq x\leq 2R}\log U(t\,,x)$ is monotone in $R$, we
conclude that almost surely,

$\displaystyle\liminf_{R\to\infty}\frac{\max_{0\leq x\leq 2R}\log
U(t\,,x)}{(\log R)^{2/3}}\geq\beta^{2/3}.$

Letting $\beta\uparrow\frac{1}{8}\sqrt{\frac{t}{2}}$, it follows that almost
surely

$\displaystyle\liminf_{R\to\infty}\frac{\max_{0\leq x\leq 2R}\log
U(t\,,x)}{(\log R)^{2/3}}\geq\frac{1}{4}\left(\frac{t}{2}\right)^{1/3},$

which is equivalent to (1.3) by stationarity.

The proof is complete. ∎

Acknowledgement. Research supported in part by National Natural Science
Foundation of China (No. 12201047), Beijing Natural Science Foundation (No.
1232010) and National Key R&D Program of China (No. 2022YFA 1006500).

## References

  * [1] Amir, G., Corwin, I. and Quastel, J.: Probability distribution of the free energy of the continuum directed random polymer in $1+1$ dimensions. Comm. Pure Appl. Math. 64 (2011), no. 4, 466–537.
  * [2] Caballero, M., Fernández, B. and Nualart, D.: Estimation of densities and applications. J. Theoret. Probab. 11 (1998), no. 3, 831–851.
  * [3] Chen, L. and Dalang, R. C.: Moments and growth indices for the nonlinear stochastic heat equation with rough initial conditions. Ann. Probab. 43 (2015), no. 6, 3006–3051.
  * [4] Chen, L., Hu, Y. and Nualart, D.: Regularity and strict positivity of densities for the nonlinear stochastic heat equation. Mem. Amer. Math. Soc. 273 (2021), no. 1340, v+102 pp.
  * [5] Chen, L. and Kim, K.: On comparison principle and strict positivity of solutions to the nonlinear stochastic fractional heat equations. Ann. Inst. Henri Poincaré Probab. Stat. 53 (2017), no. 1, 358–388.
  * [6] Chen, L., Khoshnevisan, D., Nualart, D. and Pu, F.: Spatial ergodicity for SPDEs via Poincaré-type inequalities. Electron. J. Probab. 26 (2021), Paper No. 140, 37 pp.
  * [7] Chen, L., Khoshnevisan, D., Nualart, D. and Pu, F.: Spatial ergodicity and central limit theorems for parabolic Anderson model with delta initial condition. J. Funct. Anal. 282 (2022), no. 2, Paper No. 109290, 35 pp.
  * [8] Chen, L., Khoshnevisan, D., Nualart, D., Pu, F.: Central limit theorems for spatial averages of the stochastic heat equation via Malliavin-Stein’s method. Stoch. Partial Differ. Equ. Anal. Comput.  11 (2023), no. 1, 122–176.
  * [9] Chen, X.: Spatial asymptotics for the parabolic Anderson models with generalized time-space Gaussian noise. Ann. Probab. 44 (2016), no. 2, 1535–1598.
  * [10] Conus, D., Joseph, M. nand Khoshnevisan, D.: On the chaotic character of the stochastic heat equation, before the onset of intermitttency. Ann. Probab. 41 (2013), no. 3B, 2225–2260.
  * [11] Corwin, I. and Ghosal, P.: KPZ equation tails for general initial data. Electron. J. Probab. 25 (2020), Paper No. 66, 38 pp.
  * [12] Esary, J. D., Proschan, F. and Walkup, D. W.: Association of random variables with applications. Ann. Math. Statist. 38 (1967), (5) 1466–1474.
  * [13] Ganguly, S. and Hegde,M.: Sharp upper tail estimates and limit shapes for the KPZ equation via the tangent method. arXiv:2208.08922 (2022)
  * [14] Hu, Y. and Lê, K.: Asymptotics of the density of parabolic Anderson random fields. Ann. Inst. Henri Poincaré Probab. Stat. 58 (2022), no. 1, 105–133.
  * [15] Moreno Flores, G. R.: On the (strict) positivity of solutions of the stochastic heat equation. Ann. Probab. 42 (2014), no. 4, 1635–1643.
  * [16] Mueller, C.: On the support of solutions to the heat equation with noise. Stochastics Stochastics Rep. 37 (1991), no. 4, 225–245.
  * [17] Huang, J. and Lê, K. Spatial asymptotic of the stochastic heat equation with compactly supported initial data. Stoch. Partial Differ. Equ. Anal. Comput. 7 (2019), no. 3, 495–539.
  * [18] Kuzgun, S. and Nualart, D.: Convergence of densities of spatial averages of stochastic heat equation. Stochastic Process. Appl. 151 (2022), 68–100.
  * [19] Prakasa Rao, B. L. S.: Associated sequences, demimartingales and nonparametric inference. Probability and its Applications. Birkhäuser/Springer, Basel, 2012.
  * [20] Nualart, D.: The Malliavin calculus and related topics. Second edition. Probability and its Applications. Springer-Verlag, Berlin, 2006.
  * [21] Pu, F.: On the association of the Airy1 process. arXiv:2311.11217 (2023)
  * [22] Walsh, J. B.: An introduction to stochastic partial differential equations. École d’été de probabilités de Saint-Flour, XIV—1984, 265–439, Lecture Notes in Math., 1180, Springer, Berlin, 1986.

Fei Pu Laboratory of Mathematics and Complex Systems, School of Mathematical
Sciences, Beijing Normal University, 100875, Beijing, China.
Email<EMAIL_ADDRESS>


789200620051199988

11institutetext: Schnörringen Telescope Science Institute, Ringweg 8a, 51545
Waldbröl, Germany

later

# Statistical errors in equivalent widths - A clarification

T. Eversberg Corresponding author<EMAIL_ADDRESS>

###### Abstract

In a recent mathematical approach, Netzel (2018) proposes a method for
determining the statistical error of spectral line equivalent widths. Using
various approximations, he derives a determination equation that differs
significantly from earlier approaches by Vollmann & Eversberg (2006) and
Chalabaev & Mailard (1983) and evaluates these works with his approach.
Several points stand out, which have a not to be neglected influence on the
evaluation of this approach.

###### keywords:

techniques: spectroscopic – instrumentation: spectrographs – methods: data
analysis

##  1 An alternative approach

The determination of spectral line equivalent widths is a central tool in
light analysis in astronomy. To determine the errors of these measurements,
Chalabaev & Mailard (1983, hereinafter CM1983) calculated a corresponding
mathematical expression in their appendix. Vollmann & Eversberg (2006,
hereinafter VE2006) then proposed an alternative approach for pure photon
noise statistics whose results deviated significantly from CM1983. Recently
Netzel published a simplified approach, also considering pure photon
statistics. As VE2006, he starts with the definition of the equivalent width
and develops a summation expression for the variance. The basis for this are
the pixel signals within the spectral line (his equation (3)). Using Poisson’s
scaling in his equation (4), CN2018 then determines an expression (5) for the
variance of the equivalent width. In addition to a measurement error caused by
photon noise, CN2018 also calculates a dominant error portion based on the
modeled continuum or its normalization. Finally, he compares his result via a
numerical example with the two considerations carried out by CM1983 and VE2006
and gives a preference to the method of CM1983. However, CN2018 makes various
fundamental physical assumptions and performs mathematical steps that do not
stand up to scrutiny. As a result, his confirmation of the error determination
method from CM1983 must be discarded.

##  2 The critique

CN2018 contains a number of significant ambiguities which have an influence on
his concluding assessments that cannot be ignored. In detail:

  1. 1.

To determine an example error of the equivalent width of a spectral line,
CN2018 uses the H$\alpha$ line of the star $\gamma$ Cas recorded with his own
instruments. He then compares his error value with the results of CM1983 and
VE2006. He calculates that the values determined with the VE2006 method are a
factor 0.61 Å/0.23 Å = 2.65 above those of CM1983. His error
$\sigma_{CW}=\sqrt{\sigma_{W}^{2}+\sigma_{C}^{2}}$ of 0.21 Å determined with
his new method is very close to the value of 0.23 Å determined by CM1983. He
concludes that the method of CM1983 is to be considered ”more appropriate”. An
analysis for this conclusion is missing. He also does not illuminate the
correction factor $\sqrt{2}$ determined by VE2006 concerning CM1983. However,
the result of 0.23 Å determined by CN2018 from CM1983 (equation A10 for the
case of ”dominating photon noise”) cannot be correct for the ”Example” in
CN2018. Using CM1983 and the spectral values of CN2018 one obtains
$\sigma_{W}=0.48\,$Å. At first it seems that the author calculated
$\sigma_{W}^{2}$ and forgot to take the square root ($\sqrt{0.23}=0.48$). For
easy verification (A10) of CM1983 and the correct calculation with the CN2018
example numbers are given here:

$\sigma_{T}^{2}=M\cdot\left(\frac{h_{\lambda}}{S/N}\right)^{2}\cdot\frac{\bar{F_{j}}}{\bar{F_{c}}}+\left[\frac{\sigma(\bar{F_{c}})}{F_{c}}(\Delta\lambda-W)\right]^{2}$

with

$\frac{\bar{F_{j}}}{\bar{F_{c}}}=\frac{1}{M}\sum_{j=1}^{M}\frac{F_{j}}{F_{c}}=1.615$

This results in

$\begin{split}\sigma_{T}^{2}=\frac{65.5\,\rm{{\AA}}}{0.0688\,\rm{{\AA}}}\cdot\left(\frac{0.0688\,\rm{{\AA}}}{222}\right)^{2}\cdot
1.615+\\\ \
\left[\frac{1}{222}(65.5\,\rm{{\AA}}-(-40.3\,\rm{{\AA}})\right]^{2}\approx
0.23\,\rm{{\AA}}^{2}\end{split}$

and hence

$\sigma_{T}=\sqrt{0.23\,\rm{{\AA}}^{2}}=0.48\,\rm{{\AA}}$

If we now apply the correction factor calculated by VE2006
($\sigma_{VE2006}=\sqrt{2}\cdot\sigma_{CM1983}$) the result is consistent with
that of the CN2018 data using the error expression in VE2006 (the slight
deviation of about 10% probably results from the inaccurate determination of
the continuum used in the CN2018 example). According to Netzel (2018b),
however, the above calculation was not actually performed in CN2018. Instead,
he directly used the value $\sigma_{W}=0.23\,$Å specified in CM1983 Table 1,
column (9) for his comparison. But as shown above, formula (A10) in CM1983
does not provide this result for the CN2018 example data. It therefore does
not matter whether CN2018 has miscalculated or merely compared his data with
those from Table 1 of CM1983. In both cases his conclusion to prefer the
method of CM1983 is factually inappropriate.

  2. 2.

With $\sigma_{W}$ = 0.0224 Å equation (7) of CN2018 delivers a value about 30
times smaller for $\sigma_{W}$ than the analog expression (7) of VE2006 and
about 10 times smaller than CM1983. Only if the inaccuracy of the continuum is
included in his equation (8), does CN2018 achieve a value similar to CM1983,
which in reality is still about 2 times higher due to improper comparison (see
1.). The total error of CN2018 is therefore dominated by an inaccurate
continuum, which in turn depends only on the line width and the S/N (see 5.).
With an ”ideal rectification” (no contribution from equations (8) and (9)),
the error of CN2018 would even be below the spectral dispersion and would be
indeterminable.

  3. 3.

According to the definition of the equivalent width, its integrand is
dimension-less, since it is normalized with the spectral continuum. However,
the correction term $C=(F_{c_{\lambda_{n}}}+F_{c_{\lambda_{0}}})/2$ introduced
by CN2018 is a signal with a corresponding dimension. In his equation (8) the
correction term in the integrand and the dimension-free ratio
$\frac{F(\lambda)}{F_{c}(\lambda)}$ are added. Equation (8) is therefore non-
physical and the exact meaning of this equation is unclear. Therefore,
equation (9) lacks a factor that changes the result.

  4. 4.

In connection with 3. the meaning of the statement about equation (8) is not
comprehensible: ”When we determine the line as the average of flux at the two
endpoints…”. The purpose of the calculation in equations (8) and (9) can at
best be guessed, but a spectral line cannot be reasonably approximated by the
”flux at the two endpoints”.

  5. 5.

The derivation of equation (9) is unclear. Excluding the critical points in 2.
and 3. and assuming that equation (9) is correct, the problem arises that the
error portion $\sigma_{C}$ increases with the wavelength difference
$\lambda_{n}-\lambda_{0}$. This difference represents the base point width of
the line and thus corresponds approximately to twice the FWHM
($\lambda_{n}-\lambda_{0}\approx 2\cdot FWHM$). Thus the error of the
equivalent width would depend on the line width! Very broad lines like e.g.
emission lines of fast rotating Be-stars or even WR-stars would therefore show
a large error in equivalent width even with large S/N (correspondingly vice
versa with very narrow lines). The text does not provide an explanation for
this irritating result.

##  3 Minor ambiguities

  1. a)

In his introduction CN2018 falsely claims that VE2006 invalidates a
H$\alpha$-H$\beta$ correlation published by CM1983. CM1983 had neither
investigated nor ever claimed such a correlation. They examined H$\alpha$ and
the region around 8500 Å, but not H$\beta$.

  2. b)

In chapter 2 one can read ”In practice, we have for each pixel $(1\leq\nu\leq
m)$ the measured observables $F_{\nu}$ and the quantities $Fc_{\nu}$ for the
flux and continuum. The latter is usually for non-normalized spectra defined
as a polynomial fit of the flux $Fc_{\nu}$ of, say m $(1\leq\mu\leq m)$ the
pixel of the continuum in the vicinity of the line.” Above equation (3),
however, one finds the statement: ”Each of the measurable quantities $F_{\nu}$
and $Fc_{\nu}$ is subject to measurement errors.” For $F_{\nu}$ this last
statement of CN2018 certainly applies, but with the ambiguous definition
before it must be assumed that $Fc_{\nu}$ is a polynomfit of the continuum.
However, in the ideal case of ”Gaussian scatter around the mean value” assumed
here, this polynomial fit does not represent a quantity affected by
measurement errors. A clear terminology to avoid such contradictions is
missing.

  3. c)

For the same reason as in b) another problem arises. Between equation (1) and
(2) in CN2018 one can find the approximation
$\sigma_{Fc_{\nu}}\sim\frac{1}{\sqrt{m}}\sigma_{Fc_{\mu}}\leq\sigma_{Fc_{\mu}}$.
The meaning of the left part of the equation is unclear. According to the
expression, these are formally the standard deviations of the same random
variable $Fc$ (but probably at different $\nu$ and $\mu$ points due to the
previous definitions). However, it remains unclear how between two standard
deviations of the same size the factor $\frac{1}{\sqrt{m}}$ can occur. In his
reference CN2018 refers to Barlow (1988), but this (in reality Barlow 1989)
does not provide sufficient information for this particular question

  4. d)

Equation (2) in CN2018 is formally incorrect. The sum has $n$ summands and
must therefore start at $\nu=1$ and not at $\nu=0$ (or should end at $n-1$).
Otherwise the formula used in the text
$\Delta\lambda=\frac{\lambda_{n}-\lambda_{0}}{n}$ is not consistent with the
sum. If the sum is executed, there is a sign error before $\Delta\lambda$ in
the second line of equation (2).

  5. e)

In equations (5) and (6) identical $F_{\nu}$ are used although a normalization
is performed between these two equations. Then the two fluxes should also be
labeled differently.

  6. f)

Equation (8) averages $C=(Fc_{\lambda_{n}}+Fc_{\lambda_{0}})/2$ linearly.
However, the goal of most standardizations is a sufficient definition of the
line continuum by means of adequate polynomials (e.g. splines). A linear fit
is only a special case. This therefore also applies to the additional term
(9).

In addition, several formatting errors in the running text and in equations
are noticeable, which could have been avoided with appropriate editing.

##  4 Conclusion

Netzel (2018) makes fundamentally physical assumptions that are erroneous,
which in reality do not lead to a correct mathematical and physical
methodology. Its method is not an appropriate tool for the determination of
error bars of equivalent widths and therefore cannot evaluate previous work on
this topic.

## Acknowledgments

I thank Tony Moffat and Klaus Vollmann for helpful discussions.

## References

  * [1] Chalabaev, A., Maillard, J.P.: 1983, A&A 127, 279
  * [2] Netzel, C.: 2018, AN 339, 101
  * [3] Netzel, C.: 2018b, private communication
  * [4] Vollmann, K., Eversberg, T.: 2006, AN 327, 862