# Learning a Fourier Transform for Linear Relative Positional Encodings in
Transformers

Krzysztof Choromanski  Shanda Li  Valerii Likhosherstov  Avinava Dubey
Shengjie Luo  Di He  Yiming Yang  Tamas Sarlos  Thomas Weingarten  Adrian
Weller

###### Abstract

We propose a new class of linear Transformers called
$\mathrm{FourierLearner}$-$\mathrm{Transformers}$ ($\mathrm{FLTs}$), which
incorporate a wide range of relative positional encoding mechanisms (RPEs).
These include regular RPE techniques applied for nongeometric data, as well as
novel RPEs operating on the sequences of tokens embedded in higher-dimensional
Euclidean spaces (e.g. point clouds). $\mathrm{FLTs}$ construct the optimal
RPE mechanism implicitly by learning its spectral representation. As opposed
to other architectures combining efficient low-rank linear attention with
RPEs, $\mathrm{FLTs}$ remain practical in terms of their memory usage and do
not require additional assumptions about the structure of the RPE-mask.
$\mathrm{FLTs}$ allow also for applying certain structural inductive bias
techniques to specify masking strategies, e.g. they provide a way to learn the
so-called local RPEs introduced in this paper and providing accuracy gains as
compared with several other linear Transformers for language modeling. We also
thoroughly tested $\mathrm{FLTs}$ on other data modalities and tasks, such as:
image classification and 3D molecular modeling. For 3D-data $\mathrm{FLTs}$
are, to the best of our knowledge, the first Transformers architectures
providing RPE-enhanced linear attention.

Machine Learning, ICML

##  1 Introduction

Transformers architectures have revolutionized machine learning (ML), not only
by providing significant quantitative gains of ML models, but by leading to
dramatic qualitative improvements and opening new opportunities for applying
them in few- or even zero-shot learning and abstract reasoning settings
(Chowdhery et al., 2022; Brown et al., 2020; Radford & Narasimhan, 2018;
Ramesh et al., 2021; Reed et al., 2022; Ouyang et al., 2022; Srivastava et
al., 2022; Lewkowycz et al., 2022; Rae et al., 2021; Borgeaud et al., 2022;
Devlin et al., 2019; Raffel et al., 2020; Liu et al., 2019; Lan et al., 2020;
Du et al., 2022; Thoppilan et al., 2022).

The research on scaling up the attention architecture, a core module of
Transformers responsible for direct propagation of the signal between
different tokens of the input sequence, started with their birth (Vaswani et
al., 2017). Attention modules have quadratic space and time complexity with
respect to the input sequence length $L$ and thus are computationally
incapable of modeling longer-range distances in long input sequences. The
research on “efficient” Transformers has taken on a new importance as the size
of Transformers models grew from the GPT-1 architecture of “only” 117M
parameters to GPT-3 with 175B parameters, a 1000$\times$ increase within just
two years.

In several applications, local attention (Vaswani et al., 2021a; Zhou et al.,
2021) addresses these new challenges. Tokens attend only to the compact sets
of their neighbors, and the attention matrix is effectively zeroed out in most
entries. In other problems requiring direct modeling of long-range
dependencies, this approach is not sufficient (Zaheer et al., 2020). For
instance, genome modeling (Gupta & Rush, 2017; Ji et al., 2021; Clauwaert et
al., 2021) is a notoriously difficult task, because several of the DNA’s
functionalities, such as regulatory properties, depend directly on the DNA’s
3D conformation and thus are inherently non-local phenomena.

To model long-range dependencies directly, several other models were proposed,
where tokens were grouped together into subsets via clustering or hashing
methods (Roy et al., 2021; Vyas et al., 2020; Kitaev et al., 2020; Sun et al.,
2022). The attention was then modeled only for pairs of tokens within the same
partition. In these approaches, the resulting attention matrices are still
sparse.

Another popular class of scalable Transformers architectures, called
Performers, was proposed by Choromanski et al. (2021). The idea is to find an
approximate low-rank decomposition of the attention matrix and leverage it to
improve space and time complexity of the attention mechanism via the
associativity property of matrix multiplications. Interestingly, in contrast
to previously discussed methods, the approximate attention matrix (that is
never explicitly constructed, but rather used implicitly) is an unbiased
estimate of the original attention matrix encoding similarities between tokens
via the softmax-kernel. The random feature map mechanism used in Performers to
produce the low-rank decomposition of the softmax attention matrix was the
subject of significant follow-up research (Choromanski et al., 2022b;
Likhosherstov et al., 2022; Chowdhury et al., 2022). Several other kernels for
replacing softmax attention upon their effective linearization, such as
Performer-ReLU, were studied. Furthermore, as they are straightforward to
implement, Performers were adopted into many Transformers stacks to provide
linear space and time complexity (Yuan et al., 2021; Horn et al., 2021; Tay et
al., 2021) – recently even for robotic navigation (Xiao et al., 2022).

Unfortunately this simplicity comes at a price. It is well known that
incorporating structural inductive priors – which is usually implemented via
various additive relative masking mechanisms in regular attention
architectures – is difficult for Performers. We refer to these methods as
Relative Positional Encodings (or RPEs) (Shaw et al., 2018; Raffel et al.,
2020; Wu et al., 2021; Gong et al., 2022; Luo et al., 2022b). RPEs play a
critical role in improving the performance of Transformers in long-range
modeling, e.g. for speech (Liutkus et al., 2021) and genomic data (Žiga Avsec
et al., 2021).

At first glance, Performers are not compatible with general RPE techniques,
since they seem to require explicit materialization of the attention matrix to
apply the RPE-mask, which is exactly what Performers avoid in order to achieve
computational improvements.111Certain RPE masking mechanisms can be
implemented in linear space and time complexity, for instance causal masking
that can be thought of as an instantiation of RPE and admits linear
incorporation into Performers via the prefix-sum mechanism, see (Choromanski
et al., 2021). Recently a substantial effort was made to reconcile Performers
with RPEs (more details in Sec. 2), but so far these attempts fell short of
providing two properties at the same time: (a) practical computational gains,
and (b) inclusion of general RPE methods, for inputs with nontrivial
topological structures.

In this paper, we propose a new class of linear Transformers called
$\mathrm{FourierLearner}$-$\mathrm{Transformers}$ ($\mathrm{FLTs}$), which
incorporate a wide range of relative positional encoding mechanisms (RPEs).
These include regular RPE techniques applied for nongeometric data, and novel
RPEs operating on sequences of tokens embedded in higher-dimensional Euclidean
spaces (e.g. point clouds). $\mathrm{FLTs}$ construct the optimal RPE
mechanism implicitly by learning its spectral representation. As opposed to
other architectures combining efficient low-rank linear attention with RPEs,
$\mathrm{FLTs}$ remain practical in terms of their memory usage and do not
require additional assumptions about the structure of the RPE-mask.
$\mathrm{FLTs}$ also allow the application of certain structural inductive
bias techniques to specify masking strategies, e.g. they provide a way to
learn what we call local RPEs, introduced in this paper and providing accuracy
gains compared with several other linear Transformers for language modeling.
We thoroughly test $\mathrm{FLTs}$ on other data modalities and tasks, such as
image classification and molecular modeling. For 3D-data $\mathrm{FLTs}$ are,
to the best of our knowledge, the first Transformers architectures providing
linear attention and incorporating RPE-masking.

To summarize, our main contributions are as follows:

  1. 1.

In Sec. 3, we introduce the RPE-enhanced linear attention defining
$\mathrm{FourierLearner}$-$\mathrm{Transformers}$. We discuss several
instantiations (see Sec. 3.3), in particular $\mathrm{FLTs}$ with so-called
Gaussian mixture RPEs, shift-invariant kernel RPEs and local RPEs.

  2. 2.

In Sec. 4, we conduct extensive empirical evaluations of $\mathrm{FLTs}$ on
tasks ranging from language modeling (Sec. 4.1), through image classification
(Sec. 4.2) to molecular property predictions (Sec. 4.3). We show in particular
that $\mathrm{FLTs}$ obtain the most accurate language models compared to nine
other strong scalable Transformer architectures, with the local RPE variant
introduced in this paper achieving the best performance.

##  2 Related works

One of the first attempts to address the problem of combining low-rank
implicit attention Transformers with RPEs was presented in (Liutkus et al.,
2021). The method relies on the low-rank decomposition of the RPE-mask and
comes in two variants: $\mathrm{sineSPE}$ (also in a gated form) and
$\mathrm{convSPE}$. Both model the RPE-mask as a stationary position kernel
with a Toeplitz mask structure. While $\mathrm{sineSPE}$ represents the values
of the kernel via periodic functions with a fixed number of sinusoidal
components, $\mathrm{convSPE}$ uses convolutions and random projections.

The time complexity of the two variants are $O(drLT^{2})$ and $O(drLP)$
respectively, where $d$ is query/key dimensionality, $r$ is the number of rows
of the random noise (projection) matrices, $L$ is the sequence length, $T$
stands for the number of sinusoidal components and $P$ is the convolutional
filters’ lengths. While linear in $L$, in practice these mechanisms need to be
used with sufficiently small $T$ and $P$ to satisfy computational demands, and
effectively achieved $\mathbf{7}$ points worse perplexity on language modeling
tasks compared to $\mathrm{FLTs}$ (see Sec. 4.1). They also constrain the RPE-
mask to be a valid kernel-matrix, which need not to be the case (for instance,
the causal mechanism can be considered an RPE masking method but does not even
provide a symmetric RPE-mask). Finally, they cannot be applied for even more
general RPE mechanisms with tokens embedded in the higher-dimensional
Euclidean spaces.

More recently, Luo et al. (2021) showed that the RPE mechanism for 1D
sequential data (e.g., language sequences) can be combined with Performers in
$O(L\log(L))$ time complexity. The method relies on the elegant observation
that log-linear time complexity can be achieved as long as the exponentiated
RPE-mask supports fast matrix-vector multiplication, and that this is the case
for the RPEs defined in 1D since the the corresponding masks have a Toeplitz
structure. Interestingly, the algorithm does not even approximate the RPE
mechanism, but applies its exact variant. Unfortunately, the space complexity
of the method is $O(Lmd)$, where $m$ stands for the number of kernel features
and $L$ and $d$ are as before. Even though still linear in $L$, it is now much
larger than for the corresponding Performer variant ($O(Lm+md+Ld)$). In our
experiments, this variant worked well for language modeling (see Sec. 4.1),
but ran out of memory for image classification tasks (see Sec. 4.2).

Even more recently, this algorithm has been extended to the substantially more
general RPE mechanisms, enabling high-dimensional spaces for positional
vectors, and leveraging a large class of methods for efficient matrix-vector
multiplication for the exponentiated RPE-mask matrix (Choromanski et al.,
2022a). Though providing a comprehensive support for the general RPE
mechanism, this method is still characterized by $O(Lmd)$ space complexity,
which becomes a computational bottleneck unless a sufficiently small number of
kernel features $m$ is used.

##  3 The algorithm

###  3.1 Preliminaries

We start by introducing the general relative positional encoding (RPE)
mechanism in Transformers, and regular RPE-free Performer architectures.

Consider an input sequence of $L$ tokens. The attention used in a regular
Transformer linearly projects their representations:
$\mathbf{x}_{1},...,\mathbf{x}_{L}\in\mathbb{R}^{N}$ into three learnable
matrices $\mathbf{Q},\mathbf{K}\in\mathbb{R}^{N\times d_{QK}}$,
$\mathbf{V}\in\mathbb{R}^{N\times d_{V}}$ called queries, keys and values
respectively. We also associate with all the tokens additional feature vectors
$\mathbf{r}_{1},...,\mathbf{r}_{L}\in\mathbb{R}^{\ell}$ that are used to
define the RPE mechanism, see below.

######  Definition 3.1 (General RPE for attention).

General Relative Positional Encoding enhanced attention is of the following
form, where
$\mathbf{N}=[f(\mathbf{r}_{i}-\mathbf{r}_{j})]_{i,j=1,...,L}\in\mathbb{R}^{L\times
L}$ is the so-called RPE-mask and $f:\mathbb{R}^{\ell}\rightarrow\mathbb{R}$
is a (potentially learnable) functon:

