CMX Student/Postdoc Seminar

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 fast singular value decay. When the singular values decay slowly, there can be significant errors! Our ongoing work improves the accuracy of randomized low-rank matrix approximation for matrices with slow singular value decay. We analyze an 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.