# Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 89 references that are in the map.
- First posted on arXiv 13 Jul 2022.

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

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Finite Versus Infinite Neural Networks: an Empirical Study](https://mlsanity.com/paper/2007.15801/) (2020)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Time-lagged autoencoders: Deep learning of slow collective variables for molecular kinetics](https://mlsanity.com/paper/1710.11239/) (2017)
- [A Framework and Benchmark for Deep Batch Active Learning for Regression](https://mlsanity.com/paper/2203.09410/) (2022)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks](https://mlsanity.com/paper/2108.00131/) (2021)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)
- [Diversity sampling is an implicit regularization for kernel methods](https://mlsanity.com/paper/2002.08616/) (2020)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)

## Built on by (most cited first, 30 of 32)

- [Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian Processes](https://mlsanity.com/paper/2304.01294/) (2023)
- [xRFM: Accurate, scalable, and interpretable feature learning models for tabular data](https://mlsanity.com/paper/2508.10053/) (2025)
- [Toward Large Kernel Models](https://mlsanity.com/paper/2302.02605/) (2023)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Data-Efficient Kernel Methods for Learning Differential Equations and Their Solution Operators: Algorithms and Error Analysis](https://mlsanity.com/paper/2503.01036/) (2025)
- [Operator Learning at Machine Precision](https://mlsanity.com/paper/2511.19980/) (2025)
- [Multiresolution kernel matrix algebra](https://mlsanity.com/paper/2211.11681/) (2022)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [The fast committor machine: Interpretable prediction with kernels](https://mlsanity.com/paper/2405.10410/) (2024)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky](https://mlsanity.com/paper/2410.03969/) (2024)
- [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)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Learning where to learn: Training data distribution optimization for scientific machine learning](https://mlsanity.com/paper/2505.21626/) (2025)
- [Kernel Density Machines](https://mlsanity.com/paper/2504.21419/) (2025)
- [Inference on Variable Importance for Treatment Effect Heterogeneity: Shapley Values and Beyond](https://mlsanity.com/paper/2510.18843/) (2025)
- [Linearization Explains Fine-Tuning in Large Language Models](https://mlsanity.com/paper/2602.08239/) (2026)
- [Randomly Pivoted Partial Cholesky: Random How?](https://mlsanity.com/paper/2404.11487/) (2024)
- [Conditional Moment Kernels: Joint Modeling of Expected Returns and Covariances in Unbalanced Panels](https://mlsanity.com/paper/2410.21858/) (2024)
- [Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2505.11638/) (2025)
- [Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modeling](https://mlsanity.com/paper/2507.20459/) (2025)
- [Adaptive randomized pivoting and volume sampling](https://mlsanity.com/paper/2510.02513/) (2025)
- [GPTQ-intrinsic LoRA: A Near-optimal Algorithm for Low-precision Quantization with Low-rank Adaptation](https://mlsanity.com/paper/2606.01412/) (2026)
- [Variational Markov chain mixtures with automatic component selection](https://mlsanity.com/paper/2406.04653/) (2024)
- [Metric Learning in an RKHS](https://mlsanity.com/paper/2508.04476/) (2025)
- [A Streaming Sparse Cholesky Method for Derivative-Informed Gaussian Process Surrogates Within Digital Twin Applications](https://mlsanity.com/paper/2511.00366/) (2025)
- [Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs](https://mlsanity.com/paper/2601.17136/) (2026)
- [Deep Convolutional Large-Margin ℓp-SVDD for Visual Anomaly Detection](https://mlsanity.com/paper/2607.22212/) (2026)
- [Fast Length-Squared Sampling for Positive-Semidefinite Matrices](https://mlsanity.com/paper/2608.12503/) (2026)

## Abstract (arXiv)

The randomly pivoted partial Cholesky algorithm (RPCholesky) computes a factorized rank-k approximation of an N x N positive-semidefinite (psd) matrix. RPCholesky requires only (k + 1) N entry evaluations and O(k^2 N) additional arithmetic operations, and it can be implemented with just a few lines of code. The method is particularly useful for approximating a kernel matrix. This paper offers a thorough new investigation of the empirical and theoretical behavior of this fundamental algorithm. For matrix approximation problems that arise in scientific machine learning, experiments show that RPCholesky matches or beats the performance of alternative algorithms. Moreover, RPCholesky provably returns low-rank approximations that are nearly optimal. The simplicity, effectiveness, and robustness of RPCholesky strongly support its use in scientific computing and machine learning applications.