#  Computing on Functions Using Randomized Vector Representations ††thanks:
The work of DK was supported by the European Union’s Horizon 2020 Programme
under the Marie Skłodowska-Curie Individual Fellowship Grant (839179). The
work of CJK was supported by the Department of Defense (DoD) through the
National Defense Science & Engineering Graduate (NDSEG) Fellowship Program.
FTS was supported by Intel and NIH R01-EB026955. The work of BAO and DK was
supported in part by the DARPA’s VIP (Super-HD Project) and AIE (HyDDENN
Project) programs and by AFOSR FA9550-19-1-0241. The work of FTS, BAO, and DK
was supported in part by Intel’s THWAI program.

E. Paxon Frady1,2, Denis Kleyko2,3, Christopher J. Kymn2,
Bruno A. Olshausen2, Friedrich T. Sommer1,2

(1. Intel, Neuromorphic Computing Lab
2\. UC Berkeley, Redwood Center for Theoretical Neuroscience
3\. Research Institutes of Sweden, Intelligent Systems Lab
)

###### Abstract

Vector space models for symbolic processing that encode symbols by random
vectors have been proposed in cognitive science and connectionist communities
under the names Vector Symbolic Architecture (VSA), and, synonymously,
Hyperdimensional (HD) computing. In this paper, we generalize VSAs to function
spaces by mapping continuous-valued data into a vector space such that the
inner product between the representations of any two data points represents a
similarity kernel. By analogy to VSA, we call this new function encoding and
computing framework Vector Function Architecture (VFA). In VFAs, vectors can
represent individual data points as well as elements of a function space (a
reproducing kernel Hilbert space). The algebraic vector operations, inherited
from VSA, correspond to well-defined operations in function space.
Furthermore, we study a previously proposed method for encoding continuous
data, fractional power encoding (FPE), which uses exponentiation of a random
base vector to produce randomized representations of data points and fulfills
the kernel properties for inducing a VFA. We show that the distribution from
which elements of the base vector are sampled determines the shape of the FPE
kernel, which in turn induces a VFA for computing with band-limited functions.
In particular, VFAs provide an algebraic framework for implementing large-
scale kernel machines with random features, extending Rahimi and Recht,
(2007). Finally, we demonstrate several applications of VFA models to problems
in image recognition, density estimation and nonlinear regression. Our
analyses and results suggest that VFAs constitute a powerful new framework for
representing and manipulating functions in distributed neural systems, with
myriad applications in artificial intelligence.

##  1 Introduction

The impressive recent achievements in artificial intelligence (AI) are driven
by models that compute on data representations embedded in high-dimensional
vector spaces, to date most notably, neural networks (Bengio et al.,, 2021).
Once provided with input data and, if applicable, supervisory signals, neural
networks provide powerful end-to-end training mechanisms to optimize
performance for a given task. However, state-of-the-art neural networks still
suffer from two fundamental problems. One is that the application of learned
knowledge is brittle and does not easily generalize to new contexts outside
the training set. It has been argued that this problem is due in part to the
inability to do variable binding (Fodor and Pylyshyn,, 1988; Greff et al.,,
2020), which is crucial for enabling knowledge learned in one domain to be
detached and flexibly applied to other domains (Smolensky,, 1990). A second
inherent problem with current neural networks is a lack of transparency. That
is, both the vector representations and transformations in the neural network
have no clear interpretation in terms of computation. Although the explicit
computations whereby signals are combined through weighted sums and
thresholding are well specified and understood for each neuron in the network,
the overall system is often treated as a black box without gaining insight
into the mathematical structure of the representations learned or the
underlying computational function that is being performed by the network as a
whole. The lack of transparency is an obstacle both in using neural networks
as explanatory models for brain function, and in analyzing, understanding, or
explaining the decisions of a neural network in specific application settings.

In recent years, we and others have made progress in advancing a vector space
computing framework called Vector Symbolic Architecture (VSA), or synonymously
Hyperdimensional (HD) computing, that both enables variable binding and is
fully transparent (Plate, 1994a, ; Kanerva,, 1996; Gayler, 1998a, ; Eliasmith
and Thagard,, 2001; Rachkovskij and Kussul,, 2001). In VSA, symbols, data, or
other entities are represented by randomly mapping them into a vector space of
fixed dimensionality. An algebra over these vectors consisting of addition,
multiplication and permutation enables the operations of bundling, binding and
sequencing, respectively (Kleyko et al.,, 2021). There are now multiple
successful examples of this approach applied to text analysis (Jones and
Mewhort,, 2007; Joshi et al., 2016a, ; Recchia et al.,, 2015), decoding of EEG
and EMG signals (Rahimi et al.,, 2019; Moin et al.,, 2021), sequence learning
(Hannagan et al.,, 2011; Frady et al., 2018c, ), and robotics (Neubert et
al.,, 2019). However, to date most of these applications have been limited to
discrete data such as text, words or other tokens, or by discretizing data
that are fundamentally continuous in nature and thereby ignoring important
topological similarity relationships in the data (Edelman,, 1998).

In this paper, we turn to the question of how continuous data and functions
may be represented in a vector space, and how they may be manipulated via the
algebra of VSA. We develop a new framework for computing with functions in a
vector space, which by analogy to VSA we call Vector Function Architecture
(VFA). Like VSA, VFA is fully transparent. Vectors can represent individual
data points as well as elements of a function space that is well-defined as a
reproducing kernel Hilbert space. The domain of the functions can encode
continuous-valued quantities in data, such as position, time or wavelength.
Functions are manipulated by the vector operations of VSA: addition of vectors
corresponds to addition of functions, and binding of vectors corresponds to
convolution of functions. The function domain is encoded by exponentiating a
fixed random base vector — this encoding has been introduced before as
fractional power encoding (Plate,, 1992; Plate, 1994a, ). Together, these
encodings and operations open the door to a powerful new way of computing on
data such as images, sound waveforms, and myriad other types of continuous
information streams where one desires to manipulate functions — as is
currently done in symbolic computing — but where information is represented
holistically by elements of the system as in neural networks.

Beyond its relation to VSA, VFA may be seen as part of a larger class of
algorithms that leverage randomness to either expand dimensionality — e.g.,
hashing (Cormen et al.,, 2009; Dasgupta et al.,, 2008), stochastic computing
(Alaghi and Hayes,, 2018), reservoir computing (Frady et al., 2018c, ;
Cuchiero et al.,, 2021) — or reduce dimensionality — e.g., compressed sensing
(Candès et al.,, 2006; Donoho,, 2006; Frady et al.,, 2021). In particular,
VFAs provides an algebraic framework for implementing large-scale kernel
machines with random features, including and extending Rahimi and Recht,
(2007). On the other hand, what sets VFA apart from all of these methods is
that it contains a mathematically grounded framework for computing on the
high-dimensional representations.

We envision that the VFA framework will help towards building a type of AI
which uses representations that are distributed, interpretable, and can be
processed by algebraic vector operations with well-defined computational
meaning. This AI approach could combine advantages of neural networks,
probabilistic reasoning and symbolic AI; that is, the ability to learn, to be
executable on distributed hardware, and to have the capability of rule-based
reasoning for generalizing and extrapolating prior knowledge. We believe the
approach may also help provide insight into highly distributed representations
in the brain, such as in entorhinal cortex and hippocampus.

The rest of the paper is organized as follows. Section 2 revisits classical
VSA models and states results from functional analysis that are relevant for
this paper. In Section 3, we reformulate symbolic VSA in terms of inner
product kernels, and generalize these kernels to describe the similarity of
real-valued data mapped to vectors by locality-preserving encoding (LPE) .
Under certain conditions, the resulting vector space model exhibits
transparency and forms a VFA, i.e., the vectors represent functions of a
defined function space and the VSA vector operations perform specific
operations in the function space. Section 4 describes the construction of VFA
with an existing LPE method called fractional power encoding, or fractional
binding (Plate,, 1992; Plate, 1994b, ). We generalize fractional power
encoding to yield VFAs with phasor-valued, real-valued, and sparse
representations, together with algebraic operations that can be efficiently
implemented in hardware. In Section 5, we analyze the possible kernel shapes
in VFAs. Notably, VFAs with kernels for a variety of different applications
can be easily constructed by sampling the base vector in the FPE non-
uniformly. In Section 6, we describe how a given vector in VFA can be decoded
and denoised. Decoding provides the transparency of VFA computations.
Denoising, similar as in VSAs, is essential for preventing error accumulation
known from analog computers. In Section 7, we demonstrate applications of
VFAs. Finally, the discussion in Section 8 summarizes our results, and
explains implications for technical applications and neuroscience, as well as
relations to the previous literature.

##  2 Background

###  2.1 Symbolic VSA models

The question of how to represent and process information in high-dimensional
vector spaces has a long tradition not only in cognitive neuroscience
(Gayler,, 2003; Günther et al.,, 2019), but also in language processing (Van
Rijsbergen,, 2004; Widdows,, 2004). Here our starting point is vector models
for symbolic cognitive reasoning, known as Vector Symbolic Architectures (VSA)
or Hyperdimensional Computing (Plate,, 1995; Kanerva,, 1997; Gayler, 1998a, ;
Rachkovskij,, 2001).

VSAs are models for symbolic reasoning with vector representations that have
two distinguishing properties. The first is that symbols are represented by
randomized $n$-dimensional vectors. In the classical VSA models, symbols are
encoded by vectors whose components are drawn i.i.d. from a specified
distribution. This encoding strategy ensures that representations of different
symbols are well separated, where the _similarity_ of symbols is typically
measured by the inner product between vectors, or a simple function of the
inner product, such as cosine similarity. Here, we generally use the inner
product with a model-dependent normalization factor to represent the
similarity. The normalization factor will be omitted in the following for
notational simplicity. In VSA, a vector is decoded by comparing it with
representation vectors of symbols stored in a codebook. Decoding and memory-
based denoising is an important step in the course of a VSA computation, as it
prevents the error accumulation detrimental in analog computing (Marsocci,,
1956).

Different VSA models use different types of random vectors. For example, the
Binary Spatter Code uses binary vectors (Kanerva,, 1997), the Holographic
Reduced Representation uses real-valued vectors (Plate,, 1995), and the
Frequency domain Holographic Reduced Representation uses complex-valued
vectors (Plate,, 1995). Most VSA models do not support sparse representations
(but see Rachkovskij, (2001)), which are advantageous in terms of energy
consumption and usage of synaptic memory. Recently, VSA models were proposed
that operate with sparse vectors that have block structure (Laiho et al.,,
2015; Frady et al.,, 2021), which are related to the Modular Composite
Representation VSA model (Snaider and Franklin,, 2014).

The second essential property of VSAs is that all computations can be composed
by a small number of elementary vector operations, that, together with the
vector representation space, form an algebraic ring structure. VSAs feature at
least two elementary dyadic operations, which map two (or more than two, by
consecutive execution) vectors into a new vector. The bundling operation:

$\mathbf{s}=\mathbf{x}+\mathbf{y}$ (1)

is commonly used to represent sets of symbols (Kleyko et al., 2020c, ), and is
simply the component-wise sum (superposition)111In some VSA models bundling
also involves normalization and/or thresholding of the components of the sum
vector, e.g., to keep components of the vector in the binary space (Kanerva,,
1997) or to preserve the norm of the vector (Plate,, 1995). of corresponding
symbol vectors. The elements of the set represented by $\mathbf{s}$ can be
read out by forming the inner product between the set representation and
representations of individual symbols. Depending on the vector dimension, the
elements of the set can be detected precisely by a high inner product; for
theoretical analysis of this “readout”, see Frady et al., 2018c ; Thomas et
al., (2020); Kleyko et al., 2020d .

Conversely, the binding operation:

$\mathbf{z}=\mathbf{x}\circ\mathbf{y}$ (2)

is commonly used to represent an association between two vectors, such as a
key-value pair (Kanerva,, 2009). An important property of binding is that
there exists the inverse operation, unbinding, which extracts from the
compound data structure $\mathbf{z}$ formed by (2) one of its constituents:

$\mathbf{y}\approx\mathbf{x}{\setminus\\!\\!\\!\circ\,}\mathbf{z}=\tilde{\mathbf{x}}\circ\mathbf{z}$
(3)

In (3), $\tilde{\mathbf{x}}$ denotes the inverse of $\mathbf{x}$ in terms of
the binding operation. The binding operation produces a vector for the
association of two or more symbols that, in terms of the inner product, is
dissimilar from its arguments. The binding operation $\circ$ has an
approximate inverse operation ${\setminus\\!\\!\\!\circ\,}$ in the sense that
the “unbound” vector has the same inner products with other symbol
representations as the argument originally used in the binding step. We will
use notation that includes real- and complex-valued vector spaces, i.e., the
inner product of two vectors $\mathbf{x}$ and $\mathbf{y}$ will be written as
$\mathbf{x}^{\top}\overline{\mathbf{y}}$, where $\overline{\mathbf{y}}$ is the
vector with the conjugate complex components of $\mathbf{y}$. A general
property of VSA models is the following interaction between the
binding/unbinding operations and the inner product:

$(\mathbf{x}\circ\mathbf{y})^{\top}\overline{\mathbf{z}}=\mathbf{y}^{\top}\overline{(\mathbf{x}{\setminus\\!\\!\\!\circ\,}\mathbf{z})}=\mathbf{y}^{\top}\overline{(\tilde{\mathbf{x}}\circ\mathbf{z})},$
(4)

here $\tilde{\mathbf{x}}$ denotes the inverse of $\mathbf{x}$ with respect to
binding. There are natural combinations of random vector types and specific
binding operations, i.e., combinations in which the binding operation
preserves the vector type. For example, for bipolar (Kanerva,, 2009) or phasor
vectors (Frady et al., 2018c, ), the Hadamard product preserves the vector
type, whereas for binary vectors (Kanerva,, 1997) it is the component-wise XOR
operation. For real- or complex-valued random vectors (Plate,, 1995), circular
convolution preserves the vector type, and for block sparse vectors, block-
local circular convolution (Frady et al.,, 2021) does so.

The combination of the dyadic vector operations and symbolic representations
allows VSA models to represent and query an impressive range of data
structures (see Kleyko et al., (2021) for an overview), such as key-value
pairs (Kanerva,, 2009), sets (Kleyko et al., 2020c, ), histograms (Joshi et
al., 2016b, ), sequences (Hannagan et al.,, 2011), trees (Rachkovskij and
Kussul,, 2001; Frady et al.,, 2020), stacks (Yerxa et al.,, 2018), state
automata (Osipov et al.,, 2017), etc.

VSAs have been extended to process real-valued data by combining the symbolic
and algebraic features with locality preserving encoding (LPE) methods, which
have shown promise in applications (Plate,, 1992; Weiss et al.,, 2016; Rahimi
et al.,, 2017; Frady et al., 2018b, ; Komer et al.,, 2019), but have
previously lacked theoretical underpinning. To provide a solid theoretical
foundation, we build on fundamental results from functional analysis,
described in the following section.

###  2.2 Functional analysis results for extending VSA to real-valued data

In order to process data on a continuous manifold, VSAs have been combined
with an LPE method (Plate,, 1992; Weiss et al.,, 2016). In Section 3.1, we
show how the encoding in symbolic VSA can be formulated in terms of an inner
product similarity kernel. In Section 3.2, we generalize the inner product
similarity kernel of symbolic VSA to describe an LPE. In this paper, we will
focus on kernel LPEs (KLPE), that is, LPEs with a translation-invariant,
positive-definite, smoothly decaying similarity kernel (see the definition in
Section 3.2). Combining KLPE and VSA produces a computing framework we refer
to as Vector Function Architectures (VFA), in which not only symbols but real-
valued data and functions can be represented and manipulated in a transparent
fashion. The following definitions and results from functional analysis are
crucial for understanding the objects that are represented in VFA.

Definition: A kernel $K(\mathbf{x}_{1},\mathbf{x}_{2})$ is positive definite
if, for any finite set of points
$\\{\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{m}\\}$, the Gram matrix
$K(\mathbf{x}_{i},\mathbf{x}_{j})$ is positive definite (i.e., all eigenvalues
are non-negative).

Theorem: All inner product kernels are positive definite (Schölkopf et al.,,
2002; Hofmann et al.,, 2008).