$\displaystyle\begin{split}\mathrm{Att}(\mathbf{Q},\mathbf{K},\mathbf{V},\mathbf{N})&=\mathbf{D}^{-1}\mathbf{A}\mathbf{V},\\\
\mathbf{A}=\exp\left(\mathbf{N}+\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d_{QK}}}\right)&,\quad\mathbf{D}=\mathrm{diag}(\mathbf{A}\mathbf{1}_{L}).\end{split}$
(1)

Here $\exp(\cdot)$ is applied element-wise, $\mathbf{1}_{L}$ is the all-one
vector of length $L$, and $\mathrm{diag}(\cdot)$ is a diagonal matrix with the
input vector as the diagonal. The time complexity of computing Eq. (1) is
$O(L^{2}d)$.

Low-rank attention techniques leverage a decomposition of the attention matrix
$\mathbf{A}$ to avoid the quadratic space and time complexity in $L$ by
avoiding explicit materialization of $\mathbf{A}$. For the softmax attention,
this is achieved by linearizing the softmax-kernel
$\mathrm{K}(\mathbf{x},\mathbf{y})\overset{\mathrm{def}}{=}\exp(\mathbf{x}^{\top}\mathbf{y})$
via novel random features mechanisms:
$\mathrm{K}(\mathbf{x},\mathbf{y})=\mathbb{E}[\phi(\mathbf{x})^{\top}\phi(\mathbf{y})]$
for certain randomized mappings:
$\phi:\mathbb{R}^{d_{QK}}\rightarrow\mathbb{R}^{m}$ (and some
$m\in\mathbb{N}^{*}$). This mechanism leads to the fruitful class of linear
space and time complexity Transformers, called Performers (Choromanski et al.,
2021). We refer to vector $\phi(\mathbf{u})$ as a random feature map (RFM) for
$\mathbf{u}\in\mathbb{R}^{d_{QK}}$. We then define
$\mathbf{Q}^{\prime},\mathbf{K}^{\prime}\in\mathbb{R}^{L\times m}$ as matrices
of rows given as $\phi(\mathbf{q}_{i}^{\top}d_{QK}^{-\frac{1}{4}})^{\top}$ and
$\phi(\mathbf{k}_{i}^{\top}d_{QK}^{-\frac{1}{4}})^{\top}$ respectively. The
softmax-kernel linearization with no RPE-masking directly leads to the
following approximate algorithm for attention:

$\displaystyle\begin{split}\widehat{\mathrm{Att}_{\mathrm{K}}}(\mathbf{Q},\mathbf{K},\mathbf{V})&=\widehat{\mathbf{D}}^{-1}(\mathbf{Q}^{\prime}((\mathbf{K}^{\prime})^{\top}\mathbf{V})),\\\
\widehat{\mathbf{D}}&=\mathrm{diag}(\mathbf{Q}^{\prime}((\mathbf{K}^{\prime})^{\top}\mathbf{1}_{L})).\end{split}$
(2)

Here $\widehat{\mathrm{Att}_{\mathrm{K}}}$ stands for the approximate
attention and brackets indicate the order of computations. The time and space
complexity of this mechanism are $O(Lmd)$ and $O(Lm+md+Ld)$ respectively,
compared to $O(L^{2}d)$ and $O(L^{2}+Ld)$ for regular attention. Thus for
$m\ll L$, Performers provide substantial computational improvements.

###  3.2 The FourierLearner-Transformer ($\mathrm{FLT}$)

The algorithm presented in Eq. (2) does not incorporate RPE mechanisms.
However, any low rank decomposition of the RPE-mask $\mathbf{N}$ from Eq. (1)
would naturally lead to a Performer-friendly RPE attention mechanism. Indeed,
the following is true if
$\widehat{\mathbf{N}}=\mathbf{N}_{1}\mathbf{N}_{2}^{\top}$ for
$\mathbf{N}_{1},\mathbf{N}_{2}\in\mathbb{R}^{L\times r}$:

$\widehat{\mathbf{A}}\overset{\mathrm{def}}{=}\exp\left(\widehat{\mathbf{N}}+\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d_{QK}}}\right)=\exp\left(\widehat{\mathbf{Q}}\widehat{\mathbf{K}}^{\top}\right),$
(3)

and
$\widehat{\mathbf{Q}}=[\mathbf{N}_{1},\mathbf{Q}d_{QK}^{-\frac{1}{4}}]\in\mathbb{R}^{L\times(m+r)}$,
$\widehat{\mathbf{K}}=[\mathbf{N}_{2},\mathbf{K}d_{QK}^{-\frac{1}{4}}]\in\mathbb{R}^{L\times(m+r)}$
where the concatenation is conducted along the second axis. RPE-masked
attention is now translated to regular softmax attention that admits
“Performization”, as described in Eq. (2). The time and space complexity of
this mechanism are: $O(L(m+r)d)$ and $O(L(m+r)+(m+r)d+Ld)$ respectively. Below
we explain how the decomposition of $\mathbf{N}$ into $\mathbf{N}_{1}$ and
$\mathbf{N}_{2}$ is conducted.

Figure 1: Examples of the local RPE mechanisms discussed in Sec. 3.3 and
supported via $\mathrm{FLTs}$. Both examples are for tokens with positions
described by two coordinates ($\ell=2$). The $x$ and $y$ coordinates encode
the difference vector $\Delta\mathbf{r}=(\Delta r_{1},\Delta r_{2})^{\top}$.
The $z$-coordinate provides the value of a function $f$. Left: Non-continuous
local RPE mechanism for $\ell=2$ of the form:
$f_{\mathbf{v},C}(\Delta\mathbf{r})=C\cdot\mathbbm{1}[|\Delta r_{1}|\leq
v_{1}]\mathbbm{1}[|\Delta r_{2}|\leq v_{2}]$ for some
$\mathbf{v}=(v_{1},v_{2})^{\top}$. Right: This time
$f_{\mathbf{v}}(\Delta\mathbf{r})=\mathbbm{1}[|\Delta r_{1}|\leq
v_{1}]\mathbbm{1}[|\Delta r_{2}|\leq v_{2}](-|\Delta r_{1}|+v_{1})(-|\Delta
r_{2}|+v_{2})$. The latter local RPE mechanism is continuous, but as the
former, vanishes outside the bounded region. Both can be modeled with
$\mathrm{FLTs}$ via FTs, factorized into powers of $\mathrm{sinc}$ functions
$\frac{\sin(\pi x)}{\pi x}$.

The key observation is that the function
$f:\mathbb{R}^{\ell}\rightarrow\mathbb{R}$ can be rewritten as follows, where
$g:\mathbb{R}^{\ell}\rightarrow\mathbb{R}$ denotes its Fourier Transform (FT):

$f(\mathbf{z})=\int_{\mathbb{R}^{d}}\exp(2\pi\mathbf{i}\mathbf{z}^{\top}\boldsymbol{\xi})\frac{g(\boldsymbol{\xi)}}{p(\boldsymbol{\xi})}p(\boldsymbol{\xi})\mathrm{d}\boldsymbol{\xi}.$
(4)

Here $\mathbf{i}^{2}=-1$ and $p$ is the probability density function of some
probabilistic distribution $\mathrm{P}\in\mathcal{P}(\mathbb{R}^{\ell})$. The
representation from Eq. (4) leads to the following RFM-mechanism for unbiased
approximation of $f(\mathbf{x}-\mathbf{y})$ for any
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{\ell}$, where $m$ stands for the number
of random features:

$\displaystyle\begin{split}f(\mathbf{x}-\mathbf{y})=\mathbb{E}[\varphi(\mathbf{x})^{\top}\psi(\mathbf{y})].\end{split}$
(5)

The random feature maps
$\varphi,\psi:\mathbb{R}^{\ell}\rightarrow\mathbb{R}^{r}$ are defined as
follows for
$\boldsymbol{\xi}_{1},...,\boldsymbol{\xi}_{r}\overset{\mathrm{iid}}{\sim}\mathrm{P}$,
$\widehat{\boldsymbol{\xi}}_{j}=-\boldsymbol{\xi}_{j}$, and $t_{j}u_{j}=1$ for
$j=1,...,r$:

$\displaystyle\varphi(\mathbf{z})\overset{\mathrm{def}}{=}$
$\displaystyle\frac{1}{\sqrt{r}}\left(\mathrm{e}^{2\pi\mathrm{i}\mathbf{z}^{\top}\boldsymbol{\xi}_{1}}\sqrt{\frac{g(\boldsymbol{\xi}_{1})}{p(\boldsymbol{\xi}_{1})}}t_{1},\cdots,\mathrm{e}^{2\pi\mathrm{i}\mathbf{z}^{\top}\boldsymbol{\xi}_{r}}\sqrt{\frac{g(\boldsymbol{\xi}_{r})}{p(\boldsymbol{\xi}_{r})}}t_{r}\right)^{\top}$
$\displaystyle\psi(\mathbf{z})\overset{\mathrm{def}}{=}$
$\displaystyle\frac{1}{\sqrt{r}}\left(\mathrm{e}^{2\pi\mathrm{i}\mathbf{z}^{\top}\widehat{\boldsymbol{\xi}}_{1}}\sqrt{\frac{g(\boldsymbol{\xi}_{1})}{p(\boldsymbol{\xi}_{1})}}u_{1},\cdots,\mathrm{e}^{2\pi\mathrm{i}\mathbf{z}^{\top}\widehat{\boldsymbol{\xi}}_{r}}\sqrt{\frac{g(\boldsymbol{\xi}_{r})}{p(\boldsymbol{\xi}_{r})}}u_{r}\right)^{\top}$

Then, we can define
$\mathbf{N}_{1}=\left[\varphi(\mathbf{x}_{1}),\cdots,\varphi(\mathbf{x}_{L})\right]^{\top}\in\mathbb{R}^{L\times
r}$ and
$\mathbf{N}_{2}=\left[\psi(\mathbf{x}_{1}),\cdots,\psi(\mathbf{x}_{L})\right]^{\top}\in\mathbb{R}^{L\times
r}$, respectively.

Instead of learning function $f$ and trying to compute its Fourier Transform
$g$ to obtain a low-rank decomposition of $\mathbf{N}$, the FourierLearner-
Transformer ($\mathrm{FLT}$) directly learns $g$, effectively learning an
implicit representation of $f$. In practice, $\mathrm{P}$ needs to be chosen
in such a way that we can efficiently sample from it and compute its
probability density function (e.g. Gaussian or truncated Gaussian
distribution).

We point out that our formulations are general enough to cover a wide range of
RPE variants used in practice.

##### Regular RPE for sequential data:

In this setting the input sequence does not have richer geometric structure
and thus vectors $\mathbf{r}_{j}$ can be identified with the indices of tokens
in the sequence, i.e., $\mathbf{r}_{j}=j$. Thus, $\mathrm{FLT}$ learns a
function $g:\mathbb{R}\rightarrow\mathbb{R}$ (see: Sec. 4.1, 4.2).

##### RPE for the 3D-data:

For this input type (e.g. point clouds or 3D molecular data), it is natural to
identify vectors $\mathbf{r}_{j}$ with the 3D coordinates of tokens.
Therefore, $\mathrm{FLT}$ learns a function
$g:\mathbb{R}^{3}\rightarrow\mathbb{R}$ (see: Sec. 4.3).

Nowhere in the analysis so far have we relied on any structural properties of
$f$. In particular, the matrix $\mathbf{N}$ does not need to be a valid
positive definite kernel-matrix or even symmetric. However, if needed, desired
inductive bias can be incorporated into $\mathrm{FLT}$ via certain
parameterization schemes used to train $g$, as we discuss next.

###  3.3 The topology of the Fourier Transform $g$

##### Gaussian mixture RPEs.

One of the most general parameterizations of $g$ that we have considered is
the so-called Gaussian mixture variant:

$g(\boldsymbol{\xi})=\sum_{t=1}^{T}w_{t}\exp\left(-\frac{\|\boldsymbol{\xi}-\boldsymbol{\mu}_{t}\|^{2}}{2\sigma_{t}^{2}}\right).$
(6)

Therefore the FT $g$ is parameterized by $(2+\ell)T$ numbers:
$w_{1},...,w_{T},\sigma_{1},...,\sigma_{T}\in\mathbb{R}$,
$\boldsymbol{\mu}_{1},...,\boldsymbol{\mu}_{T}\in\mathbb{R}^{\ell}$. In the
special case where $T=1$, the FT becomes a renormalized Gaussian kernel and as
such, defines $f$ as another Gaussian kernel.

