Matrix Factorizations with Uniformly Random Pivoting
This work solves a longstanding open problem in numerical linear algebra by improving the theoretical understanding and stability of matrix factorization algorithms, which are foundational for computational mathematics and scientific computing.
The paper establishes a formal connection between two families of matrix factorization algorithms, such as Jacobi eigenvalue and Gaussian elimination, by casting them as special cases of a general class and introducing a randomized pivoting rule. This rule enables a unified analysis showing a linear convergence rate for all algorithms and provides a provable polynomial bound on the numerical stability of the Jacobi eigenvalue algorithm, addressing an open problem from 1992.
This paper highlights a formal connection between two families of widely used matrix factorization algorithms in numerical linear algebra. One family consists of the Jacobi eigenvalue algorithm and its variants for computing the Hermitian eigendecomposition and singular value decomposition. The other consists of Gaussian elimination and the Gram-Schmidt procedure with various pivoting rules for computing the Cholesky decomposition and QR decomposition respectively. Both families are cast as special cases of a more general class of factorization algorithms. We provide a randomized pivoting rule that applies to this general class (which differs substantially from the usual pivoting rules for Gaussian elimination / Gram-Schmidt) which admits a unified analysis of the entire class of algorithms. The result is the same linear rate of convergence for each algorithm, irrespective of which factorization it computes. One important consequence of this randomized pivoting rule is a provable polynomial bound on the numerical stability of the Jacobi eigenvalue algorithm without any preconditioning, which addresses a longstanding open problem of Demmel and VeseliÄ `92.