randUTV: a blocked randomized algorithm for computing a rank-revealing UTV factorization
Martinsson P., Quintana-Ortí G., Heavner N.  ACM Transactions on Mathematical Software 45(1): 1-26, 2019. Type: Article
Date Reviewed: 07/12/21

Matrix singular value decomposition (SVD) has broad applications in both computational linear algebra and data analysis. Robust SVD algorithms and sophisticated software implementations have been available in the literature for decades. However, efficiently calculating SVD for large-sized matrices through parallel processing remains a challenge due to computational dependency. Nevertheless, with the rise of big data, professionals and practitioners often need to process datasets with millions of rows and columns in real-world applications. There is a strong demand for alternative algorithms that are able to efficiently find numerical solutions with high accuracy for SVD applications of large matrices.

To meet the needs, the authors of this work propose a randomized matrix for computing UTV factorization (randUTV) as an alternative to SVD. That is to factor a matrix A as A = UTV* instead of A = UΣ V*, “where U and V have orthonormal columns, T is triangular,” and Σ consists of singular values as a diagonal matrix. The randUTV algorithm “builds a UTV factorization in an incremental ... and noniterative way.” With a specified tolerance, the factorization process is able to execute concurrently. Computational experiments show that the randUTV algorithm can improve computational efficiency when compared with other known alternatives. Much more significantly, the randUTV alternative is able to produce far more accurate numerical solutions, that is, very close to that of SVD. This work compares the accuracy of randUTV with another economic alternative: column-pivoted QR. The authors clearly explain the improvement in efficiency. However, they do not provide theoretical justifications for the high accuracy in terms of closeness to singular values.

I strongly recommend this paper to professionals and practitioners, especially those who deal with large-sized matrices in computational linear algebra and data science. Although the paper does not provide a rigorous proof to justify the achieved high accuracy mathematically, likely due to the randomness, the presented computational results demonstrate the usefulness of randUTV, which is an effective alternative to SVD with very high accuracy and efficiency.

 Reviewer:  Chenyi Hu Review #: CR147305

Reproduction in whole or in part without permission is prohibited.   Copyright 2021 ComputingReviews.com™