##### Shift-invariant kernels for RPE-masks.

It is straightforward to apply the $\mathrm{FLT}$ mechanism for RPEs to make
$\mathbf{N}$ a kernel-matrix of any shift-invariant kernel (Rahimi & Recht,
2007). Note that by Bochner’s Theorem:

$\mathrm{K}(\mathbf{x}-\mathbf{y})=C\int_{\mathbb{R}^{d}}e^{\mathbf{i}(\mathbf{x}-\mathbf{y})^{\top}\boldsymbol{\xi}}p_{\mathrm{K}}(\boldsymbol{\xi})\mathrm{d}\boldsymbol{\xi}$
(7)

for the shift-invariant kernel:
$\mathrm{K}:\mathbb{R}^{\ell}\times\mathbb{R}^{\ell}\rightarrow\mathbb{R}$,
the corresponding probabilistic distribution $p_{\mathrm{K}}$ and some
positive constant $C>0$. Thus to unbiasedly approximate an RPE-mask
$\mathbf{N}$ representing kernel-matrix
$[\mathrm{K}(\mathbf{s}_{i},\mathbf{s}_{k})]_{i,k=1,...,L}$ for the shift-
invariant kernel $\mathrm{K}$, it suffices to take:
$\mathbf{r}_{j}=\frac{1}{2\pi}\mathbf{s}_{j}$,
$g(\boldsymbol{\xi})=Cp_{\mathrm{K}}(\boldsymbol{\xi})$, and $t_{j}=u_{j}=1$
for $j=1,....r$. Even if a particular class of shift-invariant kernels has
been chosen, $\mathrm{FLT}$ still provides a way to learn its specific
instantiation through learning an appropriately parameterized $g$.

##### Local RPEs.

$\mathrm{FLT}$ is also capable (through the corresponding structured
parameterized Fourier Transforms $g$) of modeling various schemes where the
RPE mechanism needs to be applied only locally and regular attention is to be
used for tokens far enough from each other. We call such strategies local RPEs
or LRPEs. These include higher-dimensional LRPEs, particularly relevant for
tokens with positions embedded in $\mathbb{R}^{\ell}$ for $\ell>1$. The
mechanism, which we present below in detail, can be considered an RFM-based
smoothing of the original objective described by discrete parameters (such as
the radius of the local RPE measured in the number of the nearest tokens).

The most basic LRPE type takes $\mathbf{r}_{j}=j$ and defines $f$ as follows
for an attention radius $v>0$ and constant $C\in\mathbb{R}$:

$f_{v,C}(\Delta r)=C\cdot\mathbbm{1}[|\Delta r|\leq v].$ (8)

Such an RPE mechanism would (de)amplify the regular attention score between
tokens close to each other by a certain multiplicative amount and might play a
similar role as local attention (Vaswani et al., 2021b). It turns out that the
FT for such a $f$ has a particularly simple form:

$g_{f_{v,C}}(\xi)=C\cdot\frac{\sin(2\pi v\xi)}{\pi\xi}.$ (9)

Instead of using one indicator function in Eq. (8), one can also apply a sum
of many with learnable radii and a list of coefficients $C$. Interestingly,
RPEs from Eq. (8) can be easily generalized to a higher-dimensional LRPE of
the following form (with $\mathbf{r}_{j}$ in the formula for $\mathbf{N}$
corresponding to positions of tokens in the higher-dimensional space
$\mathbb{R}^{\ell})$:

$f_{\mathbf{v},C}(\Delta\mathbf{r})=\prod_{j=1}^{\ell}C\cdot\mathbbm{1}[|\Delta
r_{j}|\leq v_{j}].$ (10)

The corresponding FT $g$ can be factorized as follows:

$g_{f_{\mathbf{v},C}}(\boldsymbol{\xi})=C\cdot\prod_{j=1}^{\ell}\frac{\sin(2\pi
v_{j}\xi_{j})}{\pi\xi_{j}}.$ (11)

This result can be further generalized. The inverse FTs for functions $g$ of
the following form:

$g_{k_{1},...,k_{\ell}}^{v_{1},...,v_{\ell}}(\boldsymbol{\xi})=C\cdot\prod_{j=1}^{\ell}\frac{\sin^{k_{j}}(2\pi
v_{j}\xi_{j})}{\pi\xi_{j}}$ (12)

are of the form:
$f(\Delta\mathbf{r})=M\cdot\prod_{j=1}^{d}f_{j}^{v_{j}}(\Delta r_{j})$, where
$M$ is a constant and each $f^{v_{j}}_{j}$ is: (1) continuous, (2) symmetric,
(3) with compact support of length depending on $v_{j}$, and (4) piece-wise a
polynomial of order $k_{j}-1$. Such functions $f$ are natural candidates for
continuous LRPE mechanisms for tokens with positions embedded in
$\mathbb{R}^{\ell}$ and any $\ell\geq 1$. Examples of local RPE variants for
$\ell=2$, supported via $\mathrm{FLT}$, are presented in Fig. 1.

The above theoretical results can be directly obtained via straightforward
integration and a realization that the $N$-dim FT of a function:
$h(x_{1},\cdots,x_{N})\overset{\mathrm{def}}{=}h_{1}(x_{1})\cdot\cdots\cdot
h_{N}(x_{N})$ can be represented as the product of 1D FTs of the individual
components $h_{j}$.

Model | Perplexity
---|---
Linear Trans. (Katharopoulos et al., 2020) | 38.4
RFA-Gaussian (Peng et al., 2021) | 33.6
RFA-arccos (Peng et al., 2021) | 36.0
RFA-GATE-Gaussian (Peng et al., 2021) | 31.3
RFA-GATE-arccos (Peng et al., 2021) | 32.8
Performer (Choromanski et al., 2021) | 31.1
Performer-sineSPE (Liutkus et al., 2021) | 38.0
Performer-convSPE (Liutkus et al., 2021) | 37.8
Log-linear Performer (Luo et al., 2021) | 30.6
$\mathrm{FLT}$ (Gaussian mixture RPE) (ours) | 30.3
$\mathrm{FLT}$ (local RPE) (ours) | 30.1
Table 1: Language model perplexity scores on the WikiText-103 validation set.
We highlight in bold the lowest perplexity.

Dataset name | # of classes | Training set size | Test set size
---|---|---|---
ImageNet2012 (Deng et al., 2009) | 1K | 1.2M | 100K
Places365 (Zhou et al., 2018) | 365 | 1.8M | 328K
I_naturalist2021 (Horn et al., 2018) | 10K | 2.7M | 500K
Fashion-MNIST (Xiao et al., 2017) | 10 | 60K | 10K

Table 2: Details of the datasets used in image classification tasks with the
FourierLearner-Transformer.

Figure 2: Left: Comparison of the $\mathrm{FLT}$ with a regular Performer on
the $\mathrm{ImageNet}$ classification task. $\mathrm{FLT}$ provides 2.3%
accuracy gain. Right: Additional ablation studies for the $\mathrm{FLT}$
architecture, where number of modes $T$ for the Gaussian mixture RPEs as well
as the number of random features $r$ used to encode the RPE varies. The red
dotted line indicates the performance of the regular Performer.

##  4 Experiments

In this section, we provide experimental results on diverse tasks from
language modeling, through image classification to molecular property
prediction, to demonstrate the effectiveness of the $\mathrm{FLT}$
architecture.

###  4.1 Language modeling

We conduct experiments on the WikiText-103 language modeling task to show the
effectiveness of our proposed method in NLP applications.

####  4.1.1 Compared methods

In this experiment, we study $\mathrm{FLT}$ with two RPE vaiants, Gaussian
mixture RPE and local RPE. We compare our model with the following strong
baselines:

  * •

Linear Transformer proposed by Katharopoulos et al. (2020), which uses
kernelized low-rank attention with $\mathrm{elu}(\cdot)+1$ as the feature map.

  * •

Random feature attention (RFA) proposed by Peng et al. (2021), which has two
variants (Gaussian and arc-cosine) and an optional gating mechanism.

  * •

The regular Performer proposed by Choromanski et al. (2021), which applies the
FAVOR+ mechanism for attention matrix approximation.

  * •

Performer-SPE proposed by Liutkus et al. (2021), which incorporates a special
class of RPE into low-rank attention and has two variants (sineSPE and
convSPE).

  * •

The log-linear Performer proposed by Luo et al. (2021) which extends
Performers to work with an arbitrary Toeplitz RPE attention mask.

##### Implementation details.

All the tested models are efficient Transformer variants based on kernelized
low-rank attention, with 6 decoder layers. In each layer, there are 8
attention heads. The hidden dimension is set to 512. The dimension of the
feed-forward sub-layer is set to 2048. The feature map dimension $m$ is set to
64 in the low-rank approximation of the attention matrix. For our
$\mathrm{FLT}$ models, the number of random features for RPE $r$ is set to 32.
More details regarding training can be found in Appendix A.2. We use the
validation perplexity as the evaluation metric: lower perplexity indicates
better performances.

Figure 3: Comparison of the $\mathrm{FLT}$ with a regular Performer on
different classification datasets: $\mathrm{Places365}$,
$\mathrm{I}$_$\mathrm{naturalist}$, $\mathrm{Fashion}$-$\mathrm{MNIST}$ and
$\mathrm{ImageNet}$, but with the Transformer topology from (Dehghani et al.,
2019) (as opposed to Fig. 2).

####  4.1.2 Results

The results are shown in Table 1. Both variants of our $\mathrm{FLT}$
outperform all the baselines. Compared with efficient Transformers without
RPE, our $\mathrm{FLT}$ obtains much stronger performance. For example, the
validation perplexity of our $\mathrm{FLT}$ with local RPE is 1.0 point lower
than that of the regular Performer, which indicates that our method brings
substantial performance gains by incorporating RPE into the attention module.

Compared with other efficient Transformer variants with RPE, our
$\mathrm{FLT}$ is still very competitive. For example, our $\mathrm{FLT}$
achieves lower perplexity than the strong log-linear Performer baseline. Note
that our $\mathrm{FLT}$ is also more efficient than the log-linear Performer.
As we have noted before, the time and space complexity of the $\mathrm{FLT}$
are $O(L(m+r)d)$ and $O(L(m+r)+(m+r)d+Ld)$, respectively, while the time and
space complexity of log-linear Performer are $O(Lmd\log L)$ and $O(Lmd)$.
Therefore, our $\mathrm{FLT}$ is both more accurate and more scalable than the
baselines.

Dataset name | ImageNet2012 | Places365 | I_naturalist2021 | Fashion-MNIST
---|---|---|---|---
Performer training time | 6h 22 min | 6h 41 min | 7h 28 min | 56 min
$\mathrm{FLT}$ training time | 6h 28min | 8h 23 min | 6h 43 min | 55 min
Performer # steps / sec | 5.331 | 5.283 | 27.38 | 33.18
$\mathrm{FLT}$ # steps / sec | 4.625 | 4.586 | 28.38 | 33.93

Table 3: Comparisons of the total train time and number of steps per second
for the $\mathrm{FLT}$ and Performer architecture on four classification
datasets. Total train time includes also preemptions periods and thus is not
as accurate metric as the number of steps per second (we report it for
completeness though). We highlighted in bold the faster architecture. All the
experiments were run on the TPU architecture.

###  4.2 Image classification

We thoroughly benchmarked $\mathrm{FLT}$ variants of Vision Transformers
(ViTs, Dosovitskiy et al., 2021) on several image classification datasets, see
Table 2.

####  4.2.1 Compared methods

We compared $\mathrm{FLT}$ with the regular Performer and its variations
incorporating different methods for efficient RPE-masking. We chose our most
competitive competitor from Sec. 4.1, the log-linear Performer, and added the
Factor-Performer variant based on the matrix approximation framework from
(Halko et al., 2011). The latter first approximates the action-space of a
matrix $\mathbf{N}$ by applying random Gaussian vectors to probe it (such a
probing can be done efficiently without explicitly materializing $\mathbf{N}$
since $\mathbf{N}$ in this setting is Toeplitz and admits log-linear matrix-
vector multiplication) and then computes its orthonormal basis to use for the
low-rank decomposition of $\mathbf{N}$.

##### Implementation details.

All tested ViTs consist of 12 layers with 12 attention heads in each layer.
The dimension of the feed-forward sub-layer is set to 3072. More details
regarding training can be found in Appendix A.2.

