TY - GEN
T1 - A Fast and Accurate Frequent Directions Algorithm for Low Rank Approximation via Block Krylov Iteration
AU - Yi, Qianxin
AU - Wang, Chenhao
AU - Liao, Xiuwu
AU - Wang, Yao
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/5
Y1 - 2020/5
N2 - It is known that frequent directions (FD) is a popular deterministic matrix sketching technique for low rank approximation. However, FD and its randomized variants usually meet high computational cost or computational instability in dealing with large-scale datasets, which limits their use in practice. To remedy such issues, this paper aims at improving the efficiency and effectiveness of FD. Specifically, by utilizing the power of Block Krylov Iteration and count sketch techniques, we propose a fast and accurate FD algorithm dubbed as BKICS-FD. We derive the error bound of the proposed BKICS-FD and then carry out extensive numerical experiments to illustrate its superiority over several popular FD algorithms, both in terms of computational speed and accuracy.
AB - It is known that frequent directions (FD) is a popular deterministic matrix sketching technique for low rank approximation. However, FD and its randomized variants usually meet high computational cost or computational instability in dealing with large-scale datasets, which limits their use in practice. To remedy such issues, this paper aims at improving the efficiency and effectiveness of FD. Specifically, by utilizing the power of Block Krylov Iteration and count sketch techniques, we propose a fast and accurate FD algorithm dubbed as BKICS-FD. We derive the error bound of the proposed BKICS-FD and then carry out extensive numerical experiments to illustrate its superiority over several popular FD algorithms, both in terms of computational speed and accuracy.
KW - Block Krylov Iteration
KW - frequent directions
KW - low rank approximation
KW - randomized algorithms
KW - streaming algorithms
UR - https://www.scopus.com/pages/publications/85089220778
U2 - 10.1109/ICASSP40776.2020.9054022
DO - 10.1109/ICASSP40776.2020.9054022
M3 - 会议稿件
AN - SCOPUS:85089220778
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 3167
EP - 3171
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 -