# Kernel approximation on algebraic varieties

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 56 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models](https://mlsanity.com/paper/1703.05160/) (2017)
- [Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling](https://mlsanity.com/paper/2007.03927/) (2020)
- [Algebraic Variety Models for High-Rank Matrix Completion](https://mlsanity.com/paper/1703.09631/) (2017)

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

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention](https://mlsanity.com/paper/2608.28150/) (2026)

## Abstract (arXiv)

Low-rank approximation of kernels is a fundamental mathematical problem with widespread algorithmic applications. Often the kernel is restricted to an algebraic variety, e.g., in problems involving sparse or low-rank data. We show that significantly better approximations are obtainable in this setting: the rank required to achieve a given error depends on the variety's dimension rather than the ambient dimension, which is typically much larger. This is true in both high-precision and high-dimensional regimes. Our results are presented for smooth isotropic kernels, the predominant class of kernels used in applications. Our main technical insight is to approximate smooth kernels by polynomial kernels, and leverage two key properties of polynomial kernels that hold when they are restricted to a variety. First, their ranks decrease exponentially in the variety's co-dimension. Second, their maximum values are governed by their values over a small set of points. Together, our results provide a general approach for exploiting (approximate) "algebraic structure" in datasets in order to efficiently solve large-scale data science problems.