The regular Performer baseline applies the FAVOR+ mechanism from (Choromanski
et al., 2021) for attention matrix approximation with $m=128$ random features
and resampling mechanism turned off. The $\mathrm{FLT}$ variant uses the same
core attention mechanism and applies Gaussian mixture RPEs (Sec. 3.3) with $T$
varying between 6 and 50, and the number of random features for RPE-encoding
$r=64$. In addition, we run more detailed ablation studies on $T$ and $r$ for
the $\mathrm{ImageNet}$ dataset.

####  4.2.2 Results

The results are presented in Figs. 2 and 3. The log-linear Performer
architecture ran out of memory for $m=128$ and did not train when $m$ was
reduced (with a fixed batch size of 4096) to fit the assigned memory. The
Factor-Performer variant did not exceed the allocated memory, but also did not
train due to the numerical instability of the Gram-Schmidt orthogonalization
procedure applied to find an orthonormal basis of the action-spacee of
$\mathbf{N}$. Hence these variants are not presented on the plots.

For the $\mathrm{ImageNet}$ classification task, $\mathrm{FLT}$ provided a
$\mathbf{2.3\%}$ accuracy improvement over regular Performer with the number
of Gaussian mixture modes $T=25$ and the number of random features for RPE
$r=64$ (Fig. 2). Additional ablations over $T$ and $r$ demonstrated that
increasing $r$ improves accuracy, but more interestingly, this does not need
to be the case when $T$ is increased. In fact the best $\mathrm{FLT}$ variant
used only $T=25$ Gaussian modes and was substantially better than its
counterpart with $T=50$ (and the same $r=64$). This suggests that even though
increasing $T$ also increases model expressiveness, it might make training
more difficult.

Fig. 3 shows that $\mathrm{FLT}$ provides improvements also on other datasets,
though the gains vary. We also present there the performance of
$\mathrm{FLT}$, as compared to the Performeer, on the $\mathrm{ImageNet}$
dataset, but for the modified ViT model, the so-called Universal Transformer
(Dehghani et al., 2019).

In all the experiments from Fig. 3 we applied at most $T=50$ Gaussian modes -
a negligible overhead in terms of the total number of parameters of the
architecture.

The comparison of the training time of the regular Performer and the
$\mathrm{FLT}$ architecture on all considered image datasets as well as the
number of Transformer steps per second for both architectures is presented in
Table 3. Total training time includes the preemption periods that are not
related to the time complexity of the mechanism. We see that in practice
$\mathrm{FLT}$ has speed comparable to the regular Performer and in fact is
faster on two out of four datasets.

###  4.3 Molecular property prediction

We further evaluate our $\mathrm{FLT}$ model on the molecular property
prediction task to show its capability to handle 3D input data and complicated
(non-Toeplitz) RPE-masks. To the best of our knowledge, in this scenario,
$\mathrm{FLT}$ is the first Transformer providing RPE-enhanced scalable
attention that enjoys linear complexity with respect to the number of input
tokens.

We use a publicly-available large-scale electrocatalysts dataset - the Open
Catalyst 2020 (OC20) dataset and focus on the IS2RE task which requires to
predict the energy of the relaxed structure given the initial structure of
solid catalysts with adsorbate molecules (Chanussot* et al., 2021).

####  4.3.1 Compared methods

We compare our $\mathrm{FLT}$ with the regular Performer without RPE. For the
$\mathrm{FLT}$ model, we consider to approximate RPE-masks based on Gaussian
basis functions, which are popularly used in neural networks for molecular
modeling (Gasteiger et al., 2021; Shi et al., 2022; Luo et al., 2022a).
Specifically, the RPE-mask is defined as
$\mathbf{N}=[f(\mathbf{r}_{i}-\mathbf{r}_{j})]_{i,j=1,...,L}\in\mathbb{R}^{L\times
L}$, where $\mathbf{r}_{i}\in\mathbb{R}^{3}$ is the position of the $i$-th
input atom, $L$ is the total number of input atom, and
$f(\mathbf{r})=\sum_{t=1}^{T}\frac{w_{t}}{(\sqrt{2\pi}\sigma_{t})^{3}}\exp\left(-\frac{\|\mathbf{r}\|^{2}}{2\sigma_{t}^{2}}\right).$
Note that RPE only calculates the relative distances between atoms, which
naturally preserves many invariant and equivariant properties. It easy to see
that the Fourier Transform of $f$ is
$g_{f}(\boldsymbol{\xi})=\sum_{t=1}^{T}w_{t}\exp\left(-2\pi^{2}\sigma_{t}^{2}\|\boldsymbol{\xi}\|^{2}\right)$,
which enables us to approximate the RPE-mask $\mathbf{N}$ in $\mathrm{FLTs}$
using the technique described in Sec. 3.

##### Implementation details.

We adopt most of the hyperparameters and training recipes of 3D-Graphormer
(Shi et al., 2022). Specifically, we trained a regular Performer with 12
layers and two $\mathrm{FLT}$ with 10 and 12 layers respectively. Following
existing works (Jumper et al., 2021; Shi et al., 2022), model outputs are
repeatedly fed to the model for four times. In each layer, there are 48
attention heads. The hidden dimension is set to 768. The dimension of the
feed-forward sub-layer is set to 2048. The feature map dimension $m$ is set to
64 in the low-rank approximation of the attention matrix. For our
$\mathrm{FLT}$ models, the number of random features for RPE $r$ is set to 16
and the number of Gaussian basis functions in RPE $T$ is set to 32. More
details can be found in Appendix A.2.

We evaluate the performance of the tested models on the in-domain validation
set, where the validation samples come from the same distribution as the
training distribution. We use Mean Absolute Error (MAE) of the energies and
the percentage of Energies within a Threshold (EwT) of the ground truth energy
to evaluation the accuracy of the predicted energies.

####  4.3.2 Results

| Energy MAE (eV) | EwT (%)
---|---|---
Performer-12L | 0.5454 | 4.90
$\mathrm{FLT}$-10L (ours) | 0.5157 | 5.44
$\mathrm{FLT}$-12L (ours) | 0.5046 | 5.33

Table 4: Comparisons of the $\mathrm{FLT}$ with the regular Performer on OC20
IS2RE task. The suffix “-$k$L” means the model consists of $k$ layers, e.g.,
$\mathrm{FLT}$-10L refers to a 10-layer $\mathrm{FLT}$. The evaluation metrics
are Mean Absolute Error (MAE) of the energies and the percentage of Energies
within a Threshold (EwT) of the ground truth energy. We highlighted in bold
the best performance. Figure 4: Validation loss curves of $\mathrm{FLTs}$ and
the regular Performer on the IS2RE task of OC20 dataset.

The results are presented in Table 4. We also present the validation loss
curves of the models in Fig. 4 for a more comprehensive comparison. Clearly,
our $\mathrm{FLT}$ models obtain better performance in both evaluation metrics
and produce more accurate energy predictions. For example, the energy MAE of
the 12-layer $\mathrm{FLT}$ is more than 0.04eV lower than that of the
12-layer regular Performer, which indicates that the use of RPE effectively
increases the predictive power of the model. One may argue that the use of RPE
in $\mathrm{FLT}$ may add some computational overhead and increase the number
of model parameters. However, it should be noted that a shallower 10-layer
$\mathrm{FLT}$ can also significantly outperform the 12-layer regular
Performer, while being faster and using less parameters. Therefore, we believe
our $\mathrm{FLT}$ is a powerful scalable Transformer variant for 3D data with
complex RPE.

##  5 Conclusion

We introduced a new class of Transformers called FourierLearner-Transformers
($\mathrm{FLTs}$) that effectively adapt the relative positional encoding
(RPE) mechanism into Performers - low-rank implicit-attention Transformers
with linear space and time complexity. In contrast to other architectures
combining Performers with RPEs, $\mathrm{FLTs}$ maintain linear complexity of
the attention modules with no additional structural assumptions regarding the
RPE-mask. $\mathrm{FLTs}$ allow the use of certain structural inductive bias
techniques to specify masking strategies, e.g. they provide a way to learn
local RPEs and inject locality bias. We thoroughly tested $\mathrm{FLTs}$ on
various tasks and data modalities, including language modeling, image
classification and 3D molecular property prediction. For certain modalities,
such as 3D data, they are (to the best of our knowledge) the first
Transformers providing linear attention and including RPE-masking.

