Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
In this very interesting paper, the authors study the following question: What are the best algorithms for finding a low-rank approximation of a large positive semi-definite kernel matrix? The question is motivated in part by kernel methods which are used in machine learning to do various tasks for example interpolation, regression, clustering, and summarization of data for a large number of points. The authors introduce an algorthim they call a randomly pivoted Cholesky algorithm (RPCholesky) which computes a factorized rank-\(k\) appoximation of an \(N\times N\) positive-semidefinite matrix. The algorithm requires only \((k+1)N\) entry evaluations with an additional \(O(k^{2}N)\) arithmetic operations and is in particular very useful in approximating a kernel matrix when the number of entries is large. The paper gives a very detailed theoretical and empirical analysis of the algorthm and show hiw it beats many other classical algorithms in many applications.
- 10.1162/15324430260185619
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- An Identity for the Schur Complement of a Matrix
- An introduction to matrix concentration inequalities
- Determinantal point processes for machine learning
- Determinantal point processes in randomized numerical linear algebra
- Diversity sampling is an implicit regularization for kernel methods
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast monte-carlo algorithms for finding low-rank approximations
- High-dimensional probability. An introduction with applications in data science
- High-performance sampling of generic determinantal point processes
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 6276143 (Why is no real title available?)
- scientific article; zbMATH DE number 4189084 (Why is no real title available?)
- Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
- Kernel Approximation on Algebraic Varieties
- Kernel methods are competitive for operator learning
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Matrix approximation and projective clustering via volume sampling
- Matrix theory. Basic results and techniques
- Mechanism for feature learning in neural networks and backpropagation-free machine learning models
- On the Nyström method for approximating a gram matrix for improved kernel-based learning
- Optimal column-based low-rank matrix reconstruction
- Randomized numerical linear algebra: Foundations and algorithms
- Sublinear time low-rank approximation of positive semidefinite matrices
- The Schur complement and its applications
- Trace inequalities and quantum entropy: an introductory course
- Variational Markov chain mixtures with automatic component selection
- Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
- Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
- A gradient-based and determinant-free framework for fully Bayesian Gaussian process regression
- Sparse inverse Cholesky factorization of dense kernel matrices by greedy conditional selection
- Efficient nonlocal linear image denoising: bilevel optimization with nonequispaced fast Fourier transform and matrix-free preconditioning
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- Parametric kernel low-rank approximations using tensor train decomposition
- Adaptive, Matrix-Free Low-Rank Approximation
- Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows
- Entry growth in Gaussian elimination
- A new analysis of the randomly pivoted Cholesky algorithm
- Stable algorithms for general linear systems by preconditioning the normal equations
- Randomized structured total-least-squares-based higher-order extended dynamic mode decomposition
- Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
- Invariant kernels: rank stabilization and generalization across dimensions
- A Geometric View of Adaptive Cross Approximation via Exterior Algebra
- Incremental Column Subset Selection via Conditional Determinantal Point Processes
- SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCA
- Robust, randomized preconditioning for kernel ridge regression
- matsketch
This page was built for publication: Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7000432)
