A Numerical Study of Efficient Sampling Strategies for Randomized Singular Value Decomposition

Siriwan Intawichai, Saifon Chaturantabut

Abstract

The randomized singular value decomposition (rSVD) method is a powerful dimension reduction technique that uses random projection matrices to project the data onto lower dimensional subspace. A crucial step of rSVD algorithm is the sampling process, which will be used further to generate a lowdimensional basis for the subspace of available data. To improve computational performance, this paper incorporates rSVD with different efficient sampling strategies, which include Gaussian sampling, uniform sampling, sparse sampling and sampling with K-mean clustering. The numerical tests compare the accuracy and the execution time used in computing optimal low-rank basis by applying rSVD with each of these sampling methods for an image reconstruction application.