## References

  * Borgeaud et al. (2022) Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford, E., Millican, K., van den Driessche, G., Lespiau, J., Damoc, B., Clark, A., de Las Casas, D., Guy, A., Menick, J., Ring, R., Hennigan, T., Huang, S., Maggiore, L., Jones, C., Cassirer, A., Brock, A., Paganini, M., Irving, G., Vinyals, O., Osindero, S., Simonyan, K., Rae, J. W., Elsen, E., and Sifre, L.  Improving language models by retrieving from trillions of tokens.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 2206–2240. PMLR, 2022.  URL https://proceedings.mlr.press/v162/borgeaud22a.html.
  * Brown et al. (2020) Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Chanussot* et al. (2021) Chanussot*, L., Das*, A., Goyal*, S., Lavril*, T., Shuaibi*, M., Riviere, M., Tran, K., Heras-Domingo, J., Ho, C., Hu, W., Palizhati, A., Sriram, A., Wood, B., Yoon, J., Parikh, D., Zitnick, C. L., and Ulissi, Z.  Open catalyst 2020 (oc20) dataset and community challenges.  _ACS Catalysis_ , 2021.  doi: 10.1021/acscatal.0c04525.
  * Choromanski et al. (2022a) Choromanski, K., Lin, H., Chen, H., Zhang, T., Sehanobish, A., Likhosherstov, V., Parker-Holder, J., Sarlós, T., Weller, A., and Weingarten, T.  From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked transformers.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 3962–3983. PMLR, 2022a.  URL https://proceedings.mlr.press/v162/choromanski22a.html.
  * Choromanski et al. (2021) Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlós, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A.  Rethinking attention with performers.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=Ua6zuk0WRH.
  * Choromanski et al. (2022b) Choromanski, K. M., Lin, H., Chen, H., Sehanobish, A., Ma, Y., Jain, D., Varley, J., Zeng, A., Ryoo, M. S., Likhosherstov, V., Kalashnikov, D., Sindhwani, V., and Weller, A.  Hybrid random features.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net, 2022b.  URL https://openreview.net/forum?id=EMigfE6ZeS.
  * Chowdhery et al. (2022) Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B., Pope, R., Bradbury, J., Austin, J., Isard, M., Gur-Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., Garcia, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim, H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pellat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang, X., Saeta, B., Diaz, M., Firat, O., Catasta, M., Wei, J., Meier-Hellstern, K., Eck, D., Dean, J., Petrov, S., and Fiedel, N.  Palm: Scaling language modeling with pathways.  _CoRR_ , abs/2204.02311, 2022.  doi: 10.48550/arXiv.2204.02311.  URL https://doi.org/10.48550/arXiv.2204.02311.
  * Chowdhury et al. (2022) Chowdhury, S. P., Solomou, A., Dubey, A., and Sachan, M.  On learning the transformer kernel.  _Transactions of Machine Learning Research_ , 2022.  URL https://arxiv.org/abs/2110.08323.
  * Clauwaert et al. (2021) Clauwaert, J., Menschaert, G., and Waegeman, W.  Explainability in transformer models for functional genomics.  _Briefings Bioinform._ , 22(5), 2021.  doi: 10.1093/bib/bbab060.  URL https://doi.org/10.1093/bib/bbab060.
  * Dehghani et al. (2019) Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, L.  Universal transformers.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.  URL https://openreview.net/forum?id=HyzdRiR9Y7.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA_ , pp. 248–255. IEEE Computer Society, 2009.  doi: 10.1109/CVPR.2009.5206848.  URL https://doi.org/10.1109/CVPR.2009.5206848.
  * Devlin et al. (2019) Devlin, J., Chang, M., Lee, K., and Toutanova, K.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Burstein, J., Doran, C., and Solorio, T. (eds.), _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)_ , pp. 4171–4186. Association for Computational Linguistics, 2019.  doi: 10.18653/v1/n19-1423.  URL https://doi.org/10.18653/v1/n19-1423.
  * Dosovitskiy et al. (2021) Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=YicbFdNTTy.
  * Du et al. (2022) Du, N., Huang, Y., Dai, A. M., Tong, S., Lepikhin, D., Xu, Y., Krikun, M., Zhou, Y., Yu, A. W., Firat, O., Zoph, B., Fedus, L., Bosma, M. P., Zhou, Z., Wang, T., Wang, Y. E., Webster, K., Pellat, M., Robinson, K., Meier-Hellstern, K. S., Duke, T., Dixon, L., Zhang, K., Le, Q. V., Wu, Y., Chen, Z., and Cui, C.  Glam: Efficient scaling of language models with mixture-of-experts.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 5547–5569. PMLR, 2022.  URL https://proceedings.mlr.press/v162/du22c.html.
  * Gasteiger et al. (2021) Gasteiger, J., Becker, F., and Günnemann, S.  Gemnet: Universal directional graph neural networks for molecules.  _Advances in Neural Information Processing Systems_ , 34:6790–6802, 2021.
  * Gong et al. (2022) Gong, Z., Gao, C., Wang, Y., Gu, W., Peng, Y., and Xu, Z.  Source code summarization with structural relative position guided transformer.  In _IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022, Honolulu, HI, USA, March 15-18, 2022_ , pp. 13–24. IEEE, 2022.  doi: 10.1109/SANER53432.2022.00013.  URL https://doi.org/10.1109/SANER53432.2022.00013.
  * Gupta & Rush (2017) Gupta, A. and Rush, A.  Dilated convolutions for modeling long-distance genomic dependencies, 2017\.  URL https://doi.org/10.1101/200857.
  * Halko et al. (2011) Halko, N., Martinsson, P., and Tropp, J. A.  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  _SIAM Rev._ , 53(2):217–288, 2011.  doi: 10.1137/090771806.  URL https://doi.org/10.1137/090771806.
  * Horn et al. (2018) Horn, G. V., Aodha, O. M., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., and Belongie, S. J.  The inaturalist species classification and detection dataset.  In _2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018_ , pp. 8769–8778. Computer Vision Foundation / IEEE Computer Society, 2018.  doi: 10.1109/CVPR.2018.00914.  URL http://openaccess.thecvf.com/content_cvpr_2018/html/Van_Horn_The_INaturalist_Species_CVPR_2018_paper.html.
  * Horn et al. (2021) Horn, M., Shridhar, K., Groenewald, E., and Baumann, P. F. M.  Translational equivariance in kernelizable attention.  _CoRR_ , abs/2102.07680, 2021.  URL https://arxiv.org/abs/2102.07680.
  * Ji et al. (2021) Ji, Y., Zhou, Z., Liu, H., and Davuluri, R. V.  DNABERT: pre-trained bidirectional encoder representations from transformers model for dna-language in genome.  _Bioinform._ , 37(15):2112–2120, 2021.  doi: 10.1093/bioinformatics/btab083.  URL https://doi.org/10.1093/bioinformatics/btab083.
  * Jumper et al. (2021) Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Katharopoulos et al. (2020) Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F.  Transformers are rnns: Fast autoregressive transformers with linear attention.  In _International Conference on Machine Learning_ , pp. 5156–5165. PMLR, 2020.
  * Kitaev et al. (2020) Kitaev, N., Kaiser, L., and Levskaya, A.  Reformer: The efficient transformer.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.  URL https://openreview.net/forum?id=rkgNKkHtvB.
  * Lan et al. (2020) Lan, Z., Chen, M., Goodman, S., Gimpel, K., Sharma, P., and Soricut, R.  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, 2020.  URL https://openreview.net/forum?id=H1eA7AEtvS.
  * Lewkowycz et al. (2022) Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V. V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., Wu, Y., Neyshabur, B., Gur-Ari, G., and Misra, V.  Solving quantitative reasoning problems with language models.  _CoRR_ , abs/2206.14858, 2022.  doi: 10.48550/arXiv.2206.14858.  URL https://doi.org/10.48550/arXiv.2206.14858.
  * Likhosherstov et al. (2022) Likhosherstov, V., Choromanski, K., Dubey, A., Liu, F., Sarlós, T., and Weller, A.  Chefs’ random tables: Non-trigonometric random features.  _to appear at AAAI 2023_ , abs/2205.15317, 2022.  doi: 10.48550/arXiv.2205.15317.  URL https://doi.org/10.48550/arXiv.2205.15317.
  * Liu et al. (2019) Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692, 2019.  URL http://arxiv.org/abs/1907.11692.
  * Liutkus et al. (2021) Liutkus, A., Cífka, O., Wu, S., Simsekli, U., Yang, Y., and Richard, G.  Relative positional encoding for transformers with linear complexity.  In Meila, M. and Zhang, T. (eds.), _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 7067–7079. PMLR, 2021.  URL http://proceedings.mlr.press/v139/liutkus21a.html.
  * Luo et al. (2021) Luo, S., Li, S., Cai, T., He, D., Peng, D., Zheng, S., Ke, G., Wang, L., and Liu, T.  Stable, fast and accurate: Kernelized attention with relative positional encoding.  _CoRR_ , abs/2106.12566, 2021.  URL https://arxiv.org/abs/2106.12566.
  * Luo et al. (2022a) Luo, S., Chen, T., Xu, Y., Zheng, S., Liu, T.-Y., Wang, L., and He, D.  One transformer can understand both 2d & 3d molecular data.  _arXiv preprint arXiv:2210.01765_ , 2022a.
  * Luo et al. (2022b) Luo, S., Li, S., Zheng, S., Liu, T.-Y., Wang, L., and He, D.  Your transformer may not be as powerful as you expect.  _arXiv preprint arXiv:2205.13401_ , 2022b.
  * Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., and Lowe, R.  Training language models to follow instructions with human feedback.  _CoRR_ , abs/2203.02155, 2022.  doi: 10.48550/arXiv.2203.02155.  URL https://doi.org/10.48550/arXiv.2203.02155.
  * Peng et al. (2021) Peng, H., Pappas, N., Yogatama, D., Schwartz, R., Smith, N., and Kong, L.  Random feature attention.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=QtTKTdVrFBB.
  * Radford & Narasimhan (2018) Radford, A. and Narasimhan, K.  Improving language understanding by generative pre-training.  2018\.
  * Rae et al. (2021) Rae, J. W., Borgeaud, S., Cai, T., Millican, K., Hoffmann, J., Song, H. F., Aslanides, J., Henderson, S., Ring, R., Young, S., Rutherford, E., Hennigan, T., Menick, J., Cassirer, A., Powell, R., van den Driessche, G., Hendricks, L. A., Rauh, M., Huang, P., Glaese, A., Welbl, J., Dathathri, S., Huang, S., Uesato, J., Mellor, J., Higgins, I., Creswell, A., McAleese, N., Wu, A., Elsen, E., Jayakumar, S. M., Buchatskaya, E., Budden, D., Sutherland, E., Simonyan, K., Paganini, M., Sifre, L., Martens, L., Li, X. L., Kuncoro, A., Nematzadeh, A., Gribovskaya, E., Donato, D., Lazaridou, A., Mensch, A., Lespiau, J., Tsimpoukelli, M., Grigorev, N., Fritz, D., Sottiaux, T., Pajarskas, M., Pohlen, T., Gong, Z., Toyama, D., de Masson d’Autume, C., Li, Y., Terzi, T., Mikulik, V., Babuschkin, I., Clark, A., de Las Casas, D., Guy, A., Jones, C., Bradbury, J., Johnson, M., Hechtman, B. A., Weidinger, L., Gabriel, I., Isaac, W. S., Lockhart, E., Osindero, S., Rimell, L., Dyer, C., Vinyals, O., Ayoub, K., Stanway, J., Bennett, L., Hassabis, D., Kavukcuoglu, K., and Irving, G.  Scaling language models: Methods, analysis & insights from training gopher.  _CoRR_ , abs/2112.11446, 2021.  URL https://arxiv.org/abs/2112.11446.
  * Raffel et al. (2020) Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67, 2020.  URL http://jmlr.org/papers/v21/20-074.html.
  * Rahimi & Recht (2007) Rahimi, A. and Recht, B.  Random features for large-scale kernel machines.  In Platt, J. C., Koller, D., Singer, Y., and Roweis, S. T. (eds.), _Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007_ , pp. 1177–1184. Curran Associates, Inc., 2007.
  * Ramesh et al. (2021) Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M., and Sutskever, I.  Zero-shot text-to-image generation.  In Meila, M. and Zhang, T. (eds.), _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 8821–8831. PMLR, 2021.  URL http://proceedings.mlr.press/v139/ramesh21a.html.
  * Reed et al. (2022) Reed, S. E., Zolna, K., Parisotto, E., Colmenarejo, S. G., Novikov, A., Barth-Maron, G., Gimenez, M., Sulsky, Y., Kay, J., Springenberg, J. T., Eccles, T., Bruce, J., Razavi, A., Edwards, A., Heess, N., Chen, Y., Hadsell, R., Vinyals, O., Bordbar, M., and de Freitas, N.  A generalist agent.  _CoRR_ , abs/2205.06175, 2022.  doi: 10.48550/arXiv.2205.06175.  URL https://doi.org/10.48550/arXiv.2205.06175.
  * Roy et al. (2021) Roy, A., Saffar, M., Vaswani, A., and Grangier, D.  Efficient content-based sparse attention with routing transformers.  _Trans. Assoc. Comput. Linguistics_ , 9:53–68, 2021.  URL https://transacl.org/ojs/index.php/tacl/article/view/2405.
  * Shaw et al. (2018) Shaw, P., Uszkoreit, J., and Vaswani, A.  Self-attention with relative position representations.  In Walker, M. A., Ji, H., and Stent, A. (eds.), _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT, New Orleans, Louisiana, USA, June 1-6, 2018, Volume 2 (Short Papers)_ , pp. 464–468. Association for Computational Linguistics, 2018.  doi: 10.18653/v1/n18-2074.  URL https://doi.org/10.18653/v1/n18-2074.
  * Shi et al. (2022) Shi, Y., Zheng, S., Ke, G., Shen, Y., You, J., He, J., Luo, S., Liu, C., He, D., and Liu, T.-Y.  Benchmarking graphormer on large-scale molecular modeling datasets.  _arXiv preprint arXiv:2203.04810_ , 2022.
  * Srivastava et al. (2022) Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A., Kluska, A., Lewkowycz, A., Agarwal, A., Power, A., Ray, A., Warstadt, A., Kocurek, A. W., Safaya, A., Tazarv, A., Xiang, A., Parrish, A., Nie, A., Hussain, A., Askell, A., Dsouza, A., Rahane, A., Iyer, A. S., Andreassen, A., Santilli, A., Stuhlmüller, A., Dai, A. M., La, A., Lampinen, A. K., Zou, A., Jiang, A., Chen, A., Vuong, A., Gupta, A., Gottardi, A., Norelli, A., Venkatesh, A., Gholamidavoodi, A., Tabassum, A., Menezes, A., Kirubarajan, A., Mullokandov, A., Sabharwal, A., Herrick, A., Efrat, A., Erdem, A., Karakas, A., and et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _CoRR_ , abs/2206.04615, 2022.  doi: 10.48550/arXiv.2206.04615.  URL https://doi.org/10.48550/arXiv.2206.04615.
  * Sun et al. (2022) Sun, Z., Yang, Y., and Yoo, S.  Sparse attention with learning to hash.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net, 2022.  URL https://openreview.net/forum?id=VGnOJhd5Q1q.
  * Tay et al. (2021) Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, L., Ruder, S., and Metzler, D.  Long range arena : A benchmark for efficient transformers.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=qVyeW-grC2k.
  * Thoppilan et al. (2022) Thoppilan, R., Freitas, D. D., Hall, J., Shazeer, N., Kulshreshtha, A., Cheng, H., Jin, A., Bos, T., Baker, L., Du, Y., Li, Y., Lee, H., Zheng, H. S., Ghafouri, A., Menegali, M., Huang, Y., Krikun, M., Lepikhin, D., Qin, J., Chen, D., Xu, Y., Chen, Z., Roberts, A., Bosma, M., Zhou, Y., Chang, C., Krivokon, I., Rusch, W., Pickett, M., Meier-Hellstern, K. S., Morris, M. R., Doshi, T., Santos, R. D., Duke, T., Soraker, J., Zevenbergen, B., Prabhakaran, V., Diaz, M., Hutchinson, B., Olson, K., Molina, A., Hoffman-John, E., Lee, J., Aroyo, L., Rajakumar, R., Butryna, A., Lamm, M., Kuzmina, V., Fenton, J., Cohen, A., Bernstein, R., Kurzweil, R., Aguera-Arcas, B., Cui, C., Croak, M., Chi, E. H., and Le, Q.  Lamda: Language models for dialog applications.  _CoRR_ , abs/2201.08239, 2022.  URL https://arxiv.org/abs/2201.08239.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.  Attention is all you need.  In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pp. 5998–6008, 2017.
  * Vaswani et al. (2021a) Vaswani, A., Ramachandran, P., Srinivas, A., Parmar, N., Hechtman, B. A., and Shlens, J.  Scaling local self-attention for parameter efficient visual backbones.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021_ , pp. 12894–12904. Computer Vision Foundation / IEEE, 2021a.  doi: 10.1109/CVPR46437.2021.01270.
  * Vaswani et al. (2021b) Vaswani, A., Ramachandran, P., Srinivas, A., Parmar, N., Hechtman, B. A., and Shlens, J.  Scaling local self-attention for parameter efficient visual backbones.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021_ , pp. 12894–12904. Computer Vision Foundation / IEEE, 2021b.  URL https://openaccess.thecvf.com/content/CVPR2021/html/Vaswani_Scaling_Local_Self-Attention_for_Parameter_Efficient_Visual_Backbones_CVPR_2021_paper.html.
  * Vyas et al. (2020) Vyas, A., Katharopoulos, A., and Fleuret, F.  Fast transformers with clustered attention.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.  URL https://proceedings.neurips.cc/paper/2020/hash/f6a8dd1c954c8506aadc764cc32b895e-Abstract.html.
  * Wu et al. (2021) Wu, K., Peng, H., Chen, M., Fu, J., and Chao, H.  Rethinking and improving relative position encoding for vision transformer.  In _2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021_ , pp. 10013–10021. IEEE, 2021.  doi: 10.1109/ICCV48922.2021.00988.  URL https://doi.org/10.1109/ICCV48922.2021.00988.
  * Xiao et al. (2017) Xiao, H., Rasul, K., and Vollgraf, R.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _CoRR_ , abs/1708.07747, 2017.  URL http://arxiv.org/abs/1708.07747.
  * Xiao et al. (2022) Xiao, X., Zhang, T., Choromanski, K., Lee, T. E., Francis, A. G., Varley, J., Tu, S., Singh, S., Xu, P., Xia, F., Persson, S. M., Kalashnikov, D., Takayama, L., Frostig, R., Tan, J., Parada, C., and Sindhwani, V.  Learning model predictive controllers with real-time attention for real-world navigation.  _CoRL 2022_ , abs/2209.10780, 2022.  doi: 10.48550/arXiv.2209.10780.  URL https://doi.org/10.48550/arXiv.2209.10780.
  * Yuan et al. (2021) Yuan, L., Chen, Y., Wang, T., Yu, W., Shi, Y., Jiang, Z., Tay, F. E. H., Feng, J., and Yan, S.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  In _2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021_ , pp. 538–547. IEEE, 2021.  doi: 10.1109/ICCV48922.2021.00060.  URL https://doi.org/10.1109/ICCV48922.2021.00060.
  * Zaheer et al. (2020) Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., et al.  Big bird: Transformers for longer sequences.  _Advances in Neural Information Processing Systems_ , 33:17283–17297, 2020.
  * Zhou et al. (2018) Zhou, B., Lapedriza, À., Khosla, A., Oliva, A., and Torralba, A.  Places: A 10 million image database for scene recognition.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 40(6):1452–1464, 2018.  doi: 10.1109/TPAMI.2017.2723009.  URL https://doi.org/10.1109/TPAMI.2017.2723009.
  * Zhou et al. (2021) Zhou, J., Wang, P., Wang, F., Liu, Q., Li, H., and Jin, R.  ELSA: enhanced local self-attention for vision transformer.  _CoRR_ , abs/2112.12786, 2021.  URL https://arxiv.org/abs/2112.12786.
  * Žiga Avsec et al. (2021) Žiga Avsec, Agarwal, V., Visentin, D., Ledsam, J. R., Grabska-Barwinska, A., Taylor, K. R., Assael, Y., Jumper, J. M., Kohli, P., and Kelley, D. R.  Effective gene expression prediction from sequence by integrating long-range interactions.  _Nature Methods_ , 18:1196 – 1203, 2021.

