Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky

2024/10/04 by Ethan N. Epperly, Joel A. Tropp, Epperly, Ethan N. +3 · 9 citations
Computer Science · #65C99 #65F55 #68T05 #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Machine Learning (stat.ML) #Neural Networks and Applications #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.2410.03969

openalex publication_date 2024/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Cited by

• Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
• Numerical Stability of the Nyström Method
• Accelerated decomposition of bistochastic kernel matrices by low rank approximation
• Adaptive randomized pivoting and volume sampling
• Structured Column Subset Selection for Bayesian Optimal Experimental Design
• Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
• Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra
• Revisiting column subset selection through the lens of submodularity
• Learning Dynamical Systems with the Spectral Exterior Calculus

Related

• Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
• Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
• Make the most of what you have: Resource-efficient randomized algorithms for matrix computations
• CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT)
• Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications