randUTV: A blocked randomized algorithm for computing a rank-revealing UTV factorization
For practitioners needing fast, accurate matrix factorizations for low-rank approximation and solving ill-conditioned systems, randUTV offers a practical alternative to the SVD with improved efficiency.
The paper introduces randUTV, a blocked randomized algorithm for computing a rank-revealing UTV factorization that is faster and more parallelizable than the SVD while providing comparable accuracy for low-rank approximation and other tasks. Numerical experiments show it outperforms column pivoted QR in both speed and accuracy.
This manuscript describes the randomized algorithm randUTV for computing a so called UTV factorization efficiently. Given a matrix $A$, the algorithm computes a factorization $A = UTV^{*}$, where $U$ and $V$ have orthonormal columns, and $T$ is triangular (either upper or lower, whichever is preferred). The algorithm randUTV is developed primarily to be a fast and easily parallelized alternative to algorithms for computing the Singular Value Decomposition (SVD). randUTV provides accuracy very close to that of the SVD for problems such as low-rank approximation, solving ill-conditioned linear systems, determining bases for various subspaces associated with the matrix, etc. Moreover, randUTV produces highly accurate approximations to the singular values of $A$. Unlike the SVD, the randomized algorithm proposed builds a UTV factorization in an incremental, single-stage, and non-iterative way, making it possible to halt the factorization process once a specified tolerance has been met. Numerical experiments comparing the accuracy and speed of randUTV to the SVD are presented. These experiments demonstrate that in comparison to column pivoted QR, which is another factorization that is often used as a relatively economic alternative to the SVD, randUTV compares favorably in terms of speed while providing far higher accuracy.