Real-Valued Hyperdimensional Sequence Representations with Hadamard Product Binding and Shift Equivariance

Motivation

• HDC/VSA encodes sequences by binding each element vector to a position vector and superimposing the bound vectors.Explicit position vectors can preserve similarity or proximity between nearby positions.Source: §1 · p. 2

Fractional Power Encoding

• FPE generates position vectors whose similarity reflects positional distance and supports shifting an encoded sequence without recomputing all bindings.This makes temporal patterns detectable across different sequence positions.Source: §1 · p. 2

Problem

• Standard FPE is not directly compatible with real-valued Hadamard product binding because the required algebraic structure is unavailable in real-valued vector spaces.Efficient real-valued HDC/VSA models such as MAP use component-wise multiplication for binding.Source: §1 · p. 2

Contribution

• The paper investigates real-valued position encodings compatible with Hadamard binding while retaining FPE-like similarity structure and shift equivariance.The study introduces variants and evaluates their theoretical properties and empirical performance.Source: §1 · p. 2

Sequence encoding approaches

• Permutation-based encoding applies position-dependent transformations before superposition, whereas explicit role–filler encoding binds each element to an explicit position vector.The explicit formulation controls sequence properties through position-vector construction.Source: §2 · p. 3

Permutation limitations

• Random permutations encode order but make neighboring positions nearly orthogonal, motivating partial permutations and shift-equivariant alternatives.These extensions aim to produce more gradual similarity changes across nearby positions.Source: §2 · p. 3

FPE and RFF

• FPE constructs related position vectors whose similarity decreases with positional difference and induces a shift-invariant kernel.Its kernel interpretation connects it to RFF, which approximates shift-invariant kernels using sampled frequencies.Source: §2 · p. 3

Research gap

• Most FPE formulations target circular convolution or complex multiplication, while MAP uses real-valued Hadamard binding.Their compatibility and resulting similarity and shift-equivariance properties had not been systematically analyzed.Source: §2 · p. 3

Scope

• The paper focuses on multiplicative binding with explicit position vectors and excludes permutation-based and related n-gram encodings.Its objective is efficient realization of similarity-preserving, shift-equivariant encodings using Hadamard operations.Source: §2 · p. 4

Binding-based sequence encoding

• A sequence representation superimposes element vectors bound to explicit position vectors, with its properties determined largely by position-vector construction.The formulation uses positions t = 1, . . . ,T and vectors in R^D.Source: §3.1 · p. 4

Fractional Power Encoding

• FPE generates a family of related position vectors from a base vector through repeated binding operations, extending to continuous positional values.Hermitian symmetry yields real-valued vectors, while unit-magnitude complex components maintain constant norms.Source: §3.2 · pp. 4–5

Fourier-domain binding

• In HRR, binding uses circular convolution, equivalent to component-wise multiplication in the complex Fourier domain with FFT and IFFT.Fourier-domain components are complex phasors whose angular frequencies determine their evolution with position.Source: §3.2 · pp. 4–5

Similarity kernels

• The angular-frequency distribution determines the shift-invariant kernel approximated by normalized inner products between position vectors.Uniform, Gaussian, and sinc-based distributions produce sinc-type, Gaussian-like, and triangular-decrease kernels, respectively.Source: §3.3 · pp. 5–6

Shift equivariance

• FPE shift equivariance makes a positional shift correspond to a binding operation and allows shifted sequence representations without recomputing all element-position bindings.The similarity profile shifts while preserving the kernel shape.Source: §3.4 · p. 6

Compatibility

• The baseline problem is that FPE relies on circular convolution or complex multiplication, which is incompatible with efficient real-valued Hadamard binding.MAP is an example of a real-valued HDC/VSA model using Hadamard binding.Source: §4 · p. 6

Similarity preservation

• Position encodings should preserve shift-invariant similarity so nearby positions remain similar while distant positions remain distinguishable.This requirement is defined through dependence on positional difference.Source: §4 · p. 7

Stable norms

• Position-vector norms should remain exactly or approximately constant to avoid unstable sequence representations and distorted element contributions.The requirement concerns stability across positions t.Source: §4 · p. 7