Our first central result, Theorem 1, the mathematical interpretation of
representations and operations in VFA, will leverage the following theorem by
Nachman Aronszajn (1907-1980).

Theorem (Aronszajn,, 1950): Each positive definite kernel defines a
reproducing kernel Hilbert space (RKHS).

The following famous theorem of Salomon Bochner (1899-1982) will be used to
analyze VFAs and to design models with the desired shapes of similarity
kernels.

Theorem (Bochner,, 1932): Each continuous kernel $K(\mathbf{x}-\mathbf{y})$ is
positive definite if, and only if, it is the Fourier transform of a positive
definite measure $p({\boldsymbol{\omega}})$:

$K(\mathbf{x}-\mathbf{y})=\int
d{\boldsymbol{\omega}}\;p({\boldsymbol{\omega}})e^{\imath\;{\boldsymbol{\omega}}^{\top}(\mathbf{x}-\mathbf{y})}=E_{p({\boldsymbol{\omega}})}\left[e^{\imath\;{\boldsymbol{\omega}}^{\top}\mathbf{x}}\overline{e^{\imath\;{\boldsymbol{\omega}}^{\top}\mathbf{y}}}\right]$
(5)

Proof: For formulation of this theorem and proof, see Rudin, (1962).

Kernel methods have been first used in nonlinear pattern recognition by
Aizerman et al., (1964) and became a corner stone of machine learning in the
1990ies. For an excellent textbook on functional analysis of kernel methods
and its applications in machine learning, see Schölkopf et al., (2002).

##  3 Vector Function Architecture (VFA)

In this section, we define and characterize a generalization of VSA for
computing with functions, which shares its transparency with the original
symbolic VSA described in Section 2.1. Our generalization of VSA starts from
reformulating symbolic VSA in terms of an inner-product similarity kernel
described in the following subsection.

###  3.1 The kernel of symbolic VSAs

For symbolic operations (e.g., for analogical reasoning (Plate, 1994b, ;
Rachkovskij and Slipchenko,, 2012)) the encoding scheme
$s\to\mathbf{z}(s)\in\mathbb{C}^{n}$ should guarantee the best possible
separation of different symbols by their high-dimensional projections, i.e.,
by forming inner products between representations $\mathbf{z}(s)$. Further,
the binding operation associating vectors of symbols $s_{1}$ and $s_{2}$
creates a new representation vector $\mathbf{z}(s_{1})\circ\mathbf{z}(s_{2})$,
which is well separated from both of the representations $\mathbf{z}(s_{1})$
and $\mathbf{z}(s_{2})$. This property is crucial because it enables the
construction of compound data structures “on the fly”.

An optimal separation can be achieved by an encoding scheme with exactly
orthogonal representation vectors. The inner product of orthogonal vectors
constitutes, up to a normalization factor, the ideal similarity kernel for
symbolic computation:

$\mathbf{z}(s_{1})^{\top}\overline{\mathbf{z}(s_{2})}\overset{\mbox{\tiny
large }n}{\longrightarrow}K_{Kron}(s_{1},s_{2}):=\delta_{s_{1},s_{2}},$ (6)

with $\delta_{u,v}$ being the Kronecker delta function. This encoding scheme,
however, is limited to maximally $n$ symbols, a quite inefficient use of an
$n$-dimensional representation space.

Therefore, symbolic VSA models typically employ encoding schemes with pseudo-
orthogonal random vectors, sampled from some distribution $p(\mathbf{z})$.
This encoding scheme allows expression of many more symbols than dimensions in
the vector space. The inner product still equals the ideal kernel value for
$s_{1}=s_{2}$, however, for $s_{1}\not=s_{2}$ it only approximates its value
of $0$:

$\left|\mathbf{z}(s_{1})^{\top}\overline{\mathbf{z}(s_{2})}-K_{Kron}(s_{1},s_{2})\right|\leq\epsilon(n)$
(7)

with $\epsilon(n)\to 0$ for increasing $n$. The convergence of pseudo-
orthogonality to exact orthogonality, i.e., of the inner product to the ideal
Kronecker delta kernel, is referred to in statistics as concentration of
measure (Ledoux,, 2001), and can be analyzed rigorously (Frady et al., 2018c,
; Thomas et al.,, 2020).

The correction of these errors, as well as noise from other sources, is an
important part of VSA computation – it prevents uncontrollable error
accumulation, a major problem in analog computers (Marsocci,, 1956). For error
correction in VSA, a vector, occurring in the input or in the course of
algebraic reasoning, is compared with the base vectors assigned to symbols. In
symbolic VSA, detection and denoising is typically accomplished by a content-
addressable memory (Plate,, 1995; Gritsenko et al.,, 2017). The correctness of
the detection process depends on the amount of noise and can be predicted by
the signal detection theory (Frady et al., 2018c, ).

###  3.2 Locality preserving encoding with a kernel

Typical VSA representations with independent random vectors encode via the
inner product only binary information, i.e., “same” versus “different”, about
the relationship between the encoded objects. Encoding graded similarity
information between objects requires a dedicated method of locality preserving
encoding (LPE). An LPE produces vector representations of points on a
manifold, so that the inner product of the vectors reflects the relationship
between the points. This allows data to be expressed and manipulated in the
context of a data manifold.

Here we focus on the combination of VSA with a particular type of LPE that
induces by the inner product of the encoding vectors a translation-invariant
similarity kernel. Generalizing our treatment of encoding functions for
symbolic VSA in Section 3.1, we can define the following type of LPE
functions:

Definition 1: A randomizing LPE encoding function
$f:r\in\mathbb{R}\to\mathbf{z}(r)\in\mathbb{C}^{n}$ is a kernel-LPE (KLPE),
that is, it induces a similarity kernel, if the following requirement holds:

  * In the limit for large dimensionality $n$, the inner product between point representations defines a translation-invariant similarity kernel:

$\mathbf{z}(r_{1})^{\top}\overline{\mathbf{z}(r_{2})}\overset{\mbox{\tiny
large }n}{\longrightarrow}K(r_{1}-r_{2}),$ (8)

with a kernel function $K(d)$, which is real-valued, assumes its maximum at
$d=0$ and gradually reaches zero for large $|d|$.Under quite general
conditions, the convergence in (8), is fast:

$\mbox{Pr}\left(\left|\mathbf{z}(r_{1})^{\top}\overline{\mathbf{z}(r_{2})}-K(r_{1}-r_{2})\right|>\epsilon\right)<g(m,\epsilon),$
(9)

with $g(m,\epsilon)$ a positive function that for any fixed $\epsilon$
approaches zero exponentially fast with growing $n$ (Rahimi and Recht,, 2007).
The empirical convergence of kernels with increasing vector dimension is shown
in the Figures 3, 5 and 6 below. For specific algorithms we will discuss the
dependency between vector dimension and computing precision in Section 7.2.

Representations of data points formed by a KLPE have the following properties.
For a large distance between the data points $r_{1}$ and $r_{2}$, the
resulting representations are pseudo-orthogonal, just as in symbolic VSA.
Conversely, for a small distance, the corresponding representation vectors
have a systematic correlation.

###  3.3 Definition and properties of VFA

Based on the theorem of Aronszajn, (1950), stated in Section 2.2, we can
concisely define the combination of VSA and KLPE and characterize its
properties. We start with the following definitions:

Definition 2: A KLPE is compatible with a VSA binding operation $\circ$, if
the addition of two values of the encoded variable can be represented by
binding the individual representations of the values:

$\mathbf{z}(r_{1}+r_{2})=\mathbf{z}(r_{1})\circ\mathbf{z}(r_{2}).$ (10)

Definition 3: The combination of a VSA with a KLPE that is compatible with the
VSA binding operation induces an RKHS of functions with inner product
$\left<f,g\right>:=\int_{-\infty}^{\infty}f(r)g(r)dr$ that we will call a
Vector Function Architecture (VFA):

  * a)

A function of the form:

$f(r)=\sum_{k}\alpha_{k}K(r-r_{k})$ (11)

is represented via (9), $f(r)=\mathbf{y}_{f}^{\top}\overline{\mathbf{z}(r)}$,
by the vector:

$\displaystyle\mathbf{y}_{f}$ $\displaystyle=$
$\displaystyle\sum_{k}\alpha_{k}\mathbf{z}(r_{k})$ (12)

  * b)

The reproducing kernel property is $[f*K](u)=\left<f,K_{u}\right>=f(x+u)$,
with $K_{u}:=K(x-u)$ and in particular $\left<K_{s},K_{u}\right>=[K\ast
K](s-u)=K(s-u)$ (Hofmann et al.,, 2008).

We can now ask how different vector operations act on functions represented in
the VFA. The following theorem summarizes the function operations available in
VFA.

Theorem 1: In VFA, the following operations in the corresponding RKHS function
space can be computed by elementary VSA vector operations:

  * •

Point-wise readout of a function is the inner product between the VSA
representation of the function and the LPE representation of point $s$:

$f(s)=\left<f,K_{s}\right>=\mathbf{y}_{f}^{\top}\overline{\mathbf{z}(s)}$ (13)

with $K_{s}:=K(r-s)$.

  * •

Point-wise addition of functions is done by the bundling operation (1):

$\mathbf{y}_{f+g}=\mathbf{y}_{f}+\mathbf{y}_{g}$ (14)

  * •

Function shifting $f(x)\to g(x)=f(x+r)$ is done by VSA binding (2) between a
function vector and the point representation of the translation vector:

$\mathbf{y}_{g}=\mathbf{y}_{f}\circ\mathbf{z}(r)$ (15)

  * •

Function convolution is done by the VSA binding operation:

$\mathbf{y}_{f*g}=\mathbf{y}_{f}\circ\mathbf{y}_{g}$ (16)

  * •

Overall similarity between functions, the inner product in function space, is
equal to the inner product in VFA space:

$\left<f,g\right>=\mathbf{y}_{f}^{\top}\overline{\mathbf{y}_{g}}$ (17)

Proof:

Point-wise readout of a function (13) is part of the Definition of VFA.

Point-wise addition of functions (14) follows from linearity of inner product
kernels.

Function shifting (15) follows from the RKHS properties, see Definition VFA,
and the compatibility of the KLPE with binding (10).

Function convolution (16) can be is computed as:

$\displaystyle[f*g](u)$ $\displaystyle=$
$\displaystyle\int_{-\infty}^{\infty}f(r)g(u-r)dr=\left<f,g_{u}\right>=\sum_{k,l}\alpha_{k}\beta_{l}K(r_{k}+r_{l}+u)$
(18) $\displaystyle=$
$\displaystyle\sum_{k,l}\alpha_{k}\beta_{l}\mathbf{z}(r_{k})^{\top}\overline{\mathbf{z}(-r_{l}+u)}=\left(\sum_{k}\alpha_{k}\mathbf{z}(r_{k})\right)^{\top}\overline{\sum_{l}\beta_{l}\mathbf{z}(-r_{l}+u)}$
$\displaystyle=$
$\displaystyle\left(\sum_{k}\alpha_{k}\mathbf{z}(r_{k})\right)^{\top}\overline{\sum_{l}\beta_{l}\mathbf{z}(-r_{l})\circ\mathbf{z}(u)}=\left(\sum_{k}\alpha_{k}\mathbf{z}(r_{k})\right)^{\top}\overline{\sum_{l}\beta_{l}\tilde{\mathbf{z}}(r_{l})\circ\mathbf{z}(u)}$
$\displaystyle=$
$\displaystyle\mathbf{y}_{f}^{\top}\overline{\tilde{\mathbf{y}_{g}}\circ\mathbf{z}(u)}=\left[\tilde{\tilde{\mathbf{y}_{g}}}\circ\mathbf{y}_{f}\right]^{\top}\overline{\mathbf{z}(u)}=\left[\mathbf{y}_{g}\circ\mathbf{y}_{f}\right]^{\top}\overline{\mathbf{z}(u)}$

In (18) we use $\tilde{\mathbf{y}}$ to denote the inverse of $\mathbf{y}$ with
respect to the binding operation. The transformations here used (10) and (4).

Overall similarity between functions (17) can be calculated as:

$\left<f,g\right>=\int_{-\infty}^{\infty}f(r)g(r)dr=\sum_{k,l}\alpha_{k}\beta_{l}K(r_{k}-r_{l})=\sum_{k}\alpha_{k}\mathbf{z}(r_{k})\sum_{l}\beta_{l}\overline{\mathbf{z}(r_{l})}=\mathbf{y}_{f}^{\top}\overline{\mathbf{y}_{g}}$
(19)

$\Box$

As we will discuss later on, VFAs can equally be defined on multi-dimensional
spaces, just by using a KLPE method for multi-dimensional input. The
corresponding kernel function is:

$K(\mathbf{r}-\mathbf{s})=\mathbf{z}(\mathbf{r})^{\top}\overline{\mathbf{z}(\mathbf{s})}$
(20)

and the represented functions are of the form
$f(\mathbf{s})=\sum_{k}\alpha_{i}K(\mathbf{r}^{k}-\mathbf{s})$. The same
function operations as described above can be performed in such VFAs for
functions with a multi-dimensional domain.

##  4 VFA with fractional power encoding (FPE)

The previous section defined and described VFA in general. A prerequisite of a
VFA is a KLPE which is compatible with a VSA binding operation. We now focus
on a particular LPE, fractional power encoding (FPE), which is based on a
binding operation, and was already introduced in the early VSA literature
(Plate, 1994a, ). We describe the different flavors of FPE, show that they are
KLPEs compatible with binding. These findings suggest that earlier models
combining VSA with FPE do qualify as VFAs - although their ability to
represent and manipulate functions was not exploited exlicitly.

###  4.1 Generalization of Plate’s fractional power vector

FPE is a generalization of the fractional power vector (Plate,, 1992; Plate,
1994a, ), an LPE method for encoding topological spaces based on circular
convolution binding. Here we generalize the concept to other VSA binding
operations. FPE starts from self-binding, i.e., binding a base vector, a
random vector $\mathbf{z}\sim p(\mathbf{z})$, $i$ times with itself, which
defines an encoding strategy for integers:

$\mathbf{z}(i):=(\mathbf{z})^{(\circ
i)}=\circ_{j=1}^{i}\mathbf{z}=\mathbf{z}\circ...\circ\mathbf{z}$ (21)

Here $\circ$ is a generic VSA binding operation. Note that by the properties
of VSA binding, self-binding creates pseudo-orthogonal representation vectors
$\mathbf{z}(i)$ for different integers $i$.

FPE (Plate,, 1992) is the generalization of self-binding (21) from integer
exponents to real-valued exponents (see also Section 5.6 in Plate, 1994a ):

$f_{\mathrm{FPE}}:r\in\mathbb{R}\to\mathbf{z}(r)=(\mathbf{z})^{(\circ
r)}\in\mathbb{C}^{n}$ (22)

Let us denote the set of norm-preserving vectors with respect to the binding
operation $\circ$ with:

$A_{\circ}:=\\{\mathbf{z}:||\mathbf{v}\circ\mathbf{z}||^{2}=||\mathbf{v}||^{2}\;\forall\;\mathbf{v}\\}$
(23)

Note that with the base vector chosen in $A_{\circ}$, all points $r$ are
mapped by (22) to vectors also within $A_{\circ}$. Further, if the base vector
is sampled from the probability distribution $p(\mathbf{z})$, representations
for values other than $r=1$ are random vectors described by other
distributions than the base vector. In particular, the representation
$\mathbf{z}(0)=(\mathbf{z})^{(\circ 0)}$ is the identity vector with respect
to the binding operation, the same deterministic vector for any base vector.
The full vector space of a VFA can be visualized (Figure 1). The dashed circle
marks the subset $A_{\circ}$ of unitary vectors. For one specific FPE, a fixed
base vector $\mathbf{z}$, marked by $\times$, is sampled from a distribution
$p(\mathbf{z})$. A subset of vectors, symbolized by the solid circle, can be
decoded or interpreted in the context of this FPE. The part of this set that
overlaps with $A_{\circ}$, $\mathbf{P}_{\mathbf{z}}:=\\{\mathbf{z}(r):\forall
r\\}$, contains the representations of single points. The other part of the
set, $\mathbf{Y}_{\mathbf{z}}$, contains non-unitary vectors that represent
functions. Vectors outside the solid circle cannot be interpreted in the
context of the one specific FPE, they could be used to encode other objects,
such as symbols or function spaces defined by other FPEs. Thus, for a given
arbitrary vector occurring in the input or during a calculation, there is a
detection and decoding problem in VFA, which is similar to the detection
problem in symbolic VSA. We will propose a solution to this in Section 6.

