TY - JOUR
T1 - Efficient Low-Rank Approximation of Matrices Based on Randomized Pivoted Decomposition
AU - Kaloorazi, Maboud F.
AU - Chen, Jie
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020
Y1 - 2020
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 orthogonal, 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. In this paper, we present an algorithm called randomized pivoted TSOD (RP-TSOD), where the middle factor is lower triangular. Key in our work is the exploitation of randomization, and RP-TSOD is primarily devised to efficiently construct an approximation to a low-rank matrix. We provide three different types of bounds for RP-TSOD: (i) we furnish upper bounds on the error of the low-rank approximation, (ii) we bound the k approximate principal singular values, and (iii) we derive bounds for the canonical angles between the approximate and the exact singular subspaces. Our bounds describe the characteristics and behavior of our proposed algorithm. Through numerical tests, we show the effectiveness of the devised bounds as well as our proposed algorithm.
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 orthogonal, 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. In this paper, we present an algorithm called randomized pivoted TSOD (RP-TSOD), where the middle factor is lower triangular. Key in our work is the exploitation of randomization, and RP-TSOD is primarily devised to efficiently construct an approximation to a low-rank matrix. We provide three different types of bounds for RP-TSOD: (i) we furnish upper bounds on the error of the low-rank approximation, (ii) we bound the k approximate principal singular values, and (iii) we derive bounds for the canonical angles between the approximate and the exact singular subspaces. Our bounds describe the characteristics and behavior of our proposed algorithm. Through numerical tests, we show the effectiveness of the devised bounds as well as our proposed algorithm.
KW - dimension reduction
KW - image recovery
KW - low-rank approximation
KW - Matrix decomposition
KW - randomized numerical linear algebra
KW - rank-revealing factorization
UR - http://www.scopus.com/inward/record.url?scp=85086727734&partnerID=8YFLogxK
U2 - 10.1109/TSP.2020.3001399
DO - 10.1109/TSP.2020.3001399
M3 - 文章
AN - SCOPUS:85086727734
SN - 1053-587X
VL - 68
SP - 3575
EP - 3589
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
ER -