Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method

• URL: http://arxiv.org/abs/2608.06860v1
• Date: Fri, 07 Aug 2026 06:37:28 GMT
• Title: Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method
• Abstract summary: We propose NysHD, a new method for mapping raw data to high-dimensional space.<n>NysHD can achieve, on average, 11% and 17% better classification accuracy on graph and string datasets respectively.
• Score: 11.913975113422717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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öm 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.

Related papers

• The FIL Hypothesis: Inductive Biases Help with Kernel Engineering [88.25617363280156]
  General-purpose methods that scale with computation and data ultimately outperform those with built-in human knowledge.<n>We revisit this principle by observing a new and critical scaling dimension: the duration of the Feedback Information Loop (FIL)<n>We argue that future AI applications in science and the physical world will inherently involve FILs ranging from hours to weeks.
  arXiv  Detail & Related papers  (2026-06-29T15:16:33Z)
• Large-Margin Hyperdimensional Computing: A Learning-Theoretical Perspective [4.132339396232777]
  Hyperdimensional computing (HDC) is an emerging resource efficient and low-complexity machine learning method.<n>We propose a maximum-margin HDC classifier, which significantly outperforms baseline HDC methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2026-03-04T08:29:07Z)
• When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning [53.17227599983122]
  Functional tensor decomposition can analyze multi-dimensional data with real-valued indices.<n>We propose a rank-revealing functional low-rank tensor completion (RR-F) method.<n>We establish the universal approximation property of the model for continuous multi-dimensional signals.
  arXiv  Detail & Related papers  (2025-12-25T03:15:52Z)
• An Encoding Framework for Binarized Images using HyperDimensional Computing [0.0]
  This article proposes a novel light-weight approach to encode binarized images that preserves similarity of patterns at nearby locations. The method reaches an accuracy of 97.35% on the test set for the MNIST data set and 84.12% for the Fashion-MNIST data set.
  arXiv  Detail & Related papers  (2023-12-01T09:34:28Z)
• Streaming Encoding Algorithms for Scalable Hyperdimensional Computing [12.829102171258882]
  Hyperdimensional computing (HDC) is a paradigm for data representation and learning originating in computational neuroscience. In this work, we explore a family of streaming encoding techniques based on hashing. We show formally that these methods enjoy comparable guarantees on performance for learning applications while being substantially more efficient than existing alternatives.
  arXiv  Detail & Related papers  (2022-09-20T17:25:14Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  State-of-the-art convex learning methods can perform far worse than their centralized counterparts when clients have dissimilar data distributions. We show this disparity can largely be attributed to challenges presented by non-NISTity. We propose a Train-Convexify neural network (TCT) procedure to sidestep this issue.
  arXiv  Detail & Related papers  (2022-07-13T16:58:22Z)
• HDTorch: Accelerating Hyperdimensional Computing with GP-GPUs for Design Space Exploration [4.783565770657063]
  We introduce HDTorch, an open-source, PyTorch-based HDC library with extensions for hypervector operations. We analyze four HDC benchmark datasets in terms of accuracy, runtime, and memory consumption. We perform the first-ever HD training and inference analysis of the entirety of the CHB-MIT EEG epilepsy database.
  arXiv  Detail & Related papers  (2022-06-09T19:46:08Z)
• An Extension to Basis-Hypervectors for Learning from Circular Data in Hyperdimensional Computing [62.997667081978825]
  Hyperdimensional Computing (HDC) is a computation framework based on properties of high-dimensional random spaces. We present a study on basis-hypervector sets, which leads to practical contributions to HDC in general. We introduce a method to learn from circular data, an important type of information never before addressed in machine learning with HDC.
  arXiv  Detail & Related papers  (2022-05-16T18:04:55Z)
• GraphHD: Efficient graph classification using hyperdimensional computing [58.720142291102135]
  We present a baseline approach for graph classification with HDC. We evaluate GraphHD on real-world graph classification problems. Our results show that when compared to the state-of-the-art Graph Neural Networks (GNNs) the proposed model achieves comparable accuracy.
  arXiv  Detail & Related papers  (2022-05-16T17:32:58Z)
• HDC-MiniROCKET: Explicit Time Encoding in Time Series Classification with Hyperdimensional Computing [14.82489178857542]
  MiniROCKET is one of the best existing methods for time series classification. We extend this approach to provide better global temporal encodings using hyperdimensional computing (HDC) mechanisms. The extension with HDC can achieve considerably better results on datasets with high temporal dependence without increasing the computational effort for inference.
  arXiv  Detail & Related papers  (2022-02-16T13:33:13Z)
• Learnable Subspace Clustering [76.2352740039615]
  We develop a learnable subspace clustering paradigm to efficiently solve the large-scale subspace clustering problem. The key idea is to learn a parametric function to partition the high-dimensional subspaces into their underlying low-dimensional subspaces. To the best of our knowledge, this paper is the first work to efficiently cluster millions of data points among the subspace clustering methods.
  arXiv  Detail & Related papers  (2020-04-09T12:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.