$A_{\circ}$$\mathbf{Y}_{\mathbf{z}}$Entire VFA vector
space$\mathbf{P}_{\mathbf{z}}$$\times\;\mathbf{z}$ Figure 1: Visualization of
the representation space in a VFA based on FPE. The elipse symbolizes the
entire space of representation vectors. The dashed circle symbolizes
$A_{\circ}$, the set of unitary vectors with respect to a specific binding
operation $\circ$. The point $\mathbf{z}$, marked by $\times$, is the random
base vector of a specific FPE $\mathbf{z}(r)$. The solid circle symbolizes the
subset of vectors that can be interpreted in the context of this specific FPE:
The subset $\mathbf{P}_{\mathbf{z}}:=\\{\mathbf{z}(r):\forall r\\}$ contains
the representations of single points that are encoded by unitary vectors,
lying in $A_{\circ}$. The set $\mathbf{Y}_{\mathbf{z}}$ contains the linear
superpositions of elements in $\mathbf{P}_{\mathbf{z}}$, these are non-unitary
vectors that represent other elements of the function space associated with
the specific VFA.

###  4.2 Existing binding operations induce different types of VFA

FPE hinges critically on the VSA binding operation and the properties of the
vector sets depicted in Figure 1 depend on the individual binding operation.
In the following we define and analyze the properties of FPEs based on
previously proposed binding operations, the Hadamard product, circular
convolution or block-local circular convolution. For the corresponding VFAs,
the definitions yield concrete formulae for computing the function
manipulations in Theorem 1, as well as for the sets depicted in Figure 1.

####  4.2.1 VFA with Hadamard product

The Hadamard product between two vectors is the vector of the multiplied
individual vector components:

$\mathbf{z}=\mathbf{x}\odot\mathbf{y}:=(x_{1}y_{1},....x_{n}y_{n})^{\top}\;\;\;;\;\;\;\mathbf{y}=\mathbf{x}{\;\setminus\\!\\!\\!\\!\odot\,}\mathbf{z}=\tilde{\mathbf{x}}\odot\mathbf{z}=\overline{\mathbf{x}}\odot\mathbf{z}$
(24)

An FPE based on Hadamard product encodes a value $r\in\mathbb{R}$ by:

$\mathbf{z}^{hp}(r):=(\mathbf{z})^{r}$ (25)

where $\mathbf{z}\in A_{\odot}$ is a fixed base vector, and $(\mathbf{z})^{r}$
denotes the exponentiation of each vector component by $r$. The set of unitary
vectors with respect to Hadamard binding is:

$A_{\odot}:=\\{\mathbf{z}:||\mathbf{v}\odot\mathbf{z}||^{2}=||\mathbf{v}||^{2}\;\forall\;\mathbf{v}\\}=\\{\mathbf{z}:|z_{i}|=1\;\forall\;i\\},$
(26)

the set of all phasor vectors, $z_{i}=e^{\phi_{i}}$. Commonly, a base vector
is determined by sampling each component independently from a uniform phase
distribution:

$p(\phi_{i})=\begin{cases}\frac{1}{2\pi}&\text{if
$\phi_{i}\in\\{-\pi,\pi\\}$}\\\ 0&\text{else}\end{cases}$ (27)

but see Section 5.2 below for other choices of $p(\mathbf{z})$.

Let us briefly return to symbolic processing in classical Hadamard VSAs
(Gayler, 1998b, ; Kanerva,, 2009). In these models, the components of symbol
representations are drawn i.i.d. from a probability distribution, i.e.,
$p(\mathbf{z})=\prod_{i}p(z_{i})$. For encoding two symbols $s_{1}$ and
$s_{2}$ with vectors $\mathbf{z}$ and $\mathbf{y}$, the joint probability for
each pair of components $z_{i},y_{i}$ is:

$p(z,y|s_{1},s_{2})=\begin{cases}p(z|s_{1})\;\delta(z-y)&\text{if
$s_{1}=s_{2}$}\\\ p(z|s_{1})p(y|s_{2})&\text{otherwise}\end{cases}$ (28)

Thus, for a large enough vector dimension $n$, the inner product converges to
the expectation defined by the probability distribution (28):

$\frac{1}{n}\mathbf{z}(s_{1})^{\top}\overline{\mathbf{z}(s_{2})}\overset{\mbox{\tiny
large
}n}{\longrightarrow}E_{p(z,y|s_{1},s_{2})}[z\;\overline{y}]=\begin{cases}E_{p(z|s_{1})}[z\;\overline{z}]&\text{if
$s_{1}=s_{2}$}\\\ E_{p(z|s_{1})p(y|s_{2})}[z\;\overline{y}]&\text{if
$s_{1}\not=s_{2}$}\end{cases}$ (29)

Similarly, in the Hadamard FPE (25), vector components $\mathbf{z}(r)$ can be
described by a probability distribution. But in this case the distribution
depends on the distribution from which the base vector was sampled (27), as
well as on the particular encoded value: $\forall i:z_{i}\sim p(z_{i}|r)$. For
a large enough vector dimension $n$, this distribution again determines
exactly the inner product of two vectors:

$\frac{1}{n}\mathbf{z}(r_{1})^{\top}\overline{\mathbf{z}(r_{2})}=E_{p(z|r_{1})p(y|r_{2})}\left[z\overline{y}\right].$
(30)

This relation will be used below to determine the kernel shape of Hadamard
FPEs.

Hadamard FPEs require a complex state space. An often used VSA framework
(Gayler, 1998b, ; Kanerva,, 2009) uses real-valued components with Hadamard
product binding where the norm-preserving vectors are bipolar vectors.
However, one cannot define an FPE forming real-valued vectors based on the
Hadamard product. First, all even and all odd integer powers of $r$ are mapped
to the same representation vector. Second, non-integer values of $r$ produce
complex vectors. Note that bipolar vectors are a special case of complex
vectors with a particular sampling distribution; we will return to discuss how
different distributions affect the properties of VFAs.

####  4.2.2 VFA with circular convolution

Circular convolution is the standard convolution operation used in the
discrete finite Fourier transform ${\cal F}$ which can be used to produce a
vector from two input vectors $\mathbf{x}$ and $\mathbf{y}$:

$\displaystyle(\mathbf{x}\circledast\mathbf{y})_{k}$ $\displaystyle:=$
$\displaystyle\sum_{i=1}^{N}x_{(i-k)_{\mbox{\tiny
mod}N}}y_{i}=\mathbf{1}^{\top}\left[\mathbf{x}\mathbf{y}^{\top}\odot\mathbf{P}_{k}\right]\mathbf{1}=\mbox{Tr}\left(\left[\mathbf{x}\mathbf{y}^{\top}\odot\mathbf{P}_{k}\right]\mathbf{P}_{-k}\right)=\left({\cal
F}^{-1}\left(\mathbf{X}\odot\mathbf{Y}\right)\right)_{k}$ (31)
$\displaystyle(\mathbf{x}{\;\setminus\\!\\!\\!\\!\circledast\,}\mathbf{y})_{k}$
$\displaystyle:=$ $\displaystyle\left({\cal
F}^{-1}\left(\overline{\mathbf{X}}\odot\mathbf{Y}\right)\right)_{k}$

where, $\mathbf{P}_{k}$ is the cyclic index shift permutation by $k$, i.e.,
$\mathbf{P}_{0}=\mathds{1}$, $\mathbf{1}$ is the all one vector. The bold
capital letters denote the discrete Fourier transform of the corresponding
bold lower-case letters, e.g., ${\cal F}(\mathbf{x})=\mathbf{X}$. The first
proposal of FPE was based on circular convolution and referred to as the
fractional power vector (Plate,, 1992; Plate, 1994a, ). FPE based on circular
convolution is defined:

$\displaystyle\mathbf{z}^{cc}(r):=\mathbf{z}^{(\circledast r)}$
$\displaystyle=$ $\displaystyle{\cal F}^{-1}\left({\cal
F}(\mathbf{z})^{r}\right)=F^{-1}\left(F\mathbf{z}\right)^{r}$ (32)

The set of unitary vectors with respect to circular convolution are vectors
whose Fourier transforms are phasor vectors
$A_{\circledast}:=\\{\mathbf{z}:|(F\mathbf{z})_{i}|=1\;\forall i\\}$:

$||\mathbf{v}\circledast\mathbf{z}||^{2}=||F^{-1}\left(F\mathbf{v}\cdot
F\mathbf{z}\right)||^{2}=||\left(F\mathbf{v}\cdot
F\mathbf{z}\right)||^{2}\overset{\mathbf{z}\in
A_{\circledast}}{=}||\mathbf{v}||^{2}$

Here $F$ and $F^{-1}$ are the Vandermonde matrices representing the discrete
Fourier transform and its inverse.

The unitary vectors in $A_{\circledast}$ are of the form:

$F^{-1}(e^{\imath\phi_{0}},e^{\imath\phi_{1}},...,e^{\imath\phi_{n-1}})^{\top}=\frac{1}{\sqrt{n}}\left(\sum_{k}e^{\imath(2\pi
0k+\phi_{k})},\sum_{k}e^{\imath(2\pi
1k+\phi_{k})},...,\sum_{k}e^{\imath(2\pi(n-1)k+\phi_{k})}\right)^{\top}$ (33)

for an arbitrary phasor vector in the Fourier domain with phase angles
$\phi_{0},...,\phi_{n-1}$. If the phasor in Fourier space is sampled from a
flat phase distribution (27), the inverse Fourier transform results in
complex-valued vector components where real and imaginary parts appear to be
distributed like Gaussian random variables. However, producing base vectors by
independently sampling each component from a Gaussian distribution, as
originally described by Plate, (1991), is not a good strategy because these
vectors are unlikely to be exactly unitary.

A notable subset of the unitary vectors $A_{\circledast}$ are one-hot phasor
vectors $(0,0,...,z_{l},...0)^{\top}$, which are unitary because their Fourier
transforms are dense phasor vectors:

$F\mathbf{z}=z_{l}(e^{-\frac{2\pi\imath}{n}0l},...,e^{-\frac{2\pi\imath}{n}(n-1)l})^{\top}=z_{l}F_{l}^{\top}$
(34)

where $F_{l}^{\top}$ is the $l$-th column of the discrete Fourier matrix.
Thus, when the Fourier vectors are columns of the discrete Fourier matrix
(with constant phase offset) the corresponding base vectors are one-hot.

Further, it is often desired that the base vectors used in circular
convolution are purely real-valued. This requires Hermitian symmetry of the
random vectors sampled in the Fourier domain, that is, a phasor entry for a
negative frequency must be the complex conjugate of the phasor entry for the
corresponding positive frequency (Komer et al.,, 2019).

####  4.2.3 VFA with block-local circular convolution

The FPE base vectors of VFAs described so far are either fully dense phasors
in models with Hadamard product binding, or they can be maximally sparse,
i.e., one-hot phasors, in models with circular convolution binding. One can
build VFAs on a middle ground, in which the FPE base phasor vector has a
desired sparsity level of $k<n$. In this construction, the base vectors are
sparse block vectors, with $k$ equally sized compartments, in which each
compartment is a one-hot phasor. Previously, VSA with such sparse block
vectors have been proposed that use so-called block-local circular convolution
(LCC) as the binding operation (Frady et al.,, 2021):

$\displaystyle(\mathbf{z}\ast_{\\!B}\mathbf{y})_{(\mbox{\tiny block }i)}$
$\displaystyle:=$ $\displaystyle\mathbf{z}_{(\mbox{\tiny block
}i)}\circledast\mathbf{y}_{(\mbox{\tiny block
}i)}=F^{-1}\left(F\mathbf{z}_{(\mbox{\tiny block }i)}\odot
F\mathbf{y}_{(\mbox{\tiny block }i)}\right)$ (35)
$\displaystyle(\mathbf{z}{\;\setminus\\!\\!\\!\ast_{\\!B}\,}\mathbf{y})_{(\mbox{\tiny
block }i)}$ $\displaystyle:=$ $\displaystyle
F^{-1}\left(\overline{F\mathbf{z}_{(\mbox{\tiny block }i)}}\odot
F\mathbf{y}_{(\mbox{\tiny block }i)}\right)$

where $F$ is the Vandermonde matrix representing the discrete Fourier
transform for a block of size $n/k$. In essence, the binding operation (35)
forms a new one-hot vector for each block, the index of the active element is
just the sum of indices of the hot components of the input vectors modulo
block size (Laiho et al.,, 2015; Frady et al.,, 2021).

FPE based on LCC is defined by generalizing self-binding with LCC:

$\mathbf{z}^{lcc}(r)_{(\mbox{\tiny block
}i)}:=\mathbf{z}^{(\ast_{\\!B}\,r)}_{(\mbox{\tiny block
}i)}=F^{-1}\left(F\mathbf{z}_{(\mbox{\tiny block }i)}\right)^{r}$ (36)

The properties of the set of unitary vectors $A_{\ast_{\\!B}}$ can be
understood by realizing that each block of a unitary vector has to be unitary
with respect to circular convolution, see Section 4.2.2. Thus, the unitary
vectors include $k$-sparse phasor vectors, in which each block is exactly one-
hot, but also vectors that are denser than $k$-sparse vectors. For producing
as sparse as possible representation vectors we sample the base vector of an
LCC FPE from a distribution $p(\mathbf{z})$ that produces an exactly
$k$-sparse random vector in $A_{\ast_{\\!B}}$. The representations of all
integer values of $r$ are then again exactly $k$-sparse, for intermediate
values, the sparsity is slightly lower as shown in Figure 2.

Figure 2: A. Representations of different values ($r=1,2,1.5$) produced by an
LCC FPE with a $k$-sparse ($k=5$) base vector (upper panel; plots show
magnitude). The representations of integer values are exactly $k$-sparse
(upper and middle panel), the representations of non-integer values are less
sparse (lower panel). B. $L_{1}$ norm of vectors produced by LCC FPE as a
function of encoded values between 1 and 3.

##  5 The kernels of FPE

We have seen in Section 4 that the combination of a VSA and an FPE induces a
VFA. Although such models have been described earlier, their power in
representing certain classes of functions and manipulating them has not been
exploited explicitly. In this section, we analyze the kernel properties that
can be realized in such VFA models.

###  5.1 FPEs with uniformly sampled base vectors have a universal kernel

Formally, FPE looks quite different for the different realizations of the
binding operation. Depending on the realization it also requires different
base vectors. Nevertheless, FPE possesses a universal similarity kernel, as
stated in the following theorem.

Theorem 2: Assume an FPE with a uniformly sampled base vector, which is the
typical procedure for sampling VSA vectors. For a Hadamard FPE this means the
phases of the base vector are sampled from the uniform phase distribution,
whereas for CC FPE and LCC FPE this means the base vector corresponds in the
Fourier domain to a random phasor vector with samples from the uniform phase
distribution. The FPE then induces a VFA which is the RKHS of band-limited
continuous functions, independent of the underlying realization of the binding
operation. Specifically, the kernel of FPE is the sinc function, which defines
the RKHS of the band-limited continuous functions.

Proof:

  * 1)

Hadamard product: Using (30), the inner product of the representations of $r$
and $r+d$ can be written:

$\displaystyle\begin{split}\frac{1}{n}(\mathbf{z}(r+d))^{\top}\overline{\mathbf{z}(r)}&=\frac{1}{n}(\mathbf{z}^{r+d})^{\top}\overline{\mathbf{z}^{r}}=\frac{1}{n}(\mathbf{z}^{d})^{\top}\mathbf{1}=\frac{1}{n}\sum_{j}e^{\imath\phi_{j}d}\to
E_{p(\phi)}[e^{\imath\phi d}]\\\ &=2\pi\int_{\omega}p(2\pi\omega)e^{\imath
2\pi\omega d}d\omega=2\pi{\cal F}[p(2\pi\omega)](d)\end{split}$ (37)

