TY - GEN
T1 - Low-Rank Approximation of Matrices Via A Rank-Revealing Factorization with Randomization
AU - Kaloorazi, Maboud Farzaneh
AU - Chen, Jie
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/5
Y1 - 2020/5
N2 - Given a matrix A with numerical rank k, the two-sided orthogonal decomposition (TSOD) computes a factorization A = UDVT, 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.
AB - Given a matrix A with numerical rank k, the two-sided orthogonal decomposition (TSOD) computes a factorization A = UDVT, 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.
KW - image recovery
KW - low-rank approximation
KW - randomized numerical linear algebra
KW - rank-revealing factorization
UR - http://www.scopus.com/inward/record.url?scp=85089240600&partnerID=8YFLogxK
U2 - 10.1109/ICASSP40776.2020.9053528
DO - 10.1109/ICASSP40776.2020.9053528
M3 - 会议稿件
AN - SCOPUS:85089240600
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 5815
EP - 5819
BT - 2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020
Y2 - 4 May 2020 through 8 May 2020
ER -