Robert Webber, Caltech

Abstract: Randomized low-rank matrix approximation is one of the great success stories of randomized numerical linear algebra. It is a fast, scalable approach that has been widely adopted in scientific computing. However, the approach is most successful at approximating matrices with quickly decaying singular values since there can be significant random errors when the singular values decay slowly. Our ongoing work improves the accuracy of randomized low-rank matrix approximation for matrices with slow singular value decay. We study an emerging approach called 'randomized block Krylov iteration', which builds a rich approximation space from the output of repeated matrix-matrix multiplications. Our contributions are two-fold: first, we derive an efficient implementation of randomized block Krylov iteration that reduces the standard runtime by a half, and second, we establish error bounds that quantify the rapid convergence of randomized block Krylov iteration, demonstrating its advantage over alternative methods.