where $\mathbf{1}$ is the vector of $1$-entries. Note that the inner product
(37) is the average over $n$ random phasors $e^{\imath\phi d}$. For large $n$,
this average can be rewritten as the expectation of these random phasors under
the uniform phase distribution (27) used to generate the phases $\phi_{j}$ of
the base vector $\mathbf{z}$. By renaming the phase variable $\phi$ as a
frequency $2\pi\omega$, the expectation becomes a Fourier integral. Expressing
the kernel as the Fourier transform of a distribution is an application of
Bochner’s theorem (5). Thus, the inner product kernel (37) converges to the
Fourier transform of a rectangular frequency distribution $2\pi p(2\pi\omega)$
with $p(\phi)$ from (27). The result is the sinc function:

$K_{\odot}(d)\to{\cal F}[p(\omega)](d)=\frac{1}{\sqrt{2\pi}}\mbox{sinc}(\pi
d)$ (38)

This result is well known in statistical optics, as the averaging of phasors
is a problem often encountered in optics (Goodman,, 2007, 2015).

  * 2)

Circular convolution: The inner product of the representations of $r$ and
$r+d$ can be written:

$(\mathbf{z}^{(\circledast(r+d))})^{\top}\overline{\mathbf{z}^{(\circledast
r)}}=\left(F^{-1}(F\mathbf{z})^{(r+d)}\right)^{\top}\overline{F^{-1}\left(F\mathbf{z}\right)^{r}}=\left((F\mathbf{z})^{(r+d)}\right)^{\top}\overline{\left(F\mathbf{z}\right)^{r}}=\sum_{j}(F\mathbf{z})_{j}^{d}$
(39)

Thus, the inner product is again a sum of $n$ random phasors $e^{\imath\phi
d}$ with $\phi\sim p(\phi)$ from (27), and the inner product kernel
$K_{\circledast}(d)$ for circular convolution binding converges for large $n$
to the same kernel as for FPE with Hadamard product (38), the sinc function,
see also Voelker, (2020).

  * 3)

Block-local circular convolution: The inner product of the representations of
$r$ and $r+d$ can be written:

$\frac{1}{k}\sum_{i=1}^{k}(\mathbf{z}^{(\ast_{\\!B}\,(r+d))}_{(\mbox{\tiny
block }i)})^{\top}\overline{\mathbf{z}^{(\ast_{\\!B}\,r)}_{(\mbox{\tiny block
}i)}}=\frac{1}{k}\sum_{i=1}^{k}\left((F\mathbf{z}_{(\mbox{\tiny block
}i)})^{(r+d)}\right)^{\top}\overline{\left(F\mathbf{z}_{(\mbox{\tiny block
}i)}\right)^{r}}=\frac{1}{k}\sum_{i=1}^{k}\sum_{j=1}^{n/k}(F\mathbf{z}_{(\mbox{\tiny
block }i)})_{j}^{d}$ (40)

Again, the inner product is a sum of $n$ random phasors $e^{\imath\phi d}$
with $\phi\sim p(\phi)$ from (27), and the kernel for LCC $K_{\ast_{\\!B}}(d)$
equals the kernel for FPE with Hadamard product (38), the sinc function.

$\Box$

###  5.2 Shaping the kernel in FPEs

####  5.2.1 Phase distribution determines kernel shape

By drawing the base vector of an FPE from distributions other than the uniform
band-limited distribution (27), one can design kernels with shapes that differ
from the sinc function. The Bochner theorem (5) states that any kernel whose
Fourier transform is a proper density function can be represented with Fourier
features drawn from this density (Rahimi and Recht,, 2007). Equation (37)
suggests how the Fourier density of some kernels can be used to construct an
FPE. For each kernel that has a Fourier density $p(\omega)$ with support not
exceeding the frequency range $[-1/2,1/2]$, the phase density
$p(\phi/(2\pi))/(2\pi)$ is within the support $[-\pi,\pi]$, and generates
random base vectors of an FPE with this kernel.

Figure 3 shows several specific phase distributions (depicted in red) of base
vectors, resulting shapes of the corresponding FPE kernels (in blue) for
$n=1,024$, and convergence of Root Mean Square Error (RMSE) between the ideal
kernel and its concrete FPE realization for increasing values of $n$
(logarithmic scale). Figure 3 shows the RMSE for only a couple of kernels
since all of them demonstrate the same dependency.

Figure 3:  Similarity kernels for FPEs with base vectors sampled from various
phase distributions and examples of RMSE convergence . Panels with red curves
illustrate various probability density functions used to randomly sample
phases for the base vector. The corresponding panels with gray and blue curves
show the similarity kernels resulting from the particular choice of phase
distribution for $r=15.5$ and $r=25.0$, respectively. The similarity kernels
are averages computed from $100$ simulation runs, $n=1,024$. Panels with green
curves depict the relation between the RMSE (ideal kernel vs. an FPE
realization) and dimensionality of FPE vectors $n$ in the logarithmic scale.
The reported RMSE are averages computed from $100$ simulation runs; $n$ was in
range $[64,2048]$ with step $64$.

The upper left panel depicts the FPE with uniform distribution and the sinc
function kernel. The other panels show that it is possible to get similarity
kernels, which are very close to, e.g., Gaussian (left panels in the second
row), Laplace (right panels in the second row), or triangular (left panels in
the third row) kernels. In fact, the shape of the kernel can be very complex
such as the one in the lower right panels where the distribution of phases was
defined using the truncated absolute values of the sinc function. Moreover,
the RMSE between the ideal kernel and its FPE approximation decays
exponentially with $n$.

####  5.2.2 Periodic kernels

It is clear from the Bochner theorem that periodic kernels will correspond to
a discrete Fourier transform. Generally, the periodicity of the kernel is
determined by the discrete sampling of the roots of the identity vector for
each binding operation. In the case of Hadamard binding, periodic kernels
result from phasor base vectors in which each component is sampled
independently from a discretized phase distribution. For instance, a kernel
with periodicity of $l$ results from a base vector whose individual phases are
uniformly sampled from the $l$ phase values, $z_{i}\sim\mathcal{U}\\{e^{i2\pi
j/l},\ \forall j\in\\{1,...,l\\}\\}$. Data on a circular manifold can be
encoded by a base vector with phase values that equal $l$-th roots of $1$ (see
Figure 4 for an example). These properties extend to circular convolution
binding by sampling the discrete phases in the Fourier domain. The LCC code
produces loops when the hot phasor elements are also discretely sampled. The
looping behavior depends more complexly on the products of common factors
depending on block size and phase discretization. For instance, if the block
code is purely binary (all phases are 0), then the cycle period will be the
block size.

Figure 4: Periodic kernels are formed by sampling phases from the discrete
roots of 1. The periodicity of the similarity is based on the order of the
root.

###  5.3 Multi-dimensional FPE formed with binding

FPE can be extended to encode multi-dimensional data spaces:

$f_{\mathrm{LPE}}:\mathbf{r}\in\mathbb{R}^{m}\to\mathbf{z}(\mathbf{r})\in\mathbb{C}^{n}\mbox{
where }m>1$ (41)

A simple method for a multi-dimensional FPE is a Cartesian combination of one-
dimensional FPEs that has been proposed before (Weiss et al.,, 2016; Frady et
al., 2018a, ). The Cartesian construction involves orthogonalization of the
individual FPEs with the binding operation:

$\mathbf{z}(\mathbf{r})=\mathbf{z}_{1}(r_{1})\circ\mathbf{z}_{2}(r_{2})\circ\cdots\circ\mathbf{z}_{m}(r_{m})$
(42)

with $\mathbf{z}_{i}(r_{i})$ being one-dimensional FPEs independently sampled.
It is important that the different FPEs are mutually independent, that is, the
(unlikely) case has to be excluded that there are any intersecting paths.

Using the encoding scheme (42), the inner product kernel
$\mathbf{z}(\mathbf{x})^{\top}\overline{\mathbf{z}(\mathbf{y})}\to
K(\mathbf{x}-\mathbf{y})$ is a valid inner product kernel (see Theorem 3 for
Hadamard FPE in Supplement A). This can be generalized to the other binding
operations considered in this paper via Parseval’s theorem. The functions
represented in the resulting VFA are of the form
$f(\mathbf{s})=\sum_{k}\alpha_{k}K(\mathbf{r}^{k}-\mathbf{s})$ are represented
by vectors $f\equiv\mathbf{y}_{f}$:

$\mathbf{y}_{f}=\sum_{k}\alpha_{k}\mathbf{z}_{1}(r^{k}_{1})\circ\mathbf{z}_{2}(r^{k}_{2})\circ\cdots\circ\mathbf{z}_{m}(r^{k}_{m})$
(43)

The operations in function space are the same as for the one-dimensional VFA.

In the limit of large VSA dimension, the inner product of an FPE formed from
multiple one-dimensional FPEs with sinc function kernels converges to the
multi-dimensional Cartesian sinc function:

$K_{sinc}(\mathbf{x}-\mathbf{y}):=K_{sinc}(x_{1}-y_{1})\times\cdots\times
K_{sinc}(x_{m}-y_{m})$ (44)

whose 2-D Fourier transform is a square. In Figure 5 the combination of FPEs
by binding (42) is compared to a combination by Smolensky’s tensor product
(70) in Supplement A. Because Hadamard binding can be viewed as a lossy
compression of the tensor product (Frady et al.,, 2021), it is not surprising
that the Hadamard product method converges somewhat more slowly. However, when
comparing the methods on representations of the same dimensionality, the
Hadamard product method converges slightly faster (within sinc bandwidth), see
Figure 5D. Note that for finite VFA dimension, the largest deviations in power
occur within the bandwidth of the sinc kernel, thus, high-frequency
distortions and aliasing effects remain relatively small.

For concrete formulae describing a Cartesian multi-dimensional FPE with
respect to Hadamard binding, see Section A of the Supplement.

Figure 5:  Convergence of binding of two FPEs to the 2-D Cartesian sinc
kernel. A) Top: Scatterplot of phases drawn from $[-\pi,\pi]$. Each blue point
is a pair of phases, and the red box denotes the interval boundary. Bottom:
Resulting kernel. B) Top: power spectrum of the 2-D Cartesian sinc kernel.
Bottom: power spectrum of a kernel formed by Hadamard binding of two FPEs
(42). With high enough dimension, the kernel approximates the 2-D Cartesian
sinc kernel. Power spectra are normalized by number of samples. C) Higher
dimensional representations show less in-bandwidth (top) and out-of-bandwidth
error (down), respectively. Since the Fourier transform of a multi-dimensional
sinc kernel is rectangular, in-bandwidth frequencies are defined as those
frequencies inside the rectangle. Each plot shows the standard deviation of
the difference between the power spectra of the 2-D sinc kernel and the FPE
encoding. The blue trace is calculated for combination of the two dimensions
by Hadamard product, the green trace for combination by the tensor product
(70) in Supplement A. D) Same as C, except plotting the dimension of the
vectors after binding on the x-axis instead. The Hadamard product is a
dimension-preserving binding, whereas the tensor product of two vectors
results in an $n^{2}$-dimensional representation. In this regard, the Hadamard
and tensor products have roughly equal convergence.

###  5.4 Shaping the kernels of multi-dimensional FPEs

Multi-dimensional kernels can be shaped by shaping the one-dimensional kernels
that compose them, as described in Section 5.2. Further, one can produce non-
Cartesian kernels by sampling the base vectors of the FPEs encoding different
dimensions from a joint phase distribution which does not factorize.

####  5.4.1 Kernels with non-Cartesian structure

Like in the case of one-dimensional FPEs in Section 5.2, the Bochner theorem
can be used to shape multi-dimensional kernels. For example, one can produce
FPEs with non-Cartesian sinc kernels. Sinc kernels can be generalized as the
Fourier transform of the characteristic function of the Brillouin zone, a
primitive cell of a Bravais lattice in reciprocal space (Ye and Entezari,,
2011). For example, the hexagonal sinc kernel (see Figure 6), can be composed
from three 2-D Cartesian sinc kernels as:

$K(\mathbf{x})=\mbox{sinc}_{hex}(\mathbf{x})=\frac{1}{3}\sum_{i=1}^{3}\cos(\pi{\boldsymbol{\xi}}_{i}^{\top}\mathbf{x})\;\mbox{sinc}({\boldsymbol{\xi}}_{i+1}^{\top}\mathbf{x})\;\mbox{sinc}({\boldsymbol{\xi}}_{i+2}^{\top}\mathbf{x})$
(45)

where the indices are modulo 3, and $\\{{\boldsymbol{\xi}}_{i}:i=1,2,3\\}$ are
the vectors along the axes of the hexagonal grid:
${\boldsymbol{\xi}}_{1}=(1/4,\sqrt{3}/4)$,
${\boldsymbol{\xi}}_{2}=(1/4,-\sqrt{3}/4)$, ${\boldsymbol{\xi}}_{3}=(-1/2,0)$.
Since the Fourier transform of the hexagonal sinc function is the
characteristic function of a hexagon, we can form the hexagonal sinc function
by sampling pairs of phases of two base vectors to lie within a hexagon
(Figure 6, middle row). With increasing dimension $n$, this method converges
to the hexagonal sinc.

An alternate method for generating a hexagonal sinc function comes from using
three base vectors with phases drawn uniformly from $[-\pi,\pi]$. The
projections of the 2-D vector $\mathbf{x}$ on the three hexagonal grid vectors
we call $x_{i}={\boldsymbol{\xi}}_{i}^{\top}\mathbf{x}$.The encoding function:

$\mathbf{z}(\mathbf{x})=\left(e^{\imath\pi
x_{1}}\mathbf{z}_{1}(x_{2})\circ\mathbf{z}_{2}(x_{3}),\ e^{\imath\pi
x_{2}}\mathbf{z}_{1}(x_{3})\circ\mathbf{z}_{2}(x_{1}),\ e^{\imath\pi
x_{3}}\mathbf{z}_{1}(x_{1})\circ\mathbf{z}_{2}(x_{2})\right)^{\top}$ (46)

produces an encoding vector that is a concatenation of three vectors formed
from the representations of 2-D FPEs with the pseudo-orthogonal base phasor
vectors $\mathbf{z}_{1}$ and $\mathbf{z}_{2}$. Using this encoding function,
the real part of the inner product between two representations
$\mathbf{z}(\mathbf{x})^{\top}\overline{\mathbf{z}(\mathbf{y})}$ resembles
hexagonal similarity kernel (45), $\mbox{sinc}_{hex}(\mathbf{x}-\mathbf{y})$.
Figure 6 demonstrates that with increasingly higher dimensional vectors,
equation (46) slowly converges to the hexagonal sinc function. This happens
because the kernels of the 2-D FPEs are slowly converging to the 2-D Cartesian
sinc kernel. For further discussion with the specific example of Hadamard
binding, see equation (71) in the Supplement B.

Figure 6:  Top row: Hexagonal sinc function and its power spectrum. Second
row: a method for generating hexagonal phases based on joint sampling of base
vector phases uniformly from a hexagon inscribed in the valid phase range
$[-\pi,\pi]$. This figure also converges to a hexagonal sinc function. Bottom
row: Method for constructing phases based on 3 vectors with phases drawn from
a uniform distribution. RMSE shows convergence to sinc function for both as a
function of effective dimension ($n$). For $n$-dimensional base vectors, the
effective dimension is $n$ for the joint phases (JP) method and $3n$ for the
concatenated projections (CP) method. Traces show average RMSE over 20 trials.
Examples from the bottom two rows show one random example ($n=5,000$). Power
spectra are normalized such that total power sums to 1.

####  5.4.2 Non-Cartesian kernels with periodic structure

