Low-Rank Approximation of Matrices Via A Rank-Revealing Factorization with Randomization

Given a matrix A with numerical rank k, the two-sided orthogonal decomposition (TSOD) computes a factorization A = UDV^T, where U and V are unitary, and D is (upper/lower) triangular. TSOD is rank-revealing as the middle factor D reveals the rank of A. The computation of TSOD, however, is demanding, especially when a low-rank representation of the input matrix is desired. To treat such a case efficiently, in this paper we present an algorithm called randomized pivoted TSOD (RP-TSOD) that constructs a highly accurate approximation to the TSOD decomposition. Key in our work is the exploitation of randomization, and we furnish (i) upper bounds on the error of the low-rank approximation, and (ii) bounds for the canonical angles between the approximate and the exact singular subspaces, which take into account the randomness. Our bounds describe the characteristics and behavior of our proposed algorithm. We validate the effectiveness of our proposed algorithm and devised bounds with synthetic data as well as real data of image reconstruction problem.