Analysis of randomized block Krylov methods

Randomized block Krylov subspace methods form a powerful class of algorithms for computing the (extreme) eigenvalues and singular values of a matrix. The purpose of this paper is to develop new theoretical bounds on the performance of randomized block Krylov subspace methods for these problems. The results demonstrate that, for many matrices, it is possible to obtain an accurate spectral norm estimate using only a constant number of steps of the randomized block Krylov method. Furthermore, the analysis reveals that the behavior of the algorithm depends in a delicate way on the block size. Randomized block Krylov subspace methods are a powerful class of algorithms for computing information about the spectrum of a matrix. The purpose of this note is to develop new theoretical bounds on the performance of randomized block Krylov subspace methods for estimating a number of extreme eigenvalues. The results demonstrate that, for many matrices, it is possible to obtain accurate approximations using only a constant number of steps of the randomized block Krylov method. Randomized block Krylov subspace methods are a powerful class of techniques for computing information about the spectrum of a matrix. The purpose of this paper is to develop new theoretical bounds on the performance of randomized block Krylov subspace methods for computing a low-rank approximation of a matrix. The results demonstrate that, for many matrices, it is possible to obtain accurate approximations using only a constant number of steps of the randomized block Krylov method.