Fast Updating Truncated SVD for Representation Learning with Sparse Matrices
Authors: Haoran Deng
Yang Yang
Jiahe Li
Cheng Chen
Weihao Jiang
Shiliang Pu
Venue: ICLR 2024 poster (2024)
Keywords: Singular value decomposition; Sparse matrix; Unsupervised learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We propose a fast algorithm for updating truncated SVD in sparse matrix.

Abstract: Updating truncated Singular Value Decomposition (SVD) has extensive applications in representation learning.
The continuous evolution of massive-scaled data matrices in practical scenarios highlights the importance of aligning SVD-based models with fast-paced updates.
Recent methods for updating truncated SVD can be recognized as Rayleigh-Ritz projection procedures where their projection matrices are augmented based on the original singular vectors.
However, the updating process in these methods densifies the update matrix and applies the projection to all singular vectors, resulting in inefficiency.
This paper presents a novel method for dynamically approximating the truncated SVD of a sparse and temporally evolving matrix.
The proposed method takes advantage of sparsity in the orthogonalization process of the augment matrices and employs an extended decomposition to store projections in the column space of singular vectors independently.
Numerical experimental results on updating truncated SVD for evolving sparse matrices show an order of magnitude improvement in the efficiency of our proposed method while maintaining precision comparing to previous methods.