##  Appendix A Appendix

###  A.1 Potential negative social impact & limitations

This paper works on building scalable and powerful Transformer variants. While
they led to significant advances in language modeling and several other
domains, we note that they should be used cautiously, given the carbon
emission footprint of their training. In addition, this paper only studies
scalable Transformer variants based on low-rank attention (e.g., Performer),
and the technique may not be directly applied to other classes of efficient
Transformers.

###  A.2 Detailed experiment settings

##### Language modeling.

Following existing works (Peng et al., 2021; Luo et al., 2021), the sequence
length is set to 512 during both training and evaluation. All models are
trained without access to the context from previous mini-batches for a fair
comparison. The dropout ratio and weight decay are set to 0.1 and 0.01,
respectively. The batch size is set to 64. We use $\mathrm{Adam}$ as the
optimizer, and set its hyperparameter $\varepsilon$ to $1\mathrm{e}-6$ and
$(\beta_{1},\beta_{2})$ to (0.9, 0.98). The model is trained for 150k steps
with a 6k-step warm-up stage followed by an inverse square-root learning rate
scheduler, with the peak learning rate set to $2\mathrm{e}-3$.

For the $\mathrm{FLT}$ variant with Gaussian mixture RPE, the FT of the RPE
function, i.e., the function $g$, is parameterized as described in Eq. (6).
For the $\mathrm{FLT}$ variant with local RPE, the function $g$ is
parameterized as

$g(\xi)=\sum_{t=1}^{T}w_{t}\cdot\frac{\sin(2\pi v_{t}\xi)}{\pi\xi},$ (13)

where $w_{1},\cdots,w_{T}$ and $v_{1},\cdots,v_{T}$ are learnable parameters
and $T$ is a pre-defined hyper-parameter. In this case, the underlying implict
RPE function $f$ is

$f(\Delta r)=\sum_{t=1}^{T}w_{t}\cdot\mathbbm{1}[|\Delta r|\leq v_{t}].$ (14)

For both $\mathrm{FLT}$ variants, the RPE masks are different in different
attention heads, but are shared across different layers. The random features
$\xi_{1},\cdots,\xi_{r}$ are sampled from the standard Gaussian distribution.

##### Image classification.

For all the models, we used a dropout rate of 0.1 and no attention dropout. We
applied the $\mathrm{Adam}$ optimizer with weight decay equal to 0.05 and a
standard batch size of 4096. All Transformers were trained on TPU
architectures until convergence.

Table 5: Hyperparameters for Image Classification. Parameter |  | Value
---|---|---
Batch size |  | $4096$
Optimizer |  | AdamW
Base Learning rate |  | $1.5\mathrm{e}-4$
Weight decay |  | 0.05
Optimizer momentum |  | $(\beta_{1},\beta_{2})=(0.9,0.95)$
Learning rate schedule |  | cosine decay
Warm up epochs |  | 40
Augmentation |  | RandomResizedCrop
Compute resources |  |  $8\times 8$ TPUv3

##### Molecular property prediction.

For all the models, the attention dropout ratio and the weight decay are set
to 0.1 and 0.001, respectively. The batch size is set to 64. We use
$\mathrm{Adam}$ as the optimizer, and set its hyperparameter $\varepsilon$ to
$1\mathrm{e}-6$ and $(\beta_{1},\beta_{2})$ to (0.9, 0.98). The peak learning
rate is set to $3\mathrm{e}-4$ with a 10K-step warm-up stage. After the warm-
up stage, the learning rate decays linearly to zero. All the models are
trained for 500k steps in total.


Numerical Matrix Decomposition and its Modern Applications:
A Rigorous First Course

Jun Lu

CHAPTER: ABSTRACT

In 1954, Alston S. Householder published Principles of Numerical Analysis, one of the first modern treatments on matrix decomposition that favored a (block) LU
decomposition-the factorization of a matrix
into the product of lower and upper triangular
And now, matrix decomposition has become a core technology in machine learning, largely due to the development of the back propagation algorithm in fitting a neural network. The sole aim of this survey is to give a self-contained introduction to concepts and mathematical tools in numerical linear algebra and matrix analysis in order to seamlessly introduce matrix decomposition techniques and their applications in subsequent sections. However, we clearly realize our inability to cover all the useful and interesting results concerning matrix decomposition and given the paucity of scope to present this discussion, e.g., the separated analysis of the Euclidean space, Hermitian space, Hilbert space, and things in the complex domain. We refer the reader to literature in the field of linear algebra for a more detailed introduction to the related fields.

This survey is primarily a summary of purpose, significance of important matrix decomposition methods, e.g., LU, QR, and SVD, and the origin and complexity of the methods which shed light on their modern applications.
Most importantly, this article presents improved procedures for most of the calculations of the decomposition algorithms which potentially reduce the complexity they induce.
Again, this is a decomposition-based context, thus we will introduce the related background when it is needed and necessary. In many other textbooks on linear algebra, the principal ideas are discussed and the matrix decomposition methods serve as “byproduct". However, we focus on the decomposition methods instead and the principal ideas serve as fundamental tools for them. The mathematical prerequisite is a first course in linear algebra. Other than this modest background, the development is self-contained, with rigorous proof provided throughout.

Existence and computing of matrix decompositions, Complexity, Floating point operations (flops), Low-rank approximation, Pivot, LU decomposition for nonzero leading principal minors, Data distillation, CR decomposition, CUR/Skeleton decomposition, Interpolative decomposition, Biconjugate decomposition, Coordinate transformation, Hessenberg decomposition, ULV decomposition, URV decomposition, Rank decomposition, Gram-Schmidt process, Householder reflector, Givens rotation, Rank revealing decomposition, Cholesky decomposition and update/downdate, Eigenvalue problems, Alternating least squares, Randomized algorithm, Tensor decomposition, CP decomposition, Tucker decomposition, High-order SVD.

[Ailon and Chazelle, 2006]
Nir Ailon and Bernard Chazelle.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss
In Proceedings of the thirty-eighth annual ACM symposium on
Theory of computing, pages 557–563, 2006.

[Anderson and Styan, 1980]
Theodore Wilbur Anderson and George PH Styan.
Cochran's theorem, rank additivity, and tripotent matrices.
Technical report, STANFORD UNIV CA DEPT OF STATISTICS, 1980.

[Baarland, 1991]
A Baarland.
Perturbation bounds for the LDLH and the LU factorizations.
BIT, 31:0 341–352, 1991.

[Bai and Demmel, 1993]
Zhaojun Bai and James W Demmel.
Computing the generalized singular value decomposition.
SIAM Journal on Scientific Computing, 140
(6):0 1464–1486, 1993.

[Banerjee and Roy, 2014]
Sudipto Banerjee and Anindya Roy.
Linear algebra and matrix analysis for statistics, volume 181.
Crc Press Boca Raton, FL, USA:, 2014.

[Beck, 2017]
Amir Beck.
First-Order Methods in Optimization, volume 25.
SIAM, 2017.

[Bennett et al., 2007]
James Bennett, Stan Lanning, et al.
The netflix prize.
In Proceedings of KDD cup and workshop, volume 2007, page 35.
New York, NY, USA., 2007.

[Bigoni et al., 2016]
Daniele Bigoni, Allan P Engsig-Karup, and Youssef M Marzouk.
Spectral tensor-train decomposition.
SIAM Journal on Scientific Computing, 380
(4):0 A2405–A2439, 2016.

[Bischof, 1986]
Christian Bischof.
The two-sided block Jacobi method on a hypercube architecture,
volume 86.
Mathematical Sciences Institute, Cornell University, 1986.

[Bishop, 2006]
Christopher M Bishop.
Pattern recognition.
Machine learning, 1280 (9), 2006.

[Bojanczyk et al., 1987]
Adam W Bojanczyk, RP Brent, Paul Van Dooren, and FR De Hoog.
A note on downdating the Cholesky factorization.
SIAM Journal on Scientific and Statistical Computing,
80 (3):0 210–221, 1987.

