Shifted Randomized Singular Value Decomposition
Authors: Ali Basirat
Venue:  (2020)
Keywords: SVD
PCA
Randomized Algorithms

Abstract: 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.

Under review as a conference paper at ICLR 2020
SHIFTED RANDOMIZED SINGULAR VALUE DECOMPO- SITION
Anonymous authors Paper under double-blind review
ABSTRACT
We extend the randomized singular value decomposition (SVD) algorithm (Halko et al. 201T) to estimate the SVD of shifted data matrix without explicitly con- structing the matrix in the memory. With no loss in the accuracy of the original algorithm, the extended algorithm provides for 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 differ- ent types of data matrices, our experimental results confirm the advantages of the extensions made to the original algorithm.
INTRODUCTION
The singular value decomposition (SVD) is one of the most used matrix decompositions in many areas science. Among the typical applications of SVD are the low-rank matrix approximation and principal component analysis (PCA) of data matrices (Joliiffe 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 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 sparse matrix turns it dense matrix which requires considerable amount of memory and CPU time to be analyzed. This motivates us to extend the randomized SVD algorithm introduced by (Halko et al. 201T) to estimate the singular value decomposition of a mean-centered matrix without explicitly forming the matrix in the memory.
More generally, we introduce shifted randomized SVD algorithm that provides for the SVD esti- mation of data matrix shifted by any vector in the eigenspace of its column vectors. The proposed algorithm facilitates the low-rank matrix approximation and the principal component analysis of data matrix through merging the mean-centering and the SVD steps. The mean-centering is crucial to obtain the minimum PCA reconstruction error through deterministic SVD. We experimentally show that it plays essential role in case of using the randomized SVD algorithm too. Our exper- iments with different types of data matrices show that the extended algorithm performs better than the original algorithm when both applied to center-off data matrix.
In the followings, we briefly introduce the principal component analysis and its connection with the singular value decomposition. Then, introduce the shifted randomized SVD algorithm and provide an analysis of its performance. Finally, we report our experimental results obtained from the principal component analysis of different types of data matrices using the extended and the original randomized SVD algorithms.
2 PRINCIPAL COMPONENT ANALYSIS
Principal component analysis (PCA) is method to study the variance of a random vector. PCA projects random vector the eigenspace of its covariance matrix. Let be an m-dimensional random vector with the mean vector O. PCA projects x to a latent random vector y as below:
y A
(1)
where the square matrix is composed of the eigenvectors of the covariance matrix Ex- The elements of y are called the principal components of In many use cases of PCA, contains

---

Under review as a conference paper at ICLR 2020
subset of the eigenvectors of Σx. The minimum PCA reconstruction enror is obtained from the eigenvectors corresponding to the top eigenvalues of the covariance matrix (Jollifee 2002).
The matrix of cigenvectors A in Equation I can be efficiently estimated from the singular value decomposition (SVD) of a sample matrix X. To this end, the sample matrix should be first centered around its mean vector:
X = X =xx1
The fact that the matrix of left singular vectors of is equal to the eigenvectors the covariance matrix of X, the PCA projection of X is:
Y -- SVT
(3)
where X = USVT.
The mean-centering step in Equation 2 can be very costly X is a large sparse matrix and Fx * O. In this case, X is a dense matrix that requires vast amount of memory and cannot be processed in a reasonable time. In the next section, we introduce a randomized SVD algorithm to estimate the SVD of X without explicitly performing the mean subtraction step.
SHIFTED SINGULAR VALUE DECOMPOSITION
Let X be an m X n (m n) matrix and μ be dimensional vector in the space of the column vectors of X. Algorithm | extends the randomized matrix factorization method introduced by Halko (2011) to return a rank-k approximation of the singular value decomposition of the matrix f1 without explicitly forming X. The differences between the extended algorithm and the original one are in lines 6 10 and [2] the followings, we explain the entire algorithm with
a more in-depth focus on the modified parts.
The SHIFTED RANDOMIZED-SV algorithm works in three major steps:
1. Estimate basis matrix for X
2. Project X to the space of the basis matrix
3. Estimate the SVD factors of X from its projection
In the first step (lines 2 to 11 rank K basis matrix Q1 (k < K & m) that spans the column vectors of X is computed. In Line 2 random matrix is drawn from the standard Gaussian distribution. This matrix is then used in Line 3 to form the sample matrix X₁ whose columns are independent random points in the range of X. This sample matrix used estimate basis matrix for X in two steps. In Line 4 basis matrix Q2 is computed through QR oR-facttrizzatin of X1. Since X₃ is sampled from X, the basis matrix considered as an approximation of the basis of X. Then in 6ine the basis of X is estimated from the Q1 by the QR-update algorithm proposed by Golub & Van Loan [996] p. 607). For a given QR factorization such as Q X, and two vectors u, and the QR-update algorithm computes the Oa-tooctrinnation in Equation by updating the already available factors Q1 and Ri.
QR X1 + uo.
The computational complexity of the Qp-ute of the m x K matrix X2 is (m Replacing with - and with 1, the QR-update in Line returns the basis matrix Q that span the range of the matrix
X X 41
(5)
In other words, X can be approximated from Q:
X QQ
(6)
Note that the basis matrix of X is computed without explicitly constructing the matrix X itself. The if statement in Line controls the useless performance of the QR-update step with the null vector.
The for loop starting at Line estimates basis matrix for = (X X
X using the basis of X, Q. The matrix B with positive integer power has the same singular vectors X, but with sharper
'The computational complexity of the QR-update of matrix O(N2) where N max(m, n).
2

---

Under review as a conference paper at ICLR 2020
decay in its singular values since ()) =sy (X))2x+1 where sy()) returns the jth singular vectors of its imput matrix. The sharp decay in singular values improves the accuracy of the randomized SVD when the singular values of X decay slowly. This effect is because the reconstruction error of the randomized SVD is directly proportional to the first top unused singular vector of X (see Equation 12).
The basis of (X is computed via alternative applications of matrix product on X and X. For q - in Line 9 basis matrix of X X is estimated through QR-factorization of X To avoid forming X explicitly, instead of direct multiplication X Q, we use the distributive property of multiplication over addition:
where 1 is a vector of ones. The product 1(2² Q) can be efficiently computed in ((nK) memory space if higher priority is given to the parentheses. In Line I0, basis matrix of X X is esti- mated through QR- OR-factorizztton of XQ' where Q' is basis matrix of XTQ. Similar to Equation the product XQ' is computed as:
XQ' (X ) = XX'-=((('""
with the same amount of memory space, (nnK). The matrix multiplication loop iterates g times. At this stage, we have the basis matrix Q that approximates basis for X.
In the second major step of the algorithm, the matrix X is projected to the space spanned by Q:
Y ==Q²x Q"
This step in done Line 12 using the same trick as in Equation g
Y (x- = x
p17)
(10)
Finally, in the third step, the SVD factors of X are estimated from the K X matrix Y in two steps. First, a rank-k approximation Y computed using a standard method of singular value
decomposition, i.e., Y = UTV (Line 13 Then, the left singular vectors are updated by U
QU, resulting in UEVT QY (Line 14p. Replacing Y with Q X and using Equation 6 (X RM
QQ" X), we have the rank-k approximation of X:
UWV ~
(1I)
Algorithm The rank-k singular value decomposition the m x n matrix X - p11 UEVT with (m < n) using the sampling parameter K (k: < K < m) and E (0, 1,2,.....
1: procedure SHIFTED-RANDON RANDOMIZED- SVD(,, μl, k. K, q)
2: Draw
K standard Gaussian matrix f
3: Form the sample matrix X1 < XΩ
4: Compute the QR factorization X; R1
5:
if μ * then
6:
Compute QR Qi =11 using the QR-update algorithm
7: end if
8:
for i 1,2, .2...... q do Compute the QR- QR-tactorinnnion ='²'==' - - =
9:
Compute the QR-factorination QR XQ'--XX''''XX0 =(11'Q" end for
11:
Form Y + Q pQ"
13:
Compute the singular value decomposition of Y - =U;EVT
14:
U + QU,
15:
return (U, E, V)
16:
end procedure
The shifting vector μ in Algorithm | can be any vector in the space of the column vectors of X. it is set to the null vector O, then the algorithm reduces to the original randomized SVD algorithm of Halko et al. (201T). it is set to the mean vector of X, then the algorithm estimates the singular vectors of the cennecentered matrix X. In this case, the algorithm facilitates the principal compo- nent analysis of a data matrix X through merging the centering step in Equation 2 and the SVD step in Equation 3
3

---

Under review as a conference paper at ICLR 2020
4 PERFORMANCE ANALYSIS
The SHIFTED-RAA RANDOMIZED-SVI algorithm explained in the previous section approximates the SVD of shifted data matrix X = X μ1' without explicitly constructing the matrix in the memory. In this section, we study the performance of the algorithm based on the accuracy and the efficiency of the original randomized SVD algorithm Halko al. (2011).
To estimate the singular value decomposition of a sifted matrix using the original randomized SVD algorithm, X should be explicitly formed and passed to the algorithm. Since SHIFTED- RANDOMIZED-S SV adds no extra randomness to the original algorithm, we have the same re- construction error bound as if the original algorithm factorized the shifted matrix X:
2m k
2641
E||| X USVV [)
+
44
k++1
(12)
where ah+1 is the (k + 1 1)th singular value of the x n matrix X with m Sn 2, k S 2 decomposition rank, and q Z+ is power value explained in Algorithm |
is the
In the followings, we study the computational complexity of the SVD factorization of X using the original randomized SVD algorithm and its extended version in Algorithm [ For an m X n matrix X, the computational complexity of the original randomized SVD algorithm is:
O(ak + (m + n))²
(13)
where a the cost of the matrix vvettor multiplication with the input matrix X. If X is dense matrix then a = mn, and if X is a sparse matrix then a = T, a small constant value.
Algorithm T adds a QR-update step (Line 6 and three matrix-matrix multiplications (lines 10 and 12) to the original algorithm. The matrix multiplications do not affect the computational com- plexity of the original algorithm since their computational complexity equal the complexity of computing Q" X in the original algorithm. The QR-update step, running in O(m)), however, can affect the computational complexity of the algorithm.
Assuming that * O, if both X and X are dense matrices then both algorithms have the same computational complexity as:
O(mnk + (m + +))²²)
(14)
This equality is because the computational complexity of the QR-update step, O(m²). is dominated by the complexity of the original algorithm (i.e., m² < mm for every S where m, n E N). In addition, the construction of X to be use by the original algorithm takes O(mn) time which is greater than or equal to the complexity of the QR-update step. Hence, the added operations do not affect the computational complexity of the original algorithm. Halko et al. (2011) show that for a dense input matrix, the randomized SVD algorithm can be performed in (mmn log + (m + n))?²) if instead of the random normal matrix Q2 in Line a structured random matrix such as the sub-sampe sabbsa random Fourier transform used. This improvement can be considered for the SVD algorithm too.
If the input matrix X is sparse, then X is dense matrix for every μ * 0. In this case, the computa- tional complexity of the RAATFEDD-RADDMIIDE-SSWAS algorithm is:
о m² + (m + n))-²)
(15)
where the constant T is the cost of multiplying sparse matrix to a vector, and the parameter m² is related to the complexity of the Qp-ute step. On the other hand, since X is dense matrix, the complexity of the original algorithm is O(mnk + (m + n)kk) which is higher than the complexity of the extended algorithm.
In a special case where X is a dense matrix and X is sparse matrix, the original algorithm can factorize X in ( + 62))) but SHIFTED- RANDOMIZED-S time. In this case, if Algorithm iis applied to X with μ O, the factorization can be performed in the same processing time as the original algorithm. As a summary, we showed that the SHIFTED- RANDOMIZED- SVD algorithm illustrated in Algorithm i as efficient as the randomized SVD algorithm proposed by Halko et al. (201T) if the input matrix is dense, and more efficient than the input matrix is sparse.
needs O(mnk (m++))43)
4

---

Under review as a conference paper at ICLR 2020
5 EXPERIMENTS
We experimentally study the difference between performing PCA with the randomized SVD algo- rithm (RSVD) proposed by Halko al. (2011) and its extended version in Algorithm [] (S-RSVD). The fact that a minimum PCA reconstruction error is obtained from the deterministic SVD of mean-centered data matrix, the performance of S-RSVD on an off-center data matrix with its mean vector as the shifting vector is expected to be more accurate than the performance of RSVD on the same data matrix. Since the two algorithms are randomized nature, important to test if this expectation is valid for different types of data matrices.
We experimentally compare the two algorithms based on the mean of the squared L2 norm of PCA reconstruction error (MSE). The same parameters K = 2k and g = 0 are used for both S-RSVD and RSVD unless it is clearly mentioned. The shifting vector μ for S-RSVD set to the mean vector of data matrices. The experiments are carried out different types of data matrices including randomly generated data, a set of images, and word co-occurrence matrices. The characteristics of the data matrices are illustrated in the corresponding sections.
5.1 RANDOM DATA
In this section, we examine how the two SVD algorithms are affected by the parameters such as the number of principal components, the size and the distribution of a data matrix, and the power iteration scheme. Our experiments based on two comparison metrics, 1) an MSE value obtained from a fixed number of principal components, and 2) the sum of MSE values obtained from different number of principal components ranging from 100.
Figure la represents the effect of the number of principal components on the MSE values obtained from a 100 x 1000 matrix sampled from -i0deimeniional random vector uniformly distribution in the range O, 1. The results show that mean-centente centering leads to substantial reduction to the reconstruc- tion error when the number of principal components small. This observation is in line with the fact that the contribution of the mean mean-centering is mostly to the accuracy of top principal components.
The effect of the sample size on the two factorization algorithms is represented in Figure Tb in which the X-axis is the sample size and the Y-axis is the sum of the MSE values obtained from different number of principal components ranging from to 100. The data matrices are generated by 100-dimensional uniform random vector in the range 0, 1. The results show that S-RSVD is more accurate and stable than RSVD. Despite the fact that both algorithms are randomized, the stability of S-RSVD is less sensitive to the sample size.
Figure compares the performance of the two algorithms with respect to the data distribution. The Y-axis the sum of MSE values. Reguaddeegs of the data distribution, S-RSVD is more accurate than RSVD. This observation is in line with the fact that PCA does not make any assumption about the data distribution.
To examine whether both algorithms are equally accurate for the factorization of a mean-centered data matrix X, a comparison between the algorithms is provided in Figure 1d The Y-axis is the sum of the MSE values.In In the experiments with RSVD, the matrix X is explicitly constructed and factorized, but in the S-RSVD experiments the singular factors of X are implicitly estimated from X, The results show that S-RSVD is as accurate as RSVD applied to an already centered data matrix X. This observation supports Equation
An important parameter of the randomized SVD algorithm is the power value that has positive effect on the accuracy of the algorithm, Figure the MSE values obtained from each of the factorization algorithms with different values of q. The data matrix in this experiment is sampled from a 100-dimensional uniform distribution. The Y-axis the sum of MSE values and the X-axis represents g. The importance of mean-centering is clear when the value of q is small. The accuracy of RSVD is significantly improved as the values of g increases, while the accuracy of S-RSVD is only slightly improved. This observation
set of uniformly distributed vectors suggest that RSVD with a positive value of q (1 or 2 as suggested by Halko et al. (201T) can be as accurate as S-RSVD.
To test whether RSVD with a large value of can be as accurate as S-RSVD, we run the same experiment as above but on data with different distributions. Ifshhos the difference between
5

---

Under review as a conference paper at ICLR 2020
15
S-RSVD
90
6-RVD
10
RSVD
RSVD
5
5,000
10,000
15,000
20,000
(a)
(b)
10at
S-RSVD
10a
S-RSVD
B RSVD
BE RSVD
102
10a
Laiform
Nomaa
Uniform
Nomual
(c)
(d)
100
S-RSVD
Uniton
90
RSVD
Nummal
-400
Zipf
70
600
Poisson
100
150
(c)
(f)
Figure 1: A comparison between S-RSVD and RSVD based (a) number of principal components, (b) sample size, (c) data distribution, (d) explicit versus implicit mean-centering, (e) the power value q. and (f) the difference of their accuracies with respect to the power value and the data distribution.
the sum of MSE values obtained from each of the algorithms (i.e., Y-axis is MSE-SUM(S-RSVDD (IEESUU((SRRVVD) with respect to the parameter Being all the results negative means that S- RSVD is more accurate than RSVD. Except for the data with Zipfian distribution, the difference between the accuracy of the two algorithms approaches to zero as the value of q increases. The Zipfian graph fluctuates widely for small values of q, but it becomes flat q becomes larger. In the best case, the difference between the two algorithms on Zipfian data is -64 at q = 200. This indicates that the power iteration scheme cannot fully recover the reconstruction loss of an off- center data matrix, but depending the data distribution, it can be helpful. The power iteration Algorithm M computationally heavy step which can negatively affect the efficiency of algorithm when the value of q is large.
5.2
IMAGE DATA
In this section, experiment with handwritten digits and facial image matrices. The handwritten digits are a copy of the test set of the UCI MI. hand-written digits datasets consisting of 1979 images of size 8 We vectorize individual image matrices and stack them into single 16 1979 data matrix. The facial images consisting of 13233 images each of size 250 x 250 are downloaded from Labeled Faces in the Wild (LFW) The facial image matrix after vectorizing and stacking all of the images matrices is 62500 x 13233 matrix.
The left side of Table summarizes the results obtained from (O-dimensional PCA of the image matrices. The MSE values represented in the first two rows of the table show that S-RSVD is more accurate than RSVD. To ensure that the results are not due to chance, we run the experiment 30 times and perform two t-tests with the following null hypotheses:
thereee is no difference between the MSE of S-RSVD and RSVD.
Hhethee is no difference between the individual column reconstruction errors of S-RSVD and RSVD.
iss http:///saaaeaae..aee..cee/ee/ss https://....e..............alaes HandwrittentDion
http://vis-wwr www.:cc...aass.ommmmmmm www.s.

---

Under review as a conference paper at ICLR 2020
image data
word data
digits
faces
1c3
1c4
1c5
n = 3c5
MSE of S-RSVD
415.7
15.3e7
195e
235e
763e 5
994e-5
MSE of RSVD
430.6
16.1e7
200c-5
236e-5
765e-5
998c-5
P1- Pa-velue
0.00
0.00
0.00
0.00
0.00
0.00
Pa-value
0.00
0.00
0.00
0.00
0.00
0.00
WR of S-RSVD
66%
82%
71%
73%
77%
70%
WR of RSVD
34%
18%
29%
27%
23%
30%
Table 1: The reconstruction enror statistics of image and word data.
276
432
397
275
482
434
258
502
671
670
288
453
427
296
493
487
297
521
725
661
+
-
(a)
136e6
131e6
90e6
171e6
213e6
104e6
175e6
148e6
73e6
198e6
157e6
137e6
109e6
181e6
248e6
107e6
202e6
148e6
89e6
214e6
(b)
Figure 2: The effect of mean-centering (a) handwritten digits and (b) facial data. In each sub- figure, the top row is the original image, the rows in the middle and bottom are the S-RSVD and RSVD reconstructed images, respectively. The reconstruction errors are shown on top of each image.
The former hypothesis is validated on the 30 MSE pairs obtained from the SVD methods, but the later hypothesis is validate on the pairs of the reconstruction error of individual images. The p-values represented Table [ reject both hypotheses and confirm that the better results obtained from S- RSVD are not by chance. The rejection of H3 indicates that S-RSVD results in not only lower MSE for the entire image matrices. but also for individual images.
To provide a better picture of how well the SVD algorithms perform on individual images, we plot the first 10 images of each data matrix and estimate the win-rates of the algorithms. Figure shows the examples of the original handwritten and facial images (the top rows), and their reconstructions using S-RSVD (the middle rows) and RSVD (the bottom rows) with the reconstruction error values on top of each image. For most images, S-RSVD is more accurate than RSVD. To generalize this observation, we estimate the win-rate (WR) of the algorithms (i.e., the number of images for which algorithm is more accurate than the other algorithm out of the total number of images). The results shown in Table indicate that 66% the handwritten images and 82% of the facial images reconstructed more accurately by S-RSVD than RSVD.
7

---

Under review as a conference paper at ICLR 2020
5.3 WORD DATA
In this section, we experiment with word probability co-occurrence matrices whose elements are the probability of seeing a target word in the context of another word. Our experiments are based on the word co-occurrences probabilities estimated from the English Wikipedia corpus used in the CoNLL- Shared task 2017 For each target word w,, we estimate the probability of seeing the word conditioned on the occurrence of another word Wy, called the context word (i.e., p(wy wy) Ro n(Me,,0;)
n(wry) The ith column of probability co-occurrence matrix associated with the word wy is distributional representation of the word.
Due to the Zipfian distribution of words and relatively large number of words, a word probability co-occurrence matrix is a large and sparse matrix with a high degree of sparsity. A mean subtraction turns the matrix to dense matrix that needs huge amount of memory and processing time to be analyzed. The SHIFTED-RANDOMZERR RANDOMIZED-SVE algorithm can substantially improve the performance of analyzing a mean-centered co-occurrence matrix.
We estimate 100-dimensional PCA representations of different m X word probability co- occurrence matrices formed with m 1000 most frequent context words and n most frequent target words with different values of n. Each experiment is run 30 times with different random seeds. The right side of Table represents the statistics of the reconstruction errors obtained from each of the factorization algorithms. The first two rows of the table confirm that S-RSVD is more accurate than RSVD. To see whether the difference between MSEs statistically significant, t-test with the null hypothesis H. there is difference between the MSE of S-RSVD and RSVD is performed. Using the 30 pairs of MSE values obtained from each of the factorization algorithms, the test rejects the null hypothesis H. with high confidence level (see Pt Pı-value in Table 1p.
We study the effect of the mean- centercent on the reconstruction of the distributional representation of individual words (i.e., each column of the ro-occurrence matrix). A t-test is performed to validate the null hypothesis H6 Ho:there is no difference between the individual column reconstruction errors of S-RSVD and RSVD. The acceptance probabilities of H3 shown as p2-values in Table 1 confirm that the differences between the reconstruction errors of individual words is indeed significant. The win- rates (WR) of each of the algorithms shows that the mean-centering beneficial the reconstruction of the majority of words.
CONCLUSION
We extend the randomized singular value decomposition algorithm of Halko et al. (201T) to fac- torize shifted data matrix (i.e., a data matrix whose columns vectors are shifted by a vector in their eigenspace) without explicitly constructing the matrix in the memory. With no harm to the performance of the original algorithm on dense matrices, the extended algorithm leads to substantial improvement to the accuracy and efficiency of the algorithm when used for low-rank approximation and principal component analysis of sparse data matrices. The algorithm is tested on different types of data matrices including randomly generated data, image data, and word data, with their mean vector as the shifting vector. The experimental results show that the extended algorithm results in lower mean squared reconstructions error in all experiments through successfully incorporating the mean-centering step to SVD.
REFERENCES
G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore,
MD, USA, third edition, 1996.
N. Halko, P.G. Martinsson, and J.A. Tropp. Finding structure with randomness: Probabilistic al- gorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217-288, 2011.
I.T. Jolliffe, Principal Component Analysis. Springer Series in Statistics. Verlag, 2002.
8


Reviews:
[{"review_id": "rJlncd0aKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper adapts the approach by Halko to get a  SVD using\na low rank concept to the case where the matrix is implicit shifted.\nHonestly - there is nothing wrong with this paper except the level\nof contribution. I consider this work to be widely irrelevant. You\ncan report this on arxiv if you like but I do not think it is important in general.\nThe results show some effect - but not a relevant one. \nFor ICLR this is much to less. And there is not much more to say.\n\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n-----------------------------------------------------------------------------------\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylY8zcy5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nIn Algorithm 1, line 6, I think that one has to subtract not \\mu 1^T but \\mu 1^T \\Omega.\n\nI 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}.\n\nPage 1, line 25: that provides (for) the SVD estimation\nPage 2, line 38: that span(s) the range\nPage 4, line 6: a s(h)ifted matrix\nPage 4, line 29: to be use(d) by the\nPage 5, line 22: uniformly distribut(ion -> ed)\nPage 5, lines 33, 38: Space is missing after the period.\nPage 5, line 43: There is an extra comma.\nPage 5, line 48: suggest(s) that\nPage 6, line 4: approaches (to) zero\nPage 6, line 14: 16 \\times 1979 should read 64 \\times 1979.\nPage 7, line 2: is validate(d)\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eRnOfRYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for performing an SVD on a mean-subtracted matrix without having to actually subtract the mean from the matrix first. \n\nWhile the problem of calculating an SVD is fundamental, the paper’s idea and general problem it covers is a clear mismatch for ICLR in my opinion. The algorithm is an extension of a previous one. Since the idea is very simple, one would expect a lot of theory, but the main theoretical result in Section 4 can be copy-pasted from the previous algorithm since they share the same result. Three sources are cited, indicating either a very narrow view of the field, or overconfidence in the fundamental significance of the contribution.\n\nThe experiments show the technique works as advertised, but the importance of the result is low.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The proposed algorithm is found to be a straightforward extension of the previous work, which is not sufficient to warrant publication in ICLR2020.
Decision: Reject