Published as a conference paper at ICLR 2024
FAST UPDATING TRUNCATED SVD FOR REPRESENTA- TION LEARNING WITH SPARSE MATRICES
Haoran Deng', Yang Yang'; Jiahe Cheng Chen', Weihao Jiang', Shiliang Pu² 'Zhejiang University, "Hikvision Research Institute
[denghaoran, yangya, jiahel i ez juz www.juedd.c.. (chencheng16, jiangweihao5, pushiliang
ABSTRACT
Updating truncated Singular Value Decomposition (SVD) is crucial in represen- tation learning. In practice, when dealing with evolving large-scale data matrices, aligning SVD-based models with fast-paced updates becomes critically impor- tant. Existing methods for updating truncated SVDs employ Rayleigh- pro- jection procedures, where projection matrices are augmented based on original singular vectors. However, these methods inefficient due the densification of the update matrix and the application of the projection to all singular vectors. To overcome these limitations, we introduce a novel method for dynamically ap- proximating the truncated SVD of sparse and temporally evolving matrix. Our approach leverages sparsity in the orthogonalization process of augmented ma- trices and utilizes an extended decomposition to independently store projections in the column space of singular vectors. Numerical experiments demonstrate the efficiency of our method is improved by order of magnitude compared to pre- vious methods. Remarkably, this improvement is achieved while maintaining a comparable precision to existing approaches. Codes are available"
INTRODUCTION
Truncated Singular Value Decompositions (truncated SVDs) are widely used various machine learning tasks, including computer vision (Turk & Pentland, 1991). natural language process-
ing (Deerwester et al. 1990: Levy & Goldberg 2014), recommender systems (Koren et al., 2009) and graph representation learning (Ramasamy & Madhow/ 2015 Abu-El-Haija et al.) [202] I] Cai
iet al. 20022). Representation learning with a truncated SVD has several benefits, including the absence of gradients and hyperparameters, better interpretability derived from the optimal approx- imation properties, and efficient adaptation to large-scale data using randomized numerical linear
algebra techniques (Halko et al. 2011 Ubaru et al.. 2015 Musco & Musco 2015).
However, large-scale data matrices frequently undergo temporal evolution in practical applications. Consequently, imperative for a representation learning system that relies on the truncated SVD of these matrices to adjust the representations based on the evolving data. Node representation for a graph, for instance, can be computed with a truncated SVD of the adjacency matrix, where each row in the decomposed matrix corresponds to the representation of a node (Ramasamy & Madhow 2013). When the adjacency matrix undergoes modifications, is necessary to update the correspond- ing representation (Zhu al. 2018 Zhang al., 2018 Deng et al. (023). Similar implementations exist in recommender systems based on the truncated SVD of an evolving and sparse user-item rat- ing matrix (Sarwar al. 2002 Cremonesi al. 2010 Du et al. 2015 Nikolakopoulos al. 2019). This requirement for timely updates emphasizes the significance of keeping SVD-based models in alignment with the ever-evolving data.
Over the past few decades, methods recognized as the Rayleigh- -itz projection process (Zha & Si- mon 1999, Vecharynski & Saad 2014; Yamazaki et al. 2015 Kalantzis et al. 202T have been widely adopted for their high accuracy. Specifically, they construct the projection matrix by aug- menting the columns of the current singular vector an orthonormal matrix that roughly captures
"Corresponding author htags://gthuu.cc///nn//////////

---

Published as a conference paper at ICLR 2024
the column space of the updated singular vector. Notably, the augmentation procedure typically thickens sparse areas of the matrices, rendering the inefficiency of these algorithms. Moreover, due to the requirement of applying the projection process to all singular vectors, these methods become impractical in situations involving frequent updates or using only a portion of the representations in the downstream tasks.
In this paper, we present novel algorithm for fast updating truncated SVDs in sparse matrices. Contributions.
We study the orthogonalization process of the augmented matrix performed in an inner product space isometric the column space of the augmented matrix, which can take advantage of the sparsity of the updated matrix to reduce the time complexity. Besides, we propose an extended decomposition for the obtained orthogonal basis efficiently update singular vectors.
2. We propose an algorithm for approximately updating the rank-k truncated SVD with theoretical guarantee (Theorem []. which runs at the update sparsity time complexity when considering k and s (the rank of the updated matrix) as constants. We also propose two variants of the algorithm that can be applied to cases where s large.
3. We perform numerical experiments on updating truncated SVDs for sparse matrices in various real-world scenarios, such as representation learning applications in graphs and recommendations The results demonstrate that the proposed method achieves a speed improvement of an order of magnitude compared to previous methods, while still maintaining a comparable accuracy.
BACKGROUND AND NOTATIONS
The singular value decomposition (SVD) of an m-by-n real data matrix A is denoted by A UEV", where U E R=""" V E R="x" are orthogonal and Σ E Rm** is rectangular diagonal with non-negative real numbers sorted across the diagonal. The rank-k truncated SVD of A is obtained by keeping only the first & largest singular values and using the corresponding k columns of U and V, which is denoted by Eg V (V).
In this paper, we consider the problem of updating the truncated SVD of a sparse matrix by adding new rows (or columns) and low-rank modifications weights. Specifically, when a truncated SVD of data matrix A E Rm*x is available, our goal is to approximate the truncated SVD of the new data matrix A with addition of rows E, E R=*= (or columns E, E m=x*)) or low-rank modifications D., E R Em Rexn to A.
A A = E
A = [A E,], or A A
In several related works, including Zha-Simon's. ss key issue often revolves around the optimization of the QR decomposition of (I - U B matrix. Specifically, given an orthonormal matrix Uk and a sparse matrix B, we refer to (I U B as the Augmented Matrix with respect to Uk. where its column space orthogonal Us.
Notations. In this paper, we use the lowercase letter æ, bold lowercase letter æ and bold uppercase letter X to denote scalars, vectors, and matrices, respectively. Moreover, mmz(X) denotes the number of non-zero entries in a matrix, X denotes the updated matrix, X₃ denotes the rank-k approximation of matrix, and range( X) denotes the matrix's column space. A table of notations commonly used in this paper is listed in Appendix B
2.1 RELATED WORK
Projection Viewpoint. Recent perspectives (Vecharynski & Saad 2014 Kalantzis al.) 2021 frame the prevailing methodologies for updating the truncated SVD as instances of the Rayleigh- Ritz projection process, which can be characterized by following steps.
1. Augment the singular vector Ux and V3 by adding extra columns (or rows), resulting in Ū and V. respectively. This augmentation is performed so that range(Ü) and range(V) can effectively approximate and capture the updated singular vectors' column space.
2

---

Published as a conference paper at ICLR 2024
2. Compute Fk, O₁ G2 = SV ATV)).
3. Approximate the updated truncated SVD by U., Ok: VG..
Zha-Simon's Scheme. For A = U T. let (I U E. QR. where Q's columns are orthonormal and R is upper trapezoidal. Zha & Simon (999) method updates the truncate SVD after appending new columns E, E Rmxx to E Ik I by
A
Ak
Ec
U QI
Ex
U E R
T
r (IU Q) 2)
V2
Gk)
(I)
U Ee
where Fs, O: G5:- SVD&(
The updated approximate left singular vectors, sin-
R
gular values and right singular vectors [Ux Fz. Ok
V2
r
GR. respectively.
When it comes to weight update, let the QR-decomposition of the augmented matrices be (I
U QDRD and (I V Em QERg, then the update procedure
Σx 0
U Dm RD
V. Em Re
A A Em T
UU) Qdl
+
[v
Qel
(2)
(UR QDI
O QE G
Ex 0 +
U Dm
V Em.. Rø
where FR. A G2 = S
). The updated approximate trun-
0
RD
cated SVD is [Ux QD! Fx, O VV QEl GR.
Orthogonalization of Augmented Matrix. The above QR decomposition of the augmented matrix and the consequent compact SVD is of high time complexity and occupies the majority of the total time when the granularity of the update is large (i.e., $ is large). To reduce the time complexity, series of subsequent methods have been developed based on a faster approximation of the orthogo- nal basis of the augmented matrix. /eecarynski & Saad (2014) used Lanczos vectors conducted by Golub-Kahan Lanczos (GKL) bidiagonalization procedure to approximate the augmented matrix. Yamazaki et al. (2015) and Ubaru & Saad (2019) replaced the above GKL procedure with Random-
ized Power Iteration (RPI) and graph coarsening, respectively. Kalantzis al. (202T) suggested
determining only the left singular projection subspaces with the augmented matrix set as the identity matrix, and obtaining the right singular vectors by projection.
METHODOLOGGY
We propose algorithm for fast updating the truncated SVD based the Rayleigh-Ritz projection paradigm. In Section 3.I we present a procedure for orthogonalizing the augmented matrix that takes advantage of the sparsity of the updated matrix. This procedure is performed in an inner product space that is isometric to the augmented space. In Section 3.2] we demonstrate how to utilize the resulting orthogonal basis to update the truncated SVD. We also propose extended decomposition technique to reduce complexity. In Section 3..3 we provide a detailed description of the proposed algorithm and summarize the main findings in the form of theorems. In Section 3.4 we evaluate the time complexity of our algorithm in relation to existing methods.
3.1 FASTER ORTHOGONALIZATIIO OF AUGMENTED MATRIX
In this section, we introduce an inner product space that is isomorphic to the column space of the augmented matrix, where each element tuple of sparse vector and low-dimensional vector. The orthogonalization process in this space can exploit sparsity and low dimension, and the resulting orthonormal basis is bijective to the orthonormal basis of the column space of the augmented matrix.
Previous methods perform QR decomposition of the augmented matrix with QR = (I-U,U )B to obtain the updated orthogonal matrix. The matrix Q derived from the aforementioned procedure not only orthonormal, but its column space also orthogonal to the column space of U,. implying that matrix (Ux Q) is orthonormal.

---

Definition 1 (SV-LCOV), Let UR E Rmnk be an arbitrary matrix satisfying U Us I, and let b E T be sparse vector. Then, the SV-LCOV form of the vector z U }b is tuple denoted as (b, U) where c c= U b. Published as a conference paper at ICLR 2024
Let Z = (I - be the augmented matrix, then each column of Z can be written as a sparse m- nn-dimensiinal matrix of column vectors minus a linear combination of the column vectors of the m-by-k orthonormal matrix UR i.c., 2; b, UzC[i.. We refer to the form of sparse vector minus a linear combination of orthonormal vectors as SV-LCOV, and its definition is follows:
Converting columns of an augmented matrix into SV-LCOV is efficient, because the computation of U can be done by extracting the rows of Uy that correspond to the nonzero elements of and then multiplying them by b.
Lemma 1. For an orthonormal matrix Us E mx with U U* I, turning UU }b with sparse vector b Ihm into SV-LCOV be done in time complexity of O mnz(b)).
Furthermore, we define the scalar multiplication, addition and inner product (i.e., dot product) of SV-LCOV and show in Lemma that these operations can be computed with low time complexity when b is sparse.
Lemma 2. For an orthonormal matrix UR E TR mRak with Ug U² I, the following operations of SV-LCOV can be done the following time.
Scalar multiplication: a(b, c)u,, (ab, ac)u, in ((nmz(b) + k) time.
Addition: (1,Cc))s + (b2, C2)U, = (b) + b2, ei + 02)u,, in O(nmz(b; + b2) + k) time.
Inner product: ((b), Ci)... (b2, c2) = (b,, b2) - (ci, C2) in O(nnz(b; + b2) + k) time.
With the scalar multiplication, addition and inner product operations of SV-LCOV, we can further study the inner product space of SV-LCOV.
Lemma 3 (Isometry of SV-LCOV). For an orthonormal matrix Us E R. with U. I, let B pmxx be arbitrary sparse matrix with the columns of B [b,.... b.), then the column space of UUU B is isometric to the inner product space of their SV-LCOV.
The isometry of an inner product space here is a transformation that preserves the inner product, that in SV-
thereby preserving the angles and lengths in the space. From Lemma we LCOV, since the dot product remains unchanged, the orthogonalization process of an augmented matrix can be transformed into orthogonalization process in the inner product space.
As an example, the Modified Gram-Schmidt process (i.e. Algorithm T is commonly used to com- pute orthonormal basis for a given set of vectors. It involves series of orthogonalization and normalization steps to produce a set of mutually orthogonal vectors that span the same subspace as the original vectors. Numerically, the entire process consists of only three types of operations in Lemma 2 so we can replace them with SV-LCOV operations to obtain a more efficient method (i.e. Algorithm
Algorithm 1: Modified Cram-Schmidt
Algorithm 2: SV-LCOV's QR process
Input: x U E B
Input: E E R m= Us E RO
Output: Q E maxs R E I2*x
Output: B Rmmx C RAx*
R R
Q [I U² E:
B <- E. C U E;
for 1 to do
for to do
- V.q.q.))
3
a V b.) - (c), Cili
R.;
R., ta;
qi q:/a;
5
b: + bb/a, c: + ci/o;
for j = i to
6
for j = =it 1 do to
3 + (q:q:);
7
8 + (b. by)
(c,, ci);
R. + 3:
R.i - B;
g, 9, Bq
b, + b, Bb. C₁ +- C, Bci
10
end
10
end
end
end
12 return Q = (q..... q.l, R
return Q = [ (1b,,c)),,,... (b,, c, Co)u,,
4

---

Published as a conference paper at ICLR 2024
Lemma 4. Given an orthonormal matrix U3 E R= satisfying U.U Uk I, there exists algorithm that can obtain a orthonormal basis of a set of SV-LCOV {(b), ei)u (b,, C,)u,, in O (
k)s²) time.
Approximating the augmented matrix with SV-LCOV. The Modified less efficient when is large. To this end, Vecharynski & Saad (2014) and Yamazaki al. (2015) approximated the orthogonal basis of the augmented matrix with Golub-Kahan-I Lanczos bidiagonal- (Zation(GKI.) procedure (Golub & Kahan 1965) and Randomized Power Iteration (RPI) process. We find they consists of three operations in Lemma 2 and can be transformed into SV-LCOV to improve efficiency. Limited by space, we elaborate the proposed algorithm of SV-LCOV approxi- mation to the augmented matrix in Appendix D.I and Appendix D.2 respectively.
process is
3.2 AN EXTENDED DECOMPOSITION TO REDUCING COMPLEXITY
Low-dimensional matrix mutliplicationn and sparse matrix addition. Suppose an orthonormal basis (b1, C1 C,),,= ..... (b,, Cs)U, of the augmented matrix in the SV-LCOV is obtained, according to Definition [ this orthonormal basis corresponds to the matrix B U&C where the i-th column of B is b; Regarding the final step of the Rayleigh- Ritz process for updating the truncated SVD by adding columns, we have the update procedure for the left singular vectors:
Un + UUx Q Fx Us Fa kj + [k :k:
F& k] + (B [.
(F&
CF& :]) + BF
where Fil: k] denotes the submatrix consisting of the first &o rows of Fu, and F& [k :] denotes the submatrix consisting of rows starting from the (A + 1)-th rows of Fk.
Equation 3 shows that each update of the singular vectors UR consists of the following operations:
1. A low-dimensional matrix multiplication to UR by a k-by-k matrix (F& k] [. :))-
2. A sparse matrix addition to UR by sparse matrix B BF [k: :] that has most nnz (B): k non-zero entries. While F& [k :] may appear relatively dense in the context, considering it as a sparse matrix during the process of sparse matrix addition ensures asymptotic complexity.
An extended decomposition for reducing complexity. truncated SVD as product of the following five matrices:
To reduce the complexity, we write the
U Ukik Σaxk ViRT VHT
(4)
with orthonormal U U" UU" and V' V" (but not V or V"), that is, the singular vectors will be obtained by the product of the two matrices. Initially, U" and V are set by the k-by- k identity matrix, and U' V' are set as the left and right singular vectors. Similar additional decomposition was used in Brand (2006) for updating of SVD without any truncation and with much higher complexity. With the additional decomposition presented above, two operations can be performed to update the singular vector:
- KJ :)
(5)
T U-U+ BFx UF :J
which is a low-dimensional matrix multiplication and a sparse matrix addition. And the update of the right singular vectors
Vx
= Ve G
[ Galk:
V
G
+]+
(6)
I
where GEl= kt] denotes the submatrix consisting of the first k rows of G and G& [k :] denotes the submatrix cosisting of rows starting from the (k: + 1)-th rows of GR. Now this can be performed as
V V G2|:: k]
Append matrix G [k: :IV to V
Above we have only shown the scenario of adding columns, but a similar approach can be used to add rows and modify weights. Such extended decomposition reduces the time complexity of
5

---

Published as a conference paper at ICLR 2024
updating the left and right singular vectors, allowing them to be deployed to the large-scale matrix with large m and n. In practical applications, the aforementioned extended decomposition might introduce potential numerical issues when the condition number of the matrix is large, though in most cases these matrices have relatively low condition numbers. One solution to this issue is to reset the k-by-k matrix to the identity matrix.
3.3 MAIN RESULT
3 and Algorithm 4 are the pseudocodes of the proposed algorithm for adding columns and modifying weights, respectively.
Algorithm
Algorithm 3: Add columns
Algorithm 4: Update weights
Input: (U", ), En, Vi(V', V"),
Input: (U' ), Ex. Ve(V', V"), Du. E.m
Turn (I UR E. into SV-LCOV and get
Turn (I U ) into SV-LCOV and get
QB, C), with Algorithm 2
QD BD: CD). ; RD with Algorithm 2
U
E.
Turn (I V4 Vg Em into SV-LCOV and get
Fr, Ox, G. < {
):
R
Qe Bg, Cε); Re with Algorithm
U" + (F
CF
[K
:));
3 Fa, En, Ga
U' + U'+ U' BF k JU"
Σn
0
U Dm
V. Em
Σx Os: A;:
SVD
+
RD
RÆ
)
V" + V. k]:
U" UF kj
F
:]):
Append new columns Gik :] V to V
s U <- U" B'+BnD :J-!!:
E. <- O2:
. V" + V" |: k
CEG lk: :)):
V t V + BB :
The time complexity of the proposed algorithm in this paper is summarized in Theorem | and detailed examination of the time complexity is provided in Appendix F
Theorem (Main result). There data structure for maintaining an approximate rank-k trun- cated SVD of A E mmxx with the following operations in the following time.
A
Add rows E,): Update UR, Ex. V& < +VVD
in O(nnz(E,)) + k)² + (s + +))3) time.
E,
Add columns E.): Update Uk, Ek, Vz +- >VD time.
As E. in ((nzz (E.) k)2 (s k)3)
Update weights( Dm, Emn): Update Uv, Ex. V (A + D Em T) O(nnz D,,. + Em)(s + k)² + (s + k))) time.
(i): Return U [i] (or Vi(i)) and Eg in O(k2) time.
where A V and is the rank of the update matrix.
Remark 1. Please note that we uses As the best rank-k approximation of A, rather than the original A matrix as the starting point of the updating process. Therefore, the update here may not obtain the updated best rank-k approximation of the new matrix.
The proposed method can theoretically produce the same output as Zha Simon (1999) method with much lower time complexity.
The proposed variants with the approximate augmented space. To address updates with coarser granularity (i.e., larger s), we propose two variants of the proposed algorithm based on approximate augmented spaces with GKL and RPI (see section 1 SV-LCOV, denoted with the suffixes -GKL. and -RPI, respectively. The proposed variants procude theoretically the same output Vecharynski & Saad (2014) and Yamazaki et al. (2015), repectively. We elaborate the proposed variants in Appendix D.3

---

Published as a conference paper at ICLR 2024
Table 1: Time complexity comparing to previous methods
Algorithm
Asymptotic complexity
Kalantzis et al. 2021
mm + k2 mn=(A)k (k + s)k²
Zha & Simon 1999
(m + n2)k nks ns (k s)3
Vecharynski & Saad
22144
(m + n))² nkl + +)
Yamazaki ct al.
(0155)
(m + +0=
nnz + +k
ours
ours- GKL
mn² + (
ours ours-RPI
nn: (E) + nnz BD +
1)2
3.4 TIME COMPLEXITY COMPARING TO PREVIOUS METHODS
presents the comparison of the time complexity of our proposed algorithms with the pre- vious algorithms when updating rows E E Rax., To simplify the results, we have assumed s < n and omitted the big-O notation. / denotes the rank of approximation in GKL and RPI. denotes the number of iteration RPI performed.
Table.
Our method achieves a time complexity of ((nn((E)) for updating, without any O(n) or (m)) terms when and A are considered as constants (i.e., the proposed algorithm is at the update sparsity time complexity). This because SV-LCOV is used to obtain the orthogonal basis, eliminating the (n) or (m) terms when processing the augmented matrix. Additionally, our extended decompo- sition avoids the ((n) or O(m) terms when restoring the SV-LCOV and eliminates the projection in all rows of singular vectors. Despite the time complexity of the query increases from O(k) to Olk²), ) this trade-off remains acceptable considering the optimizations mentioned above.
For updates with one coarse granularity (i.e. larger 8), the proposed method of approximating the augmented space with GKL or RPI the SV-LCOV space eliminates the squared term of in the time complexity, making the proposed algorithm also applicable to coarse granularity update.
NUMERICAL EXPERIMENT
In this section, we conduct experimental evaluations of the update process for the truncated SVD on sparse matrices. Subsequently, we assess the performance of the proposed method by applying it to two downstream tasks: (1) link prediction, where we utilize node representations learned from an evolving adjacency matrix, and (2) collaborative filtering, where we utilize user/item representations learned from an evolving user-item matrix.
4.1 EXPERIMENTAL DESCRIPTION
Baselines. We evaluate the proposed algorithm and its variants against existing methods, includ- ing Zha & Simon (1999). Vecharynski & Saad (2014) and Yamazaki et al. (2015). Throughout the experiments,
set I, the spatial dimension of the approximation, to 10 based on previous set- tings (Vecharynski & Saad 2014). The required number of iterations for the RPI, denoted by t, is set 3. In the methods of Vecharynski & Saad (2014) and Yamazaki al.] (2015). there may be differences in running time between 1) directly constructing the augmented matrix, and 2) accessing the matrix-vector multiplication as needed without directly constructing the augmented matrix. We conducted tests under both implementations and considered the minimum value as the running time.
Tasks and Settings. For the adjacency matrix, we initialize the SVD with the first 50% of the rows and columns, and for the user-item matrix, we initialize the SVD with the first 50% of the columns.
The experiment involves & batch updates, adding n/o rows and columns each time for 2n-sized adjacency matrix. For user-item matrix with 2n columns, n/ columns are added per update.
Link Prediction aims predicting whether there is link between given node pair. Specifically, each node's 's representation is obtained by a truncated SVD the adjacency matrix. During the inference stage, first query the representation obtained by the truncated SVD of the node pair