Kernels with periodic structure play an important role in engineered and
neurobiological navigation systems. For instance in neuroscience, grid cells
are a widely observed phenomenon in recordings from entorhinal cortex (Hafting
et al.,, 2005), where neurons fire at regular spatial intervals as the animal
explores an environment, forming a hexagonal lattice. To construct a hexagonal
lattice in VFA, one can leverage concepts from crystallography. The molecules
of a crystal can be described by a Bravais lattice, ideal grids constructed by
a set of base vectors multiplied with integers. The Fourier transform of a
Bravais lattice is called the reciprocal lattice, and the reciprocal lattice
of typical Bravais lattices is band-limited and discrete. Thus, we can once
again use the Bochner theorem and the relabeling of frequency with phase to
construct LPEs with ideal grid-cell-like patterns. Indeed, the hexagonal
lattice (Figure 7, top left) is just one type of 2-D Bravais lattice. Other
Bravais lattices can be constructed by choosing phases lying along their
reciprocal lattice; for examples, see the first two rows in Figure 7.

Note that regular lattices are just a subset of discrete band-limited
functions, the bottom two rows of Figure 7 illustrate other possibilities.

Figure 7:  Examples of hexagonal and non-hexagonal lattices generated by
strategic selection of phases jointly. Top two rows: Choosing phases of two
base vectors jointly from the reciprocal of a 2-D Bravais lattice generates a
kernel shaped in the form of that infinite 2-D lattice. The grid spacing of
the kernel is determined by the spacing of the phases. Third row: When phases
are chosen from an average of Gaussian distributions (whose centers form a
reciprocal lattice) instead, the inner product goes to 0 with large distance.
Left image is from Gaussians with $\sigma=0.2$, right is from Gaussians with
$\sigma=0.4$. Higher variance results in a smaller window of non-zero inner
product. Bottom two rows: Further examples of symmetric kernels that can be
generated from a discrete phase distribution. All kernels are the result of 1
simulation with two random base vectors ($n=5,000$).

Our method is similar, but not identical, to the method for generating
periodic kernels proposed in Komer, (2020). Their method for generating grid-
cell-like kernels is based on sampling discrete phases for the base vectors
used in equation (72). An example of this method is shown in Figure 8, and
since its Fourier transform is also band-limited and discrete, its lattice
appears quite similar to the hexagonal lattice we show in Figure 7.
Nevertheless, there are subtle differences. For example, using the method of
Komer, (2020) generates local maxima in-between peaks of cross-sections of the
kernel, whereas our method of choosing phases jointly does not create these
additional local maxima.222Another difference is that the method of Komer,
(2020) requires sampling from more discrete phases to change the grid scale,
whereas our method based on the Bochner theorem only requires changing the
spacing of the phase pairs).

Figure 8: Sampling discrete phases, as in (Komer,, 2020), also results in a
periodic kernel. Top left: Hexagonal kernel generated according to (73), with
phases for base vectors sampled uniformly from $[0,2\pi]$. This kernel is not
periodic. Top right: Hexagonal kernel where phases are uniformly drawn from
$\\{0,2\pi/3,4\pi/3\\}$ results in a periodic kernel ($n=5,000$). Bottom left:
A cross-section of the periodic kernel shown in the top right. Cross-sections
of kernel generated from (73) have irregular structures between periods,
unlike the hexagonal or square lattices in Figure 7 that do not tend to have
local maxima between peaks. Bottom right: The power spectrum of the periodic
kernel (shown in top right) is band-limited and discrete yet also has higher
power at lower frequencies.

##  6 Detection, decoding and denoising in VFA

Function manipulation in VFA requires methods for detecting and decoding
encoded values and functions. In this section, we describe a circuit model for
detection and decoding in VFA. Recall from Section 3.1 that in symbolic VSA,
substantial computation is devoted to error correction, i.e., the detection,
decoding, and denoising of VSA representations (Kleyko et al.,, 2021). A
similar procedure for detection and error correction has to be part of VFAs.
In a VFA, only the vectors in the subsets $\mathbf{P}_{\mathbf{z}}$ and
$\mathbf{Y}_{\mathbf{z}}$ in Figure 1 have meaning in the context of the
function space. We explain first the group theoretic structure of
$\mathbf{P}_{\mathbf{z}}$. Then we describe the proposed method, and a circuit
for computing it, in the context of a Hadamard FPE encoding a one-dimensional
data manifold.

For the design of a decoding procedure it is important to understand the group
theoretic structure of the set of point representations
$\mathbf{P}_{\mathbf{z}}$. There is a direct relation between the Hadamard FPE
and the exponential map, $t\to e^{Ht}$, of diagonal skewed Hermitian matrices
$H$, which produces a subset of unitary matrices. For a particular FPE with
base vector $\mathbf{z}=(e^{\imath\phi_{1}},...,e^{\imath\phi_{n}})$, consider
the exponential map of a diagonal skew Hermitian matrix
$H(\mathbf{z})=\imath\;\mbox{diag}({\boldsymbol{\phi}})$, with a real-valued
diagonal matrix formed from the phase angles of $\mathbf{z}$. The exponential
map takes a single $H(\mathbf{z}):\mathbf{z}\in A_{\odot}$ as the generator,
and forms the subgroup by the so-called “path”, a one-parameter manifold of
matrices, a Lie group (Gilmore,, 2012). It is known that the exponential map
of a general skew Hermitian matrix forms an injective map onto the unitary
matrices (Gallier and Quaintance,, 2020). Thus, the path formed by the single
point representations in a Hadamard FPE is a one-parameter Lie group which is
isomorphic to a subgroup of the unitary matrices. This parametrized group
structure of $\mathbf{P}_{\mathbf{z}}$ is symbolized by the line in Figure 9.
Due to the non-uniqueness of the complex exponential, for certain base vectors
the path can also be a loop, that is, periodically revisit the same unitary
matrices. This loop structure yields periodic kernels as seen in Section
5.2.2.

For an unknown given vector, the decoding problem consists of decomposing the
vector into a linear combination of vectors on the path
$\mathbf{P}_{\mathbf{z}}$. If vectors are close are only near the path they
should be error corrected to lie on the path and defining the encoded value.
If the vector cannot be decomposed into points near the path, the decoding
should be rejected.

$\mathbf{Y}_{\mathbf{z}}$Entire VFA vector
space$\mathbf{P}_{\mathbf{z}}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\mathbf{z}$$\mathbf{z}^{\beta}$$\mathbf{z}^{2\beta}$$\mathbf{z}^{3\beta}$
Figure 9: The two matching steps of the proposed decoding method visualized in
the state space. Decoding in a VFA serves to determine whether and where an
unkwown vector lies in the set of interpretable vectors, depicted by the
circle. For a representation of an unknown point on the data manifold, the
coarse matching step compares the vector to a set of discrete anchor points,
marked by $\bullet$, on the path of point representations, symbolized by the
line. Once the best coarse match is found, the second decoding step determines
the exact location of the point on the path between the anchor points. If the
vector encodes a function, i.e., lies in the green region, the same two
matching steps are repeated multiple times, each time decoding the coefficient
and support point of one term in the function (11). One term, once decoded, is
subtracted from the input vector before the decoding process is repeated until
all terms constituting the function are determined.

The nature of the decoding problem in VFA is not a new one. In neuroscience,
line attractor networks have been proposed as models for how a neural circuit
can decode, denoise, and represent real-valued inputs. In principle, we could
use a line attractor in VFA. This would require a circuit that can stabilize
and denoise the entire path for an FPE with a given base vector. However, it
is unclear how to store the path of a specific FPE in a line attractor
network. A naive solution could be to finely discretize the path and store the
resulting points in a Hebbian associative memory. But this might fail because
a sufficiently fine path discretization could result in a set of patterns,
which is too large and its members too correlated to be successfully stored in
a Hebbian associative memory circuit (Lewenstein and Tarkowski,, 1992).

Thus, here we propose instead a two-step procedure for detection and error
correction, including a coarse and fine matching steps. For coarse matching,
we store anchor points on the path in a content-addressable memory, see the
points on the line in Figure 9. For forming the coarse anchor points of the
path, the base vector exponentiated at an interval somewhat smaller than $2$,
for example, $\\{\mathbf{z}^{k\beta}:k=1,2,k_{max},\beta=2\times 0.8\\}$. This
discretization of the path is chosen such that for a representation of any
point on the path, the closest anchor point has a higher inner product
compared to the other anchor points. The coarse matching step can be
accomplished in a phase associative memory, in which all the anchor points are
stored using the standard outer product learning rule (Frady and Sommer,,
2019).

Once the coarse matching step returns the closest anchor point, the second
mechanism precisely decodes the analog value. This mechanism involves the FPE
$\mathbf{z}(s)=\mathbf{z}^{s}$ also used to encode input vectors, and a
circuit forming the inner product between the representation of a value $s$
and the unknown vector $\mathbf{x}$.

$c(s)=[\mathbf{z}^{s}]^{\top}\overline{\mathbf{x}}=\sum_{j}e^{\imath(s-r)\phi_{j}}$
(47)

The phase distribution in the sum in (47) is centered rectangular (27) with
width $s-r$. Maximizing $c(s)$ yields the encoded value $s=r$, as this setting
shrinks the width of the phase distribution to zero in all components
simultaneously. Thus, if $\mathbf{x}$ is the representation of a single point
$r$ ($\mathbf{x}=\mathbf{z}(r)=\mathbf{z}^{r}$), the control signal $c(s)$
changes like the kernel function as $s$ is approaching $r$. As long as the
anchor points are close enough so that the kernel increases monotonously, the
fine matching procedure is convex optimization and can be solved via, e.g.,
the gradient descent. Left panel in Figure 10 depicts the RMSE resulting from
the denoising over the input signal-to-noise ratio (SNR) for three different
values of vector dimension $n$.

Figure 10:  Decoding VFA representations with the circuit in (47). For both
panels $k_{max}=20$, $\beta=2\times 0.8$, $n\in\\{64,128,256\\}$. Left panel:
denoising point encoding vectors. The results were averaged over $50,000$
simulations. Right panel: decoding of function vectors. The results were
averaged over $5,000$ simulations.

Decoding can also be accomplished for function vectors in the VFA, i.e., non-
phasor vectors which are a weighted superposition of the FPE vectors of the
support points of the function (12). To decode the weight value and support
point with largest weight, one can just process the function vector in the
same way as a single point encoding vector described above. Once the support
point value $r_{1}$ is decoded, one can subtract the contribution of the first
support point $\hat{\alpha}_{1}\mathbf{z}^{\hat{r}_{1}}$ from the function
vector and then proceed to decode weight value and support point with the
second largest weight, and so on. Decoding of the function vectors is
demonstrated in the right panel of Figure 10. The average cosine similarity
between the original vector representation of a function and the
representation of the decoded function is plotted over the number of
individual support points in the VFA vector for three different values of $n$.

##  7 VFA application examples

We have shown so far that FPE induces a VFA in which vectors represent the
band-limited functions. Here we describe concrete applications of VFAs of this
type, for image processing (Section 7.1), density estimation (Section 7.2.1),
and nonlinear regression (Section 7.2.2).

###  7.1 Processing image data

We start by describing how to represent and manipulate image data by high-
dimensional vectors, an example that showcases critical VFA properties. In
essence, we treat simple images of letters as functions over the image domain.
For simplicity, this demonstration uses the Hadamard VFA. Locations in the
image plane are encoded by a two-dimensional FPE, with base vectors
$\mathbf{x}$ and $\mathbf{y}$. To avoid a reduction of image power when
translations move image parts outside the image boundary, we desire a function
space with a torus structure that seamlessly connects the image boundaries. To
achieve this, we shape a periodic kernel by choosing the base vectors from a
discretized phase distribution as described in Section 5.4.2. For images of
size 56x56 pixels, the phases of $\mathbf{x}$ are chosen from the 56 discrete
points around the phase circle, likewise for $\mathbf{y}$.

A letter image is an element of the VFA function space, with each term in the
kernel expansion of the function (11) encoding intensity and position of a
pixel by coefficient and support point, respectively, see left panel in Figure
11. Several letters can be composed into a scene by adding the individual
image vectors (center panel in Figure 11). The letters can be positioned in
the scene by binding each image vector with fractional power encoding of the
position. The scene vector can then be decoded through a coarse search as
described in Section 6:

$\hat{Im}(x,y)=\frac{1}{n}(\mathbf{v}_{scene})^{\top}\overline{(\mathbf{x}^{x}\odot\mathbf{y}^{y})}$
(48)

The entire scene can be shifted by again binding the scene vector with FPE
translation vectors. Due to the torus structure of the function space the
letters wrap around the image.

Figure 11: Encoding and manipulating images. Each panel shows an image decoded
from a vector. Left: Images of letters are encoded as functions over the image
domain. Each pixel is encoded by a support vector representing its location,
weighted by the pixel intensity. A complete letter image is represented as the
VFA vector containing the sum of all individual pixel terms. Middle: A scene
of several letters can be generated by positioning and adding individual
letter vectors. Right: The entire scene can also be manipulated by binding the
scene vector with an FPE translation vector. To keep the image power invariant
under translations, we use a VFA with periodic kernel. The kernel creates a
torus topology, that is, when shifting the scene, parts that move outside the
image frame wrap around and enter the image on the opposite side.

###  7.2 VFA models for nonparametric kernel methods

####  7.2.1 Density estimation

The application of VFA in density estimation can leverage early work using
sinc kernels in density estimation (Davis,, 1975; Davis et al.,, 1977;
Devroye,, 1992; Glad et al.,, 2003; Agarwal et al.,, 2017).

##### Method

For a given set of $k$ data points $r_{1},...,r_{k}$, Agarwal et al., (2017)
proposed a method for density estimation with band-limited functions. We use
this method to construct a vector $\mathbf{y}^{p}$ that represents the band-
limited probability maximum likelihood (BLML) estimator for the density $p(r)$
of the data points:

$p(r)=\left(\frac{f_{c}}{k}\sum_{i=1}^{k}\hat{c}_{i}K(f_{c}(r-r_{i}))\right)^{2}=\left(\frac{f_{c}}{kn}\sum_{i=1}^{k}\hat{c}_{i}\mathbf{z}(f_{c}r_{i})\overline{\mathbf{z}(f_{c}r)}\right)^{2}=\left((\mathbf{y}^{p})^{\top}\overline{\mathbf{z}(f_{c}r)}\right)^{2}$
(49)

with
$\mathbf{y}^{p}:=\frac{f_{c}}{kn}\sum_{j=1}^{k}\hat{c}_{j}\mathbf{z}(f_{c}r_{j})$,
$f_{c}$ the cut-off frequency, and
$\hat{\mathbf{c}}=\underset{\rho_{n}(\mathbf{c})=0}{\mbox{argmax}}\prod_{i=1}^{k}\frac{1}{c_{i}^{2}}$,
$\rho_{n}(\mathbf{c})_{i}=\frac{1}{k}\sum_{j=1}^{k}c_{j}K(f_{c}(r_{i}-r_{j}))-\frac{1}{c_{i}}$.
An equivalent formulation of the optimization to find $\hat{\mathbf{c}}$ is:

$\hat{\mathbf{c}}=\underset{\mathbf{1}=\mathbf{c}\odot\mathbf{K}\mathbf{c}}{\mbox{argmax}}\;\;\prod_{i=1}^{k}\frac{1}{c_{i}^{2}}$
(50)

where $\mathbf{1}$ is the $k$-dimensional all one-vector, and $\mathbf{K}$ is
the Gram matrix of the representation vectors of the $k$ data points. This
optimization problem involves exhaustive search among the $2^{k}$ local maxima
(one in each orthant). To avoid this expensive search, Agarwal et al., (2017)
proposed three approximate solution algorithms. In the experiments below, we
used BLMLTrivial algorithm. If $p(x)$ is indeed band-limited and strictly
positive then this algorithm converges to the true BLML estimator
asymptotically.

##### Empirical evaluation

We use an example of a surrogate probability density function (pdf) from
Agarwal et al., (2017):

$f(x)=0.078(\mbox{sinc}^{2}(0.2x)+\mbox{sinc}^{2}(0.2x+0.2))^{2}.$ (51)

This pdf is band-limited with a cut-off frequency of $f_{c}=0.4$ Hz.

We followed the experimental setup in Agarwal et al., (2017) by first randomly
drawing $k$ samples from the pdf and then using these samples to estimate the
density of the pdf in the range $[-5,5]$ with step $0.001$. The values of
$\hat{\mathbf{c}}$ were obtained with the BLMLTrivial algorithm Agarwal et
al., (2017). It is a computationally efficient algorithm as it obtains
$\hat{\mathbf{c}}$ in one step by first selecting an orthant in which the
global maximum for (50) may lie. Once the orthant is chosen,
$\rho_{n}(\mathbf{c})=0$, which is monotonic in a given orthant, is solved in
that orthant (see Section 3.3.2 in Agarwal et al., (2017) for details). We
used the mean integrated square error (MISE) between estimate and ground truth
value and an indicator of the quality of the estimation.