[Boutsidis and Gallopoulos, 2008]
Christos Boutsidis and Efstratios Gallopoulos.
SVD based initialization: A head start for nonnegative matrix
Pattern recognition, 410 (4):0 1350–1362,

[Boutsidis et al., 2009]
Christos Boutsidis, Michael W Mahoney, and Petros Drineas.
An improved approximation algorithm for the column subset selection
In Proceedings of the twentieth annual ACM-SIAM symposium on
Discrete algorithms, pages 968–977. SIAM, 2009.

[Boyd and Vandenberghe, 2018]
Stephen Boyd and Lieven Vandenberghe.
Introduction to applied linear algebra: vectors, matrices, and
least squares.
Cambridge university press, 2018.

[Boyd et al., 2004]
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.
Convex optimization.
Cambridge university press, 2004.

[Bueno and Dopico, 2004]
M Isabel Bueno and Froilán M Dopico.
Stability and sensitivity of tridiagonal LU factorization without
BIT Numerical Mathematics, 440 (4):0 651–673,

[Chan, 1982]
Tony F Chan.
An improved algorithm for computing the singular value decomposition.
ACM Transactions on Mathematical Software (TOMS), 80
(1):0 72–83, 1982.

[Chan, 1987]
Tony F Chan.
Rank revealing QR factorizations.
Linear algebra and its applications, 88:0 67–82,

[Chang, 1997]
Xiao-Wen Chang.
Pertubation Analysis of Some Matrix Factorizations.
McGill University Montreal, 1997.

[Chang and Paige, 1998]
Xiao-Wen Chang and Christopher C Paige.
On the sensitivity of the LU factorization.
BIT Numerical Mathematics, 380 (3):0 486–501,

[Chang et al., 1997]
Xiao-Wen Chang, Christopher C Paige, and GW Stewart.
Perturbation analyses for the QR factorization.
SIAM Journal on Matrix Analysis and Applications, 180
(3):0 775–791, 1997.

[Chen et al., 2015]
Tianqi Chen, Ian Goodfellow, and Jonathon Shlens.
Net2net: Accelerating learning via knowledge transfer.
arXiv preprint arXiv:1511.05641, 2015.

[Chen et al., 2008]
Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam.
Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization
and update/downdate.
ACM Transactions on Mathematical Software (TOMS), 350
(3):0 1–14, 2008.

[Cheng et al., 2005]
Hongwei Cheng, Zydrunas Gimbutas, Per-Gunnar Martinsson, and Vladimir Rokhlin.
On the compression of low rank matrices.
SIAM Journal on Scientific Computing, 260
(4):0 1389–1404, 2005.

[Christensen, 1991]
Ronald Christensen.
Linear models for multivariate, time series, and spatial data,
volume 1.
Springer, 1991.

[Chu et al., 1995]
Moody T Chu, Robert E Funderlic, and Gene H Golub.
A rank–one reduction formula and its applications to matrix
SIAM review, 370 (4):0 512–530, 1995.

[Cichocki et al., 2016]
Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and
Danilo P Mandic.
Tensor networks for dimensionality reduction and large-scale
optimization: Part 1 low-rank tensor decompositions.
Foundations and Trends® in Machine Learning,
90 (4-5):0 249–429, 2016.

[Cipra, 2000]
Barry A Cipra.
The best of the 20th century: Editors name top 10 algorithms.
SIAM news, 330 (4):0 1–2, 2000.

[Comon et al., 2009]
Pierre Comon, Xavier Luciani, and André LF De Almeida.
Tensor decompositions, alternating least squares and other tales.
Journal of Chemometrics: A Journal of the Chemometrics
Society, 230 (7-8):0 393–405, 2009.

[Davis, 2008]
Timothy A Davis.
User guide for CHOLMOD: a sparse Cholesky factorization and
modification package.
Department of Computer and Information Science and Engineering,
University of Florida, Gainesville, FL, USA, 2008.

[Davis and Hager, 1999]
Timothy A Davis and William W Hager.
Modifying a sparse Cholesky factorization.
SIAM Journal on Matrix Analysis and Applications, 200
(3):0 606–627, 1999.

[Dawes and Corrigan, 1974]
Robyn M Dawes and Bernard Corrigan.
Linear models in decision making.
Psychological bulletin, 810 (2):0 95, 1974.

[De Lathauwer et al., 2000]
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle.
A multilinear singular value decomposition.
SIAM journal on Matrix Analysis and Applications, 210
(4):0 1253–1278, 2000.

[Dongarra and Sullivan, 2000]
Jack Dongarra and Francis Sullivan.
Guest editors' introduction: The top 10 algorithms.
IEEE Computer Architecture Letters, 20 (01):0
22–23, 2000.

[Dopico et al., 2006]
Froilán M Dopico, Charles R Johnson, and Juan M Molera.
Multiple LU factorizations of a singular matrix.
Linear algebra and its applications, 4190
(1):0 24–36, 2006.

[Drineas et al., 2012]
Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruff.
Fast approximation of matrix coherence and statistical leverage.
The Journal of Machine Learning Research, 130
(1):0 3475–3506, 2012.

[Fierro and Hansen, 1997]
Ricardo D Fierro and Per Christian Hansen.
Low-rank revealing UTV decompositions.
Numerical Algorithms, 150 (1):0 37–55, 1997.

[Foster, 2003]
Leslie V Foster.
Solving rank-deficient and ill-posed problems using UTV and QR
SIAM journal on matrix analysis and applications, 250
(2):0 582–600, 2003.

[Fox, 1997]
John Fox.
Applied regression analysis, linear models, and related
Sage Publications, Inc, 1997.

[Francis, 1961]
John GF Francis.
The QR transformation a unitary analogue to the LR
transformation—part 1.
The Computer Journal, 40 (3):0 265–271, 1961.

[Francis, 1962]
John GF Francis.
The QR transformation—part 2.
The Computer Journal, 40 (4):0 332–345, 1962.

[Gallier and Quaintance, 2017]
Jean Gallier and Jocelyn Quaintance.
Fundamentals of Linear Algebra and Optimization.
Department of Computer and Information Science, University of
Pennsylvania, 2017.

[Gallier et al., 2010]
Jean Gallier et al.
The schur complement and symmetric positive semidefinite (and
definite) matrices.
Penn Engineering, pages 1–12, 2010.

[Gauss, 1809]
Carl Friedrich Gauss.
Theoria motus corporum coelestium in sectionibus conicis solem
ambientium, volume 1.
FA Perthes, 1809.

[Gauss, 1810]
Carl Friedrich Gauss.
Disquisitio de elementis elliptics Palladis.
Dieterich, 1810.

[Gentle, 1998]
James E Gentle.
Numerical linear algebra for applications in statistics.
Springer Science & Business Media, 1998.

[Gentle, 2007]
James E Gentle.
Matrix algebra.
Springer texts in statistics, Springer, New York, NY, doi,
10:0 978–0, 2007.

[Giampouras et al., 2018]
Paris V Giampouras, Athanasios A Rontogiannis, and Konstantinos D Koutroumbas.
Alternating iteratively reweighted least squares minimization for
low-rank matrix factorization.
IEEE Transactions on Signal Processing, 670
(2):0 490–503, 2018.

[Gilbert, 1991]
George T Gilbert.
Positive definite matrices and Sylvester's criterion.
The American Mathematical Monthly, 980 (1):0
44–46, 1991.

[Gill et al., 1974]
Philip E Gill, Gene H Golub, Walter Murray, and Michael A Saunders.
Methods for modifying matrix factorizations.
Mathematics of computation, 280 (126):0
505–535, 1974.

[Gill et al., 2021]
Philip E Gill, Walter Murray, and Margaret H Wright.
Numerical linear algebra and optimization.
SIAM, 2021.

[Gillis, 2014]
Nicolas Gillis.
The why and how of nonnegative matrix factorization.
Connections, 12:0 2–2, 2014.

[Gohberg and Goldberg, 1996]
Israel Gohberg and Seymour Goldberg.
A simple proof of the jordan decomposition theorem for matrices.
The American Mathematical Monthly, 1030 (2):0
157–159, 1996.

[Goldfarb, 1976]
Donald Goldfarb.
Factorized variable metric methods for unconstrained optimization.
Mathematics of Computation, 300 (136):0
796–811, 1976.

[Golub and Kahan, 1965]
Gene Golub and William Kahan.
Calculating the singular values and pseudo-inverse of a matrix.
Journal of the Society for Industrial and Applied Mathematics,
Series B: Numerical Analysis, 20 (2):0 205–224, 1965.

[Golub and Van Loan, 2013]
Gene H Golub and Charles F Van Loan.
Matrix computations, volume 3.
JHU press, 2013.

[Goodfellow et al., 2016]
Ian Goodfellow, Yoshua Bengio, and Aaron Courville.
Deep learning.
MIT press, 2016.

[Goreinov and Tyrtyshnikov, 2001]
Sergei A Goreinov and Eugene E Tyrtyshnikov.
The maximal-volume concept in approximation by low-rank matrices.
Contemporary Mathematics, 280:0 47–52, 2001.

[Goreinov et al., 1997]
Sergei A Goreinov, Nikolai Leonidovich Zamarashkin, and Evgenii Evgen’evich
Pseudo-skeleton approximations by matrices of maximal volume.
Mathematical Notes, 620 (4):0 515–519, 1997.

[Goreinov et al., 2010]
Sergei A Goreinov, Ivan V Oseledets, Dimitry V Savostyanov, Eugene E
Tyrtyshnikov, and Nikolay L Zamarashkin.
How to find a good submatrix.
In Matrix Methods: Theory, Algorithms And Applications:
Dedicated to the Memory of Gene Golub, pages 247–256. World Scientific,

[Gut, 2009]
Allan Gut.
Quadratic forms and Cochran’s theorem.
In An Intermediate Course in Probability, pages 117–145.
Springer, 2009.

[Hales and Passi, 1999]
AW Hales and IBS Passi.
Jordan decomposition.
In Algebra, pages 75–87. Springer, 1999.

[Halko et al., 2011]
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp.
Finding structure with randomness: Probabilistic algorithms for
constructing approximate matrix decompositions.
SIAM review, 530 (2):0 217–288, 2011.

[Harper and Konstan, 2015]
F Maxwell Harper and Joseph A Konstan.
The movielens datasets: History and context.
Acm transactions on interactive intelligent systems (tiis),
50 (4):0 1–19, 2015.

[Håstad, 1989]
Johan Håstad.
Tensor rank is np-complete.
In International Colloquium on Automata, Languages, and
Programming, pages 451–460. Springer, 1989.

[Henrici, 1958]
Peter Henrici.
On the speed of convergence of cyclic and quasicyclic jacobi methods
for computing eigenvalues of hermitian matrices.
Journal of the Society for Industrial and Applied Mathematics,
60 (2):0 144–162, 1958.

[Higham, 2002]
Nicholas J Higham.
Accuracy and stability of numerical algorithms.
SIAM, 2002.

[Higham, 2009]
Nicholas J Higham.
Cholesky factorization.
Wiley Interdisciplinary Reviews: Computational Statistics,
10 (2):0 251–254, 2009.

[Hotelling, 1933]
Harold Hotelling.
Analysis of a complex of statistical variables into principal
Journal of educational psychology, 240 (6):0
417, 1933.

[Householder, 2006]
Alston S Householder.
Principles of numerical analysis.
Courier Corporation, 2006.

[Hwang et al., 1992]
Tsung-Min Hwang, Wen-Wei Lin, and Eugene K Yang.
Rank revealing LU factorizations.
Linear algebra and its applications, 175:0 115–141,

[Jacobi and Verfahren, 1846]
C. G. J. Jacobi and Über ein leichtes Verfahren.
die in der Theorie der säkular-störungen vorkommenden gleichungen
numerisch aufzulösen.
Crelle’s Journal 30, 40 (4):0 51–94, 1846.

[James, 1952]
GS James.
Notes on a theorem of Cochran.
In Mathematical Proceedings of the Cambridge Philosophical
Society, volume 48, pages 443–446. Cambridge University Press, 1952.

[Jordan, 1870]
Camille Jordan.
Traité des substitutions et des équations
Gauthier-Villars, 1870.

[Kiers, 2000]
Henk AL Kiers.
Towards a standardized notation and terminology in multiway analysis.
Journal of Chemometrics: A Journal of the Chemometrics
Society, 140 (3):0 105–122, 2000.

