mlsanityData to 7 Oct 2026

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

arXiv 2207.06503 ↗First posted 13 Jul 2022math.NA cs.NA stat.MLcited by 31

Not on the map. Why?

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.

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

Builds on

19 of 89 references.

References · 19

  1. 2014OpenML: networked science in machine learningcited by 523
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  3. 2020Finite Versus Infinite Neural Networks: an Empirical Studycited by 156
  4. 2020Kernel methods through the roof: handling billions of points efficientlycited by 88
  5. 2019Harnessing the Power of Infinitely Wide Deep Nets on Small-data Taskscited by 87
  6. 2017FALKON: An Optimal Large Scale Kernel Methodcited by 82
  7. 2017Time-lagged autoencoders: Deep learning of slow collective variables for molecular kineticscited by 64
  8. 2022A Framework and Benchmark for Deep Batch Active Learning for Regressioncited by 47
  9. 2020Determinantal Point Processes in Randomized Numerical Linear Algebracited by 41
  10. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 40
  11. 2016Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processescited by 24
  12. 2017Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Datacited by 22
7 more
  1. 2013Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Samplingcited by 21
  2. 2019Exact sampling of determinantal point processes with sublinear time preprocessingcited by 19
  3. 2017Sublinear Time Low-Rank Approximation of Positive Semidefinite Matricescited by 18
  4. 2021Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networkscited by 17
  5. 2018Distributed Adaptive Sampling for Kernel Matrix Approximationcited by 9
  6. 2020Diversity sampling is an implicit regularization for kernel methodscited by 4
  7. 2021Kernel approximation on algebraic varietiescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 7; 2025: 11; 2026: 7.

31 papers.

Sort:

  1. 2023Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian Processescited by 31
  2. 2025xRFM: Accurate, scalable, and interpretable feature learning models for tabular datacited by 14
  3. 2023Toward Large Kernel Modelscited by 12
  4. 2023Kernel quadrature with randomly pivoted Choleskycited by 11
  5. 2023Robust, randomized preconditioning for kernel ridge regressioncited by 8
  6. 2022Multiresolution kernel matrix algebracited by 6
  7. 2025Data-Efficient Kernel Methods for Learning Differential Equations and Their Solution Operators: Algorithms and Error Analysiscited by 6
  8. 2025Operator Learning at Machine Precisioncited by 6
  9. 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
  10. 2024The fast committor machine: Interpretable prediction with kernelscited by 5
  11. 2024Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuningcited by 5
  12. 2024Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Choleskycited by 5
19 more
  1. 2023A Preconditioned Interior Point Method for Support Vector Machines Using an ANOVA-Decomposition and NFFT-Based Matrix-Vector Productscited by 3
  2. 2024Supervised Kernel Thinningcited by 3
  3. 2025Kernel Density Machinescited by 2
  4. 2026Linearization Explains Fine-Tuning in Large Language Modelscited by 2
  5. 2024Randomly Pivoted Partial Cholesky: Random How?cited by 1
  6. 2024Joint Estimation of Conditional Mean and Covariance for Unbalanced Panelscited by 1
  7. 2025Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebracited by 1
  8. 2025Learning where to learn: Training data distribution optimization for scientific machine learningcited by 1
  9. 2025Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modelingcited by 1
  10. 2025Inference on Variable Importance for Treatment Effect Heterogeneity: Shapley Values and Beyondcited by 1
  11. 2026GPTQ-intrinsic LoRA: A Near-optimal Algorithm for Low-precision Quantization with Low-rank Adaptationcited by 1
  12. 2024Variational Markov chain mixtures with automatic component selectioncited by 0
  13. 2025Metric Learning in an RKHScited by 0
  14. 2025Adaptive randomized pivoting and volume samplingcited by 0
  15. 2025A Streaming Sparse Cholesky Method for Derivative-Informed Gaussian Process Surrogates Within Digital Twin Applicationscited by 0
  16. 2026Communication-Avoiding Linear Algebraic Kernel K-Means on GPUscited by 0
  17. 2026Deep Convolutional Large-Margin ℓp-SVDD for Visual Anomaly Detectioncited by 0
  18. 2026Fast Length-Squared Sampling for Positive-Semidefinite Matricescited by 0
  19. 2026SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCAcited by 0