We describe a randomized variant of the block conjugate gradient method for solving a single positive definite linear system of equations. This method provably outperforms the preconditioned conjugate gradient method with a broad class of Nyström-based preconditioners, without ever explicitly constructing a preconditioner. In analyzing our algorithm, we derive theoretical guarantees for new variants of the Nyström-preconditioned conjugate gradient method, which may be of separate interest. We also describe how our approach yields fast algorithms for key data-science tasks such as computing the entire ridge regression regularization path and generating multiple independent samples from a high-dimensional Gaussian distribution.
Chen et al. (Thu,) studied this question.