Matrix Factorizations with Uniformly Random Pivoting

What do Jacobi’s eigenvalue algorithm and an iterative algorithm for finding the QR decomposition have in common? Under a randomized pivoting strategy, a unified analysis can show that these algorithms converge with the same linear rate of convergence. We can view these algorithms, as well as iterative algorithms for SVD and Cholesky decomposition, as elements of a more general class of matrix factorizations. I will define this general class of matrix factorizations and discuss how to prove anything in this class converges under a randomized pivoting strategy.

This seminar is part of the Recent Progress and Open Directions in Matrix Computations series.