A Theoretical Perspective on Hyperdimensional Computing [pdf] (cseweb.ucsd.edu)

This paper is a comprehensive theoretical review of hyperdimensional (HD) computing that unifies recent algorithmic variants and frames them for the machine‑learning community. The authors formalize how simple, neurally plausible encoders map inputs x from a space X into high‑dimensional representations in H (often via random mappings and low‑precision coordinates like ±1), and how a small set of algebraic operations—most notably bundling (superposition) and binding (role/tuple construction)—support storage, decoding, and learning. They pose and answer key questions about representing items, sets, and sequences in H; decoding reliably under noise and hardware faults; what input structure is preserved; and the expressive power of linear separators on HD embeddings. Significance lies in connecting HD computing’s energy‑efficient, low‑latency, noise‑robust hardware appeals to formal learning theory. The review relates HD models to vector symbolic architectures and biological “expand‑and‑sparsify” transforms (e.g., insect olfaction), draws parallels to random feature/kernel perspectives, and provides mathematical conditions for reliable decoding and classification (e.g., prototype bundling for class labels). For the AI/ML community this clarifies when HD representations can replace or complement conventional models—especially in constrained hardware or noisy settings—and highlights tradeoffs between dimensionality, precision, robustness, and linear separability.