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

2024/12/04 by Yifan Chen, Ethan N. Epperly, Joel A. Tropp +1 · 12 citations
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Machine Learning and Algorithms

paper · doi:10.1002/cpa.22234

Abstract

Abstract The randomly pivoted Cholesky algorithm ( RPCholesky ) computes a factorized rank‐ approximation of an positive‐semidefinite (psd) matrix. RPCholesky requires only entry evaluations and 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.

Citations

• Fast monte-carlo algorithms for finding low-rank approximations

Cited by

• Deep Convolutional Large-Margin ℓ_p-SVDD for Visual Anomaly Detection
• Operator Learning at Machine Precision
• Numerical Stability of the Nyström Method
• Accelerated decomposition of bistochastic kernel matrices by low rank approximation
• Inference on Variable Importance for Treatment Effect Heterogeneity: Shapley Values and Beyond
• Adaptive randomized pivoting and volume sampling
• An efficient algorithm for kernel quantile regression
• Fast Rank Adaptive CUR via a Recycled Small Sketch
• Regularized Overestimated Newton
• xRFM: Accurate, scalable, and interpretable feature learning models for tabular data
• Metric Learning in an RKHS
• Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modeling

Related

• Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
• Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky
• Randomly Pivoted Partial Cholesky: Random How?
• Make the most of what you have: Resource-efficient randomized algorithms for matrix computations
• Kernel quadrature with randomly pivoted Cholesky