Hyperdimensional Computing operates in vector spaces with the following properties:
- High Dimensionality: Vectors in ℝᵈ or {0,1}ᵈ where d ∈ [1000, 10000]
- Distance Preservation: Operations preserve meaningful distance relationships
- Concentration of Measure: Most random vectors are nearly equidistant
The binding operation creates a new hypervector that is dissimilar to both operands:
Binary Binding (XOR):
c = a ⊗ b
cᵢ = aᵢ ⊕ bᵢ (XOR operation)
Bipolar Binding (Multiplication):
c = a ⊗ b
cᵢ = aᵢ × bᵢ where aᵢ, bᵢ ∈ {-1, +1}
Properties:
- Self-inverse: a ⊗ b ⊗ b = a
- Commutative: a ⊗ b = b ⊗ a
- Associative: (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
- Distributes over bundling: a ⊗ (b + c) ≈ (a ⊗ b) + (a ⊗ c)
The bundling operation creates a hypervector similar to all inputs:
Binary Bundling (Majority):
s = a + b + c
sᵢ = majority(aᵢ, bᵢ, cᵢ)
Bipolar Bundling (Normalized Sum):
s = a + b + c
sᵢ = sign(aᵢ + bᵢ + cᵢ)
Properties:
- Commutative: a + b = b + a
- Associative: (a + b) + c = a + (b + c)
- Similar to all inputs: δ(s, a) < δ(random, a)
Permutation creates a dissimilar vector while preserving structure:
p = ρ(a)
pᵢ = a_{(i+k) mod d} (cyclic shift by k)
Properties:
- Invertible: ρ⁻¹(ρ(a)) = a
- Preserves distances: δ(a, b) = δ(ρ(a), ρ(b))
- Non-commutative with binding: ρ(a ⊗ b) ≠ ρ(a) ⊗ ρ(b)
δₕ(a, b) = Σᵢ |aᵢ - bᵢ| / d
cos(a, b) = (a · b) / (||a|| ||b||)
For bipolar vectors with ||a|| = ||b|| = √d:
cos(a, b) = (a · b) / d
The number of items that can be stored with reliable retrieval:
Binary Vectors:
C ≈ 0.15 × d / log₂(d)
Bipolar Vectors:
C ≈ 0.20 × d / log₂(d)
Where d is the dimension and retrieval accuracy > 99%.
Probability of correct retrieval with noise level η:
P(correct) = Φ((1 - 2η)√d / 2)
Where Φ is the cumulative normal distribution function.
For scalar values v ∈ [vₘᵢₙ, vₘₐₓ] with L levels:
level(v) = ⌊L × (v - vₘᵢₙ) / (vₘₐₓ - vₘᵢₙ)⌋
hv(v) = H[level(v)]
Where H is a codebook of L orthogonal hypervectors.
hv(v)ᵢ = {
1 if i < t × d
0 otherwise
}
Where t = (v - vₘᵢₙ) / (vₘₐₓ - vₘᵢₙ) is the normalized value.
N-gram encoding:
hv(s) = Σᵢ bind(hv(sᵢ), ρⁱ(hv(sᵢ₊₁)), ..., ρⁿ⁻¹(hv(sᵢ₊ₙ₋₁)))
Positional encoding:
hv(s) = Σᵢ bind(hv(sᵢ), posᵢ)
For any set of n points in high-dimensional space, there exists a linear map to O(log n / ε²) dimensions that preserves distances within (1 ± ε).
Application to HDC: Ensures that high-dimensional operations preserve meaningful relationships.
In high dimensions:
- Random vectors are nearly orthogonal
- Space is vast enough to represent many concepts
- Local neighborhoods become meaningful
HDC implements holographic storage where:
- Information is distributed across all dimensions
- Each dimension contains partial information about the whole
- Robust to component failures
| Operation | Binary | Bipolar |
|---|---|---|
| Generate | O(d) | O(d) |
| Bind | O(d) | O(d) |
| Bundle | O(nd) | O(nd) |
| Similarity | O(d) | O(d) |
Where n is the number of vectors to bundle.
- Storage per item: O(d) bits (binary) or O(d log L) bits (L-level)
- Associative memory with k items: O(kd)
As the number of bundled vectors increases:
lim_{n→∞} bundle(v₁, ..., vₙ) → mean vector
The result converges to the centroid in the hyperdimensional space.
For composite structures, iterative unbinding converges:
x₀ = query
xₙ₊₁ = cleanup(unbind(memory, xₙ))
Converges to stored item if initial similarity > threshold.
- Sparse Distributed Representations: Similar to cortical representations
- Binding Problem: Addresses how the brain combines features
- Pattern Completion: Models associative memory in hippocampus
- Noise Tolerance: Reflects robustness of biological systems
- Kanerva, P. (2009). "Hyperdimensional computing: An introduction to computing in distributed representation"
- Plate, T. (2003). "Holographic Reduced Representations"
- Rachkovskij, D. A., & Kussul, E. M. (2001). "Binding and normalization of binary sparse distributed representations"
- Ge, L., & Parhi, K. K. (2020). "Classification using hyperdimensional computing: A review"