Shift equivariance

• Shift equivariance requires an operator that directly transforms the encoded representation when positions are shifted.Hadamard binding with a shift vector does not automatically provide this behavior.Source: §4 · p. 7

Computational efficiency

• Direct position-vector construction and positional binding or shifting should ideally have O(D) complexity instead of FFT-based O(D log D) operations.The paper introduces real-valued variants satisfying the requirements to different degrees.Source: §4 · pp. 7–8

• Three variants are proposed: inverse-Fourier Variant A, Sinusoid RFF-based Variant B, and Cosine-only RFF-based Variant C.They differ in construction and whether an explicit shift operator exists.Source: §5 · p. 8

Variant A

• Variant A produces real-valued vectors compatible with Hadamard binding and preserves FPE similarity kernels, but lacks a real-valued algebraic shift operator.It also requires O(D log D) operations because it uses complex exponentiation and an inverse Fourier transform.Source: §5.1 · p. 9

Variant B: Sinusoid

• Variant B uses fully real-valued Sinusoid features, supports direct Hadamard binding, and provides exact shift equivariance through an explicit operator.Position vectors are computed directly with trigonometric functions in O(D), using 2D-dimensional vectors.Source: §5.2 · pp. 10, 12

Variant C: Cosine-only

• Variant C uses only cosine features, yielding a compact O(D) real-valued encoding that approximates shift-invariant kernels but lacks exact shift equivariance.Because sine components are absent, phase shifts cannot be reconstructed within the stored representation space.Source: §5.3 · p. 13
• For equal numbers of sampled frequencies, Cosine-only uses D components while Sinusoid uses 2D, giving Sinusoid lower kernel-approximation variance at doubled dimensionality.Cosine-only norms are preserved in expectation but fluctuate for finite D.Source: §5.3 · pp. 13–14

Variant comparison

• Overall, Variant B preserves the kernel structure and enables an exact real-valued shift operator, whereas Variant C trades that capability for compactness and efficiency.Variant A remains primarily a reference formulation because it lacks an algebraic shift operator after real-valued transformation.Source: §5.1 · p. 9, §5.4 · p. 14

• The representations compare circular convolution and real-valued Hadamard product binding across FPE variants.Source: of FPE · p. 15
• The exponential representation is preserved through a constant offset in the exponent or approximated through Random Fourier Features.Source: of FPE · p. 15
• Standard inverse-Fourier processing uses complex phasors, whereas Sinusoidal and Cosine embeddings provide real-valued alternatives.Source: of FPE · p. 15
• The standard formulation has constant norm from unit-magnitude complex phasors, while the alternative embeddings differ in how norm is maintained.Source: of FPE · p. 15
• Inverse FFT and circular convolution require O(D log D), while purely real operations and Hadamard binding require O(D).The comparison identifies a linear-complexity path for real-valued operations.Source: of FPE · p. 15
• Table 2 reports datasets exceeding ±5% relative changes in accuracy between ROCKET and corresponding HDC-based approaches.The table includes dataset counts, percentage metrics, and relative changes in accuracy and error.Source: Table 2 · p. 16

Experimental setup

• The evaluation tests proposed real-valued positional variants for efficient Hadamard-binding sequence representations in time-series classification.Source: §6 · p. 16, §6.1 · p. 16
• The comparison includes Standard FPE Variant A, Sinusoid Variant B, and Cosine Variant C.Source: §6.1 · p. 16
• Angular frequencies are sampled from U(−π,π) for the sinc kernel, β is selected by cross-validation, and results average 30 random-seed repetitions.Source: §6.1 · pp. 16–17

Classification results

• MiniROCKET HDC models improve mean accuracy by approximately 1.4%, with maximum gains of 14.8% and mean relative error reduction up to −8%.Source: §6.1 · p. 17
• MultiROCKET-HYDRA shows about 1.1% mean relative accuracy improvement, maximum gains up to 23.6%, and relative error reductions up to 62%.Source: §6.1 · p. 17
• Across datasets, the variants have comparable overall performance, while Variant B combines competitive classification with shift equivariance.Source: §6.1 · p. 17

Component distributions

