Sublinear time low-rank approximation of positive semidefinite matrices

DOI10.1109/FOCS.2017.68MaRDI QIDQ6946318zbMATH OpenFDO

Authors David P. Woodruff, Cameron Musco

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2017.68

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(6)

• Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
• Universal matrix sparsifiers and fast deterministic algorithms for linear algebra
• Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
• Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
• A very sketchy talk (invited talk)
• A new analysis of the randomly pivoted Cholesky algorithm

This page was built for publication: Sublinear time low-rank approximation of positive semidefinite matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946318)