Shifted Randomized Singular Value Decomposition

Among the typical applications of SVD are the low-rank matrix approximation and principal component analysis (PCA) of data matrices (Jolliffe, 2002). Using SVD to accurately estimate a low-rank factorization or the principal components of a data matrix, a mean-centering step should be carried out before performing SVD on the matrix. Despite its simplicity, the mean-centering can be very costly if the data matrix is large and sparse. This cost is because the mean subtraction of a sparse matrix turns it to a dense matrix which requires a considerable amount of memory and CPU time to be analyzed. This motivates us to extend the randomized SVD algorithm introduced by (Halko et al., 2011) to estimate the singular value decomposition of a mean-centered matrix without explicitly forming the matrix in the memory. More generally, we introduce a shifted randomized SVD algorithm that provides for the SVD estimation of a data matrix shifted by any vector in the ali.basirat@lingfil.uu.se 1 arXiv:1911.11772v2