Parallelizing Randomized Singular Value Decomposition using GPUs

Parallelizing Randomized Singular Value Decomposition using GPUs is Available on Medium

Singular value decomposition is among the most powerful and widely used matrix decompositions in applied linear algebra. Though useful for extracting key features and patterns from data (e.g. Principal Component Analysis) it quickly becomes challenging to execute this algorithm on increasingly large matrices.

Randomized numerical linear algebra offers an interesting approach to this efficiency problem by positing a randomized singular value decomposition algorithm (Halko et al. (2009)). Theoretically, much like the approximation of pricing functionals from mathematical finance, this becomes an approximate decomposition with numerical error constrained using ideas from high dimensional geometry and measure theory (e.g. concentration of measure). Discussion of measure theory is beyond the scope of this article, perhaps it will be the subject of another — though I have a hard time believing I can explain it better than Terence Tao.

This article serves three purposes…

- Intuitively motivate the singular value decomposition (SVD)

- Intuitively explain the randomized singular value decomposition (rSVD)

-Exhibit parallelization as further means of speeding up rSVD