randUTV
Abstract
A randomized algorithm for computing a so-called UTV factorization efficiently is presented. Given a matrix A , the algorithm “randUTV” 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, and determining bases for various subspaces associated with the matrix. 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 noniterative 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. Other experiments also 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 14, 2019
- Source ID
- 10.1145/3242670
Entities
People
- G. Quintana-ortí
- N. Heavner
- P. G. Martinsson
Organizations
- Defense Advanced Research Projects Agency
- Jaume I University
- National Science Foundation
- University of Colorado Boulder
- University of Oxford