Figure 12:  Left panel: True pdf ((51), dotted line) and estimations obtained
with VFA implementing the BLMLTrivial algorithm. The number of samples from
$f(x)$ was fixed to $k=81$. Center panel: True pdf –
$0.170(0.8\mbox{sinc}^{2}(-0.2x+0.8)+\mbox{sinc}^{2}(0.2x+0.5))^{2}$ (dotted
line) and estimations obtained with VFA implementing different variants of the
BLMLTrivial algorithm. In both panels, the solid lines correspond to the
original variant from Agarwal et al., (2017); dashed and dash-dotted lines
correspond to the proposed variant (49) for different dimensionalities of the
base vector $\mathbf{z}$. To be consistent with Agarwal et al., (2017) (cf.
Figure 1.B there) the number of samples was fixed to $k=81$. The reported pdf
estimates are the mean values from $500$ simulation runs. For each run,
samples were drawn randomly from the corresponding pdf; for the variants with
FPE, the base vector $\mathbf{z}$ was also chosen randomly at each run. Right
panel: Logarithm of MISE plotted against the logarithm of the number of
samples for different estimates of the pdf. Numeric version of the BLMLTrivial
algorithm (solid line) and estimates with VFA for seven different base vector
dimensions. The number of samples varied in the range $2^{[0,11]}$ with step
$0.5$. MISE were averaged over $500$ simulation runs. For each run, samples
were drawn randomly from (51); for the VFAs, the base vector $\mathbf{z}$ was
also chosen randomly at each run.

Figure 12 shows how the estimation quality of the VFA improves as the vector
dimension is increased. While a vector dimension of $n=32$ provides a decent
estimate of the overall curve shape but overestimates the tails, for a vector
dimension of $n=512$ the estimate is close to the ground truth even in the
tails. Thus, the dimensionality of the VFA affects the quality of the
estimation. This observation enabled the next experiment, where both the
number of samples $k$ and the dimensionality $n$ are varied jointly.

Note that in the right panel in Figure 12, the MISE of the numerical
implementation of the BLMLTrivial algorithm (thick solid line) is steadily
decreasing with the growing number of samples. This decrease reflects the
improvement of precision as data limitation is gradually lifted. The MISE
curves of VFA models follow this curve, but at some point deviate from the
solid line and plateau. In practice this has the following consequences.

In the regime of unlimited data, i.e., for large numbers of samples, the
precision of VFA models steadily improves with its dimensionality. This
improvement with dimensionality has also been observed in classical VSAs, and
has been referred to as the “blessing of dimensionality” (Gorban and Tyukin,,
2018).

In the data-limited regime, i.e., for a small, fixed number of observation
points, the situation is quite different. In this case, VFAs with large enough
fixed dimension already achieve the same performance as the numerical variant.
Increasing the dimensionality beyond this point does not improve the
performance further. Thus, in the data-limited regime, one can limit the
dimensionality of the VFA to some fixed value without compromising
performance.

####  7.2.2 Nonlinear regression

To demonstrate nonparametric nonlinear regression with VFA, we can leverage
some previous literature on regression with sinc kernels (Bissantz and
Holzmann,, 2007; Exterkate,, 2011; Bousselmi et al.,, 2020).

##### Method

The regression task is formulated as follows: given a training set
$\\{(X_{i},Y_{i}),1\leq i\leq k\\}$ with $k$ samples, where $Y_{i}$ is a noisy
value of an unknown function $f(x)$ at $X_{i}$ ($Y_{i}=f(X_{i})+\eta_{i}$);
provide an estimate of the function for previously unseen values of $x$ –
$\hat{f}(x)$.

Two methods for performing regression with sinc kernels were recently
described in (Bousselmi et al.,, 2020). The first method is called empirical
projection, and it can be used in the special case when values of $X_{i}$ are
independent and uniformly distributed on the interval $I=[-1,1]$ and $f(x)$
lies in a subspace of the Hilbert space $L^{2}(I)$. The empirical projection
regression estimator with the sinc kernel is defined as:

$\hat{f}_{c,k}(x)=\frac{2}{k}\sum_{i=1}^{k}Y_{i}K_{c}(x,X_{i})=\frac{2c}{k\pi}\sum_{i=1}^{k}Y_{i}\mbox{sinc}\left(\frac{c}{\pi}(X_{i}-x)\right),$
(52)

where $c$ is the bandwidth parameter of the kernel.

Using the FPE, the empirical projection method can be realized as follows:

$\hat{f}_{c,k,n}(x)=\frac{2c}{k\pi}\sum_{i=1}^{k}Y_{i}\mbox{sinc}\left(\frac{c}{\pi}(X_{i}-x)\right)=\frac{2c}{kn\pi}\sum_{i=1}^{k}Y_{i}\mathbf{z}(\frac{c}{\pi}X_{i})^{\top}\overline{\mathbf{z}(\frac{c}{\pi}x)}=(\mathbf{y}^{X})^{\top}\overline{\mathbf{z}(\frac{c}{\pi}x)},$
(53)

where
$\mathbf{y}^{X}=\frac{2c}{kn\pi}\sum_{i=1}^{k}Y_{i}\mathbf{z}(\frac{c}{\pi}X_{i})$
is the FPE-based estimator of $f(x)$.

The second method is Tikhonov regularization, which is more general as it does
not require $X_{i}$ to be within $I$. The Tikhonov regularization regression
estimator with the sinc kernel is defined as:

$\hat{f}_{c,k}^{\lambda}(x)=\sum_{i=1}^{k}c_{i,\lambda}K_{c}(x,X_{i})=\frac{c}{\pi}\sum_{i=1}^{k}c_{i,\lambda}\mbox{sinc}\left(\frac{c}{\pi}(X_{i}-x)\right),$
(54)

where $\lambda$ is a regularization parameter and
$\mathbf{C}_{\lambda}=(c_{i,\lambda})_{1\leq i\leq k}$ is the expansion
coefficients vector, which is calculated using regularized linear regression
as:

$\mathbf{C}_{\lambda}=G_{\lambda}^{-1}\mathbf{Y}=\left[\left[K_{c}(X_{i},X_{j})\right]_{1\leq
i,j\leq k}+k\lambda I_{k}\right]^{-1}\mathbf{Y},\mathbf{Y}=(Y_{i})_{1\leq
i\leq k},$ (55)

where $I_{k}$ is the $k\crossproduct k$ identity matrix and
$\left[K_{c}(X_{i},X_{j})\right]_{1\leq i,j\leq k}$ is the Gram matrix for the
training data $(X_{i})_{1\leq i\leq k}$.

Similar to empirical projection, the estimator for the Tikhonov regularization
method can be expressed in VFA as:

$\hat{f}_{c,k,n}^{\lambda}(x)=\frac{c}{\pi}\sum_{i=1}^{k}c_{i,\lambda}\mbox{sinc}\left(\frac{c}{\pi}(X_{i}-x)\right)=\frac{c}{n\pi}\sum_{i=1}^{k}c_{i,\lambda}\mathbf{z}(\frac{c}{\pi}X_{i})^{\top}\overline{\mathbf{z}(\frac{c}{\pi}x)}=(\mathbf{y}^{X})^{\top}\overline{\mathbf{z}(\frac{c}{\pi}x)},$
(56)

where
$\mathbf{y}^{X}=\frac{c}{n\pi}\sum_{i=1}^{k}c_{i,\lambda}\mathbf{z}(\frac{c}{\pi}X_{i})$.
Note that the expansion coefficient vector $\mathbf{C}_{\lambda}$ for the VFA
is also obtained with (55) but using the Gram matrix calculated for
similarities between FPEs $\mathbf{z}(\frac{c}{\pi}X_{i})$.

##### Empirical evaluation

In order to demonstrate FPE-based methods for nonparametric nonlinear
regression and their numeric counterparts, we used the same synthetic data as
in Bousselmi et al., (2020) (cf. Example 1 therein):

$f(x)=\mbox{sinc}(\frac{20}{\pi}x),x\in I;$ (57)

where $c=20$. For the training set, values of $X_{i}$ were independent and
uniformly distributed, while the values of $Y_{i}$ were obtained as:

$Y_{i}=f(X_{i})+\eta_{i},\eta_{i}\in\mathcal{N}(0,0.01).$ (58)

Following the setup in Bousselmi et al., (2020), the value of $c$ for the
empirical projection method was set to $20$ while for the Tikhonov
regularization method the parameters were: $c=30$, $\lambda=0.01$.

Figure 13:  Nonlinear regression with VFA. Left panel shows the target
function, $f(x)=\mbox{sinc}(\frac{20}{\pi}x)$, (green line), $k=150$ randomly
drawn noisy samples from $f(x)$ (dots), and the estimations $\hat{f}(x))$
obtained with VFAs implementing empirical projection (orange line) and
Tikhonov regularization (dashed black line) methods. Middle and right panels
depict the logarithms of the RMSE against the number of samples $k$ for
empirical projection (middle panel) and Tikhonov regularization (right panel).
The results are shown for numeric calculations of the kernel and for seven
different dimensionalities of the VFA. The number of samples varied in the
range $2^{[0,12]}$ with step $1$. RMSE values are averages computed from $500$
simulation runs. For each run, samples and noise added to $f(x)$ were drawn
randomly, for the variants using the FPE, the base vector $\mathbf{z}$ was
also chosen randomly at each run.

This experiment demonstrates that the VFA implementations of both
regularization methods provide decent estimates of the target function (left
panel) in Figure 13. Compared to the empirical projection VFA, the Tikhonov
VFA achieved lower RMSE. This improvement, however, comes at additional
computational costs, as the Tikhonov VFA one needs to solve (55).

Concerning the scaling of performance with number of available data points and
VFA dimensionality, we observed similar trends as for density estimation. The
error decreases with increased $k$ and $n$ and for fixed $k$ there is a
minimum dimensionality that reaches optimal performance. Interestingly, the
required VFA size for optimal performance is significantly smaller for the
Tikhonov VFA than for the empirical projection VFA.

##  8 Discussion

###  8.1 Summary of results

Our main contribution is the formal characterization of vector function
architectures (VFA), a new framework for computing on functions by
manipulating high-dimensional randomized vectors. This work generalizes vector
symbolic architecture (VSA) models for symbolic reasoning and it formalizes
some of the earlier proposals to use VSA on subsymbolic data (see Section
8.4.1 below). Our results can be put into the following statements:

  * •

The combination of VSA with a KLPE that is compatible with the VSA binding
operation induces a Vector Function Architecture (VFA), i.e., a reproducing
kernel Hilbert space (RKHS) in which functions are represented by vectors and
can be manipulated by vector operations that form an algebra over the
representation space. The algebraic vector operations can perform the
following function operations: point-evaluation, integration, addition, shift,
and convolution (Theorem 1).

  * •

Vector binding of two symbol representations in VSA forms a representation of
the symbol pair, expressing, for example, a key-value or role-filler
association between the symbols. It is interesting that in the framework of
VSA, binding of function vectors expresses function convolution333This result
should not be too surprising because the vector binding in VSA and VFA is
implemented by convolution (circular convolution binding), or convolution in
Fourier space (Hadamard binding).. Convolution has been proven a very
important composition/decomposition operation for functions, as exemplified
lately by the success of convolutional neural networks (Bengio et al.,, 2021).

  * •

Fractional Power Encoding (FPE), an existing LPE method based on the VSA
binding operation, induces VFAs for one- and multi-dimensional data spaces.
The kernel shape depends on the random structure of the FPE base vector.
Uniformly sampled base vectors produce VFAs with a universal kernel shape, the
sinc function, independent of the underlying binding operation. Thus, vectors
in the resulting VFA can represent the band-limited functions (Theorem 2).

  * •

A recipe is described how to shape the kernels in VFA. Specifically, any
kernel with a Fourier density band-limited within $[-1/2,1/2]$ can be produced
in a VFA by sampling the FPE base vector accordingly. In particular, it is
shown how to construct VFE with kernels useful to various applications, such
as Gaussian kernels, non-Cartesian multi-dimensional sinc kernels, periodic
grid kernels, etc.

  * •

Like in traditional symbolic VSAs, VFAs require a mechanism for detecting,
decoding and denoising of representations. A circuit mechanism is proposed to
serve this purpose.

  * •

We showcase a few examples of kernel computations with VFA, image processing,
density estimation and nonlinear regression.

  * •

Other types of LPEs (that have been used with VSA in the past), such as float
codes, random vector concatenation, and random projections can also induce
RKHS function spaces. However, none of these other LPEs induce a VFA because
they do not include a binding operation compatible with the encoding scheme,
see Supplement C.

###  8.2 Technical applications of VFA

In addition to VFA applications pioneered by earlier related work in Section
8.4.1 below, the exact definition of function space and algebraic function
operations provided here pave the way for a host of novel applications. They
include:

  * •

VSAs/Hyperdimensional Computing: VFA provides an algebraic, theoretically
grounded approach to expand VSA/Hyperdimensional Computing techniques to
computing with functions. For an application example, see Section 7.1.

  * •

Large-scale kernel machines: VFA provides feature representations and vector
operations for implementing kernel methods at large scale. The idea to
overcome the curse of dimensionality of traditional kernel methods (Bach,,
2019) by representing kernels as inner products of feature vectors has been
pointed out earlier in (Rahimi and Recht,, 2007), and see Section 8.4.2. For
examples of kernel applications of VFAs, see Section 7.2.

  * •

Probabilistic data structures/sketches: Probabilistic data structures or
sketches are reduced representations of mathematical objects formed from data
points (Mitzenmacher and Upfal,, 2017). Such reduced representations can be
more computation- and memory-efficient than storing all the individual data
points. In essence, a VFA vector can be seen as a compact probabilistic data
structure or sketch of a function (Section 7.2) or an object (Section 7.1).
Interestingly, VFAs add new capabilities to probabilistic data structures.
Specifically, a single VFA vector can implement the functionality of a kernel
machine, going beyond the standard application domain of sketches, such as
membership testing (Bloom filters (Bloom,, 1970)) or frequency estimation
(count-min sketches (Cormode and Muthukrishnan,, 2005)) – for an example, see
Section 7.2.

  * •

Reservoir computing: It has been emphasized previously that reservoir
computing can implement the algebraic framework of VSAs in recurrent networks
(Frady et al., 2018c, ; Kleyko et al., 2020a, ). Changing the input encoding
from random projection methods in conventional reservoir computing to KLPEs
will yield a new class of recurrent networks for computing in a transparent
fashion in a well-defined function space.

  * •

Neural networks: It has been posited that the missing of a binding operation
in neural networks is the root of their lack of data efficiency,
generalization, and robustness (Greff et al.,, 2020). The generalization of
the VSA binding concept from a symbolic domain to a function domain by VFAs is
a critical step towards developing neural network approaches with a binding
operation. Also, by representing functions as vectors, VFA provides an
interesting input interface for processing functions with current-type neural
networks. Further, there are known connections between kernels and deep
learning, specifically, gradient-based learning can be formulated in terms of
so-called path kernels (Domingos,, 2020), an extension of neural tangent
kernels (Jacot et al.,, 2018). Whether or not, such kernels can be expressed
in VFAs, is an open problem for future research.

  * •

Dynamic cognitive modeling: To model cognitive function of the brain, it has
been suggested, e.g., (Port and Van Gelder,, 1995; Eliasmith,, 1996), to map
discrete symbolic reasoning to continuous dynamical systems, specifically to
dynamic neural field models (Amari,, 1977; Ermentrout and McLeod,, 1993; Jirsa
and Haken,, 1996; Erlhagen and Schöner,, 2002). These models introduce a
continuous, low-dimensional topological space as internal or “mental”
navigation space. It has been emphasized how vector-symbolic concepts enable
the construction of dynamic cognitive models but challenging inverse problems
remain, i.e., how to appropriately design the mental space and a neural
dynamics suitable to solve a given cognitive problem (Beim Graben and
Potthast,, 2009; Widdows and Cohen,, 2015). Using VFA enables the shaping of
the similarity structure in the mental space, potentially offering new
approaches to tackle the inverse problems of challenging cognitive tasks.

