Block Randomized Singular Value Decomposition on GPUs

Yuechao LU  Yasuyuki MATSUSHITA  Fumihiko INO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.9   pp.1949-1959
Publication Date: 2020/09/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7265
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
randomized singular value decomposition,  GPU,  

Full Text: PDF(1.8MB)>>
Buy this Article




Summary: 
Fast computation of singular value decomposition (SVD) is of great interest in various machine learning tasks. Recently, SVD methods based on randomized linear algebra have shown significant speedup in this regime. For processing large-scale data, computing systems with accelerators like GPUs have become the mainstream approach. In those systems, access to the input data dominates the overall process time; therefore, it is needed to design an out-of-core algorithm to dispatch the computation into accelerators. This paper proposes an accurate two-pass randomized SVD, named block randomized SVD (BRSVD), designed for matrices with a slow-decay singular spectrum that is often observed in image data. BRSVD fully utilizes the power of modern computing system architectures and efficiently processes large-scale data in a parallel and out-of-core fashion. Our experiments show that BRSVD effectively moves the performance bottleneck from data transfer to computation, so that outperforms existing randomized SVD methods in terms of speed with retaining similar accuracy.