matsketch
Implements recent randomized algorithms that answer questions about a large positive-semidefinite matrix while touching only a small part of it. Randomly pivoted Cholesky builds a low-rank approximation from a few rows of a kernel matrix (Chen, Epperly, Tropp and Webber (2025) <doi:10.1002/cpa.22234>), with an accelerated variant based on rejection sampling (Epperly, Tropp and Webber (2025) <doi:10.1137/24m1699048>). The XTrace, XNysTrace and XDiag estimators recover the trace and diagonal of a matrix that is available only through matrix-vector products (Epperly, Tropp and Webber (2024) <doi:10.1137/23m1548323>), alongside the Hutch++ estimator of Meyer, Musco, Musco and Woodruff (2021) <doi:10.1137/1.9781611976496.16>. Randomized Nystrom preconditioning speeds up the conjugate gradient method for regularized linear systems (Frangella, Tropp and Udell (2023) <doi:10.1137/21m1466244>). These pieces are combined to fit restricted maximum likelihood variance-component models on genomic relationship matrices without forming or factorizing the covariance matrix.
- Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
- Hutch++: Optimal Stochastic Trace Estimation
- Randomized Nyström Preconditioning
- Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
- XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation
This page was built for software: matsketch