###  8.3 VFA models for neuroscience

The predictions of VFA as a model for neuronal coding in the brain depend
critically on the choice of the encoding/binding method. The binding
operations of classical VSAs, Hadamard product and circular convolution, do
not easily map onto the function of biological neuronal circuits. They also
require dense representation vectors that seem incompatible with the
observation of sparse activity patterns in neural recordings (Rachkovskij and
Kussul,, 2001; Frady et al.,, 2021). Interestingly however, phasor vectors, as
used in Hadamard FPE, can be naturally represented by spikes, where the
complex phases are represented by the timing of periodic spike patterns (Frady
and Sommer,, 2019). One can introduce population sparsity in phasor codes and
build high-capacity associative memory networks for patterns with analog phase
angles in a subset of neurons (Frady and Sommer,, 2019). Block-local circular
convolution (Section 4.2.3) is a binding operation that can operate with such
codes. Potentially, this binding method could be implemented by biological
mechanisms (Frady et al.,, 2021), for example, leveraging active dendrites and
coincidence detection (Schaefer et al.,, 2003).

There are previous attempts to build models for hippocampus/entorinal cortex
using FPEs. One of these models with a spike-timing phase code exhibited
phenomena that coincide with experimental observations, such as place fields
and phase precession (Frady et al., 2018a, ). Another model, based on rate
codes and circular convolution binding (Komer and Eliasmith,, 2020), showed
that the model neurons can exhibit grid-cell like responses. It is intriguing
to speculate whether hippocampus and entorhinal cortex could implement and
leverage full VFA functionality. A VFA model of hippocampus/entorhinal cortex
would predict that activity patterns can represent functions over the
environmental space, such as probability densities of rewards and future
paths. Although the rate-based model implements a full VFA, the ability to
represent functions was not exploited in the original publications. The phase
code hippocampus model (Frady et al., 2018a, ) could be extended to a full VFA
by adding a binding operation like block-local circular convolution as
described in Section 4.2.3.

VFA sheds new light on potential computational roles of neural coding. Neural
coding is often seen as the outcome of statistical learning on the intrinsic
structure of sensory signals. For example, source coding (Shannon,, 1949) or
redundancy reduction (Barlow,, 2001) are objectives that can often result in
dimensionality reduction, but also in dimensionality expansion, when combined
with sparsity (Olshausen and Field,, 1996). Other theories for neural coding
are based on random sampling, not learning, for example, using randomized
synaptic projections. The computational objectives for such models include
hashing for forming an expanded address space for improving signal detection
(Babadi and Sompolinsky,, 2014; Fusi et al.,, 2016; Dasgupta et al.,, 2017),
or compressed sensing (Donoho,, 2006; Candès et al.,, 2006) for optimizing
neural communication under wiring constraints (Isely et al.,, 2010; Hillar and
Sommer,, 2015; Ganguli and Sompolinsky,, 2012). VFA reconciles learning-based
and randomness-based theories for neural coding. A VFA theory makes the
following predictions: a) Meaningful low-dimensional manifolds of sensory
signals are extracted (not discussed here) and then re-coded by high-
dimensional randomized activity patterns. The inner product in the high-
dimensional representation space approximates a similarity kernel on the data
manifold. b) The high-dimensional vector space can represent and manipulate
points and functions on the data manifold. The similarity between points and
available function space is determined by the kernel. c) Learning is
approximation in the kernel function space. d) Binding between vectors enables
the composition of new functions from already learned function primitives by
convolution. e) The role of neural correlations and “signal mixing”, as
vaguely defined earlier, can be made explicit: Correlations in population
activity encode information, which can be decoded by comparing the population
activity vector with memorized vectors. Signals can be mixed two in different
ways, a similarity-preserving manor by bundling, or in a similarity-destroying
manor by binding.

Most computational theories of brain function, such as Bayesian inference,
predictive coding, etc., require the encoding of functions by the population
activity of neurons. Probably closest to the VFA concept are population codes
(Pouget et al.,, 2000; Barber et al.,, 2003), such as Bayesian population
codes (Ma et al.,, 2006). In these models each neuron typically has a
Gaussian-shaped receptive field on the encoding manifold. This leads to an
inner product kernel that decays with distance and is translation invariant.
Thus Bayesian population codes induce a kernel function space. However, they
lack the binding operation (at least we are not aware of one) to perform the
algebraic function manipulations possible with VFA.

###  8.4 Related work

Although we believe we are the first to formally define VFA models and
describe their ability to represent and manipulate functions, there is related
previous work.

####  8.4.1 Earlier applications of fractional power encoding in VSA

Earlier proposals to combine VSA with FPE have pointed to a host of
interesting applications. For example, the fractional power vector based on
the circular convolution binding was proposed in Plate, (1992) as mechanism
for representing discrete sequences in recurrent neural networks. Generalizing
the fractional power vector, FPE based on circular convolution was proposed in
a VSA for representing continuous trajectories in a 2-D space (Section 5.6 in
Plate, 1994a ). The combination of VSA and circular convolution FPE444 In
Komer et al., (2019), the model combining these elements is referred to as
“spatial semantic pointers”, extending the convention of the same research
group to refer to VSA representations as “semantic pointers” (Blouw et al.,,
2016).  was revisited in a number of more recent papers in the context of the
following applications:

  * •

Reasoning on 2-D images: Weiss et al., (2016) used this model to holistically
represent 2-D images, thus offering the possibility to query the images, i.e.
answer relational queries such as “which digit is below a 2 and to the left of
a 1?” in images containing an array of MNIST digits. Similar models for
reasoning on images were also described in Frady et al., 2018b ; Lu et al.,
(2019). Our example in this application domain demonstrates how the kernel
shapes of a VFA can be adapted to optimally accommodate this application,
i.e., shaping a periodic kernel for providing toroid boundary conditions, see
Section 7.1.

  * •

Navigating a 2-D environment: Weiss et al., (2016) have demonstrated the use
of FPE in solving navigation problems, an application further elaborated in
Komer and Eliasmith, (2020).

  * •

Neuromorphic computing models: There are some initial efforts to use such
models in neuromorphic computing. In Frady et al., 2018a , a Hadamard FPE was
used in a hippocampus model linking computations and rhythm-based timing
patterns in spiking neural networks, while Dumont and Eliasmith, (2020)
proposed a way to implement FPE vectors by the rates of spiking neurons.

  * •

Prediction of dynamical systems: Voelker et al., (2021) have proposed to use
the model for simulating and predicting the behavior of dynamical systems.

####  8.4.2 Kernel machines with random Fourier features

It has been known that positive definite kernels are equivalent to inner
products in a derived feature space (Schölkopf et al.,, 2002). Rahimi and
Recht, (2007) pointed out how the Bochner theorem (Section 2.2) allows to
construct representation spaces with random Fourier features so that the inner
product approximates a similarity kernel of a certain kind. Every Fourier
density $p({\boldsymbol{\omega}})$ in (5) defines such a similarity kernel. If
the Fourier density is $[-1/2,1/2]$-band-limited, it induces a Hadamard FPE:

$\mathbf{z}(\mathbf{x})=\mathbf{z}_{1}(x_{1})\odot\mathbf{z}_{2}(x_{2})\odot\cdots\odot\mathbf{z}_{m}(x_{m})$
(59)

with the base vectors being random phasors
$\mathbf{z}_{i}(1)=\left(e^{\imath\phi^{i}_{1}},...,e^{\imath\phi^{i}_{n}}\right)$
sampled from $p({\boldsymbol{\phi}}={2\pi\boldsymbol{\omega}})$. Thus, random
Fourier features contain Hadamard FPEs as a special case. Conversely, FPEs
with binding operations other than the Hadamard product constitute encoding
schemes that are not contained in random Fourier features. Although random
Fourier features enable Hadamard VFAs, to our knowledge this potential has not
been exploited. Specifically, Rahimi and Recht, (2007) did not use Hadamard
binding between representation vectors to manipulate functions as described by
Theorem 1.

####  8.4.3 The discrete Fourier transform

The Hadamard FPE generalizes another simple construction of an LPE that comes
to mind, the representation of points by the discrete Fourier transform of the
band-limited delta function, the sinc function. First a finite interval of the
(one-dimensional) data space is tiled equally by $n$ points,
$x_{0},...,x_{n-1}$. The representation of an arbitrary point $r$ is then
given by:

$\displaystyle\mathbf{z}(r)$ $\displaystyle=$ $\displaystyle{\cal
F}\left(\sqrt{\frac{2}{\pi}}\mbox{sinc}(x+r)\right)=\int d\omega
e^{\imath\omega r}\Pi\left(\frac{\omega}{2}\right)$ (60) $\displaystyle=$
$\displaystyle
F(\mbox{sinc}(x_{0}+r),\mbox{sinc}(x_{1}+r),\cdots,\mbox{sinc}(x_{n-1}+r))^{\top}$
$\displaystyle=$
$\displaystyle\left((e^{\imath\omega(-1/2)},e^{\imath\omega(-1/2+1/n)},\cdots,e^{\imath\omega(-1/2+(n-1)/n)})^{r}\right)^{\top}$

with $\Pi(x)$ the box distribution. Thus, (60) is a Hadamard product FPE with
a particular base vector, which is a regular phasor vector, not a random
phasor. The base vector is essentially a column of the DFT matrix $F$. The
important generalization provided by our treatment here is that every random
phasor seed induces an LPE, and for pseudo-orthogonal random seeds the
corresponding LPEs do not interact (or, more correctly, only interact with
very low probability), and thus, can be combined to represent multi-
dimensional spaces.