---

Published as a conference paper at ICLR 2024
Zha Simon (1999)
Vecharynski Saad (2024)
Yamazakd et (2015)
Slashdot
Flickr
Epinions
10"
1.20
255
Figure 1: Computational efficiency of adjacency matrix when l is 16, 32, 64, 128, 256
Slashdot
Flickr
Epinions
32"
-2.
10
127
327
32"
Figure Computational efficiency of adjacency matrix when @ is 10², 102, 10 104
(i,1). A score is then performed, representing the inner product between pairs of nodes
U ΣVis
make predictions. Maximum value both directions taken for undirected graphs. sort the scores in the test set and label the edges between node pairs with high scores positive ones. Based previous research, we create the training set G' by randomly removing 30% of the edges from the original graph G. The node pairs connected by the eliminated edges are then chosen, together with an equal number of unconnected node pairs from to create the testing Eistt
Collaborative Filtering in recommender systems is technique using a small sample of user preferences to predict likes and dislikes for a wide range of products. In this paper, we focus on predicting the values of the normalized user-item matrix.
In this task, a truncated SVD is used to learn the representation for each user and item. And the value is predicted by the inner product between the representation of i-th user and j-th item with
Uli EV
The matrix is normalized by subtracting the average value of each item. Values in the matrix are initially divided into the training and testing with ratio of 8
Datasets. The link prediction experiments are conducted on three publicly available graph datasets, namely Slashdot (Leskovec et al., 2009) with 82, 168 nodes and 870, 161 edges, Flickr (Tang & Liu 2009) with 80, 513 nodes and 11, 799, 764 edges, and Epinions (Richardson et al., (003) with 75, 879 nodes and 1, 017, 674 edges. The social network consists of nodes representing users, and edges indicating social relationships between them. In our setup, all graphs are undirected.
For the collaborative filtering task, we use data from MovieLens (Harper & Konstan 2015). The MovieLens25M, dataset contains more than 2, 500, 000 ratings for 62, 423 movies. According to the selection mechanism of the dataset, all selected users rated least 20 movies, ensuring the dataset's validity and a moderate level of density. All ratings the dataset are integers ranging from 1 to 5.
4.2 EFFICIENCY STUDY
To study the efficiency of the proposed algorithm, we evaluate the proposed method and our opti- mized GKL and RPI methods in the context of link prediction and collaborative filtering tasks.
Experiments are conducted on the undirected graphs of Slashdot (Leskovec et al., 2009), Flickr (Tang & Liu 2009), and Epinions (Richardson et al. (203)) to investigate link prediction. The obtained results are presented in Table 2
Fig. [ and Fig. 2 Our examination metrics for the
Efficiency section include runtime and Average Precision (AP) which is the percentage of correctly predicted edges in the predicted categories to the total number predicted edges. Besides, we report the Frobenius norm between the Ug E, V. and the train matrix. The results demonstrate
8

---

Published as a conference paper at ICLR 2024
Table 2: Experimental results adjacency matrix
Slashdot
Flickr
Epinions
Method
Norm
AP
Norm
AP
Norm
AP
7ha & Simon 1999
792.11
93.40%
2079.23
95. 15.1%%%
1370.26
95.62%
Vecharynskı & Saad (2014)
792.01
93.56%
2079.63
95.11%
1370.64
95.70%
Yamazaki et al. (2015
792.11
93.52%
2079.28
95.14%
1370.29
95.61%
ours ours-GKL ours-RPI
792.11
93.41%
2079.23
95.166 95.16%
1370.26
95.62%
792.01
93.56%
2079.63
95.11%
1370.64
95.70%
792.11
93.50%
2079.28
95.
1370.29
95.61%
Table 3: Experimental results of user-item matrix
Batch Update
Streaming Update
Method
Runtime
MSE
Runtime
MSE
Zha & Simon 1999
192s
0.8616
626s
0.8616
Vecharynski & Saad 2014
323s
0.8646
2529s
0.8647
Yamazaki al. 2015
278s
0.8618
352s
0.8619
A= 16
23s
0.8616
35s
0.3616
ours-GKL ours-RPI
18s
0.8646
48s
0.8647
45s
0.8618
43s
0.8619
Zha & Simon 1999
343s
0.8526
2410s
0.8527
Vecharynski Saad 2014
124s
0.8572
3786s
0.8568
Yamazaki 2013
313s
0,8527
758s
0,8528
k=
498
0.8526
7358
0.8527
ours-GKL ours burs-RPI
0.8572
147s
0.8568
98s
0.8527
141s
0,8528
that across multiple datasets, the proposed method and its variants have demonstrated significant increases in efficiency without compromising AP, reducing time consumption by more than 85%.
Table 3 demonstrates the results of four experiments conducted for the collaborative filtering task: 16 and A: 64. Our
batch update(á = 2000) and streaming update( = #entries) with evaluation metrics include runtime and mean squared error (MSE). The results show that our method significantly reduces runtime while maintaining the comparable accuracy. It is difficult for existing methods update large and sparse datasets, especially streaming updates, making real-time updates challenging. The methodology employed in our study effectively decreases the runtime by a factor of 10 more.
4.3 VARYING K AND
We conduct link prediction experiments on three datasets for l and Φ, aiming to explore the selection of variants and approaches in various scenarios. The results in Fig. [ show that our optimized methods are significantly faster than the original ones for different choices of k. The performance of all methods slows as k increases, which is consistent with the asymptotic complexity in Table [
We experimentally evaluate the performance of each method for different batch sizes Φ. As shown Fig. [ our methods (ours-GKL and ours-RPI) outperform others when large number of entries are updated simultaneously. Experimental results show that the efficiency of approximating the augmented space improves significantly when s larger. Therefore, choosing the proposed variants (GKL or RPI) for larger is recommended.
5 CONCLUSION
In conclusion, introduce novel algorithm along with two variants for updating truncated SVDs with sparse matrices. Numerical experiments show a substantial speed boost our method com- pared to previous approaches, while maintaining the comparable accuracy.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work supported by Zhejiang NSF (LR22F020005).
REFERENCES
Sami Abu-EI-Haija, Hesham Mostafa, Marcel Nassar, Valentino Crespi, Greg Ver Steeg, and Aram Galstyan. Implicit svd for graph representation learning. Advances in Neural Information Pro- cessing Systems, 34:8419-8431, 2021.
Matthew Brand. Fast low-rank modifications of the thin singular value decomposition. Linear algebra and its applications, 415(1))00-30, 2006.
Xuheng Cai, Chao Huang, Lianghao Xia, and Xubin Ren. Lightgel: Simple yet effective graph contrastive learning for recommendation. In The Eleventh International Conference on Learning Representations, 2022.
Paolo Cremonesi, Yehuda Koren, and Roberto Turrin. Performance of recommender algorithms on top-n recommendation tasks. In Proceedings of the fourth ACM conference on Recommender systems, pp. 39-46, 2010.
Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. Indexing by latent semantic analysis. Journal of the American society for information science, 41 (6):391-407, 1990.
Haoran Deng, Yang Yang, Jiahe Li, Haoyang Cai, Shiliang Pu, and Weihao Jiang. Accelerating dynamic network embedding with billions of parameter updates milliseconds. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 414-425, 2023.
Nan Du, Yichen Wang, Niao He, Jimeng Sun, and Le Song. Time-sensitive recommendation from recurrent user activities. Advances in neural information processing systems, 28, 2015.
Gene Golub and William Kahan. Calculating the singular values and pseudo-inverse of matrix. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis, (2):205-22) 2244, 1965.
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53 (2):217-288, 2011.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (Tis), 1(4):19:1-19:19, 2015. doi: 10.1145/ 2827872.
Vasileios Kalantzis, Georgios Kollias, Shashanka Ubaru, Athanasios N Nikolakopoulos, Lior Horesh, and Kenneth Clarkson. Projection techniques to update the truncated svd of evolving matrices with applications. In International Conference Machine Learning, pp. 5236-5246.
PMLR, 2021.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-33 2009.
Leskovec, Lang, Dasgupta, and M. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1): 29-123, 2009.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 27, 2014.
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances neural information processing systems, 28, 2015.
10

---

Published as a conference paper at ICLR 2024
Athanasios N Nikolakopoulos, Vassilis Kalantzis, Efstratios Gallopoulos, and John D Garofalakis. Eigenrec: generalizing puresvd for effective and efficient top-n recommendations. Knowledge and Information Systems, 58:59-81, 1199-81,220 81,2019 2019.
Dinesh Ramasamy and Upamanyu Madhow. Compressive spectral embedding: sidestepping the svd. Advances in neural information processing systems, 28, 2015.
M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In ISWC, 2003.
Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Incremental singular value decom- position algorithms for highly scalable recommender systems. In Fifth international conference on computer and information science, volume 1, pp. 27-8. Citeseer, 2002.
Lei Tang and Huan Liu. Relational learning via latent social dimensions, In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 817-826, 2009.
Matthew Turk and Alex Pentland. Eigenfaces for recognition. Journal of cognitive neuroscience, (1):71-86, 1991.
Shashanka Ubaru and Yousef Saad. Sampling and multilevel coarsening algorithms for fast matrix approximations, Numerical Linear Algebra with Applications, 26(3):e2234, 2019.
Shashanka Ubaru, Arya Mazumdar, and Yousef Saad. Low rank approximation using error correct- ing coding matrices. In International Conference on Machine Learning, pp. 702-710, PMLR, 2015.
Eugene Vecharynski and Yousef Saad. Fast updating algorithms for latent semantic indexing. SIAM Journal on Matrix Analysis and Applications, 35(3): 105-1131, 2014.
Ichitaro Yamazaki, Jakub Kurzak, Piotr Luszezek, and Jack Dongarra. Randomized algorithms update partial singular value decomposition on a hybrid cpu/gpu cluster. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-12, 2015.
Hongyuan Zha and Horst D Simon. On updating problems in latent semantic indexing. SIAM Journal on Scientific Computing, 21(2):782-777 1999.
Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang, and Wenwu Zhu. Timers: Error-bounded svd restart on dynamic networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Dingyuan Zhu, Peng Cui, Ziwei Zhang, Jian Pei, and Wenwu Zhu. High-order proximity preserved embedding for dynamic networks. IEEE Transactions Knowledge and Data Engineering, 30 (11):2134-2144, 2018

---

Published as a conference paper at ICLR 2024
A REPRODUCIBILITY
We released the implement all the algorithms involved in the experiment as a python package. The code is available at: https//ggitub.com//june///ssssss code, which includes python implementations of methods involved in the experiment, as well as the datasets. The code is available at http:///gtttbbcoooooommooooooolt
We also make public experimental
B NOTATIONS
Frequently used notations throughout the paper are summarized in Table
Table 4: Frequently used notations
Notation
Description
A
The data matrix
E.
The update matrix (new columns)
Er
The update matrix (new rows)
Dm, Em
The update matrix (low rank update weight)
I
The identity matrix
U
The left singular vectors
E
The singular values
V
The right singular vectors The (left) augmented matrix
II U
[ V
The (right) augmented matrix The number of rows and columns of data matrix The rank of truncated SVD The rank of update matrix
m, n
k
The rank of approximate augmented space The number of Random Power Iteration performed
X
matrix with rank
The transpose matrix X
X
A rank-k approximation of X
The updated matrix of
|00
12-norm of
(00, (222
Dot product bewteen 21, 22 rank-k truncated SVD of X
(X)
C
OMITTED PROOFS
Proof of Lemma
Proof. We prove each of the three operations as follows.
Scalar multiplication. It takes ((nnz(b) time get ab and O(k) time to get oc, respectively.
Therefore the overall time complexity for scalar multiplication is O(nnz(b) + k)).
Addition. It takes (mnzz (bi) ====)b)) = (nnz(bi + b2)) time to get b + b2 and ( time get e₁ + C2. respectively. Therefore the overall time complexity for addition O(nnz(b; + by) + k).
Inner product. It takes ((nnz(b,) + nn=(b²)) = ((nzz(b + b²)) time to get (b, by) and O(k) time get (2), respectively. Therefore the overall time complexity for inner product is (bi + b2) + k).
12

---

Published as a conference paper at ICLR 2024
Proof of Lemma 3
Proof. Each of the three operations of SV-LCOV can correspond to the original space as follows.
Scalar multiplication.
alb, c)u, = (ab, ac)u, (ab) Uk ob) a(II )b
(8)
Addition.
(bi, + (b2, c2)u, = (b) + b2. ci + 02)u,
(b) b2) - U (ci + C2)
(9)
b U&U
ba U&U, c2
(I ULU bb, + + U-UU bb2
Inner product.
((b1, ci).. (b2, c2)u,)
(b). b2) (2)
bj b2 cl C2
bj b2 b. U. b.
bi b2 2b U&U, b2 + U,U
(10)
b, ba 2b U2U, b U,U
(b) b, U,U, (b2 (b2 U.U,
((I (
((I U,U (I U,U
Proof of Lemma
Proof. An orthogonal basis can be obtained by Algorithm 2 and we next analyze the time complex- ity of Algorithm 2
Because the number of non-zero entries of any linear combination of a set of sparse vectors (b,, b2,...,,b,, b with size at most | nnz(b;; the number of non-zero entries of the sparse vector (b) in each SV-LCOV during the process of Algorithm 2 are at most nn= bi).
There total of Oss²) projections and subtractions of SV-LCOV in Algorithm 2 and by Lemma the overall time complexity is O(nn= b,) + k)s²).
Proof of Theorem
Proof. The output of proposed method is theoretically equivalent the output of Zha Simon 1999). and the detailed time complexity analysis is given in Appendix F
13

---

Published as a conference paper at ICLR 2024
D APPROXIMATING THE AUGMENTED SPACE
D.1 APPROXIMATING THE AUGMENTED SPACE VIA GOLUD-KAIANN-ANCZOO PROCESS
Algorithm 5: GKL.
Algorithm GKI. with SV-LCOV
Input: R Ug IRink I
N+
Input: E R UR RmxE .E N
Output: Q E Raxi E Raxi
Output: Raxi
Rexi P E Rext
Z + (I U )E;
B t E, C Up E;
Choose p1 E IR., /Pill 1. Set 8o 00
2 Chouse C |pi = 1. Set 80 = 0;
for 1,..., do
for i l..... do
q: - Zp: Bi-19:-13
4
by f- P. b.) 3 -1.
a; + 9:11:
c/ + (E,P.t)] ca) 31-10-11
+ q:/aci
t [V, b.) (c)c.);
P.+1 t Z a:p::
7
b + b//ai
Orthogonalze p++ against pp]]
c 4//a;
3. p
Pi+1 + B B C ci appi:
10
P++1 P Bi
Orthogonalze p.+1 against (pi.... p.]:
end
8. + 1pi+1 ||:
P
[p Pp..... Pi+1];
13 H
diag O1y,. Oit) supediaag/1t.... B.]:
12
Pi+1 pi+1/B:
end
P
P H
Pi+1 = pp..... pt+1];
15 return (q).... q P
1s H diag (ai ..., an) + superdiag (B1..., B.):
- P
return Q (B',C"),
A step-by-step description. Specifically, the Zp; in Line 4 of Algorithm can be viewed linear combination of SV-LCOV with Line and Line 5 in Algorithm 6 The 12 norm of qi in Line 5 of Algorithm
5 is the length of SV-LCOV and be transformed into the inner product in Line
6 of Algorithm Line of Algorithm is scalar multiplication corresponding to Line and Line of Algorithm And the Z q, in Line 7 of Algorithm can be recongnized as the inner product
between SV-LCOV demonstarted in Line 9 of Algorithm
Complexity analysis of Algorithm 6 Line 4, 5 run in O((n=a(E) + k)sl) time. Line 6 runs in ( - k) time. Line 7, 8 run in ((nnz EE + k))) time. Line 9 runs in O E k))s) time. Line 10 runs in (sl?) time. Line 11, 12 run (ss)) time. Line 14, 15, 16 run in (ss?²) time.
The overall time complexity of Algorithm is O(nz + k)sl) time.
D.2 APPROXIMATING THE AUGMENTED SPACE VIA RANDOM POWER ITERATION PROCESS
Algorithm 7: RPI
Algorithm 8: RPI with SV-LCOV
Input: E E mmxs Us E mm I N+
Input: E E R Up Ro Output: Q Ruxi P n
,1, E
Output: Q E maxi
Raxi
Z + (1 (1- U,U E
+ E, C+ E;
Choose
xx with random unitary columns;
2 Choose P E B with random unitary columns:
for i = 1..... L do
3 for = 1,..., L do
P. R < QR(P);
B', C' < BP, CP:
BP.CP:
Q - Z P:
5
B', C" R QR with Algorithm
Q. R QR(Q):
P, + QR(P):
P QQ
P- B' CTC.
7
end
end
return Q P
9 return Q = CB',
Complexity analysis Algorithm Line 1 rums in O(nna(E)k) time. Line 4 runs in O((nz((B) E) k)slt) time. Line 5 runs in O(mz(E)) + k)(2t) time. Line runs in O(sl2t)
14

---

Published as a conference paper at ICLR 2024
time. Line 7 runs in (((nn((E) + kttt) time. The overall time complexity of Algorithm g (((mz((E) + (sl + Ptt + mnz(E)
D.3 THE PROPOSED UPDATING TRUNCATED SVD WITH APPROXIMATE AUGMENTED MATRIX
Algorithm Add columns with approxi- mated augmented space
Algorithm 10: Update weights with approx-
imated augmented space
Input: UR (U',,, J. Es. Vi(V. V"), E
Input: UT" ), Ds. Vo(V', V"), D, E
Turn (I U E SV-LCOV and get
Turn (I U ) into SV-LCOV and get
QBB, C), P with Algorithm or
8
QD Cp). ) PD with Algorithm 6
Σ
U
2 Turn V E into SV-LCOV
gel
FE. O2, G. (
P
QE. BE, CE): PE with Algorithm 6 or
U" + [FA
CF
:)::
Fr. ER. Gk
U' U" BF JU"-
SVDA Σn
U +
VT E
):
5 EN + Or:
PD
PB
V" + V
U UF
F
[k
:)):
Append new columns G[k V to V
U +BBBB :U"-!:
6 Σx 0x:
V" (" k) CgGA :)):
8 V' + V' + & :U
15

---

Published as a conference paper at ICLR 2024
E EXPERIMENTS
E. RUNTIME OF EACH STEP
We present the runtime analysis of each component in the experiments, specifically focusing on the verification of ø using the Slashdot datasets. Since all the baselines, well the proposed method, can conceptualized as three-step algorithm outlined in Section [.1] we provide an illustration of the runtime for each step. Specifically, we break down the entire algorithm into three distinct steps: the stage before the execution of the compact SVD, the actual execution of the compact SVD, and the segment after the execution of the compact SVD. The experimental results are depicted in Figure 3
Step-1
Step-2
Step-3
0=10
==10
==100
==10000
800
200
Runtimals)
3000
150
2000
200
100
400
1000
100
50
Zha & &imoon (1999)
ours
2ha Simon (1999)
ours
Zha & &.mmann (1999)
aurs
Zha Simon
curs
(1999)
14
60
1200
Runtmelss
10
40
800
150
30
600
6-
100
2-
10-
200
Vecharyncki ours-GKI Saad (2014)
Vecharynski (2014)
Vecharynski (2014)
Vecharynski ours-GKL Saad (2014)
60
1000
40
200
Runtimets)
30
40
600
20
30
100
50
200
10
Yamazaki (2015)
Yamazaki
Yamazaki
ours-RPI
Yamazaki (201.5)
Figure 3: Runtime of each step on the Slashdot dataset.
Compared to the original methods, the proposed methods take approximately the same amount of time to execute the compact SVD. This similarity arises because both the proposed and original methods involve decomposing a matrix of the same shape. Furthermore, as the value of Φ increases and decreases, the proportion of total time consumed by step-2 (compact SVD) increases. This trend suggests a more significant improvement efficiency for step-1 and step-3 of the algorithm.
The proposed method mainly focuses on time complexity in step-1 and step-3, respectively bene- fiting from the structure of SV-LCOV described in Section 3.1 and the extended decomposition in Section 3.2 The optimization in the first step more pronounced when ó is larger (i.e., when is smaller). This is due to the fact that in the SV-LCOV framework, the sparse vectors have fewer non- rows when is smaller. This reduction in
consequence of fewer columns
16

