mlsanityData to 14 Oct 2026

Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky

arXiv 2410.03969 ↗First posted 4 Oct 2024math.NA cs.NA stat.COcited by 5

Not on the map. Why?

Abstract (arXiv)

Randomly pivoted Cholesky (RPCholesky) is an algorithm for constructing a low-rank approximation of a positive-semidefinite matrix using a small number of columns. This paper develops an accelerated version of RPCholesky that employs block matrix computations and rejection sampling to efficiently simulate the execution of the original algorithm. For the task of approximating a kernel matrix, the accelerated algorithm can run over 40× faster. The paper contains implementation details, theoretical guarantees, experiments on benchmark data sets, and an application to computational chemistry.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 15 of its 38 references that are in the map. First posted on arXiv 4 Oct 2024.

Builds on

15 of 38 references.

References · 15

  1. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 609
  2. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  3. 2020Machine Learning Force Fieldscited by 207
  4. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  5. 2019Exact Gaussian Processes on a Million Data Pointscited by 119
  6. 2020Kernel methods through the roof: handling billions of points efficientlycited by 89
  7. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
  8. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 41
  9. 2023Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Softwarecited by 38
  10. 2016Preconditioning Kernel Matricescited by 33
  11. 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 32
  12. 2017Sublinear Time Low-Rank Approximation of Positive Semidefinite Matricescited by 18
3 more
  1. 2023Kernel quadrature with randomly pivoted Choleskycited by 11
  2. 2023Robust, randomized preconditioning for kernel ridge regressioncited by 9
  3. 2024The fast committor machine: Interpretable prediction with kernelscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
  2. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
  3. 2025Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebracited by 1
  4. 2025Adaptive randomized pivoting and volume samplingcited by 1
  5. 2026Fast Length-Squared Sampling for Positive-Semidefinite Matricescited by 0