# ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2014.

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

- [Squeezed Attention: Accelerating Long Context Length LLM Inference](https://mlsanity.com/paper/2411.09688/) (2024)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms](https://mlsanity.com/paper/2401.08260/) (2024)
- [Fast Summation of Radial Kernels via QMC Slicing](https://mlsanity.com/paper/2410.01316/) (2024)
- [Quantum Adaptive Fourier Features for Neural Density Estimation](https://mlsanity.com/paper/2208.00564/) (2022)
- [Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication](https://mlsanity.com/paper/2111.10140/) (2021)
- [A Preconditioned Interior Point Method for Support Vector Machines Using an ANOVA-Decomposition and NFFT-Based Matrix-Vector Products](https://mlsanity.com/paper/2312.00538/) (2023)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations](https://mlsanity.com/paper/2108.04167/) (2021)

## Abstract (arXiv)

We present a fast algorithm for kernel summation problems in high-dimensions. These problems appear in computational physics, numerical approximation, non-parametric statistics, and machine learning. In our context, the sums depend on a kernel function that is a pair potential defined on a dataset of points in a high-dimensional Euclidean space. A direct evaluation of the sum scales quadratically with the number of points. Fast kernel summation methods can reduce this cost to linear complexity, but the constants involved do not scale well with the dimensionality of the dataset. The main algorithmic components of fast kernel summation algorithms are the separation of the kernel sum between near and far field (which is the basis for pruning) and the efficient and accurate approximation of the far field. We introduce novel methods for pruning and approximating the far field. Our far field approximation requires only kernel evaluations and does not use analytic expansions. Pruning is not done using bounding boxes but rather combinatorially using a sparsified nearest-neighbor graph of the input. The time complexity of our algorithm depends linearly on the ambient dimension. The error in the algorithm depends on the low-rank approximability of the far field, which in turn depends on the kernel function and on the intrinsic dimensionality of the distribution of the points. The error of the far field approximation does not depend on the ambient dimension. We present the new algorithm along with experimental results that demonstrate its performance. We report results for Gaussian kernel sums for 100 million points in 64 dimensions, for one million points in 1000 dimensions, and for problems in which the Gaussian kernel has a variable bandwidth. To the best of our knowledge, all of these experiments are impossible or prohibitively expensive with existing fast kernel summation methods.