---

Published as a conference paper at ICLR 2024
in the matrix E, resulting in more significant efficiency improvements through sparse addition and subtraction operations.
Furthermore, when ò is smaller and is larger, the utilization of the proposed variant method, which involves approximating the basis of the augmented space instead of obtaining the exact basis, tends to yield greater efficiency.
E.2 EXPERIMENTS ON SYNTHETIC MATRICES WITH DIFFERENT SPARSITY
We conduct experiments using synthetic matrices with varying sparsity levels (i.c., varying the num- ber of non-zero entries) to investigate the influence of sparsity on the efficiency of updating the SVD. Specifically, we first generate several random sparse matrices with fixed size of 100,000 x 100,000. The number of non-zero elements in these matrices ranges from 1,000,000 to 1,000,000,000 (i.e.. density from 0.01% to 10%). We initialize a truncated SVD by utilizing a matrix comprised of the initial 50% of the columns. Subsequently, the remaining 50% of the columns are incrementally inserted into the matrix in é batches, with each batch containing an equal number of columns. The number of columns added in each batch is denoted as s. The experimental results are shown in Figure
(1999)
Vecharynski (2014)
(2015)
$=10 10
104
102
10
Timels)
Timale)
10a
10a
100
10a
10a
10'
10
10a
10
10a
10a
10
per
per
$=100
$=1000
10a
10a
Timeet)
Timets)
102
10
10a
101
10a
109
10a
10'
10'
10
10
10"
10a
10*
nnz per row
0nz per row
Figure 4: Computational efficiency synthetic matrices
Experimental results under various s values show that: 1) The proposed method exhibits greater efficiency improvement when the matrix is relatively sparse. 2) When the rank of the update matrix higher, the variant using Lanczos vectors for space approximation achieves faster performance.
E.3 EFFECTIVENESS
We report the Frobenius norm beteween 2 V and original matrix in the Slashdot datasets and MovieLen25M datasets in Table 5 Our proposed approach maintains a comparable precision to baselines.
17

