# A general technique for approximating high-dimensional empirical kernel matrices

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 5 Nov 2025.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology](https://mlsanity.com/paper/2002.07867/) (2020)
- [Dimension free ridge regression](https://mlsanity.com/paper/2210.08571/) (2022)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Approximation beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [How rotational invariance of common kernels prevents generalization in high dimensions](https://mlsanity.com/paper/2104.04244/) (2021)
- [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015)
- [A non-asymptotic theory of Kernel Ridge Regression: deterministic equivalents, test error, and GCV estimator](https://mlsanity.com/paper/2403.08938/) (2024)
- [An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings](https://mlsanity.com/paper/2205.06308/) (2022)
- [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regime](https://mlsanity.com/paper/2205.06798/) (2022)
- [Harmless interpolation in regression and classification with structured features](https://mlsanity.com/paper/2111.05198/) (2021)
- [Universality of Kernel Random Matrices and Kernel Regression in the Quadratic Regime](https://mlsanity.com/paper/2408.01062/) (2024)
- [Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime](https://mlsanity.com/paper/2310.18280/) (2023)
- [Overparameterized random feature regression with nearly orthogonal data](https://mlsanity.com/paper/2211.06077/) (2022)
- [Learning single-index models via harmonic decomposition](https://mlsanity.com/paper/2506.09887/) (2025)
- [New Equivalences Between Interpolation and SVMs: Kernels and Structured Features](https://mlsanity.com/paper/2305.02304/) (2023)

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

- [Power-Law Spectrum of the Random Feature Model](https://mlsanity.com/paper/2603.14578/) (2026)
- [Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index models](https://mlsanity.com/paper/2605.15082/) (2026)
- [Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs](https://mlsanity.com/paper/2607.14304/) (2026)
- [Recovery of latent inner products from an anisotropic Gaussian random geometric graph](https://mlsanity.com/paper/2607.23723/) (2026)

## Abstract (arXiv)

We present simple, user-friendly bounds for the expected operator norm of a random kernel matrix under general conditions on the kernel function k(·,·). Our approach uses decoupling results for U-statistics and the non-commutative Khintchine inequality to obtain upper and lower bounds depending only on scalar statistics of the kernel function and a ``correlation kernel'' matrix corresponding to k(·,·). We then apply our method to provide new, tighter approximations for inner-product kernel matrices on general high-dimensional data, where the sample size and data dimension are polynomially related. Our method obtains simplified proofs of existing results that rely on the moment method and combinatorial arguments while also providing novel approximation results for the case of anisotropic Gaussian data. Finally, using similar techniques to our approximation result, we show a tighter lower bound on the bias of kernel regression with anisotropic Gaussian data.