{'fraction_non_alphanumeric': 0.04480413965008598, 'fraction_numerical': 0.012715541041538487, 'mean_word_length': 4.273105398885284, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Theoretical Perspective on Hyperdimensional Computing

Hyperdimensional (HD) computing is a set of neurally inspired methods for obtaining high-dimensional, low-precision, distributed representations of data. These representations can be combined with simple, neurally plausible algorithms to effect a variety of information processing tasks. HD computing has recently garnered significant interest from the computer hardware community as an energy-efficient, low-latency, and noise-robust tool for solving learning problems. In this review, we present a unified treatment of the theoretical foundations of HD computing with a focus on the suitability of representations for learning.


Introduction
Hyperdimensional (HD) computing is an emerging area at the intersection of computer architecture and theoretical neuroscience (Kanerva, 2009). It is based on the observation that brains are able to perform complex tasks using circuitry that: (1) uses low power, (2) requires low precision, and (3) is highly robust to data corruption. HD computing aims to carry over similar design principles to a new generation of digital devices that are highly energy-efficient, fault tolerant, and well-suited to natural information processing .
The wealth of recent work on neural networks also draws its inspiration from the brain, but modern instantiations of these methods have diverged from the desiderata above. The success of these networks has rested upon choices that are not neurally plausible, most notably significant depth and training via backpropagation. Moreover, from a practical perspective, training these models often requires high precision and substantial amounts of energy. While a large body of literature has sought to ameliorate these issues with neural networks, these efforts have largely been designed to address specific performance limitations. By contrast, the properties above emerge naturally from the basic architecture of HD computing.
Indeed, a cottage industry has emerged around developing optimized implementations of HD computing based algorithms on hardware accelerators Rahimi et al., 2018;Gupta et al., 2018;Schmuck et al., 2019;Salamat et al., 2019;. Broadly speaking, this line of work touts HD computing as an energy efficient, low-latency, and noise-resilient alternative to conventional realizations of general purpose ML algorithms like support vector machines, multilayer perceptrons, and nearest-neighbor classifiers. While this work has reported impressive performance benefits, there has been relatively little formal treatment of HD computing as a tool for general purpose learning.
This review has two broad aims. The first, more modest, goal is to introduce the area of hyperdimensional computing to a machine learning audience. The second is to develop a particular mathematical framework for understanding and analyzing these models. The recent literature has suggested a variety of different HD architectures that conform to the overall blueprint given above, but differ in many important details. We present a unified treatment of many such architectures that enables their properties to be compared. The most basic types of questions we wish to answer are: 1. How can individual items, sets of items, and sequences of items, be represented and stored in H-space, in a manner that permits reliable decoding?
2. What kinds of noise can be tolerated in H-space?
3. What kinds of structure in the input x-space are preserved by the mapping to Hspace?
4. What is the power of linear separators on the φ-representation?
Some of these questions have been introduced in the HD computing literature and studied in isolation (Plate, 2003;Gallant & Okaywe, 2013;Kleyko et al., 2018;Frady et al., 2018). In this work we address these questions formally and in greater generality.

Introduction to HD Computing
In the following section we provide an introduction to the fundamentals of HD computing and provide some brief discussion of its antecedents in the neuroscience literature.

High-Dimensional Representations in Neuroscience
Neuroscience has proven to be a rich source of inspiration for the machine learning community: from the perceptron (Rosenblatt, 1958), which introduced a simple and generalpurpose learning algorithm for linear classifiers, to neural networks (Rumelhart et al., 1986), to convolutional architectures inspired by visual cortex (Fukushima, 1980), to sparse coding (Olshausen & Field, 1996) and independent component analysis (Bell & Sejnowski, 1995). One of the most consequential discoveries from the neuroscience community, underlying much research at the intersection of neuroscience and machine learning, has been the notion of high-dimensional distributed representations as the fundamental data structure for diverse types of information. In the neuroscience context, these representations are also typically sparse. To give a concrete example, the sensory systems of many organisms have a critical component consisting of a transformation from relatively low dimensional sensory inputs Input Data: x ∈ X Mixed in H, X -space Figure 1: The flow of data in HD computing. Data is mapped from the input space to HDspace under an encoding function φ : X → H. HD representations of data are stored in data structures and may be corrupted by noise or hardware failures. HD representations can be used as input for learning algorithms or other information processing tasks and may be decoded to recover the input data.
to much higher-dimensional sparse representations. These latter representations are then used for subsequent tasks such as recall and learning. In the olfactory system of the fruit fly (Masse et al., 2009;Turner et al., 2008;Wilson, 2013;Caron et al., 2013), the mapping consists of two steps that can be roughly captured as follows: 1. An input x ∈ R n is collected via a sensory organ and mapped under a random linear transformation to a point φ(x) ∈ R d (d ≫ n) in a high-dimensional space.
2. The coordinates of φ(x) are "sparsified" by a thresholding operation which just retains the locations of the largest k coordinates.
In the fly, the olfactory input is a roughly 50-dimensional vector (n = 50) corresponding to different types of odor receptor neurons while the sparse representation to which it is mapped is roughly 2,000-dimensional (d = 2000). A similar "expand-and-sparsify" template is also found in other species, suggesting that this process somehow exposes the information present in the input signal in a way that is amenable to learning by the brain (Stettler & Axel, 2009;Olshausen & Field, 2004;Chacron et al., 2011). The precise mechanisms by which this occurs are still not fully understood, but may have close connections to some of the literature on the theory of neural networks and kernel methods (Cybenko, 1989;Barron, 1993;Rahimi & Recht, 2008).

HD Computing
The notion of high-dimensional, distributed, data representations has engendered a number of computational models that have collectively come to be known as vector symbolic architectures (VSA) (Levy & Gayler, 2008). In general, VSAs provide a systematic way to generate and manipulate high-dimensional representations of symbols so as to implement cognitive operations like association between related concepts. Notable examples of VSAs include "holographic reduced representations" (Plate, 1995(Plate, , 2003, "binary spatter codes" (Kanerva, 1994(Kanerva, , 1995, and "matrix binding of additive terms" (Gallant & Okaywe, 2013). HD computing can be seen as a successor to these early VSA models, with a strong additional slant towards hardware efficiency. While our treatment focuses primarily on recent work on HD computing, many of our results apply to these earlier VSA models as well.
An overview of data-flow in HD computing is given in Figure 1. The first step in HD computing is encoding, which maps a piece of input data to its high-dimensional representation under some function φ : X → H. The nature of φ depends on the type of input and the choice of H. In this review, we consider inputs consisting of sets, sequences, and structures composed from a finite alphabet as well as vectors in a Euclidean space. The space H is some d-dimensional inner-product space defined over the real numbers or a subset thereof. Work in the literature on both HD computing and traditional neural networks has also explored complex-valued embeddings (Weiss et al., 2016;Parcollet et al., 2019;Zhang et al., 2016). However, we here focus on the more common case of real-valued embeddings. For computational reasons, it is common to restrict H to be defined over integers in a limited range [−b, b]. We emphasize that the dimension of H need not, in general, be greater than that of X . Indeed, in several cases the encoding methods discussed can be used to reduce the dimension of the data.
The HD representations of data can be manipulated using simple element-wise operators. Two common and important such operations are "bundling" and "binding." The bundling operator is used to compile a set of elements in H and takes the form of a function ⊕ : H × H → H. The function takes two points in H and returns a third point that is similar to both operands. The binding operator is used to create ordered tuples of points in H and is likewise a function ⊗ : H × H → H. The function takes a pair of points in H as input, and produces a third point dissimilar to both operands. We make these notions more precise in our subsequent discussion of encoding.
Given the HD representation φ(S) of a set of items S ⊂ X (produced by bundling the items), we may be interested to query the representation to determine if it contains the encoding of some x ∈ X . To do so, we compute a metric of similarity ρ(φ(x), φ(S)) and declare that the item is present in S if the similarity is greater than some critical value. This process can be used to decode the HD representation so as to recover the original points in X (Plate, 2003;Frady et al., 2018). We may additionally wish to assert that we can decode reliably even if φ(S) has been corrupted by some noise process. One of our chief aims in this paper is to mathematically characterize sufficient conditions for robust decoding under different noise models and input data types.
Beyond simply storing and recalling specific patterns, HD representations may also be used for learning. HD computing is most naturally applicable to classification problems. Suppose we are given some collection is a categorical variable indicating the class label of a particular x i . One simple form of HD classification bundles together the data corresponding to a particular class to generate a "prototypical" example for the class (Kanerva, 2009;Kleyko et al., 2018;Rahimi et al., 2018): The resulting φ(c k ) are sometimes quantized to lower precision or sparsified via a thresholding operation. A nice feature of this scheme is that it is extremely simple to implement in an on-line fashion: that is, on streaming data arriving continuously over time . It is common to fine-tune the class prototypes using a few rounds of perceptron training (Imani et al., , 2019b. Given some subsequent piece of query data x q ∈ X for which we do not know the correct label, we simply return the label of the most similar prototype: The similarity metric ρ is typically taken to be the dot-product, with the operands normalized if necessary. Thus, on the whole, the scheme is quite similar to classical statistical methods like naive Bayes and Fisher's linear discriminant. In Section 5.2.1, we consider properties of the HD encoding that can make linear models more powerful in HD space than in the original space. HD computing and closely related techniques have been applied to a wide variety of practical problems in fields ranging from bio-signal processing (Rahimi et al., 2016;, to natural language processing (Sahlgren, 2005), and robotics (Mitrokhin et al., 2019;Neubert et al., 2019). We are here concerned with a more abstract treatment that focuses on the basic properties of HD computing and will not attempt to survey this literature. The interested reader is referred to (Rahimi et al., 2016;Kleyko et al., 2018) for discussions related to practical aspects of HD computing.

Encoding and Decoding Discrete Data
A central object in HD computing is the mapping from inputs to their high-dimensional representations. The design of this mapping, typically referred to as "encoding" in the literature on HD computing, has been the subject of considerable research. There is a wide range of possible encoding methods. Some of these have been introduced in the HD computing literature and studied in isolation (Plate, 2003;Gallant & Okaywe, 2013;Kleyko et al., 2018). In this review, we present a novel unifying framework in which to study these mappings and to characterize their key properties in a non-asymptotic setting. We first discuss the encoding and decoding of sets in some detail. Many HD encoding procedures for more complex data types such as sequences essentially amount to transforming the data into a set and then applying the standard set-encoding method.

Finite Sets
be some finite alphabet of m symbols. Symbols a ∈ A are mapped to H under an encoding function φ : A → H. Our goal in this section is to consider the encoding of sets S whose elements are drawn from A. The HD representation of S is constructed by superimposing the embeddings of the constituent elements using the bundling operator ⊕ : H × H → H. The encoding of S is defined to be φ(S) = ⊕ a∈S φ(a). We first focus on the intuitive setting in which ⊕ is the element-wise sum and then address other forms of bundling.
To determine if some a ∈ A is contained in S, we check if the dot product φ(a), φ(S) exceeds some fixed threshold. If the codewords {φ(a) : a ∈ A} are orthogonal and have a constant length L, then we have φ(a), φ(S) = L 2 ½(a ∈ S), where ½ is the indicator function which evaluates to one if its argument is true and zero otherwise. However, when the codewords are not perfectly orthogonal, we have φ(a), φ(S) = L½(a ∈ S)+∆, where ∆ is the "cross-talk" caused by interference between the codewords. In order to decode reliably, we must ensure the contribution of the cross-talk is small and bounded. We formalize this using the notion of incoherence popularized in the sparse coding literature. We define incoherence formally as (Donoho et al., 2005): When d ≥ m, it is possible to have codewords that are mutually orthogonal, whereupon µ = 0. In general, we will be interested in results that do not require d ≥ m.

Exact Decoding of Sets
In the following section, we show how the cross-talk can be bounded in terms of the incoherence of φ, and use this to derive a simple threshold rule for exact decoding.
Theorem 2 Let L = min a∈A φ(a) and let the bundling operator be the element wise sum. To decode whether an element a lies in set S, we use the rule This gives perfect decoding for sets of size ≤ s if φ is 1/(2s)-incoherent.
Proof Consider some symbol a. Then: If a ∈ S, then the above is lower bounded by L 2 − sL 2 µ, where µ is the incoherence of φ. Otherwise, it is upper bounded by sL 2 µ. So we decode perfectly if sL 2 µ < L 2 /2, or µ < 1/(2s).

Random Codebooks
In practice, each φ(a) is usually generated by sampling from some distribution over H or a subset of H (Kanerva, 2009;Kleyko et al., 2018;Rahimi et al., 2018). We typically require that this distribution is factorized so that coordinates of φ(a) are i.i.d.. Intuitively, the incoherence condition stipulated in Theorem 2 will hold if dot products between two different codewords are concentrated around zero. Furthermore, we would like it to be the case that this concentration occurs quickly as the encoding dimension is increased. It turns out that a fairly broad family of simple distributions satisfies these properties.
As an example, suppose φ(a) is sampled from the uniform distribution over {±1} d , which we denote φ(a) ∼ {±1} d . In this case, L = √ d exactly, and a direct application of Hoeffding's inequality and the union bound yields: (Recall that m = |A|.) Stated another way, with high probability µ = O( (ln m)/d), meaning that we can make µ as small as desired by increasing d.
In fact, the same basic approach holds for the much broader class of sub-Gaussian distributions, which can be characterized as follows (Wainwright, 2019): Definition 3 Sub-Gaussian Random Variable. A random variable X ∼ P X is said to be sub-Gaussian if there exists σ ∈ R + , referred to as the sub-Gaussian parameter, such that: Intuitively, the tails of a sub-Gaussian random variable decay at least as fast those of a Gaussian. We say the encoding φ is σ-sub-Gaussian if φ(a) is generated by sampling its d coordinates independently from the same sub-Gaussian distribution with parameter σ. We say φ is "centered" if the distribution from which it is sampled is of mean zero. In general, we assume φ is centered unless stated otherwise. Codewords drawn from a sub-Gaussian distribution have the useful property that their lengths concentrate fairly rapidly around their expected value. This concentration is, in general, worse than sub-Gaussian but well behaved nonetheless. The following result is well known but we reiterate it here as it is useful for our subsequent discussion. A proof is available in the appendix.
Theorem 4 Let φ be centered and σ-sub-Gaussian. Then: for some positive absolute constant c.
Like the conventional Gaussian distribution, sub-Gaussianity is preserved under linear transformations. That is, if x = {x i } n i=1 is a sequence of i.i.d. sub-Gaussian random variables and a is an arbitrary vector in R n , then a, x is sub-Gaussian with parameter σ a 2 (Wainwright, 2019). We can obtain a more general version of the previous result about φ ∼ {±1} d which applies to φ(a) sampled from any sub-Gaussian distribution.
Theorem 5 Let φ be σ-sub-Gaussian. Then, for µ > 0, Proof Fix some a and a ′ . Treating φ(a) as a fixed vector in R d and using the fact that sub-Gaussianity is preserved under linear transformations, we may apply a Chernoff bound for sub-Gaussian random variables (e.g. Prop 2.1 of (Wainwright, 2019)) to obtain: where L max = max a∈A φ(a) 2 . Therefore, taking κ = L 2 /L 2 max , we have: and the claim follows by applying the union bound over all m 2 < m 2 /2 pairs of codewords. We note that, per Theorem 4, κ → 1 as d becomes large.
To be concrete and provide useful practical guidance, we here introduce three running examples of codeword distributions.
Dense Binary Codewords. In our first example, the most common in practice in our impression, φ(a) is sampled from the uniform distribution over the d-dimensional unit cube {−1, +1} d . This approach is advantageous because it leads to efficient hardware implementations Rahimi et al., 2018) and is simple to analyze.
Gaussian Codewords. Our second example consists of codewords sampled from the ddimensional Gaussian distribution (Plate, 2003). That is, φ(a) ∼ N (0 d , σ 2 I d ), where 0 d is the d-dimensional zero vector. Here, the codewords will not be of exactly the same length. However, Theorem 4 ensures that squared codeword lengths are concentrated around their expected value of σ 2 d. More formally, for some τ > 0: In both cases, we can see that to obtain a µ-incoherent codebook with probability 1 − δ, is it sufficient to choose: Or, stated another way, we have µ = O( (ln m)/d) with high probability. The key point in the two examples above is that the encoding dimension is inversely proportional to µ 2 . Per Theorem 2, to decode correctly it is sufficient to have µ = 1/(2s), meaning that the encoding dimension scales quadratically with the number of elements in the set, but only logarithmically in the alphabet size and probability of error.
We will also consider a third example in which the codewords are sparse and binary. However, we defer this for the time being as slightly different encoding methods and analysis techniques are appropriate.

Decoding with Small Probability of Error
The analysis above gives strong uniform bounds showing that, with probability at least 1−δ over random choice of the codebook, every subset of size at most s will be correctly decoded. However, this guarantee requires us to impose the unappealing restriction that s ≪ √ d which is a significant practical limitation. We here show that we can obtain s = O(d) but with a weaker pointwise guarantee: any arbitrarily chosen set of size at most s will be correctly decoded with probability 1 − δ over the random choice of codewords. Rather than insist on a hard upper bound on the incoherence of the codebook, we can instead require the milder condition that random sums over dot-products between ≤ s codewords are small with high-probability. We define this property more formally as follows: Definition 6 Subset Incoherence. For τ > 0, we say a random mapping φ : A → H satisfies (s, τ, δ)-subset incoherence if, for any S ⊂ A of size at most s, with probability at least 1 − δ over the choice of φ: Once again, it turns out that sampling the codewords from a sub-Gaussian distribution can readily be seen to satisfy a subset-incoherence condition with high-probability: Theorem 7 Let φ be σ-sub-Gaussian and fix some S ⊂ A of size s. Then where κ and L are as in Theorem 5.
The proof is similar to Theorem 5 and is available in the appendix. As a concrete example, in the practically relevant case that φ ∼ {±1} d the above boils down to: Stated another way, we have: τ = O( (s ln m)/d). Following Theorem 2, in order to ensure correct decoding with high probability, we must simply argue that the codebook satisfies the subset-incoherence property with τ = 1/2, meaning we should choose the encoding dimension to be d = O(s ln m). This method of analysis is similar to that of (Plate, 2003;Gallant & Okaywe, 2013;Frady et al., 2018), who reach the same conclusion vis-à-vis linear scaling using the central limit theorem. However, our formalism is more general and is non-asymptotic.

Comparing Set Representations
We can estimate the size of a set by computing the norm of its encoding, where the precision of the estimate can be bounded in terms of the incoherence of φ. In the following discussion, we make the simplifying assumption that the codewords are all of a constant length L. Again appealing to Theorem 4, we can see that this assumption is not onerous since the codeword lengths concentrate around their expected value.
Theorem 8 Let S be a set of size s. Then: The proof is by direct manipulation: The other direction is analogous.
Given a pair of sets S, S ′ over the same alphabet, we can estimate the size of their intersection and union directly from their encoded representation.
Theorem 9 Let S and S ′ be sets of size s and s ′ drawn from A and denote their encodings by φ(S) and φ(S ′ ) respectively.
The proof is similar to Theorem 8 and is deferred to the appendix. Noting as well that |S ∪ S ′ | = |S| + |S ′ | − |S ∩ S ′ |, we see that we can estimate the size of the union using the previous theorem. In practice, it may be unnecessary to compute these quantities with a high degree of precision. For instance, it may only be necessary to identify sets with a large intersection-over-union. Provided the definition of "large" is somewhat loose, we can accept a higher incoherence among the codewords in exchange for reducing the encoding dimension.

Sparse and Low-Precision Encodings
In the previous discussion, we assumed the bundling operator was the element-wise sum. This is a natural choice when the codewords are dense or non-binary. However, the resulting encodings are of unconstrained precision which may be undesirable from a computational perspective. For the purposes of representing sets of size ≤ s, we may truncate φ(S) to lie in the range [−c, c], with negligible loss in accuracy provided c = O( √ s). In practice, it is common to quantize the encodings more aggressively to binary precision by thresholding (Kanerva, 1994;Burrello et al., 2018;Imani et al., 2019a). In other words, we encode as φ(S) = g t (S), where g t is a thresholding function that is applied coordinate-wise: g t (x) = 1 if x ≥ t and 0 otherwise.
As a notable special case of the thresholding rule described above, we here consider encoding with sparse codewords. In this case, we assume that a coordinate in a codeword is non-zero with some small probability. In other words, φ(a) i ∼ Bernoulli(p), where p ≪ 1/2. We may then bundle items by taking an element-wise sum of their codewords with threshold t = 1, which is equivalent to taking the element-wise maximum over the codewords. That is, φ(S) = max a∈S φ(a), where the max operator is applied coordinate-wise. Noting that the max is upper bounded by the sum in this setting, the notion of incoherence is a relevant quantity and the analysis of Theorem 2 continues to apply.
This encoding procedure is essentially a standard implementation of the popular "Bloom filter" data structure for representing sets (Bloom, 1970). The conventional Bloom filter differs slightly in that the typical decoding rule is to threshold φ(a), φ(S) at φ(a) 1 . There is a large literature on Bloom filters with applications ranging from networking and database systems to neural coding, and several schemes for generating good codewords have been proposed (Broder & Mitzenmacher, 2004;Pagh et al., 2005;Dasgupta et al., 2018). Using the random coding scheme described here, the optimal value of p can be seen to be (ln 2)/s and, to ensure the probability of a false positive is at most δ, the encoding dimension should be chosen on the order of s ln(1/δ) (Broder & Mitzenmacher, 2004). A practical benefit of Bloom filters is that they have an efficient implementation using hash functions which does not require materializing a codebook as in methods based on random sampling. This may be beneficial when the alphabet size is large enough that storing codewords is not possible. The connections between HD computing and Bloom filters are examined in greater detail in (Kleyko et al., 2019).
We remark that this method of encoding is related to an interesting procedure known as "context dependent thinning" (CDT) which can be used to control the density of binary representations (Rachkovskij, 2001;Kleyko et al., 2018). CDT takes the logical "and" of φ(S) and some permutation σ(φ(S)) to obtain the thinned representation φ(S) ′ = φ(S) ∧ σ(φ(S)). This process can be repeated until the desired density of φ(S) is achieved. A capacity analysis of CDT representations can be found in .

Robustness to Noise
In this section we explore the noise robustness properties of the encoding methods discussed above using the formalism of incoherence. We consider some unspecified noise process which corrupts the encoding of a set S ⊂ A of size at most s according toφ We are interested in understanding the conditions under which we can still decode reliably.
Theorem 10 Suppose S has size ≤ s and ∆ S is ρ-bounded. We can correctly decode S using the thresholding rule from Theorem 2 if: The proof is a straightforward extension of Theorem 2 and is available in the appendix. The practical implication is that there is a tradeoff between the incoherence of the codebook and robustness to noise: a higher incoherence allows for a smaller encoding dimension but at the cost of a tighter constraint on ρ. We can analyze several practically relevant noise models by placing additional restrictions on ∆ S and by considering worst or typical case bounds on ρ. We here consider different forms of noise under constraints on H. Our goal is to understand how the magnitude of noise that can be tolerated scales with the encoding dimension, size s of the encoded set, and size m of the alphabet. In each setting we consider a "passive" model in which the noise is sampled randomly from some distribution, and an "adversarial" model in which the noise is arbitrary and may be designed to maliciously corrupt the encodings. We again appeal to Theorem 4 to justify a simplifying assumption that the codewords are of equal length.
Lemma 11 Sub-Gaussian Codewords. Fix a centered and σ-sub-Gaussian codebook φ whose codewords are of length L. Consider the passive additive white Gaussian noise model ; that is, each coordinate is corrupted by Gaussian noise with mean zero and variance σ 2 ∆ . Then, we can correctly decode with probability 1 − δ over random draws of ∆ S provided: Now consider an adversarial model in which ∆ S is arbitrary save for a constraint on the norm: ∆ S 2 ≤ ωL. Then, we can correctly decode provided: Proof Let us first consider the passive case in which ∆ S ∼ N (0, σ 2 ∆ I d ). Fix some a ∈ A. Then φ(a), ∆ S ∼ N (0, σ 2 ∆ L 2 ). By a standard tail bound on the Gaussian distribution (Wainwright, 2019) and the union bound, we have: Therefore, with probability 1 − δ, we have that ∆ S is ρ-bounded for ρ ≤ σ ∆ L 2 ln(2m/δ).
By Theorem 10 we can decode correctly if: Now consider the adversarial case in which ∆ S 2 ≤ ωL. By the Cauchy-Schwarz inequality, | φ(a), ∆ S | ≤ ωL 2 . Therefore, by Theorem 10, we can decode correctly if We again emphasize that, per Theorem 5, µ = O( (ln m)/d). Since L = O( √ d), we can see that we can tolerate σ ∆ ≈ d/(ln m) − s in the passive case. We next turn to a notable special case of the above in which the codewords are dense and binary. In this case, we may assume that H is constrained to be integers in the range [−s, s].
Lemma 12 Dense Binary Codewords. Fix a codebook φ such that φ(a) ∼ {±1} d for each a ∈ A. Consider a passive noise model in which ∆ S ∼ unif({−c, ..., c} d ); that is, each coordinate is shifted by an integer amount chosen uniformly at random between −c and c. Then, we can correctly decode with probability 1 − δ provided: Now consider an adversarial model in which we assume ∆ S 1 ≤ ωsd. Then we can decode correctly if: A proof is available in the Appendix. We next consider the case of Section 3.1.5 in which the codewords are sparse and binary and the bundling operator is the element-wise maximum. We here assume thatφ(S) = φ(S) + ∆ S is truncated so that each coordinate is either 0 or +1.
Lemma 13 Sparse Binary Codewords. Fix a codebook φ such that φ(a) ∈ {0, 1} d , and assume some fraction p ≪ 1/2 of coordinates are non-zero for each a ∈ A. Consider a passive noise model in which: Then we can decode correctly with probability 1 − δ provided: Now consider an adversarial model in which ∆ S 1 ≤ ωd. Then we can decode correctly if ω < p( 1 2 − sµ). Proof Consider first the passive noise model. Fix some φ(a). Then: Treating φ(a) as a fixed vector with dp non-zero entries, the sum is concentrated in the range dp(θ ± ǫ), and so ρ ≤ dp(θ + ǫ) with high probability. By Chernoff/Hoeffding and the union-bound, with probability 1 − δ: The result is obtained by noting that L = √ pd and applying Theorem 10. For the adversarial case, the result is obtained by again observing that | φ(a), ∆ S | ≤ φ(a) ∞ ∆ S 1 ≤ ωd for any a ∈ A and applying Theorem 10.

Encoding Structures
We are often interested in representing more complex data types, such as objects with multiple attributes or "features." In general, we suppose that we observe a set of features F whose values are assumed to lie in some set A. Let ψ : F → H be an embedding of features, and φ : A → H be an embedding of values. We associate a feature with its value through use of the binding operator ⊗ : H × H → H that creates an embedding for a (feature,value) pair. For a feature f ∈ F taking on a value a ∈ A, its embedding is constructed as ψ consists of n such pairs. For simplicity, we assume each x possesses all attributes, although our analysis also applies to the case that x possesses only some subset of attributes. The entire embedding for x is constructed as (Plate, 2003): As with sets we would typically like φ(x) to be decodable in the sense that we can recover the value associated with a particular feature, and comparable in the sense that φ(x), φ(x ′ ) is reflective of a reasonable notion of similarity between x and x ′ . From a formal perspective, we require the binding operator to satisfy several properties. First, binding should be associative and commutative. That is, for all a, b, c ∈ H, (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c), and a ⊗ b = b ⊗ a. Second, there should exist an identity element I ∈ H such that I ⊗ a = a for all a ∈ H. Third, for all a ∈ H, there should exist some a −1 ∈ H such that a ⊗ a −1 = I. These properties are equivalent to stipulating that H be an abelian group under ⊗. Furthermore, binding should distribute over bundling. That is, for any a, b, c ∈ H, it should be the case that a ⊗ (b + c) = a ⊗ b + a ⊗ c. We here also require that the lengths of bound pairs are bounded, that is to say: max f ∈F ,a∈A ψ(f ) ⊗ φ(a) 2 ≤ M .
A natural choice of embedding satisfying these properties is to sample ψ(f ) randomly from {±1} d and choose ⊗ to be the element-wise product. In this case ψ(f ) is its own inverse, that is ψ(f ) ⊗ ψ(f ) = I, and binding preserves lengths of codewords. We focus on this case here as it is intuitive, but our analysis generalizes in a straightforward way to any particular implementation satisfying the properties listed above. One can see the bound pairs satisfy various incoherence properties with high probability. For instance, we may declare the binding to be µ-incoherent if: where L = min a∈A φ(a) 2 . We can extend Theorem 5 to see this property is satisfied with high probability: Theorem 14 Fix d, n, m ∈ Z + and µ ∈ R + . Let φ be centered and σ-sub-Gaussian, ⊗ be the element-wise product, and ψ(f ) ∼ {±1} d . Then: where L = min a∈A φ(a) 2 and κ is as defined in Theorem 5.
The proof is similar to Theorem 5 and is available in the Appendix. This result is appealing because it means that the incoherence scales only logarithmically with m × n which may be large in practice. As a corollary to the previous theorem, we also obtain the following useful incoherence property: where ψ −1 (f ) is the inverse of ψ(f ) with respect to ⊗. This notion of incoherence is useful for decoding representations. Along similar lines: We note that the previous statement refers to symbols associated with different attributes and thus does not require any particular incoherence assumption on the φ(a).

Decoding Structures
This representation can be decoded to recover the value associated with a particular feature.
To recover the value of the i-th feature, we use the following rule: where ψ −1 (f ) denotes the group inverse of ψ(f ). Since the binding operator is assumed to distribute over bundling, the dot-product above expands to: where the incoherence can be bounded as as in Equation 3. Thus µ < 1/(2n) is a sufficient condition for decodability.

Comparing Structures
As with sets, we may wish to compare two structures without decoding them. As one would expect given Theorem 9, this is can be achieved by computing the dot-product between their encodings: Theorem 15 Let x and x ′ be two structures drawn from a common alphabet F ×A. Denote their encodings using Equation 2 by φ(x) and φ(x ′ ). Then, if binding is µ-incoherent: , that is, the features on which x and x ′ agree.
Proof Expanding: A term in the first sum is L 2 if x i = x ′ i and bounded in ±L 2 µ otherwise. So the expression above is bounded as: ≤ L 2 |x ∩ x ′ | + L 2 n 2 µ and the other direction of the inequality is analogous.
As a practical example, in bioinformatics it is common to search for regions of high similarity between a "reference" and "query" genome. Work in  and (Kim et al., 2020) explored the use HD computing to accelerate this process by encoding short segments of DNA and estimating similarity on the HD representations.

Encoding Sequences
Sequences are an important form of structured data. In this case, the feature set is simply the list of positions {1, 2, 3, ...} in the sequence. In practical applications, we are often interested in streams of data which arrive continuously over time. Typically, real-world processes do not exhibit infinite memory and we only need to store the n ≥ 1 most recent observations at any time. In the streaming setting, we would like to avoid needing to fully re-encode all n data points each time we receive a new sample, as would be the case using the method described above. This motivates the use of shift based encoding schemes (Kanerva, 2009;Kim et al., 2018). Let ρ (i) (z) denote a cyclic left-shift of the elements of z by i coordinates, and ρ (−i) (z) denote a cyclic right-shift by i coordinates. In other words: ρ (1) ((z 1 , z 2 , . . . , z d−1 , z d )) = (z 2 , z 3 , . . . , z d , z 1 ). In shift-based encoding a sequence x = (x 1 , ..., x n ) is represented as: where we take ⊕ to be the element wise sum. Now suppose we receive symbol n + 1 and wish to append it to φ(x) while removing φ(x 1 ). Then we may apply the rule: where we can additionally note that ρ is a special type of permutation and that permutations distribute over sums. However, in order to decode correctly, each φ(a) must satisfy an incoherence condition with the ρ (j) (φ(a ′ )). We can again use the randomly generated nature of the codewords to argue this is the case; however, we must here impose the additional restriction that the φ(a) be bounded, and accordingly restrict attention to the case φ(a) ∼ {±1} d .
Several other related methods for encoding sequential information have been proposed in the literature (Plate, 2003;Gallant & Okaywe, 2013). For an extensive discussion of these approaches as well as an interesting discussion involving sequences of infinite length, the reader is referred to (Frady et al., 2018).

Discussion and Comparison with Prior Work
We conclude our treatment of encoding and decoding discrete data with some brief discussion of our approach and its relation to antecedents in the literature. A key question addressed here and by several pieces of prior work is to bound the magnitude of crosstalk noise in terms of the encoding dimension (d), the number of items to encode (s) and the alphabet size (m). Early analysis in (Plate, 2003;Gallant & Okaywe, 2013;Kleyko et al., 2018) recovers the same asymptotic relationship as we do, but only under specific assumptions about the method used to generate the codewords and particular instantiations of the bundling and binding operators. Work in (Frady et al., 2018) provides a significantly more general treatment which, like ours, aims to abstract away from the particular choice of distribution from which codewords are sampled and from the particular implementation of bundling and binding operator. Their approach assumes the codewords are generated by sampling each component i.i.d. from some distribution and uses the central limit theorem (CLT) to justify modeling the crosstalk noise by a Gaussian distribution. Error bounds in the non-asymptotic setting are then obtained by applying a Chernoff style bound to the resulting Gaussian distribution. This approach again recovers the same asymptotic relationship between d, s and m as us, but does not generally yield formal bounds in the non-asymptotic setting. Our approach based on sub-Gaussianity formalizes this analysis in the non-asymptotic setting. Like us, (Frady et al., 2018) also considers the effect of noise on the HD representations, but their treatment is limited to additive white noise, whereas we address both arbitrary additive passive noise and adversarial noise.
In summary, our formalism using the notion of incoherence allows us to decouple the analysis of decoding and noise-robustness from any particular method for generating codewords and readily yields rigorous bounds in the non-asymptotic setting. Our approach is applicable to a large swath of HD computing and enables us to offer more general conditions under which thresholding based decoding schemes will succeed and of the effect of noise than is available in prior work.

Encoding Euclidean Data
One option for encoding Euclidean vectors is to treat them as a special case of the "structured data" considered in the preceding section. As before, we think of our data as a collection of (feature,value) pairs with the important caveat that x i ∈ R n . This case is more complex because the feature values may now be continuous, and because the data possesses geometric structure which is typically relevant for downstream tasks and must be preserved by encoding. We here analyze two of the most widely used methods for encoding Euclidean data and discuss general properties of structure preserving embeddings in the context of HD computing.

Position-ID Encoding
A widely-used method in practice is to quantize the raw signal to a suitably low precision and then apply the structure encoding method discussed in the previous section (Rachkovskiy et al., 2005a(Rachkovskiy et al., , 2005bKleyko et al., 2018;Rahimi et al., 2018).
In this approach, we first quantize the support of each feature f ∈ F into some set of m bins with centroids a 1 < · · · < a m and assign each bin a codeword φ(a) ∈ H. However, instead of requiring the codewords to be incoherent, we now require the correlation between codewords to reflect the distance between corresponding quantizer bins. In other words φ(a), φ(a ′ ) should be monotonically decreasing in |a − a ′ |.
A simple method can be used to generate monotonic codebooks when the codewords are randomly sampled from {±1} d (Rachkovskiy et al., 2005a;Widdows & Cohen, 2015).
Fixing some feature f , the codeword for the minimal quantizer bin, φ(a 1 ), is generated by sampling randomly from {±1} d . To generate the codeword for the second bin, we simply flip some set of ⌈b⌉ bits in φ(a 1 ), where: The codeword for the third bin is generated analogously from the second, where we assume the bits to be flipped are sampled such that a bit is flipped at most once. Thus the codewords for the minimal and maximal bins are orthogonal and the correlation between codewords for intermediate bins is monotonically decreasing in the distance between their corresponding bin centroids.
In practice, it seems to be typical to use a single codebook for all features and for the quantizer to be a set of evenly spaced bins over the support of the data. While simple, this approach is likely to have sub-optimal rate when the features are on different scales or are far from the uniform distribution. Encoding then proceeds as follows: where, as before ψ ∈ {±1} d is a vector which encodes the index i of a feature value x i as in the previous section on encoding sequences; hence the name "position-ID" encoding. There are several variations on this theme which are compared empirically in .
This general encoding method was analyzed by (Rachkovskiy et al., 2005b), in the specific case of sparse and binary codewords, who show it preserves the L1 distance between points in expectation but do not provide distortion bounds. We here provide such bounds using our formalism of matrix incoherence. We assume that the underlying quantization of the points is sufficiently fine that it is a low-order term that can be ignored.
Theorem 17 Let x and x ′ be points in [0, 1] n with encodings φ(x) and φ(x ′ ) generated using the rule described above. Assume that φ satisfies φ(a), φ(a ′ ) = d(1 − |a − a ′ |) for all a, a ′ ∈ A, and let ψ ∼ {±1} d . Then, for all x, x ′ : The proof is similar to Theorem 15 and is available in the Appendix. The practical implication of the previous theorem is that the position-ID encoding method preserves the L1 distance between points up to an additive distortion which can be bounded by the incoherence of the codebook. Per Equation 4, µ = O( ln(mn)/d). Therefore, to ensure that 1 the previous result implies we should choose d = O( n 4 ǫ 2 ln(nm)). This can be relaxed to a quadratic dependence on n in exchange for a weaker pointwise bound, but in either case means the encoding method may be problematic when the dimension of the underlying data is high.
Noting that ||φ(x)|| 2 2 ∈ nd ± n 2 dµ, we can see that the encodings of each point are roughly of equal norm and lie in a ball of radius at most n √ dµ, where the exact position depends on the instantiation of the codebook. Thus, we can loosely interpret the encoding procedure as mapping the data into a thin shell around the surface of a high dimensional sphere.

Random Projection Encoding
Another popular family of encoding methods embeds the data into H under some random linear map followed by a quantization (Rachkovskij, 2015;Imani et al., 2019c). More formally, for some x ∈ R n , these embeddings take the form: where Φ ∈ R d×n is a matrix whose rows are sampled uniformly at random from the surface of the n-dimensional unit sphere, and g is a quantizer -typically the sign function -restricting the embedding to H. The embedding matrix Φ may also be quantized to lower precision. This encoding method has also been studied in the context of kernel approximation where it is used to approximate the angular kernel (Choromanski et al., 2017), and to construct low-distortion binary embeddings (Jacques et al., 2013;Plan & Vershynin, 2014). While the following result is well known, we here show this encoding method preserves angular distance up to an additive distortion as this fact is important for subsequent analysis.
Theorem 18 Let S n−1 ⊂ R n denote the n-dimensional unit sphere. Let Φ ∈ R d×n be a matrix whose rows are sampled uniformly at random from S n−1 . Let X be a set of points supported on S n−1 . Denote the embedding of a point by φ(x) = sign(Φx). Then, for any x, x ′ ∈ X , with high probability: where d ham (a, b) is the Hamming distance between a and b, defined to be the number of coordinates on which a and b differ, and θ = 1 π cos −1 ( x, x ′ ) ∈ [0, 1] is proportional to the angle between x and x ′ .
Proof Let Φ (i) denote the ith row of the matrix Φ. Then, the ith coordinate in the embedding of x can be written as sign( Φ (i) , x ). The probability that the embeddings differ on their ith coordinate, that is ( Φ (i) , x )( Φ (i) , x ′ ) < 0, is exactly ∠(x, x ′ )/π: the angle (in radians) between x and x ′ divided by π.
Noting that φ(x), φ(x ′ ) = d−2d ham (φ(x), φ(x ′ )), we obtain the following simple corollary: Corollary 19 Let φ and θ be as defined in Theorem 18. Then, with high probability: To obtain a more explicit relationship with the dot product, we can use the first-order approximation cos −1 (x) ≈ (π/2) − x, to obtain θ ≈ 1 2 − 1 π x, x ′ , from which we obtain: We emphasize that, in comparison to the position-ID method, the distortion in this case does not depend on the dimension of the underlying data which means this method may be preferable when the data dimension is large.

Connection with Kernel Approximation
A natural question is whether the encoding procedure described above, which preserves dotproducts, can be generalized to capture more diverse notions of similarity? We can answer in the affirmative by noting that the random projection encoding method is closely related to the notion of random Fourier features which have been widely used for kernel approximation (Rahimi & Recht, 2008). The basic idea is to construct an embedding φ : where k is a shift-invariant kernel. The construction exploits the fact that the Fourier transform of a shift-invariant kernel k is a probability measure: a well known result from harmonic analysis known as Bochner's Theorem (Rudin, 1962). The embedding itself is given by φ(x) = 1 √ d cos (Φx + b), where the rows of Φ are sampled from the distribution induced by k and the coordinates of b are sampled uniformly at random from [0, 2π].
Subsequent work in (Raginsky & Lazebnik, 2009) gave a simple scheme for quantizing the embeddings produced from random Fourier features to binary precision. Their construction yields an embedding ψ : R n → {0, 1} d such that: where f 1 , f 2 : R → R are independent of the choice of kernel, and ∆ is a distortion term. The embedding itself is constructed by applying a quantizer Q t (x) = sign(x + t) coordinate wise over the embeddings constructed from random Fourier features. In other words ψ( 1], and φ(x) is a random Fourier feature. This connection is highly appealing for HD computing. The quantized random Fourier feature scheme presents a simple recipe for constructing encoding methods meeting the desiderata of HD computing while preserving a rich variety of structure in data. For instance, shift-invariant kernels preserving the L1 and L2 distance-among many others-can be approximated using the method discussed above. Furthermore, this observation provides a natural point of contact between HD computing and the vast literature on kernel methods which has produced a wealth of algorithmic and theoretical insights.

Consequences of Distance Preservation
The encoding methods discussed above are both appealing because they preserve reasonable notions of distance between points in the original data. Distance preservation is a sufficient condition to establish other desirable properties of encodings, namely preservation of neighborhood/cluster structure, robustness to various forms of noise, and in some cases, preservation of linear separability. We address the first two items here and defer the latter for our discussion of learning on HD representations. We formalize our notion of distance preservation as follows: Definition 20 Distance-Preserving Embedding: Let δ X be a distance function on X ⊂ R n and δ H be a distance function on H. We say φ preserves δ X under δ H if, there exist functions α, β : Z + → R such that β(d)/α(d) → 0 as d → ∞, and: for all x, x ′ ∈ X .
We typically wish the distance function δ H on H to be simple to compute. In practice, it is often taken to be the Euclidean, Hamming, or angular distance. The position-ID method preserves the L1 distance with δ H the squared Euclidean distance, α(d) = 2d, and β(d) ≤ n 2 µd; recall that in the constructions above, µ scales inversely with d and thus β(d)/α(d) → 0. The signed random-projection method preserves the angular distance with , and δ H the Hamming, angular, or Euclidean distance.

Preservation of Cluster Structure
In general, there is no universally applicable definition of cluster structure. Indeed, numerous algorithms have been proposed in the literature to target various reasonable notions of what constitutes a "cluster" in the data. Preservation of a distance function accords naturally with K-means like algorithms which, given a set of data X ⊂ R n compute a set of centroids C = {c i } k i=1 , and define associated clusters as the Voronoi cells associated with each centroid. We here adopt this notion and state that cluster structure C is preserved if, for any x ∈ X : argmin In other words, that the set of points bound to a particular cluster centroid does not change under the encoding. We can restate the above as requiring that, for some point x bound to a cluster centroid c, it is the case that: for any c ′ ∈ C \ {c}. From Definition 20 we have: for any x ∈ X and c, c ′ ∈ C. Rearranging the expressions above we can see the desired property will be satisfied if: where c(x) = argmin c∈C δ X (x, c) denotes the center in C closest to x. A sufficient condition for the existence of some d satisfying this property is that α(d) is monotone increasing and that α(d) is faster growing than β(d). This condition is satisfied for both the random projection and position-ID encoding methods.

Noise Robustness
It is also of interest to consider robustness to noise in the context of encoding Euclidean data. Suppose we have a set of points, X , in R n , and a distance function of interest δ X (·, ·) which is preservedà la Definition 20. Given an arbitrary point x ∈ X we consider a noise model which corrupts φ(x) to φ(x) + ∆, where ∆ is some unspecified noise process. Along the lines of Section 3.2, we say ∆ is ρ-bounded if: Suppose we wish to ensure the encodings can distinguish between all points at a distance ≤ ǫ 1 from x and all points at a distance ≥ ǫ 2 . That is: for all x ′ ∈ X such that δ X (x, x ′ ) ≤ ǫ 1 and all x ′′ ∈ X such that δ X (x, x ′ ) ≥ ǫ 2 . We say that such an encoding is (ǫ 1 , ǫ 2 )-robust.
Theorem 21 Let δ X be a distance function on X ⊂ R n and suppose φ is an embedding preserving δ X under the squared Euclidean distance on H as described in Definition 20. Suppose ∆ is ρ-bounded noise. Then φ is (ǫ 1 , ǫ 2 ) robust if: Proof Fix a point x whose encoding is corrupted as φ(x) + ∆. Then for any x ′ , x ′′ ∈ X with δ X (x, x ′ ) ≤ ǫ 1 and δ X (x, x ′′ ) ≥ ǫ 2 , we have: As before, we may consider passive and adversarial examples.
Additive White Gaussian Noise. First consider the case that H = R d and ∆ ∼ N (0, σ 2 ∆ I d ); that is, each coordinate of ∆ has a Gaussian distribution with mean zero and variance σ 2 ∆ . Then, as before, we can note that φ(x), ∆ ∼ N (0, σ 2 ∆ φ(x) 2 2 ). Then, it is very likely (four standard deviations in the tail of the normal distribution) that ρ < 4Lσ ∆ , where L = max x∈X φ(x) 2 . So then, we have the desired robustness property if: Assuming that α(d) is faster growing in d than L and β(d), there will exist some encoding dimension for which we can tolerate any given level of noise. In the case of the random projection encoding scheme described above And so we can tolerate noise on the order of: For the position-ID encoding method, α(d) = O(d), L = O( √ nd) and β(d) = O(n 2 dµ), and so we can tolerate noise: Adversarial Noise. We now consider the case that H = {±1}, as in the random-projection encoding method, and ∆ is noise in which some fraction ω · d of coordinates in φ(x) are maliciously corrupted by an adversary. Since ∆ 1 ≤ ωd, we have, for any x ∈ X : So then we can tolerate ω on the order of: In the case of the random-projection encoding method this boils down to: meaning the total number of coordinates that can be corrupted is O(d(ǫ 2 − ǫ 1 )).
Robustness to Input Noise. A natural question is whether the HD representations also confer any robustness to noise in the input space X rather than the HD space H. In general, preservation of distance does not imply any particular robustness to input noise and the answer to this question depends on the particulars of the encoding method in question.
Since a general treatment is difficult to give, we will not pursue this matter in depth at present.

Learning on HD Data Representations
We now turn to the question of using HD representations in learning algorithms. Our goal is to clarify in what precise sense the HD encoding process can make learning easier. We study two ways in which this can happen: the encoding process can increase the separation between classes and/or can induce sparsity. Both of these characteristics can be exploited by neurally plausible algorithms to simplify learning. Throughout this discussion, we assume access to a set of , where x i lies in [0, 1] n and y i ∈ C is a categorical variable indicating the class label. In general, we are interested in the case that training examples arrive in a streaming, or online, fashion, although our conclusions apply to fixed and finite data as well.

Learning by Bundling
The simplest approach to learning with HD representations is to bundle together the training examples corresponding to each class into a set of exemplars-often referred to as "prototypes"-which are then used for classification Rahimi et al., 2018;Burrello et al., 2018). More formally, as described in Section 2, we construct the prototype c k for the k-th class as: and then assign a class label for some "query" point x q as: This approach bears a strong resemblance to naive Bayes and Fisher's linear discriminant, which are both classic simple statistical procedures for classification (Bishop, 2007). Like these methods, the bundling approach is appealing due to its simplicity. However, it also shares their weaknesses in that it may fail to separate data that is in fact linearly separable.

Learning Arbitrary Linear Separators
Linear separability is one of the most basic types of structure that can aid learning. The theory of linear models is well developed and several simple, neurally plausible, algorithms for learning linear separators are known, for instance, the Perceptron and Winnow (Rosenblatt, 1958;Littlestone, 1988). Thus, if our data is linearly separable in low-dimensional space we would like it to remain so after encoding, so that these methods can be applied. We now show formally that preservation of distance is sufficient, under some conditions, to preserve linear separability.
Theorem 22 Let X and X ′ be two disjoint, closed, and convex sets of points in R n . Let p ∈ X and q ∈ X ′ be the closest pair of points between the two sets. Suppose φ preserves L2 distance on X under the L2 distance on H in the sense of Definition 20. Then, the is positive for all x ∈ X and negative for all x ′ ∈ X ′ provided: Proof We first observe: We may then use Definition 20 to obtain: By a standard proof of the hyperplane separation theorem (e.g., Section 2.5.1 of (Boyd & Vandenberghe, 2014)), for any x ∈ X , and thus f (x) > 0 if the proof for x ∈ X ′ is analogous.
A natural question is whether a linear separator on the HD representation can capture a nonlinear decision boundary on the original data? The connection with kernel methods discussed in Section 5.2.1 presents one avenue for rigorously addressing this question. As noted there, the encoding function can sometimes be interpreted as approximating the feature map of a kernel, which in turn can be used to linearize learning problems in some settings (Shawe-Taylor et al., 2004). However, a thorough examination of this question is beyond the scope of the present work.

Learning Sparse Classifiers on Random Projection Encodings
The random projection encoding method can be seen to lead to representations that are sparse in the sense that a subset of just k ≪ d coordinates suffice for determining the class label. This setting accords naturally with the Winnow algorithm (Littlestone, 1988) which is known to make on the order of k log d mistakes when the target function class is a linear function of k ≤ d variables. This can offer substantially faster convergence than the Perceptron when the margin is small. Curiously, while the Perceptron algorithm is commonly used in the HD community, we are unaware of any work using Winnow for learning.
Theorem 23 Let X and X ′ be two sets of points supported on the n-dimensional unit sphere and separated by a unit-norm hyperplane w with margin γ = min x∈X | x, w |. Let Φ ∈ R d×n be a matrix whose rows are sampled from the uniform distribution over the n-dimensional unit-sphere. Define the encoding of a point x by φ(x) = Φx. With high probability, X and X ′ are linearly separable using just k coordinates in the encoded space, provided: To prove the theorem we first use the following simple Lemma: Lemma 24 Suppose there exists a row Φ (i) of the projection matrix such that Φ (i) , w > 1 − γ 2 /2. Then Φ (i) , x is positive for any x ∈ X and negative for any x ∈ X ′ .
Proof The constraint on the dot product of Φ (i) and w implies Φ (i) − w 2 = Φ (i) 2 + w 2 − 2 Φ (i) , w < γ 2 . Thus for any x ∈ X , A similar argument shows that Φ (i) , x is negative on X ′ .
Unfortunately, the probability of randomly sampling such a direction is tiny, on the order of γ n . However, we might instead hope to sample k vectors that are weakly correlated with w and exploit their cumulative effect on x. We say a vector u ∈ R n is ρ-correlated with w if u, w ≥ ρ. We are now in a position to prove the theorem.
Proof For w ∈ S n−1 and ρ ∈ (0, 1), let C = {u ∈ S n−1 : u, w ≥ ρ} denote the spherical cap of vectors ρ-correlated with w. Suppose we pick vectors u (1) , . . . , u (k) uniformly at random from C. Then, with probability at least 1/2: To see this, note that without loss of generality we may assume w = e 1 , the first standard basis vector of R n , and write any u ∈ R n as u = (u 1 , u R ): the first coordinate and the remaining n − 1 coordinates. Now, let N = j u (j) , w = j u (j) 1 ≥ kρ. Then: The last term has a symmetric distribution around zero over random samplings of the u (j) . Thus, with probability ≥ 1/2, it is ≤ 0, whereupon To ensure the quantity above is at least 1 − γ 2 /2, we must have: It now remains to compute the probability that a vector Φ (i) sampled uniformly from S n−1 lies in C, or equivalently, that Φ (i) 1 ≥ ρ. Noting that we may simulate a random direction on S n−1 by sampling z ∼ N (0, I n ) and normalizing, we obtain the reasonable approximation: Φ (i) 1 ∼ N (0, 1/n). Therefore, the probability that Φ (i) 1 ≥ ρ is on the order of e −nρ 2 /2 . So we need: In summary, the random projection method in tandem with the Winnow algorithm seems to be well suited to the HD setting, where sparsity can be exploited to simplify learning.

Conclusion
To conclude, we lay out several research directions related to HD computing we believe it would be of particular interest to further explore. There are several interesting open problems related to encoding. Our analysis established preservation of only the most basic forms of structure in data. Can encoding procedures satisfying the desiderata of HD computing be designed that capture other forms of structure? The quantized random Fourier feature construction discussed in Section 5 presents one such option, but is only applicable to structure that can be captured using a shift-invariant kernel on a Euclidean space. For instance, can we devise encoding methods that exploit low-dimensional manifold structure in the data or which are adaptive and can be learned from a particular data set? Several recent works have claimed, based on empirical evidence, that HD computing evinces one-shot learning (Burrello et al., 2018;Rahimi et al., 2018) in which a single labeled example is needed to learn a generalizable classifier (Thrun, 1996;Lake et al., 2011). However, this work has focused on settings in which specialized handcrafted features could be extracted, and it is not clear to us that existing encoding procedures would lead to one-shot classifiers absent such outside information. We would be interested to explore whether the HD representation makes one-shot learning easier in any broader sense. We expect this will necessitate the use of more sophisticated encoding procedures that can learn salient properties of a given domain. For this latter point we see dictionary learning (Olshausen & Field, 1996) as a promising avenue for developing adaptive encoding procedures. Dictionary learning is a well studied problem and can be solved using online and neurally plausible methods (Arora et al., 2015;Mairal et al., 2010) and would thus seem to be a promising avenue to address the limitations of existing encoding procedures without sacrificing the simplicity and neural plausibility of existing HD based methods.
A.3 Proof of Theorem 9 Proof Expanding the dot product between the two representations: The other direction is analogous.

Proof of Lemma 12
Proof Consider first the case of passive noise. Fix some a ∈ A. Noting that φ(a), ∆ S is the sum of d terms bounded in [−c, c], another application of Hoeffding's inequality and the union bound will show: P(∃ a s.t. | φ(a), ∆ S | ≥ ρ) ≤ 2m exp − ρ 2 2c 2 d .