---

Published as a conference paper at ICLR 2024
Table 5: Frobenius norm w.r.t @
Slashdot
MovieLen25M
Method
Φ 10
Ø = 10a
103
Φ == 10
Φ = 10a
Φ = 10
Zha & Simon (1999)
784.48
792.16
792.11
4043.86
4044.23
4044.40
Vecharynski Saad (2014)
802.61
796.26
792.01
4073.41
4111.66
4050.53
Yamazaki et al. (2015)
796.97
795.94
792.11
4098.87
4098.62
4047.87
ours
784.48
792.16
792.11
4043.86
4044.23
4044.40
ours-GKL ours-RPI
802.85
795.65
792.01
4076.61
4110.71
4050.36
796.65
795.19
792.11
4099.11
4099.09
4047.20
F TIME COMPLEXITY ANALYSIS
A line-by-line analysis of time complexity for Algorithm 3 due the extended decomposition, the time complexity converting the augmented matrix into SV-LCOV is ((nnz(E)k*) instead of ((nnz(E)k).
10 is given below. Note that
Table 6: Asymptotic complexity of Algorithm
Asymptotic complexity (big notation is omitted)
Line 1
nnz Ek2 s2) nn= (E) k22 (k s)
Line 2
Line 3
333 + k2
Line 4
nmz E k2) + 3
Line 5
Line 6
k3
Line 7
k + k
Overall
nnz (E: + s)² + (k 8)3
Table 7: Asymptotic complexity of Algorithm
Asymptotic complexity (big-O notation is omitted)
Line
nnz (): + s2)
Line 2
nnz E (K2 + +2)
Line 3
nnz D + k + (k + s)3
Line
1.3
k2s
Line 5
nmz D (ks + k2) k3
Line 6
k
Line 7
1:3 + k:2
Line 8
nna (k + 22) k
Overall
nnz + E) (k + 3) + (le + s)²
18

