We extend the randomized singular value decomposition (SVD) algorithm (Halko et al., 2011) to estimate the SVD of a shifted data matrix without explicitly constructing the matrix in the memory. With no loss in the accuracy of the original algorithm, the extended algorithm provides for a more efficient way of matrix factorization. The algorithm facilitates the low-rank approximation and principal component analysis (PCA) of off-center data matrices. When applied to different types of data matrices, our experimental results confirm the advantages of the extensions made to the original algorithm.
This paper extends the existing randomized SVD algorithm by Halko et al. to propose a shifted randomized SVD algorithm. The proposed algorithm performs randomized SVD on \bar{X}=X-\mu 1^T with a given constant vector \mu without explicitly constructing \bar{X} from X.
The proposed algorithm seems to be a straightforward modification of the randomized SVD algorithm, so that the contribution of this paper would be incremental. Also, the claimed benefits of the proposed method are better accuracy, less memory usage, and less computational time. On memory usage and computational time, however, I could not find any experimental comparison in Section 5. At least in Section 5.3 where the data matrix is indeed sparse, there should be some comparison in these respects. Because of these reasons, I would not be able to recommend acceptance of this paper.
In Algorithm 1, line 6, I think that one has to subtract not \mu 1^T but \mu 1^T \Omega.
I guess that equation (12) comes from Theorem 1.2 in Halko et al. (2011). An explicit citation should be needed here to put an appropriate credit to that paper. Also, the conditions under which equation (12) holds should be explicitly stated. In fact, Theorem 1.2 in Halko et al. is about the expected reconstruction error with rank-2k factorization obtained by randomized SVD, which is not consistent with the authors claim in page 3, lines 4-5: The first top unused singular value is not \sigma_{k+1} but \sigma_{2k+1}.
Page 1, line 25: that provides (for) the SVD estimation
Page 2, line 38: that span(s) the range
Page 4, line 6: a s(h)ifted matrix
Page 4, line 29: to be use(d) by the
Page 5, line 22: uniformly distribut(ion -> ed)
Page 5, lines 33, 38: Space is missing after the period.
Page 5, line 43: There is an extra comma.
Page 5, line 48: suggest(s) that
Page 6, line 4: approaches (to) zero
Page 6, line 14: 16 \times 1979 should read 64 \times 1979.
Page 7, line 2: is validate(d)