• Figure 3 compares component-value histograms for Standard FPE, Sinusoid, and Cosine encodings under the sinc kernel.Source: §6.2 · p. 17, Figure 3 · p. 18
• Hadamard multiplication suppresses bound components near zero and approximately preserves magnitudes near −1 or 1, but no pronounced classification effect was observed.Source: §6.2 · p. 18

• The encoded sequence is formed by binding each feature vector with its position vector and superimposing the resulting vectors.Source: §2 · p. 18
• The experiment compares explicit re-encoding after a shift with applying the Sinusoid shift operator to the existing representation.Source: §2 · p. 18, Figure 4 · p. 19
• A synthetic signal with one temporal peak is compared with the same signal shifted by 10 time steps.Source: Figure 4 · p. 19
• Cosine similarity reaches 1.0 at the true shift s = 10, showing identity between the two representations at that shift.Source: Figure 5 · p. 19, §2 · p. 19
• The Sinusoid representation applies temporal shifts without recomputing the full sequence representation.Source: §2 · p. 19
• The proposed shift operator runs in real-valued space with O(D) complexity, versus O(D log D) for FFT-based circular convolution.Source: §2 · p. 19

Variant trade-offs

• Variant A preserves the standard FPE similarity kernel but lacks shift equivariance under Hadamard binding.Temporal shifts therefore require recomputing the sequence representation, and small-magnitude components can attenuate bound sequence-element components.Source: §7 · p. 20
• Variant B uses Random Fourier Features to preserve the similarity kernel and provide an explicit real-valued shift operator.The encoded representation can be shifted algebraically without recomputing the sequence representation.Source: §7 · p. 20
• Variant C removes sine components, retaining approximate shift-invariant similarity while sacrificing an algebraic shift-equivariant operator.Its simpler real-valued implementation may suit settings where computational simplicity outweighs shift equivariance.Source: §7 · p. 20
• Few near-zero values make the Sinusoid-related vectors better suited to Hadamard binding because they cause less component attenuation.This property is shared by the Sinusoid and Cosine-only representations.Source: §7 · p. 20

Relation to positional encoding

• The Sinusoid formulation resembles Rotary Positional Encoding through paired sine-cosine phase representations, but serves binding-based HDC/VSA rather than attention-based neural networks.Temporal shifts correspond to phase shifts in the representation.Source: §7 · pp. 20–21

Limitations and applications

• Exact shift equivariance requires paired cosine and sine components, increasing positional dimensionality and binding each sequence-element component to both phases.This is an explicit limitation of the Sinusoid variant.Source: §7 · p. 21
• Evaluation focused primarily on time-series classification with HDC-MiniROCKET, leaving broader validation on additional sequence-processing tasks for future work.The paper specifically identifies temporal-shift search and sequence alignment as relevant untested applications.Source: §7 · p. 21
• In streaming scenarios, shift equivariance can update an existing temporal representation directly instead of recomputing the full sequence encoding.This potentially improves processing efficiency for continuously arriving data.Source: §7 · p. 21

Contribution

• Three real-valued variants integrate similarity-preserving position encoding with Hadamard binding and reduce position-binding complexity from O(D log D) to O(D).The designs are motivated by Fractional Power Encoding and Random Fourier Features for Multiply-Add-Permute HDC/VSA.Source: §8 · p. 21

Conclusion

• Sinusoid provides an explicit real-valued shift operator for algebraically transforming encoded sequence representations.This preserves shift equivariance within the representation space.Source: §8 · p. 21
• Cosine-only offers a simpler alternative when computational simplicity is more important than shift equivariance.Removing sine components simplifies the representation but removes algebraic shifting.Source: §8 · p. 21

Empirical outcome

• Performance comparable to, and in some cases better than, standard FPE was achieved by Sinusoid on a large collection of time-series classification tasks.The result was obtained while retaining efficient O(D) real-valued implementation.Source: §8 · p. 22

Conclusion

• Similarity-preserving position encodings can be integrated with Hadamard binding, with Sinusoid retaining shift equivariance while avoiding Fourier-domain computations.The paper presents this as a promising alternative for efficient real-valued sequence representation.Source: §8 · p. 22