---

Published as a conference paper at ICLR 2024
Table 8: Asymptotic complexity of Algorithm
Asymptotic complexity (big-O notation is omitted)
Line I (GKL)
nnz E + nnz E + k)sl
Line 1 (RPI)
(nna (E) + (sl + 12) (n)
Line 2
(k s) 1)2
Line 3
k3 + 12
Line 4
nnz E) + k2)
Line 5
k
Line 6
k3
Line 7
k2 I k3
Overall (GKL.)
nnz (1) + al + kl) + (k:
8k + 1)2 (k +k
Overall (RPI)
nnz (n) + (2) nn
Table 9: Asymptotic complexity of Algorithm
Asymptotic complexity (big-O notation is omitted)
Line 1 (GKL)
nnz D k + mna + k)sl
Line 1 (RPI)
(nnx(D) + (s] (D)
Line 2 (GKL)
nnz E) + n
Line 2 (RPI)
(nn= (E)
+ mnn E
Line 3
nnz
+ E) + (k 1)3
Line 4
ha + 121
Line 5
nmz
(kl + k2) + k
Line 6
k
Line 7
133 + 1.21
Line 8
nnz ( + k.))
+ 1.
Overall (GKL)
nnz + E) sl + kl) + (k: (k 1)2
Overall (RPI)
-D + s) +)²
nnz (sl
G ALGORITHM OF ADDING ROWS
Algorithm 11: Add rows
Input: (U" U", Ex, Vi(V', V"), E,
Turn (I V.VV.) E. into SV-LCOV and get Q(B, C), R with Algorithm 2
Σx
Fr, O2, G2 <- SVD&
R ):
E. V2
U" < F- k);
Append new rows Flk - to U':
Ei f- O::
V" + VG CG [k: :)):
V' V +BG [
19


Reviews:
[{"review_id": "IpAcXjA1Ze", "reviewer": "Reviewer_An3v", "summary": "This manuscript proposes a scheme for computing the QR factorization of a matrix of the form $(I-UU^T)B$ for a sparse $B$ that is more efficient than the naive approach. The scheme is then used within existing schemes for updating truncated SVDs to accelerate them.", "questions": "In section 3.2, why is $BF_k[k:]$ sparse? in general the singular vectors in $F$ will not be sparse so the product likely is not as well. I guess this sort of depends on if the sparsity of $B$ is assumed to be $\\mathcal{O}(n)$ (i.e., a few non-zeros per row) or $\\mathcal{O}(s)$ (i.e., a few non-zeros per column). In the former case the product is not sparse and in the latter it is. This should be made more clear.\n\nTruncated SVD of what in equation (4)? This is not clear from the text as written. Also, how is the decomposition into, e.g., $U'$ and $U''$ done? That is also not made clear. Even if there are details in the reference it is not clear how that is used here. Maybe cite a specific algorithm or technique from that work.\n\n- What is meant buy \"approximate\" in Theorem 1? This seems too ambiguous a phrase for a theorem statement and it does not seem to be well defined anywhere.\n\n- Why Gram-Schmidt and not modified Gram-Schmidt? and are there any potential numerical issues, e.g., if columns of $B$ are nearly perpendicular to the span of $U_k$?\n\n- In the comparisons with prior work how is the QR factorization of $(I-U_kU_k^T)E$ (for example) computed? is a built in routine used or GS? There are benefits to being able to use standard libraries that could make understanding the tradeoffs more complicated/nuanced.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The manuscript identifies a place for improvement (in specific settings, see the weaknesses section) within existing algorithms for updating truncated SVDs and implements an updated orthogonalization routine that accelerates them. Numerical experiments show the potential efficacy of the scheme.", "weaknesses": "This manuscripts largest weakness (and a significant one) is its lack of clarity in many respects. This spans the interplay with existing algorithms, the contribution, in what setting the proposed method is faster, and more. While the former two points could be addressed (though the manuscript does need significant reworking), the clarity around the appropriate settings for the algorithms, and therefore the contribution, is much less clear. This is most easily shown by illustration:\n\nTo choose one of the settings, let's consider updating (i.e., adding) columns to $A.$ In this case a QR factorization of $(I-U_kU_k^T)E$ is desired. The manuscript assumes $E$ is sparse, however the improvement is actually in a narrower regime. If $E$ has a constant number of non-zeros per row then nnz(E) is $\\mathcal{O}(n)$ and the algorithms discussed in the manuscript are no more efficient than just forming $E - U(U^TE)$ and computing the dense QR factorization $\\mathcal{O}(ns^2)$. So, the only setting of interest is if $E$ has a constant number of non-zeros per column, i.e., $\\mathcal{O}(s)$ non-zeros. In this setting relatively few rows of $A$ receive updates. I don't know which setting is more/less common, but the manuscirpt lacks a clear articulation of such tradeoffs (including in the numerical experiments). This weakens the manuscript and makes it hard to understand what settings it applies to.\n\nSimilarly, it is not clear that most of section 3.1 is necessary. Bluntly it seems like an overly complicated build up of a simple choice. Considering the above setting, if $E$ has a constant number of non-zeros per column then why not just compute the Cholesky factorization $E^TE-(E^TU_k)(U_k^TE) = RR^T$ (which is \\mathcal{O}(s^3) under this sparsity assumption) and then store the QR factorization as $(I-U_kU_k^T)(ER^{-1})$ (again, computing $ER^{-1}$ via triangular solves is only $\\mathcal{O}(s^3)$ given the sparsity). Note that these all could be written with nnz(E), but again this is all only needed if nnz(E) is substantially less than $n.$ The method already implicitly assumes $U_k$ is stored as part of the process. In some sense this is what the manuscript proposes, but with what feels like an unnecessary amount of machinery that obscures the message. (Also, use of Cholesky would likely be faster since standard libraries could be used throughout). Moreover, given this simple interpretation it is not clear that Theorem 1 is particularly novel or interesting.\n\nRelated to the above points, the numerical experiments would be stronger if they were more clearly designed to show the tradeoffs between methods (e.g., using some synthetic examples where the sparsity can be controlled) rather than just \"plausible\" situations. The former actually seems more important since the accuracy should be the same. The key is to show when to use which method base on, e.g., the sparsity of $E.$ The numerical experiments are not illuminating in this regard.\n\nWhile there is clearly effort in blending these ideas into prior work and building the numerical experiments (and therefore some contribution), ultimately the manuscript does not do a good job clearly articulating what this is. This is compounded by a lack of clarity in many places.   \n\nAssorted minor comments:\n\n- Maybe it would be better to use different notation for the row, column, and low-rank updates to $A$ (i.e., not always using $E$). This can actually get confusing when thinking about dimensions of the appropriate projections.\n\n- Equation (3) has a typo, it should be $U_kC.$\n\nThe paper has numerous grammatical mistakes and typos, for example in the title, abstract, and first paragraph of the intro:\n\n- in the title what is \"in sparse matrix\"? The statement does not make sense, is it supposed to be \"with sparse matrices\"?\n\n- abstract: \"updating truncated singular value decomposition\" -> \"updating a truncated singular value decomposition\"\n\n- abstract: \"Numerical experimental results on updating truncated SVD for evolving sparse matrices\" -> Numerical experiments updating a truncated SVD for evolving sparse matrices \n\n- abstract: \"maintaining precision comparing\" -> \"maintaining precision comparable\"\n\n- intro P1: \"Truncated Singular Value Decomposition (truncated SVD) is widely used in various machine...\" -> \"Truncated Singular Value Decompositions (SVDs) are widely used in various machine...\"\n\n- intro P1: \"learning with truncated SVD benefits...\" -> \"learning with a truncated SVD benefits\"\n\n- intro P1: \"interpretability provided by optimal Frobenius-norm\" is not a cogent statement about the SVD; maybe what is meant is \"interpretability because of its optimal approximation properties\"? or similar?\n\n- intro P1: \"data under randomized\" -> \"data using randomized\"\n\nAccordingly, the manuscript would greatly benefit from a careful editing pass to address these issues (as they continue throughout the manuscript).\n\n**Update after author response**\n\nI would like to thank the authors for their thoughtful replies to my concerns and those of other reviewers.\n\nWhile some of the responses do help highlight the scope of the contribution (e.g., in terms of how to think of nnz(E)), this is not really reflected in the manuscript. Saying “input sparsity” time is fine in places, but it is more useful to follow up and contextualize that statement in terms of the sparsity of the update. This does not really seem present in the updated manuscript. \n\nNevertheless, my overall opinion of the manuscript remains essentially unchanged (I have slightly updated my score, though the unallowable 4 would more accurately reflect my current opinion). There is a (somewhat narrow, but perhaps sufficient) contribution and it might be a good fit for certain applications. However, the presentation of the manuscript is still lacking and that significantly blunts any contribution. Numerous grammatical errors remain, Theorem 1 is still not sensibly stated (i.e., Definition 2 does not actually fix my concern and “approximate” is still ambiguously defined) to be a sound theoretical result, Section 3.1 could be more simply presented, and there remain aspects of the manuscript that are unclear (some of which are new additions). E.g., the paragraph above Alg 1 and 2 is not incorrect (i.e., it refers to the old version, Appendix E.2 doesn’t even say what the experiment is (updating rows, updating columns, updating weights, …), In Section 3.3 there is an incorrect algorithm reference, which makes Appendix F unclear (is the complexity of add columns or add rows analyzed), and more.\n\nLastly, on a technical note, while the use of MGS as suggested addresses one type of potential numerical issue (i.e., if $B$ lies close to the column space of $U_k$), it does not address potential issues encountered by the persistent decoupled storage of vectors in the sparse + low-dimensional subspace. This may or may not be problematic. Hence, while Cholesky QR is also often ill-advised, it is not clear it is worse in this setting (and given some of the condition numbers reported later likely fine for the simple tasks).", "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": "", "extra_scores": {}}, {"review_id": "nEJ9OUgWEE", "reviewer": "Reviewer_jDYv", "summary": "This paper presents a method for updating the truncated singular value decompositions for sparse updates. The \"trick\" of this paper is a \"sparse vector minus a linear combination of orthonormal vectors\" representations, which is used to represent the orthogonalization of the newly inducted rows or columns against an existing basis of singular vectors. Numerical experiments show that the proposed methods leads to order-of-magnitude speedups for stylized machine learning tasks.", "questions": "### Typos and Minor Issues\n\nThere are small typos throughout, and I encourage the authors to reader their paper carefully to catch all of them. Here were a few that I happened to document:\n\n- On the top of pg. 3, $U_kU_k$ and $V_kV_k$ should have transposes on the second factors.\n- \"Orthogonalization\" is misspelled in a section header on page 3.\n- There's a typo in (3): the middle line should have $U_kC$ not $U_k^\\top C$.\n- There are inconsistencies in typesetting. E.g., some A's are set in upright bold font and others are in slanted bold font.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper proposes a simple and natural idea. The truncated SVD is a useful computational tool in data analysis, and the proposed approach is a natural and effective way of updating the approximation under sparse updates of the matrix. The numerical experiments are reasonably convincing, and they demonstrate a large speedup over existing approaches.", "weaknesses": "This paper has two weaknesses I would like to discuss: issues of writing and grammar and potential numerical instabilities. I believe that the first of these can be addressed by revisions, and the second of these is an inherent (potential) limitation of the method that deserves a brief discussion by the authors in a revision. \n\n### Writing\n\nThis paper has several issues with writing and presentation.\n\nThroughout, there are issues of grammar and English usage. The issues are numerous, but here are a few examples that stand out:\n\n- The title and the first sentence of the abstract do not parse as grammatically correct.\n- Several key phrases are ungrammatical: in many places, \"truncated SVD\" should be replaced by \"_the_ truncated SVD\" (e.g., \"updating truncated SVD\" should be \"updating _the_ truncated SVD\"). The \"augment matrix\" should be \"augmented matrix\". \"Augment procedure\" should be \"augmentation procedure\". Etc.\n- There are other grammatical issues. For instance, consider the following sentence: \"A series of methods that can be recognized as an instance of Rayleigh-Ritz projection has become a mainstream method owing to its high precision.\" The verb \"has\" should be changed to \"have\" as the subject of the sentence \"series of methods\" is plural. Similarly, \"its\" should be \"their\". Even with grammatical fixes, the sentences are difficult to read. A better version of the sentence would be as follows: \"In the past twenty-five years, Rayleigh-Ritz projection methods have become the standard methods for updating the truncated SVD, owing to their high accuracy.\"\n\nThe grammatical issues are serious enough to make the paper more difficult to read and understand. I recommend the authors do thorough revisions of their paper to improve the grammar and English usage.\n\nThere are also structural and clarity issues with the writing. Again, there are many issues, of which we highlight a few:\n\n- The phrase, \"augment matrix\" (which should be changed for grammar to \"augmented matrix\") appears in section 1 before that term is defined or even the problem stated.\n- The authors state that they provide \"RPI and GKL\" variants of their algorithm in section 3.3, but these acronyms were defined only briefly earlier in section 3.1—a section I skimmed on my first reading. A backward reference GKL and RPI, e.g., \"(see section 3.1)\" would help readers.\n- The precise meaning of isometric in lemma 3 is unclear.\n- As far as I can tell, the average precision metric is never defined.\n\nThe paper could benefit from reorganization to improve the narrative and sequencing of ideas.\n\nLastly, there's an issue of framing of the truncated SVD updating problem. In section 2, the present the problem they're solving as \"approximating the truncated SVD of $\\overline{A} = [A,E]$\". However, the problem that is really being solved is to compute (exactly) the truncated SVD of $[\\hat{A},E]$, where $\\hat{A} = U\\Sigma V^\\top \\approx A$ is the truncated SVD of $A$. The original Zha–Simon procedure is very clear about this distinction, writing\n\n> Notice that in all the above three cases instead of the original term-document matrix $A$, we have used $A_k$, the best rank-$k$ approximation of $A$ as the starting point of the updating process. Therefore, we may not obtain the best rank-$k$ approximation of the true new term-document matrix.\"\n \nI think the authors would benefit from this level of clarity about exactly what problem they are solving.\n\nOverall, this paper would be greatly improved by rewriting to improve grammar and clarity.\n\n### Numerical Stability?\n\nThere are several aspects of the current proposal that are concerning from the standpoint of numerical stability. The proposed orthogonalization procedure uses the Gram–Schmidt process, which is well-known to suffer from potentially significant loss of orthogonality. Additionally, the updating rules decompose a matrix $U_k$ with orthonormal columns are the product of two matrices, both of which could become significantly ill-conditioned and resulting in stability degradations.\n\nAssuming these stability issues are real, they are intrinsic limitations to the method; it's very unclear how these issues could be addressed while maintaining the method's competitive runtime. The numerical results suggest that the method is stable enough to remain useful for some data analysis tasks. I would like to see the authors comment on numerical stability in any revised version, just to mention this as a potential issue with the method.", "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": "", "extra_scores": {}}, {"review_id": "H8FDiAlRUZ", "reviewer": "Reviewer_YLvs", "summary": "This paper presents a new algorithm to update the truncated SVD of a dynamical matrix (new rows, columns, and/or entries). \nThe algorithm is similar to that of previous algorithms published in the literature. The main innovation seems to be a new data \nstructure that allows a more efficient handling and processing of intermediate matrices (by essentially not forming them explicitly).", "questions": "-) It seems that GKL helps the algorithm proposed by the authors but does not help the method of Vecharynski (in terms of performance). What is the exact process followed when applying GKL to the latter? How is the method of Vecharynski slower for smaller values of k (k=16 versus k=64)?  \n\n-) I am a bit puzzled since the new method replicates existing methods but is an order of magnitude faster. Is this really because of the data structure?\n\n-) Upon inspecting the code, I see that the authors form the matrix ‘X’ explicitly when running the methods of Vecharynski and Yamazaki. This implementation is quite inefficient and now I understand better why the new method is that much faster. While for the method of Zha and Simon I can understand forming ‘X’ explicitly (even then it can be implemented more appropriately though) there is absolutely no reason to form ‘X’ for GKL (or randomized SVD) since the main advantage of GKL is that it can be applied to implicitly-defined matrices. Forming ‘X’ creates a huge dense matrix that is a) expensive to apply, b) expensive to store in system memory. For large problems, one might have to store ‘X’ on secondary memory, leading to quite high wall-clock time execution such as the ones I see in this submission. All numerical experiments concerning timings must be performed from scratch using commonly accepted principles of implementing numerical algorithms. \n\nAlso, the code would be benefit tremendously by adding comments.\n\n-) The method of Zha and Simon should be more accurate than the algorithms of Vecharynski and Yamazaki, yet it seems that all three methods basically give the same accuracy. One reason for that is when ‘l’ is too large. What are the results when ‘l’ is smaller? \n\n-) At the beginning of page 7, the paragraph “As a result...” is a bit strange. Is any text missing? \n\n-) “trunacated” -> “truncated” \n\n-) Finally, a general comment: \"In Table 1, the method of Kalantzis et al. depends on nnz(A) because the matrix A is fetched at the end of each update to compute the right singular vectors in a least-squares sense. The method can be asymptotically more expensive but it is also more accurate.\"\n\nUpdate after response:\nI have altered my score.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-) All concepts and ideas are clear and the paper is not verbose. Codes and appendices are also provided.\n-) Results suggest good performance although I do have concerns (see below).\n-) The topic is important and interesting.", "weaknesses": "-) It is not clear whether the superiority of the new algorithm, as evidenced by the numerical results, is natural or the result of inefficient comparisons. See my comments below.\n-) While the algorithmic contribution is non-trivial, the new algorithms are not really new since they follow what other published algorithms already do, albeit in a more efficient fashion.", "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": "", "extra_scores": {}}, {"review_id": "cghxoFPVXo", "reviewer": "Reviewer_uuTf", "summary": "This paper presents an improved method for the computation of truncated SVD by exploiting the sparsity of the involved matrix. Here this work focus on evolving matrices and updates of a current SVD. The proposed framework shows lesser complexity than previous methods with good accuracy. The problematic is fairly general and such framework can be of used in many situations.", "questions": "The precision of the computation is mentioned on the beginning of the paper but no theorem, proposition or lemma support the claim. Is it possible to prove some error bound?\n\nThe \"Add rows\" algorithm is missing, I assume that it is very close to the \"Add columns\" algorithm. Please clarify.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed framework enjoys better complexity which keeping a good precision. This is especially interesting while dealing with a stream of data. The experiments show the efficiency of the framework for different tasks.", "weaknesses": "The paper is not always easy to read. For example, the contribution are hard to clearly assess at first even if they are detailled at the beginning of the paper.\n\nI find on minor type in page 3: \"Orthogonalzation\" instead of \"Orthogonalization\".", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)