[Kishore Kumar and Schneider, 2017]
N Kishore Kumar and Jan Schneider.
Literature survey on low rank approximation of matrices.
Linear and Multilinear Algebra, 650 (11):0
2212–2244, 2017.

[Koeber and Schäfer, 2006]
Martin Koeber and Uwe Schäfer.
The unique square root of a positive semidefinite matrix.
International Journal of Mathematical Education in Science and
Technology, 370 (8):0 990–992, 2006.

[Kolda and Bader, 2009]
Tamara G Kolda and Brett W Bader.
Tensor decompositions and applications.
SIAM review, 510 (3):0 455–500, 2009.

[Kolda, 2006]
Tamara Gibson Kolda.
Multilinear operators for higher-order decompositions.
Technical report, Citeseer, 2006.

[Kruskal, 1977]
Joseph B Kruskal.
Three-way arrays: rank and uniqueness of trilinear decompositions,
with application to arithmetic complexity and statistics.
Linear algebra and its applications, 180 (2):0
95–138, 1977.

[Lane, 2002]
PW Lane.
Generalized linear models in soil science.
European Journal of Soil Science, 530 (2):0
241–251, 2002.

[Lawson and Hanson, 1995]
Charles L Lawson and Richard J Hanson.
Solving least squares problems.
SIAM, 1995.

[Lee and Seung, 2001]
Daniel D Lee and Hyunjune Sebastian Seung.
Algorithms for non-negative matrix factorization.
In 14th Annual Neural Information Processing Systems
Conference, NIPS 2000. Neural information processing systems foundation,

[Leondes, 1995]
Cornelius T Leondes.
Multidimensional Systems: Signal Processing and Modeling
Techniques: Advances in Theory and Applications.
Elsevier, 1995.

[Lu, 2017]
Jun Lu.
Machine learning modeling for time series problem: Predicting
flight ticket prices.
arXiv preprint arXiv:1705.07205, 2017.

[Lu, 2021]
Jun Lu.
A survey on Bayesian inference for Gaussian mixture model.
arXiv preprint arXiv:2108.11753, 2021a.

[Lu, 2021]
Jun Lu.
On the column and row ranks of a matrix.
arXiv preprint arXiv:2112.06638, 2021b.

[Lu, 2021]
Jun Lu.
Revisit the fundamental theorem of linear algebra.
arXiv preprint arXiv:2108.04432, 2021c.

[Lu, 2021]
Jun Lu.
A rigorous introduction for linear models.
arXiv preprint arXiv:2105.04240, 2021d.

[Lu, 2022]
Jun Lu.
Matrix decomposition and applications.
arXiv preprint arXiv:2201.00145, 2022.

[Lu et al., 2018]
Jun Lu, Wei Ma, and Boi Faltings.
Compnet: Neural networks growing via the compact network morphism.
arXiv preprint arXiv:1804.10316, 2018.

[Ma and Lu, 2017]
Wei Ma and Jun Lu.
An equivalence of fully connected layer and convolutional layer.
arXiv preprint arXiv:1712.01252, 2017.

[Mahoney and Drineas, 2009]
Michael W Mahoney and Petros Drineas.
CUR matrix decompositions for improved data analysis.
Proceedings of the National Academy of Sciences, 1060
(3):0 697–702, 2009.

[Martinsson, 2019]
Per-Gunnar Martinsson.
Randomized methods for matrix computations.
The Mathematics of Data, 250 (4):0 187–231,

[95]
PG Martinsson and JA Tropp.
Randomized numerical linear algebra: foundations & algorithms
arXiv preprint arXiv:2002.01387.

[Miranian and Gu, 2003]
L Miranian and Ming Gu.
Strong rank revealing LU factorizations.
Linear algebra and its applications, 367:0 1–16,

[Mrode, 2014]
Raphael A Mrode.
Linear models for the prediction of animal breeding values.
Cabi, 2014.

[Oseledets, 2011]
Ivan V Oseledets.
Tensor-train decomposition.
SIAM Journal on Scientific Computing, 330
(5):0 2295–2317, 2011.

[Paige and Saunders, 1981]
Christopher C Paige and Michael A Saunders.
Towards a generalized singular value decomposition.
SIAM Journal on Numerical Analysis, 180 (3):0
398–405, 1981.

[Pan, 2000]
C-T Pan.
On the existence and computation of rank-revealing LU
Linear Algebra and its Applications, 3160
(1-3):0 199–222, 2000.

[Pauca et al., 2006]
V Paul Pauca, Jon Piper, and Robert J Plemmons.
Nonnegative matrix factorization for spectral data analysis.
Linear algebra and its applications, 4160
(1):0 29–47, 2006.

[Pearson, 1901]
Karl Pearson.
Liii. on lines and planes of closest fit to systems of points in
The London, Edinburgh, and Dublin philosophical magazine and
journal of science, 20 (11):0 559–572, 1901.

[Quarteroni et al., 2010]
Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri.
Numerical mathematics, volume 37.
Springer Science & Business Media, 2010.

[Rutishauser, 1958]
Heinz Rutishauser.
Solution of eigenvalue problems with the LR-transformation.
National Bureau of Standards, Applied Mathematics Series,
49:0 47–81, 1958.

[Schaeffer, 2004]
Lawrence R Schaeffer.
Application of random regression models in animal breeding.
Livestock Production Science, 860 (1-3):0
35–45, 2004.

[Schilders, 2009]
Wil HA Schilders.
Solution of indefinite linear systems using an LQ decomposition for
the linear constraints.
Linear algebra and its applications, 4310
(3-4):0 381–395, 2009.

[Schönhage, 1964]
A Schönhage.
On the quadratic convergence of the jacobi process.
Numer. Math, 60 (410):0 12, 1964.

[Seeger, 2004]
Matthias Seeger.
Low rank updates for the Cholesky decomposition.
Technical report, 2004.

[Shlens, 2014]
Jonathon Shlens.
A tutorial on principal component analysis.
arXiv preprint arXiv:1404.1100, 2014.

[Shroff and Schreiber, 1989]
Gautam Shroff and Robert Schreiber.
On the convergence of the cyclic jacobi method for parallel block
SIAM journal on matrix analysis and applications, 100
(3):0 326–346, 1989.

[Stewart, 1998]
Gilbert W Stewart.
Matrix Algorithms: Volume 1: Basic Decompositions.
SIAM, 1998.

[Stewart, 1993]
GW Stewart.
On the perturbation of LU, Cholesky, and QR factorizations.
SIAM Journal on Matrix Analysis and Applications, 140
(4):0 1141–1145, 1993.

[Stewart, 1997]
GW Stewart.
On the perturbation of LU and Cholesky factors.
IMA Journal of Numerical Analysis, 170 (1):0
1–6, 1997.

[Stewart, 2000]
GW Stewart.
The decompositional approach to matrix computation.
Computing in Science & Engineering, 20 (1):0
50–59, 2000.

[Strang, 1993]
Gilbert Strang.
The fundamental theorem of linear algebra.
The American Mathematical Monthly, 1000 (9):0
848–855, 1993.

[Strang, 2009]
Gilbert Strang.
Introduction to linear algebra.
Wellesley-Cambridge Press Wellesley, 4th edition, 2009.

[Strang, 2019]
Gilbert Strang.
Linear algebra and learning from data.
Wellesley-Cambridge Press Cambridge, 2019.

[Strang, 2021]
Gilbert Strang.
Linear algebra for everyone.
Wellesley-Cambridge Press Wellesley, 2021.

[Strang and Drucker, 2021]
Gilbert Strang and Daniel Drucker.
Three matrix factorizations from the steps of elimination.

[Strang and Moler, 2021]
Gilbert Strang and Cleve Moler.
LU and CR elimination.

[Sun, 1992]
Ji-Guang Sun.
Componentwise perturbation bounds for some matrix decompositions.
BIT Numerical Mathematics, 320 (4):0 702–714,

[Sun, 1992]
Ji-guang Sun.
Rounding-error and perturbation bounds for the Cholesky and LDLT
Linear algebra and its applications, 173:0 77–97,

[Swamy, 1973]
Kuduvally Swamy.
On Sylvester's criterion for positive-semidefinite matrices.
IEEE Transactions on Automatic Control, 180
(3):0 306–306, 1973.

[Symeonidis and Zioupos, 2016]
Panagiotis Symeonidis and Andreas Zioupos.
Matrix and Tensor Factorization Techniques for Recommender
Systems, volume 1.
Springer, 2016.

[Takács and Tikk, 2012]
Gábor Takács and Domonkos Tikk.
Alternating least squares for personalized ranking.
In Proceedings of the sixth ACM conference on Recommender
systems, pages 83–90, 2012.

[Tan, 1975]
WY Tan.
Some matrix results and extensions of Cochran’s theorem.
SIAM Journal on Applied Mathematics, 280 (3):0
547–554, 1975.

[Trefethen and Bau III, 1997]
Lloyd N Trefethen and David Bau III.
Numerical linear algebra, volume 50.
Siam, 1997.

[van de Geijn and Myers, 2020]
Robert van de Geijn and Margaret Myers.
Advanced linear algebra: Foundations to frontiers.
Creative Commons NonCommercial (CC BY-NC), 2020.

[Van Kempen, 1966]
HPM Van Kempen.
On the quadratic convergence of the special cyclic jacobi method.
Numerische Mathematik, 90 (1):0 19–22, 1966.

[Van Loan, 1985]
Charles Van Loan.
The block jacobi method for computing the singular value
Technical report, Cornell University, 1985.

[Van Loan, 2000]
Charles F Van Loan.
The ubiquitous kronecker product.
Journal of computational and applied mathematics, 1230
(1-2):0 85–100, 2000.

[Van Zee et al., 2012]
Field G Van Zee, Robert A Van De Geijn, Gregorio Quintana-Ortí, and
G Joseph Elizondo.
Families of algorithms for reducing a matrix to condensed form.
ACM Transactions on Mathematical Software (TOMS), 390
(1):0 1–32, 2012.

[Van Zee et al., 2014]
Field G Van Zee, Robert A Van de Geijn, and Gregorio Quintana-Ortí.
Restructuring the tridiagonal and bidiagonal QR algorithms for
ACM Transactions on Mathematical Software (TOMS), 400
(3):0 1–34, 2014.

[Voronin and Martinsson, 2017]
Sergey Voronin and Per-Gunnar Martinsson.
Efficient algorithms for CUR and interpolative matrix
Advances in Computational Mathematics, 430
(3):0 495–516, 2017.

[Wei et al., 2016]
Tao Wei, Changhu Wang, Yong Rui, and Chang Wen Chen.
Network morphism.
In International Conference on Machine Learning, pages
564–572. PMLR, 2016.

[Wilkinson, 1968]
James H Wilkinson.
Global convergene of tridiagonal QR algorithm with origin shifts.
Linear Algebra and its Applications, 10 (3):0
409–420, 1968.

[Wilkinson, 1962]
James Hardy Wilkinson.
Note on the quadratic convergence of the cyclic jacobi process.
Numerische Mathematik, 40 (1):0 296–300,

[Wilkinson, 1971]
JH Wilkinson.
The algebraic eigenvalue problem.
In Handbook for Automatic Computation, Volume II, Linear
Algebra. Springer-Verlag New York, 1971.

[Wu and Wu, 2009]
Hui-Hua Wu and Shanhe Wu.
Various proofs of the Cauchy-Schwarz inequality.
Octogon mathematical magazine, 170 (1):0
221–229, 2009.

[Yang, 2000]
Ming Yang.
Matrix decomposition.
Northwestern University, Class Notes, 2000.

[Zha, 1989]
H Zha.
Restricted singular value decomposition of matrix triplets, number
89-2 in.
Scientific Report, 1989.

[Zhang, 2017]
Xian-Da Zhang.
Matrix analysis and applications.
Cambridge University Press, 2017.

[Zhu and Lin, 2011]
X Zhu and W Lin.
Randomised pseudo-skeleton approximation and its application in
Electronics letters, 470 (10):0 590–592,

[Zoubir et al., 2012]
Abdelhak M Zoubir, Visa Koivunen, Yacine Chakhchoukh, and Michael Muma.
Robust estimation in signal processing: A tutorial-style treatment
of fundamental concepts.
IEEE Signal Processing Magazine, 290 (4):0
61–80, 2012.