# Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nystr"om Method

arXiv: https://arxiv.org/abs/2608.06860 · HTML: https://mlsanity.com/paper/2608.06860/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 63 references that are in the map.
- First posted on arXiv 7 Aug 2026.

## Builds on (most cited first, 14 of 14)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Pre-trained Models for Natural Language Processing: A Survey](https://mlsanity.com/paper/2003.08271/) (2020)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part II: Applications, Cognitive Models, and Challenges](https://mlsanity.com/paper/2112.15424/) (2021)
- [A Theoretical Perspective on Hyperdimensional Computing](https://mlsanity.com/paper/2010.07426/) (2020)
- [Computing on Functions Using Randomized Vector Representations](https://mlsanity.com/paper/2109.03429/) (2021)
- [Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification](https://mlsanity.com/paper/1905.04579/) (2019)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Understanding Hyperdimensional Computing for Parallel Single-Pass Learning](https://mlsanity.com/paper/2202.04805/) (2022)
- [A short letter on the dot product between rotated Fourier transforms](https://mlsanity.com/paper/2007.13462/) (2020)

## Built on by (most cited first, 2 of 2)

- [Vector Symbolic Policy Gradient](https://mlsanity.com/paper/2608.18404/) (2026)
- [Superposed Inference for Hyperdimensional Computing](https://mlsanity.com/paper/2609.32320/) (2026)

## Abstract (arXiv)

Hyperdimensional computing (HDC) is an approach from the cognitive science literature for solving information processing tasks using data represented as high-dimensional random vectors. The technique has a rigorous mathematical backing, and is easy to implement in energy-efficient and highly parallel hardware like FPGAs and "processing-in-memory" architectures. The effectiveness of HDC in machine learning largely depends on how raw data is mapped to high-dimensional space. In this work, we propose NysHD, a new method for constructing this mapping that is based on the Nystr"om method from the literature on kernel approximation. Our approach provides a simple recipe to turn any user-defined positive-semidefinite similarity function into an equivalent mapping in HDC. There is a vast literature on the design of such functions for learning problems. Our approach provides a mechanism to import them into the HDC setting, expanding the types of problems that can be tackled using HDC. Empirical evaluation against existing HDC encoding methods shows that NysHD can achieve, on average, 11% and 17% better classification accuracy on graph and string datasets respectively.