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

Maboud Farzaneh Kaloorazi; Jie Chen

ICASSP 2020accepted0 citations

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

Abstract

Given a matrix A with numerical rank k, the two-sided orthogonal decomposition (TSOD) computes a factorization A = UDV <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> , 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.

BibTeX

@inproceedings{icassp2020_lowrankapproxima,
  title = {Low-Rank Approximation of Matrices Via A Rank-Revealing Factorization with Randomization},
  author = {Maboud Farzaneh Kaloorazi and Jie Chen},
  booktitle = {ICASSP 2020},
  year = {2020}
}