skip to main content
Caltech

CMX Student/Postdoc Seminar

Friday, October 14, 2022
1:00pm to 2:00pm
Add to Cal
Annenberg 105
Randomized low-rank approximation with higher accuracy and reduced costs
Robert Webber, Postdoctoral Scholar, Department of Computing and Mathematical Sciences, Caltech,

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.

For more information, please contact Jolene Brink by email at [email protected] or visit CMX Website.