PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kenny Schlegel, Dmitri A. Rachkovskij, Denis Kleyko, Amy Loutfi, Stefan Streif, Evgeny Osipov

arXiv:2608.28334v1cs.AI

TL;DR

The paper addresses FPE’s limited compatibility with real-valued Hadamard binding in HDC/VSA sequence representations. It develops three real-valued variants motivated by RFF; the Sinusoid variant preserves similarity structure, supports exact algebraic shifts, and achieves comparable time-series classification performance with O(D) implementation.

  • Problem

    Standard FPE relies on circular convolution or complex-domain multiplication, limiting direct compatibility with real-valued Hadamard product binding.

  • Method

    The paper introduces three real-valued position-encoding variants for Hadamard binding: an inverse-Fourier-transform baseline, Sinusoid, and Cosine-only representations.

  • Results

    The Sinusoid variant achieves performance comparable to, and sometimes better than, the standard formulation while enabling efficient O(D) real-valued implementation.

  • Takeaways & Limitations

    The Sinusoid variant preserves shift equivariance while avoiding Fourier-domain computations, making it a promising efficient alternative for real-valued sequence representation.

  • Takeaways & Limitations

    The Cosine-only representation cannot construct a shift-equivariant operator because it omits the sine components needed to reconstruct phase shifts.

Abstract

from arXiv · show

Encoding temporal order is a fundamental requirement for sequence representations in Hyperdimensional Computing. Fractional Power Encoding provides similarity-preserving position vectors whose inner products approximate shift-invariant kernels, and it supports shift-equivariant transformations of encoded sequence representations. However, standard formulations of Fractional Power Encoding are primarily designed for binding operations such as circular convolution or complex-valued multiplication, which limits their compatibility with Hadamard product binding of real-valued vectors. This paper develops real-valued position encodings motivated by Random Fourier Features, aiming to retain the desirable properties of Fractional Power Encoding while supporting Hadamard-based operations. We propose three real-valued position-encoding variants: a real-valued baseline based on the inverse Fourier transform, and Sinusoid and Cosine-only representations derived from Random Fourier Features. Among them, the Sinusoid variant provides an explicit algebraic shift operator, allowing temporal shifts to be applied directly to the vector-encoded sequence representation without re-encoding the shifted sequence. Experiments on time-series classification datasets show that the proposed real-valued representations achieve performance comparable to standard Fractional Power Encoding while enabling computationally efficient Hadamard product binding. The Sinusoid variant offers the most favorable trade-off, combining efficient real-valued implementation with exact shift-equivariant transformations.

1 Introduction

The paper studies explicit position vectors for preserving temporal structure in HDC/VSA sequences, addressing FPE’s incompatibility with real-valued Hadamard binding. It investigates real-valued encodings that retain similarity structure 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.
  • 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.
  • 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.
  • 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.

2 Related Work

Related work contrasts permutation-based and explicit position-vector sequence encodings, then situates FPE and RFF as similarity-preserving approaches. The paper focuses on their compatibility with real-valued Hadamard binding.

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

3 Preliminaries

The preliminaries define binding-based sequence representations and FPE position vectors, whose frequency distributions determine shift-invariant similarity kernels. FPE also supports shifts through binding in the complex domain.

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

4 Design Requirements

The design requirements target real-valued Hadamard binding while preserving similarity, stable norms, shift equivariance, and computational efficiency. The paper introduces variants that satisfy these requirements to different degrees.

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

5 Methods: Hadamard-Compatible Positional Representations

The paper introduces three real-valued positional encodings compatible with Hadamard binding: an inverse-Fourier baseline, a Sinusoid representation with exact shifts, and a compact Cosine-only alternative with approximate kernels.

  • 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.
  • 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.
  • 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.
  • 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.
  • Variant C: Cosine-only: 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.
  • 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.

of FPE

The compared representations differ in binding compatibility, computational cost, and preservation of the exponential structure underlying FPE. Real-valued Hadamard binding is distinguished from circular-convolution and Fourier-based alternatives.

  • The representations compare circular convolution and real-valued Hadamard product binding across FPE variants.
  • The exponential representation is preserved through a constant offset in the exponent or approximated through Random Fourier Features.
  • Standard inverse-Fourier processing uses complex phasors, whereas Sinusoidal and Cosine embeddings provide real-valued alternatives.
  • The standard formulation has constant norm from unit-magnitude complex phasors, while the alternative embeddings differ in how norm is maintained.
  • 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.
  • 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.

6 Experimental evaluation

The experiments evaluate three real-valued position encodings in HDC time-series classifiers, comparing classification behavior and component distributions. Results show comparable performance and limited observed impact from distributional differences.

  • Experimental setup: The evaluation tests proposed real-valued positional variants for efficient Hadamard-binding sequence representations in time-series classification.
  • Experimental setup: The comparison includes Standard FPE Variant A, Sinusoid Variant B, and Cosine Variant C.
  • Experimental setup: Angular frequencies are sampled from U(−π,π) for the sinc kernel, β is selected by cross-validation, and results average 30 random-seed repetitions.
  • 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%.
  • Classification results: MultiROCKET-HYDRA shows about 1.1% mean relative accuracy improvement, maximum gains up to 23.6%, and relative error reductions up to 62%.
  • Classification results: Across datasets, the variants have comparable overall performance, while Variant B combines competitive classification with shift equivariance.
  • Component distributions: Figure 3 compares component-value histograms for Standard FPE, Sinusoid, and Cosine encodings under the sinc kernel.
  • Component distributions: Hadamard multiplication suppresses bound components near zero and approximately preserves magnitudes near −1 or 1, but no pronounced classification effect was observed.

2. Equivariant shift: the shift operator is applied directly to the sequence representation

The Sinusoid shift operator transforms an encoded sequence directly in embedding space. Its result matches explicit re-encoding at the true shift, supporting efficient shift-equivariant processing.

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

7 Discussion

The proposed variants trade representational properties against computational efficiency. Sinusoid preserves exact shift equivariance with real-valued Hadamard binding, while Cosine-only simplifies implementation but loses algebraic shifting.

  • 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.
  • Variant trade-offs: 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.
  • Variant trade-offs: 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.
  • Variant trade-offs: 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.
  • 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.
  • 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.
  • Limitations and applications: 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.
  • Limitations and applications: 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.

8 Conclusion

The paper introduces real-valued position encodings that integrate similarity-preserving sequence representations with Hadamard product binding. Across time-series classification tasks, Sinusoid matches or sometimes exceeds standard FPE while retaining efficient O(D) implementation and shift equivariance.

  • 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.
  • Conclusion: Sinusoid provides an explicit real-valued shift operator for algebraically transforming encoded sequence representations.This preserves shift equivariance within the representation space.
  • Conclusion: 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.
  • 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.
  • 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.
Loading 2608.28334v1…