## References

  * Agarwal et al., (2017) Agarwal, R., Chen, Z., and Sarma, S. V. (2017).  A novel nonparametric maximum likelihood estimator for probability density functions.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(7):1294–1308.
  * Aizerman et al., (1964) Aizerman, M. A., Braverman, E. M., and Rozonoer, L. I. (1964).  Theoretical foundations of potential function method in pattern recognition.  Automation and Remote Control, 25(6):917–936.
  * Alaghi and Hayes, (2018) Alaghi, A. and Hayes, J. P. (2018).  Computing with randomness.  IEEE Spectrum, 55(3):46–51.
  * Amari, (1977) Amari, S. (1977).  Dynamics of pattern formation in lateral-inhibition type neural fields.  Biological cybernetics, 27(2):77–87.
  * Aronszajn, (1950) Aronszajn, N. (1950).  Theory of reproducing kernels.  Transactions of the American mathematical society, 68(3):337–404.
  * Babadi and Sompolinsky, (2014) Babadi, B. and Sompolinsky, H. (2014).  Sparseness and expansion in sensory representations.  Neuron, 83(5):1213–1226.
  * Bach, (2019) Bach, F. (2019).  Are all kernels cursed?  https://francisbach.com/cursed-kernels/.  Online; accessed: 2021-05-20.
  * Barber et al., (2003) Barber, M. J., Clark, J. W., and Anderson, C. H. (2003).  Neural representation of probabilistic information.  Neural Computation, 15(8):1843–1864.
  * Barlow, (2001) Barlow, H. (2001).  Redundancy reduction revisited.  Network: computation in neural systems, 12(3):241.
  * Beim Graben and Potthast, (2009) Beim Graben, P. and Potthast, R. (2009).  Inverse problems in dynamic cognitive modeling.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 19(1):015103.
  * Bengio et al., (2021) Bengio, Y., Lecun, Y., and Hinton, G. (2021).  Deep learning for AI.  Communications of the ACM, 64(7):58–65.
  * Bissantz and Holzmann, (2007) Bissantz, N. and Holzmann, H. (2007).  Estimation of a quadratic regression functional using the sinc kernel.  Journal of statistical planning and inference, 137(3):712–719.
  * Bloom, (1970) Bloom, B. H. (1970).  Space/time trade-offs in hash coding with allowable errors.  Communications of the ACM, 13(7):422–426.
  * Blouw et al., (2016) Blouw, P., Solodkin, E., Thagard, P., and Eliasmith, C. (2016).  Concepts as semantic pointers: A framework and computational model.  Cognitive Science, 40(5):1128–1162.
  * Bochner, (1932) Bochner, S. (1932).  Lectures on Fourier Integrals.  Academic Publishing Company.
  * Bousselmi et al., (2020) Bousselmi, B., Dupuy, J.-F., and Karoui, A. (2020).  Reproducing kernels based schemes for nonparametric regression.  arXiv:2001.11213, pages 1–19.
  * Buckman et al., (2018) Buckman, J., Roy, A., Raffel, C., and Goodfellow, I. (2018).  Thermometer encoding: One hot way to resist adversarial examples.  In International Conference on Learning Representations (ICLR), pages 1–22.
  * Candès et al., (2006) Candès, E. J. et al. (2006).  Compressive sampling.  In Proceedings of the international congress of mathematicians, volume 3, pages 1433–1452. Madrid, Spain.
  * Cormen et al., (2009) Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009).  Introduction to algorithms.  MIT press.
  * Cormode and Muthukrishnan, (2005) Cormode, G. and Muthukrishnan, S. (2005).  An improved data stream summary: The count-min sketch and its applications.  Journal of Algorithms, 55(1):58–75.
  * Cuchiero et al., (2021) Cuchiero, C., Gonon, L., Grigoryeva, L., Ortega, J.-P., and Teichmann, J. (2021).  Discrete-time signatures and randomness in reservoir computing.  IEEE Transactions on Neural Networks and Learning Systems.
  * Dasgupta et al., (2008) Dasgupta, S., Papadimitriou, C. H., and Vazirani, U. V. (2008).  Algorithms.  McGraw-Hill Higher Education New York.
  * Dasgupta et al., (2017) Dasgupta, S., Stevens, C. F., and Navlakha, S. (2017).  A neural algorithm for a fundamental computing problem.  Science, 358(6364):793–796.
  * Davis, (1975) Davis, K. B. (1975).  Mean square error properties of density estimates.  The Annals of Statistics, pages 1025–1030.
  * Davis et al., (1977) Davis, K. B. et al. (1977).  Mean integrated square error properties of density estimates.  The Annals of Statistics, 5(3):530–535.
  * Devroye, (1992) Devroye, L. (1992).  A note on the usefulness of superkernels in density estimation.  The Annals of Statistics, pages 2037–2056.
  * Domingos, (2020) Domingos, P. (2020).  Every model learned by gradient descent is approximately a kernel machine.  arXiv preprint arXiv:2012.00152.
  * Donoho, (2006) Donoho, D. L. (2006).  Compressed sensing.  IEEE Transactions on information theory, 52(4):1289–1306.
  * Dumont and Eliasmith, (2020) Dumont, N. S.-Y. and Eliasmith, C. (2020).  Accurate representation for spatial cognition using grid cells.  In Annual Meeting of the Cognitive Science Society (CogSci), pages 2367–2373.
  * Edelman, (1998) Edelman, S. (1998).  Representation is representation of similarities.  Behavioral and brain sciences, 21(4):449–467.
  * Eliasmith, (1996) Eliasmith, C. (1996).  The third contender: A critical examination of the dynamicist theory of cognition.  Philosophical Psychology, 9(4):441–463.
  * Eliasmith and Thagard, (2001) Eliasmith, C. and Thagard, P. (2001).  Integrating structure and meaning: A distributed model of analogical mapping.  Cognitive Science, 25(2):245–286.
  * Erlhagen and Schöner, (2002) Erlhagen, W. and Schöner, G. (2002).  Dynamic field theory of movement preparation.  Psychological review, 109(3):545.
  * Ermentrout and McLeod, (1993) Ermentrout, G. B. and McLeod, J. B. (1993).  Existence and uniqueness of travelling waves for a neural network.  Proceedings of the Royal Society of Edinburgh Section A: Mathematics, 123(3):461–478.
  * Exterkate, (2011) Exterkate, P. (2011).  Modelling issues in kernel ridge regression.  Tinbergen Institute Discussion Papers 11-138/4, Tinbergen Institute.
  * Fodor and Pylyshyn, (1988) Fodor, J. A. and Pylyshyn, Z. W. (1988).  Connectionism and cognitive architecture: A critical analysis.  Cognition, 28(1-2):3–71.
  * (37) Frady, E. P., Kanerva, P., and Sommer, F. T. (2018a).  A framework for linking computations and rhythm-based timing patterns in neural firing, such as phase precession in hippocampal place cells.  Conference on Cognitive Computational Neuroscience.
  * (38) Frady, E. P., Kent, S. J., Kanerva, P., Olshausen, B. A., and Sommer, F. T. (2018b).  Cognitive neural systems for disentangling compositions.  In Cognitive Computing, pages 1–3.
  * Frady et al., (2020) Frady, E. P., Kent, S. J., Olshausen, B. A., and Sommer, F. T. (2020).  Resonator networks, 1: An efficient solution for factoring high-dimensional, distributed representations of data structures.  Neural Computation, 32(12):2311–2331.
  * (40) Frady, E. P., Kleyko, D., and Sommer, F. T. (2018c).  A theory of sequence indexing and working memory in recurrent neural networks.  Neural Computation, 30(6):1449–1513.
  * Frady et al., (2021) Frady, E. P., Kleyko, D., and Sommer, F. T. (2021).  Variable binding for sparse distributed representations: Theory and applications.  IEEE Transactions on Neural Networks and Learning Systems, PP(99):1–14.
  * Frady and Sommer, (2019) Frady, E. P. and Sommer, F. T. (2019).  Robust computation with rhythmic spike patterns.  Proceedings of the National Academy of Sciences, 116(36):18050–18059.
  * Fusi et al., (2016) Fusi, S., Miller, E. K., and Rigotti, M. (2016).  Why neurons mix: high dimensionality for higher cognition.  Current opinion in neurobiology, 37:66–74.
  * Gallier and Quaintance, (2020) Gallier, J. and Quaintance, J. (2020).  Differential geometry and Lie groups: a computational perspective, volume 12.  Springer Nature.
  * Ganguli and Sompolinsky, (2012) Ganguli, S. and Sompolinsky, H. (2012).  Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis.  Annual review of neuroscience, 35:485–508.
  * (46) Gayler, R. W. (1998a).  Multiplicative binding, representation operators & analogy.  In Advances in Analogy Research: Integration of Theory and Data from the Cognitive, Computational, and Neural Sciences, pages 1–4.
  * (47) Gayler, R. W. (1998b).  Multiplicative binding, representation operators & analogy.  In Gentner, D., Holyoak, K. J., Kokinov, B. N. (Eds.), Advances in analogy research: Integration of theory and data from the cognitive, computational, and neural sciences, pages 1–4, New Bulgarian University, Sofia, Bulgaria.
  * Gayler, (2003) Gayler, R. W. (2003).  Vector Symbolic Architectures Answer Jackendoff’s Challenges for Cognitive Neuroscience.  In Joint International Conference on Cognitive Science (ICCS/ASCS), pages 133–138.
  * Gilmore, (2012) Gilmore, R. (2012).  Lie groups, Lie algebras, and some of their applications.  Courier Corporation.
  * Glad et al., (2003) Glad, I. K., Hjort, N. L., and Ushakov, N. G. (2003).  Correction of density estimators that are not densities.  Scandinavian Journal of Statistics, 30(2):415–427.
  * Goltsev, (1996) Goltsev, A. D. (1996).  An assembly neural network for texture segmentation.  Neural Networks, 4(9):643–653.
  * Goodman, (2007) Goodman, J. W. (2007).  Speckle phenomena in optics: theory and applications.  Roberts and Company Publishers.
  * Goodman, (2015) Goodman, J. W. (2015).  Statistical optics.  John Wiley & Sons.
  * Gorban and Tyukin, (2018) Gorban, A. N. and Tyukin, I. Y. (2018).  Blessing of dimensionality: Mathematical foundations of the statistical physics of data.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376(2118):1–18.
  * Greff et al., (2020) Greff, K., van Steenkiste, S., and Schmidhuber, J. (2020).  On the binding problem in artificial neural networks.  arXiv preprint arXiv:2012.05208.
  * Gritsenko et al., (2017) Gritsenko, V. I., Rachkovskij, D. A., Frolov, A. A., Gayler, R. W., Kleyko, D., and Osipov, E. (2017).  Neural distributed autoassociative memories: A survey.  Cybernetics and Computer Engineering, 2(188):5–35.
  * Günther et al., (2019) Günther, F., Rinaldi, L., and Marelli, M. (2019).  Vector-space models of semantic representation from a cognitive perspective: A discussion of common misconceptions.  Perspectives on Psychological Science, 14(6):1006–1033.
  * Hafting et al., (2005) Hafting, T., Fyhn, M., Molden, S., Moser, M.-B., and Moser, E. I. (2005).  Microstructure of a spatial map in the entorhinal cortex.  Nature, 436(7052):801–806.
  * Hannagan et al., (2011) Hannagan, T., Dupoux, E., and Christophe, A. (2011).  Holographic string encoding.  Cognitive Science, 35(1):79–118.
  * Hillar and Sommer, (2015) Hillar, C. J. and Sommer, F. T. (2015).  When can dictionary learning uniquely recover sparse data from subsamples?  IEEE Transactions on Information Theory, 61(11):6290–6297.
  * Hofmann et al., (2008) Hofmann, T., Schölkopf, B., and Smola, A. J. (2008).  Kernel methods in machine learning.  The annals of statistics, pages 1171–1220.
  * Isely et al., (2010) Isely, G., Hillar, C., and Sommer, F. (2010).  Deciphering subsampled data: adaptive compressive sampling as a principle of brain communication.  Advances in Neural Information Processing Systems, 23:910–918.
  * Jacot et al., (2018) Jacot, A., Gabriel, F., and Hongler, C. (2018).  Neural tangent kernel: Convergence and generalization in neural networks.  arXiv preprint arXiv:1806.07572.
  * Jirsa and Haken, (1996) Jirsa, V. K. and Haken, H. (1996).  Field theory of electromagnetic brain activity.  Physical review letters, 77(5):960.
  * Jones and Mewhort, (2007) Jones, M. N. and Mewhort, D. J. K. (2007).  Representing word meaning and order information in a composite holographic lexicon.  Psychological Review, 114(1):1–37.
  * (66) Joshi, A., Halseth, J. J. J., and Kanerva, P. (2016a).  Language Geometry using Random Indexing.  submitted 2015, pages 1–7.
  * (67) Joshi, A., Halseth, J. T., and Kanerva, P. (2016b).  Language geometry using random indexing.  In International Symposium on Quantum Interaction (QI), pages 265–274.
  * Kanerva, (1988) Kanerva, P. (1988).  Sparse distributed memory.  MIT press.
  * Kanerva, (1996) Kanerva, P. (1996).  Binary spatter-coding of ordered K-tuples.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1112 LNCS:869–873.
  * Kanerva, (1997) Kanerva, P. (1997).  Fully distributed representation.  In Real World Computing Symposium (RWC), pages 358–365.
  * Kanerva, (2009) Kanerva, P. (2009).  Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors.  Cognitive Computation, 1:139–159.
  * Kleyko et al., (2021) Kleyko, D., Davies, M., Frady, E. P., Kanerva, P., Kent, S. J., Olshausen, B. A., Osipov, E., Rabaey, J. M., Rachkovskij, D. A., Rahimi, A., and Sommer, F. T. (2021).  Vector symbolic architectures as a computing framework for nanoscale hardware.  arXiv:2106.05268, pages 1–28.
  * (73) Kleyko, D., Frady, E. P., Kheffache, M., and Osipov, E. (2020a).  Integer echo state networks: Efficient reservoir computing for digital hardware.  IEEE Transactions on Neural Networks and Learning Systems, PP(99):1–14.
  * (74) Kleyko, D., Kheffache, M., Frady, E. P., Wiklund, U., and Osipov, E. (2020b).  Density encoding enables resource-efficient randomly connected neural networks.  IEEE Transactions on Neural Networks and Learning Systems, 32(8):3777–3783.
  * (75) Kleyko, D., Osipov, E., Papakonstantinou, N., and Vyatkin, V. (2018a).  Hyperdimensional computing in industrial systems: The use-case of distributed fault isolation in a power plant.  IEEE Access, 6:30766–30777.
  * (76) Kleyko, D., Rahimi, A., Gayler, R. W., and Osipov, E. (2020c).  Autoscaling Bloom filter: Controlling trade-off between true and false positives.  Neural Computing and Applications, 32:3675–3684.
  * (77) Kleyko, D., Rahimi, A., Rachkovskij, D. A., Osipov, E., and Rabaey, J. M. (2018b).  Classification and recall with binary hyperdimensional computing: Tradeoffs in choice of density and mapping characteristics.  IEEE Transactions on Neural Networks and Learning Systems, 29(12):5880–5898.
  * (78) Kleyko, D., Rosato, A., Frady, E. P., Panella, M., and Sommer, F. T. (2020d).  Perceptron theory for predicting the accuracy of neural networks.  arXiv:2012.07881, pages 1–12.
  * Komer, (2020) Komer, B. (2020).  Biologically Inspired Spatial Representation.  PhD thesis, University of Waterloo.
  * Komer and Eliasmith, (2020) Komer, B. and Eliasmith, C. (2020).  Efficient navigation using a scalable, biologically inspired spatial representation.  In Annual Meeting of the Cognitive Science Society (CogSci), pages 1532–1538.
  * Komer et al., (2019) Komer, B., Stewart, T. C., Voelker, A. R., and Eliasmith, C. (2019).  A neural representation of continuous space using fractional binding.  In Annual Meeting of the Cognitive Science Society (CogSci), pages 2038–2043.
  * Laiho et al., (2015) Laiho, M., Poikonen, J. H., Kanerva, P., and Lehtonen, E. (2015).  High-dimensional computing with sparse vectors.  2015 IEEE Biomedical Circuits and Systems Conference (BioCAS), pages 1–4.
  * Ledoux, (2001) Ledoux, M. (2001).  The concentration of measure phenomenon.  American Mathematical Society.
  * Lewenstein and Tarkowski, (1992) Lewenstein, M. and Tarkowski, W. (1992).  Optimal storage of correlated patterns in neural-network memories.  Physical Review A, 46(4):2139.
  * Lu et al., (2019) Lu, T., Voelker, A. R., Komer, B., and Eliasmith, C. (2019).  Representing spatial relations with fractional binding.  In Annual Meeting of the Cognitive Science Society (CogSci), pages 2214–2220.
  * Ma et al., (2006) Ma, W. J., Beck, J. M., Latham, P. E., and Pouget, A. (2006).  Bayesian inference with probabilistic population codes.  Nature neuroscience, 9(11):1432–1438.
  * Marsocci, (1956) Marsocci, V. A. (1956).  An error analysis of electronic analog computers.  IRE Transactions on Electronic Computers, (4):207–212.
  * Mitzenmacher and Upfal, (2017) Mitzenmacher, M. and Upfal, E. (2017).  Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis.  Cambridge University Press.
  * Moin et al., (2021) Moin, A., Zhou, A., Rahimi, A., Menon, A., Benatti, S., Alexandrov, G., Tamakloe, S., Ting, J., Yamamoto, N., Khan, Y., Burghardt, F., Benini, L., Arias, A. C., and Rabaey, J. M. (2021).  A wearable biosensing system with in-sensor adaptive machine learning for hand gesture recognition.  Nature Electronics, 4(1):54–63.
  * Neubert et al., (2019) Neubert, P., Schubert, S., and Protzel, P. (2019).  An introduction to hyperdimensional computing for robotics.  KI-Künstliche Intelligenz, 33(4):319–330.
  * Olshausen and Field, (1996) Olshausen, B. A. and Field, D. J. (1996).  Natural image statistics and efficient coding.  Network (Bristol, England), 7(2):333–9.
  * Osipov et al., (2017) Osipov, E., Kleyko, D., and Legalov, A. (2017).  Associative synthesis of finite state automata model of a controlled object with hyperdimensional computing.  In Annual Conference of the IEEE Industrial Electronics Society (IECON), pages 3276–3281.
  * Penz, (1987) Penz, P. A. (1987).  The closeness code: An integer to binary vector transformation suitable for neural network algorithms.  In IEEE First Annual International Conference on Neural Networks (ICNN), pages 515–522.
  * Plate, (1991) Plate, T. A. (1991).  Holographic Reduced Representations : Convolution Algebra for Compositional Distributed Representations.  Proceedings of the 12th international joint conference on Artificial intelligence, pages 30–35.
  * Plate, (1992) Plate, T. A. (1992).  Holographic recurrent networks.  In Advances in Neural Information Processing Systems (NIPS), pages 34–41.
  * (96) Plate, T. A. (1994a).  Distributed Representations and Nested Compositional Structure.  PhD thesis.
  * (97) Plate, T. A. (1994b).  Estimating analogical similarity by dot-products of holographic reduced representations.  In Advances in Neural Information Processing Systems (NIPS), pages 1109–1116.
  * Plate, (1995) Plate, T. A. (1995).  Holographic reduced representations.  IEEE Transactions on Neural networks, 6(3):623–641.
  * Port and Van Gelder, (1995) Port, R. F. and Van Gelder, T. (1995).  Mind as motion: Explorations in the dynamics of cognition.  MIT press.
  * Pouget et al., (2000) Pouget, A., Dayan, P., and Zemel, R. (2000).  Information processing with population codes.  Nature Reviews Neuroscience, 1(2):125–132.
  * Rachkovskij, (2001) Rachkovskij, D. A. (2001).  Representation and processing of structures with binary sparse distributed codes.  IEEE Transactions on Knowledge and Data Engineering, 13(2):261–276.
  * Rachkovskij, (2007) Rachkovskij, D. A. (2007).  Linear classifiers based on binary distributed representations.  Information Theories and Applications, 14(3):270–274.
  * Rachkovskij and Kussul, (2001) Rachkovskij, D. A. and Kussul, E. M. (2001).  Binding and normalization of binary sparse distributed representations by context-dependent thinning.  Neural Computation, 13(2):411–452.
  * Rachkovskij et al., (2012) Rachkovskij, D. A., Misuno, I. S., and Slipchenko, S. V. (2012).  Randomized projective methods for the construction of binary sparse vector representations.  Cybernetics and Systems Analysis, 48(1):146–156.
  * Rachkovskij and Slipchenko, (2012) Rachkovskij, D. A. and Slipchenko, S. V. (2012).  Similarity-based retrieval with structure-sensitive sparse binary distributed representations.  Computational Intelligence, 28(1):106–129.
  * Rachkovskij et al., (2005) Rachkovskij, D. A., Slipchenko, S. V., Kussul, E. M., and Baidyk, T. N. (2005).  Sparse binary distributed encoding of scalars.  Journal of Automation and Information Sciences, 37(6):12–23.
  * Rahimi et al., (2017) Rahimi, A., Datta, S., Kleyko, D., Frady, E. P., Olshausen, B., Kanerva, P., and Rabaey, J. M. (2017).  High-dimensional computing as a nanoscalable paradigm.  IEEE Transactions on Circuits and Systems I: Regular Papers, 64(9):2508–2521.
  * Rahimi et al., (2019) Rahimi, A., Kanerva, P., Benini, L., and Rabaey, J. M. (2019).  Efficient biosignal processing using hyperdimensional computing: Network templates for combined learning and classification of ExG signals.  Proceedings of the IEEE, 107(1):123–143.
  * Rahimi and Recht, (2007) Rahimi, A. and Recht, B. (2007).  Random features for large-scale kernel machines.  In Advances in Neural Information Processing Systems (NIPS), volume 20, pages 1–8.
  * Räsänen and Saarinen, (2016) Räsänen, O. and Saarinen, J. (2016).  Sequence prediction with sparse distributed hyperdimensional coding applied to the analysis of mobile phone use patterns.  IEEE Transactions on Neural Networks and Learning Systems, 27(9):1878–1889.
  * Recchia et al., (2015) Recchia, G., Sahlgren, M., Kanerva, P., and Jones, M. N. (2015).  Encoding sequential information in semantic space models: Comparing holographic reduced representation and random permutation.  Computational Intelligence and Neuroscience, pages 1–18.