Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
This interesting paper studies kernel matrix approximation via accelerated randomly pivoted Cholesky. We now give this more context. The following is an important procedure in computational linear algebra which can be stated as follows: Suppose we are given a positive-semidefinite matrix say \(B\in \mathbb C^{N\times N}\) together with a rank parameter say \(k\) satisfying \(1\leq k\leq N\). Compute a matrix \(D\in \mathbb C^{N\times N}\) with \(B\sim DD^*\). Randomly pivoted Cholesky is an algorithm for constructing a low rank approximation of a positive-semidefinite matrix using a small number of columns. It is a randomized variant of the pivoted partial Cholesky method which is one of the best well known algorithms for constructing a rank-\(k\) positive semidefinite approximation from a set of \(k\) columns.\N\NThe authors introduce a new algorithm, which, for the task of approximating a kernel matrix, can run over 40 times faster than the random pivoted Cholesky algorithm while at the same time producing approximations with the same quality. The accelerated algorithm moreover simulates the behavior of the simpler method by means of block-matrix computations and rejection sampling. \N\NGiven in the paper are theoretical guarantees, implementation details, experiments on benchmark data sets and an application to chemistry.\N\NThe paper is well written with a very good set of references.
- 10.1162/15324430260185619
- Accuracy and Stability of Numerical Algorithms
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Faster kernel ridge regression using sketching and preconditioning
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 4189084 (Why is no real title available?)
- Matrix approximation and projective clustering via volume sampling
- Matrix theory. Basic results and techniques
- On the Nyström method for approximating a gram matrix for improved kernel-based learning
- Randomized Nyström Preconditioning
- Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- Rounding error analysis of the classical Gram-Schmidt orthogonalization process
- Sketching as a tool for numerical linear algebra
- Sublinear time low-rank approximation of positive semidefinite matrices
This page was built for publication: Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6881036)
