Tensor-Based Sketching Method for the Low-Rank Approximation of Data Streams.
Authors: Cuiyu Liu
Xiao Chuanfu
Mingshuo Ding
Chao Yang
Venue: ICLR 2023 poster (2023)

Abstract: Low-rank approximation in data streams is a fundamental and significant task in computing science, machine learning and statistics. Multiple streaming algorithms have emerged over years and most of them are inspired by randomized algorithms, more specifically, sketching methods. However, many algorithms are not able to leverage information of data streams and consequently suffer from low accuracy. Existing data-driven methods improve accuracy but the training cost is expensive in practice. In this paper, from a subspace perspective, we propose a tensor-based sketching method for low-rank approximation of data streams. The proposed algorithm fully exploits the structure of data streams and obtains quasi-optimal sketching matrices by performing tensor decomposition on training data. A series of experiments are carried out and show that the proposed tensor-based method can be more accurate and much faster than the previous work.

Published as a conference paper at ICLR 2023
TENSOR-BASER SKETCHING METHOD FOR THE Low- RANK APPROXIMATION OF DATA STREAMS
Cuiyu Liu', Chuanfu Xiao Beoo@,,,Mngaee Mingshuu Ding', Chao Yang2 3+
1 AAademmy for Advanced Interdisciplinary Studies, Peking University, Beijing, China
Schooo of Mathematical Sciences, Peking University, Beijing, China
*Changsha Institute for Computing and Digital Economy, Changsha, China 21 2101213203@stu. edu. cn,
[chuanfuxian) ao, di dingmingshus chao_yang) @pku edu. cn
ABSTRACT
Low-rank approximation in data streams is fundamental and significant task computing science, machine learning and statistics. Multiple streaming algorithms have emerged over years and most of them are inspired by randomized algorithms,, more specifically, sketching methods. However, many algorithms leverage information of data streams and consequently suffer from low accuracy. Existing data-driven methods improve accuracy but the training cost is expensive in practice. In this paper, from a subspace perspective, we propose a tensor- based sketching method for low-rank approximation of data streams. The proposed algorithm fully exploits the structure of data streams and obtains quasi-optimal sketching matrices by performing tensor decomposition on training data. series of experiments are carried out and show that the proposed tensor-based method can be more accurate and much faster than the previous work.
not able
INTRODUCTION
There are many scenarios that require batch or real-time processing of data streams arising from, e.g., video (Cyganek& & Wožniak 2017 [as 2021), signal flow (Cichocki et al. 2015 Sidiropoulos [ct al. 2017). hyperspectral images (Wang et al. 2017 Zhang et al. 2019) and numerical simulations an ordered sequence of data continuously generated from one or several distributions (Muthukrishnan 2005) Indyk et al., 2019), and the data per time slot can be usually represented as matrix. Therefore, most of the processing methods of data streams can be considered as operations on matrices, such as matrix multiplications, linear system solutions and low-rank approximation. Wherein, low-rank matrix approximation plays an important role in practical applications, such as independent component analysis (ICA) (Stone) 2002 Hyvärinen] 2013), principle component analysis (PCA) (Karamizadeh al. 2020 Jollifee &
(Zhang 2022 Larcher & Klein 2019). A data stream can be
Cadima 2016), image denoising (Guo et al. 2015 Zhang et al. 2019).
In this work, we consider low-rank approximation of matrices from a data stream. Specifically, let {A, E Rmxx D described as:
Id=1 be matrices from a data stream D, then the low-rank approximation in D can be
min |A BallF, s.t. rank(Ba) Sr, B₁
(1.1)
where d 1,2, D, ||I ||r represents the Frobenius norm, and E Z4 is a user-specified target rank.
Related work. A direct approach to solve problem I.] calculate the truncated rank-r singular value decomposition (SVD) of A, in turn. and the Eckart- Young theorem ensures that it is the best low-rank approximation (Eekart & Young 1936). However, it is too expensive to one by one calculate the truncated rank-r SVD of A, for all 1, D,, particularly when m or n is large. To address this issue, many sketching algorithms have emerged such as the SCW algorithm (Sarlos 2006 Clarkson & Woodrufi 2009 2017). Unfortunately, notable weakness of sketching
"Correspondence Chao Yang.

---

Published as a conference paper at ICLR 2023
algorithms is that they achieve higher enror than the best low-rank approximation, especially when the sketching matrix is generated randomly from some distribution, such as Gaussian, Cauchy, or Rademacher distribution (Indyk] 2006 Woolfe al. 2008 Clarkson & Woodruff 2009 Halko et al.)
201T, Clarkson & Woodruft] 2017]. J. To improve accuracy. a natural idea is to perform preprocessing on the past data (seen training set) in order better handle the future input matrices (seen
lest set). This approach, which is often called the data-driven approach, has gained more attention lately, For low-rank approximation, the pioneer of this work was (Indyk et al. 2019), who proposed learning-ban based method, that we henceforth refer to as IVY. In the IVY method, the sketching matrix set to be sparse, and the values of non-zero entries are learned instead of setting them randomly as classical methods do. Specifically, learning is done by stochastic gradient descent (SGD), by optimizing a loss function that portrays the quality of the low-rank approximation obtained by the SCW algorithm as mentioned above. To improve accuracy. (Liu et al. (020) followed the line of IVY by additionally optimizing the location of the non-zero entries of the sketching matrix S, not only their values. Recently, (Indyk et al. (02T)) proposed a Few-Shot data-driven low-rank approximation algorithm, and their motivation is to reduce the training time cost of (Indyk et al. 2019). Wherein, they proposed an algorithm namely FewShotSGD by minimizing new loss function that measures the distance in subspace between the sketching matrix S and all left-SVD factor matrices of the training matrices, with SGD. However, these data-driven approaches all involve learning mechanisms, which require iterations during the optimization process. This raises question: can we design an efficient method, such as a non-iterative method, to get a better sketching matrix with both short training time and high approximation quality? It would be an important step for the development of data-driven methods, especially in scenarios requiring low latency.
Our contributions. In this work, we propose a new data-driven approach for low-rank approximation of data streams, motivated by a subspace perspective. Specifically, we observe that perfect sketching matrix S E k should be close to the top-k subspace of Ud, where Udd is the left-SVD factor matrix of A.. Due to the relevance of matrices in a data stream, it allows us to develop a new sketching matrix S to approximate the top-k subspace of U for all d = 1, D. Perhaps the heavy learning mechanisms can be climinated. In fact, our approach attains the sketching matrix by minimizing new loss function which is relaxation of that in IVY. The most important thing is that we can get the minimization of this loss function by tensor decomposition on the training set, which is non-iterative. We refer to this method rensor-based method. As extension of the main approach, we also develop the two-sided tensor-based algorithm, which involves two sketching matrices S, W. These two sketching matrices can be obtained simultaneously by performing tensor decomposition once. Both algorithms are significantly faster and more accurate than the previous data-driven approaches.
2 PRELIMINARIES
The SCW algorithm. Randomized SVD is an efficient algorithm for computing the low-rank approximation of matrices from data stream. For example, the SCW algorithm, proposed by Sarlos, Clarkson and Woodruff (Sarlos) Clarkson & Woodruff 2009 2017), is a classical randomized SVD algorithm. The algorithm only computes the SVD of the compressed matrices S and AV, and its time cost is Or + n)) when we set k O(r). The detailed procedure is shown in Algorithm
Algorithm 1 The SCW algorithm (Sarlos 2006 Clarkson & Woodruff 2009 2017).
Input: Matrix A E Rmxx, sketching matrix S e k and target rank min n)
1: ~. M VT +- full SVD of SA
2: [AV], + truncated rank-r SVD of AV
3: Á < [V
Output: Low-rank approximation of A: Å
In (Clrrkson& & Woodruff 2009), it is proved that if S satisfies the property of Johnson Lindesnn-indeesstruuss
Lemma, k = O(r log(1 /)) suffices the output À to satisfy ||A Állr r (1 + ++) A {A]r
2

---

Published as a conference paper at ICLR 2023
with probability 1 1- Therefore, the approximation quality of the SCW algorithm is highly dependent on the choice of the sketching matrix S. In general, the randomly generated sketching matrix does not meet the accuracy requirements when handle problems in data stream, S by utilizing the information of the data stream? This is the motivation of data-driven approaches.
design new
The IVY algorithm. In (Indyk et al. 2019), the sketching matrix S is initialized by sparse random sign matrix as described in (Clarkson & Woodruff, 2009). The location of the non-zero entries is fixed, while the values are optimized with SGD via the loss function follow.
min SER
Σ
(2.1)
AED
where Dirain is the training sampled from the data stream D. This requires computing the gradient of the SCW operator, which involves the SVD implementation (line 1 and 2 in Algorithm I IVY uses differential but inexact SVD based the power method, and (Liu al. 2020) suggested that the SVD in Py also feasible and much more efficient.
The Few-Shot algorithm. In (Indyk al. 2021), S is initialized the same way IVY, and the location of non-zero entries remains, too. The difference is that the authors optimize the non-zero values by letting S to approximate the left top-r subspace of few training matrices. Wherein, the proposed algorithm namely FewShotSGD minimizes the following loss function:
min SEREXm
Σ
STTS SU - Toll::
(2.2)
UEllerain
where Mirain (U A UEVT of all A D.rain. U. denotes matrix containing the first columns of U, and Io E 12 has zero entries except that (To) = 1 for 1,..., ,
As shown in (Indyk et al. 2021), the goal of FewShotSGD top-r subspace of all matrices A E Drrain well and meanwhile is orthogonal to their bottom-(n - r) subspace. This raises a question: can we directly obtain a subspace that close to the top-r subspace of all As? The answer is yes! In this way, all matrices A Durain are required to be viewed as a whole, i.e., a third-order tensor. For illustration, we introduce some basics about tensor before presenting our method.
get the sketch which preserves the left
Tensor basics. For convenience, we only consider the third-order tensor E m and Ai.j.d j.
represents the (i. d'-th entry of A. The Frobenius norm of A is defined as || 1.j.d
The mode-n (n = 1,),3) matricization of AA is to reshape it to matrix A (m). For example, the mode-1 matricization of A is A(1) E Rmxnn satisfying (
Aijj.- The 1-mode product A and a matrix TR. km denoted as x S E * which satisfies
B.jid- A...S.... Tucker decomposition (Tucker 1966 is one format of tensor decomposition,
which is also called higher-order singular value decomposition (HOSVD) (Lathauwer et al. 2000). decomposes a tensor into a set of factor matrices and one small core tensor of the same order. For A m its Tucker decomposition is
A= = 9 X W,
where U E Rmxr: V Raxr2 W E R the column orthogonal factor matrices, R" xrixrgxTr is the core tensor, and (21,72, 72, rs) is called the multilinear taaiiinnear-rnkk rank of AA There are two
important variations of Tucker decomposition, i.e., Tuckerl and Tucker2 (Kolda & Bader 2009) or 2 modes of A are decomposed), which can be represented as A = 9 x1 U and A = g x U X2 V, respectively.
3 TENSOR-BASED SKETCHING METHOD
In this section, present idea and method for low-rank approximation in data streams. The goal is to employ the given training set to get the sketch S, inspired by IVY (Indyk et al., 2019) and FewShotSGD (Indyk al. 2021
3

---

Published as a conference paper at ICLR 2023
3.1
ALGORITHM
Our main algorithm, the tensor- tensor-based algorithm. is also a data-driven algorithm for low-rank ap- proximation data streams. Instead minimizing the loss in IVY, we consider different loss, motivated by subspace perspective. This loss function is easier to optimize than [_1 since to get its minimization, only Tuckerl decomposition is required, without learning mechanisms.
( Let Drrain (Aw R =d==1'
and the loss function we consider is
min SER I
Σ
1| 5 SAS s.t. SS =Ik
(3.1)
Exroin
Using the row-wise orthogonality of S, we have ||A S = Ax |SA. ar 11 Let
A mmxxx be a third-order tensor satisfying A.,.d' As. To minimize 3.1 is equivalent to
solve
max SEReXm
Σ
|SA
max SERixm
[ s.t. SS = Ik.
(3.2)
Agr ED Deram
where A
[A] A2 ... An' is the mode-1 matricization of A. Further, shown in (Kolda & equivalent
Bader 2009), problem 3.2
IA- x1 1 SEREXH
min
(3.3)
s.t. 9 B SS I
This is a Tuckerl decomposition of A along mode-1. Let A()) = (W be the SVD of A(1)- The optimal sketch S* for problem 3.3 (U(D))
k. where (Ur("), a matrix composed of the first & columns in (1) (refer to (Kolda & Bader, 2009).. We use the optimal S* as input
of SCW, and get the output of SCW the low-rank approximation. The tensor-based algorithm is summarized in Algorithm 2
The motivation behind this choice of loss function is the theorem below, which illustrates the relationship between our loss function 3.1 and that in IVY.
Theorem 1. Let Ar E RRmx be matrix from the training set, and A Tgmxn be third-order tensor satisfying A...d' = Adr, Given the target rank E E4, and a row-wise orthogonal matrix S E kmmm for any positive integer k >> T, we have
Σ |A - SCW(As, S [1)
(3.4)
A is the mode-1 matricization of A. Furthermore, with this relaxation, problem 2.1 can be converted to our proposed problem 3.3
where Am) A2
Theorem justifies the rationality of our choice of the loss function. Below we give an analysis that using the sketch obtained by problem 3.3 the SCW computes good low-rank approximation of A.
Analysis. fact, our idea is similar that in (Indyk et al., 202T both choosing the sketch S to approximate the top-r row subspace of matrices in Derain- Let UEVT be the SVD of A, where A is matrix Darain- Since there is strong relevance among matrices D makes sense to assume that S obtained by 3.3 is close in space to Us (k > r), where Uº is matrix composed of the first & columns of U. a special case where matrices in Dergin are the same, i.c., A.r = for d' l. D', using S obtained by 3.3) we have |U S]} = 0. Theorem 2 shows that using S computed by tensor-be based algorithm, the SCW gives a good low-rank approximation of A in data stream.
Theorem 2. Let UEVT be the SVD of A E Rmxn and Up be a matrix composed of the first ls columns of U. Given a row-wise orthogonal sketching matrix S E Rkxm satisfying [U ST SI < e, then we have
A - SCW(A, ||A -[A]]
< A
(3.5)
4

---

Published as a conference paper at ICLR 2023
The proofs of Theorem 1 and are provided fully in the Appendix.
Algorithm 2 The tensor-based algorithm for low-rank approximation of the data stream D. D'
Input: Test matrix A, training set {Aa E R ( d===1 rank S (min(m,n) n), # rows of the sketching matrix
1: Tensorization: A E I + (Av 1
2: 5 Tuckerl decomposition of A along the mode-1
3: A <- (CW(A,Sr))
Output: Low-rank approximation of A: Á
3.2 TWO-SIDED TENSOR -BSSED ALGORITHM
The two-sided tensor- casorrbbased algorithm is extension of the tensor-based algorithm in Section 3.1 The motivation that if we compute the Tucker2 decomposition of mentioned in Theorem two sketching matrices and W. would be computed at once. This means that besides using S for row space compression, we can use W to compress the column space of A, too. To be clear, we consider
min SeRixm WE
1 X1 ST ST X2 W
s.t. G. E RXixD
(3.6)
SST = I,, WWT
3.6 has no explicit form, but can be efficiently approximated by an alternating iteration algorithm, namely higher-order orthogonal iteration (HOOI) (Lathauwer et al. 2000, Kolda & Bader 2009). We present the HOOI algorithm in the Appendix. However, the SCW algorithm requires only one sketching matrix for computing low-rank approximation. As result, a new sketching algorithm for two sketches is required.
Unlike 3.3 the exact solution of problem
Two-sided SCW. To this end, we develop new algorithm for low-rank approximation based on the SCW algorithm, which we call two-sided SCW. It is worth mentioning that the full SVD in line 1 of Algorithm|] is used for orthogonalization, thus can be replaced with QR decomposition to improve the computational efficiency. With this in mind, the procedure of the two-sided SCW that we design as shown in Algorithm
Algorithm 3 The two-sided SCW algorithm.
Input: Matrix A RRxxn, sketching matrices S E Rkxm and W Rixn, and target rank
mii n)
1: Q, ~ + QR decomposition of A ST
2: P, QR decomposition of AW
3: [P" AQ), f- truncated rank-r SVD of P AQ
4: P[PT AQ),QT low-rank approximation of A
Output: Low-rank approximation of A: À
Clearly, Algorithm is more efficient than the original SCW when m, n are both large. The truncated SVD only needs to be done PT AQ giik which is much smaller in size than AV e gmxx in Algorithm (m l).
The procedure of the two-sided tensor-based algorithm is similar to the previously introduced tensor- based algorithm. First, reshape the training matrices to a third-order tensor A. Then, obtain two sketching matrices S, W by computing the Tucker2 decomposition of A. Finally, taking S, W and a test matrix as input, use two-sided SCW to get the low-rank. approximation of A. We summarize this in Algorithm Recall that compute the Tucker2 decomposition of A by HOOI

---

The two-sided censor-based algorithm for low-rank approximation of the data stream D) Input: Test matrix A, training set {Aa' R D' =d target rank r I min(m, n.,, # rows of the Published as a conference paper at ICLR 2023
Lathauwer et al. 2000 If k, ~ O(r), the time cost for Tucker2 decomposition with HOOI is Ormmn + r(m + +n) while Tuckerl decomposition costs Ommn²D)) addition, as mentioned before, two-sided SCW is more efficient than the SCW algorithm. That means, the time complexity of the two-sided algorithm is asymptotic less than the original tensor-based algorithm because & m, n, usually. However, since two-sided SCW uses S, W compress both the row and column space of A while the SCW compresses the row space only, there would be some loss in accuracy for the two-sided tensor-based algorithm compared the tensor-based one.
Algorithm 4
sketching matrix & and I.
1: Tensorization: A R'xxx + {A#)
2: S, W Tucker2 decomposition of A along the mode-1 and 2
3: Á < Two-sided SCW(A,5) S, W,
Output: Low-rank approximation of A: A
4 NUMERICAL EXPERIMENTS
In this section, we test our algorithms and compare them the existing drivenriven algorithms for low-rank approximation of data streams. We use three datasets for comparison HSI (Imamoglu
al. 2018). Logo [Indyk al. 2019) and MRI.
Table 1: Summary of datasets used for experiment.
Name
Description
Dimension
# Train
# Tesst
HSD
Hyper spectral images
1024 x 768
100
400
Loge
Video
3240 x 1920
100
400
MR
Magnetic resonance imaging
217 x 181
30
120
We measure the quality of the sketching matrix S by the error the test set, and the test error is defined as Error Preue EAED
|A A Aupulll where Aopt is the best rank-r ap- A
proximation of A, and Á is the low-rank approximation computed by the tested algorithms. In all experiments, we set the rank r to 10, and the sketching size k = = 20. Experiments are run on server equipped with an NVIDIA Tesla V100 card.
Baselines. As baselines, three methods are included - IVY (Indyk et al. 2019). Few-Shot (Indyk al. 202I), and Butterfly (Ailon al. 2021).
IVY. As described in Ref. (Indyk et al. 2019). the sketching matrix is initialized by a sign matrix. Its non-zero values optimized by stochastic gradient descent (SGD) (Sadd 1998). which is an iterative optimization method widely used in machine learning.
Few-Shot. In (Indyk et al. 2021 , as IVY does, the sketching matrix is sparse, and the location of the non-zero entries is fixed. The non-zero values of the sketch are also optimized by SGD. They proposed one-shot closed-form algorithms (including /Shot/ Vec+ and /Shot2Vec), and the FewShotSGD algorithm with either 2 or 3 randomly chosen training matrices (i.e., FewShorSGDD2 and FewShotSGD-3). We compare our algorithms with all of them.
Butterfly. In (Ailon et al., 2021). it is proposed to replace a dense linear layer in a neural net- work by the butterfly network. They suggested using a butterfly gadget for learning the low-rank
RRetrieeed from http::///aithhuu.com//...a/ssttt
"Retrieved from http: http://yootu..be/55000...
RRetrieved from https://brainne
magi 11.c1/..caa///// /bra nweb2

---

Published as a conference paper at ICLR 2023
0.25
0.20
0.20
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00
-///
0.0
60.0
80.0
100.0
120.0
140.0
160.0
180.0
0.0
500.0
600.0
700.0
800.0
900.0
Time
Time (s)
(a)
(b) Logo
15hot1Vec+
1Shot2Vec
Butterfly
FowShotSGD 2
Few5hotSGD-3
(ours)
0.15
0.10
Logo
MRI
0.05
SOTA
0.0362
0.0168
0.0561
Ours
0.0198
0.0105
0.0149
0.00
10
Time (s)
(c) MRI
(d) Table: average test error
Figure
Test error per training time with the target rank r and the sketching size k 20. (d), SOTA represents the lowest test error that the baselines achieve.
approximation, also learning the non-zero values of sparse sketching matrix by SGD, similarly to IVY.
Since the baselines above all use one sketching matrix only, compare our tensor-based algorithm with them. For the two-sided tensor- tensor-based algorithm, we test its performance later in this section, only comparing with our censor-based algorithm.
Training time and test error. We compare the test error per training time for each approach. The results are reported Figure [ Table in (d) in Figure I lists the test error of the tensor-based algorithm and the lowest test error among the baselines. The tensor-based algorithm achieves at least times lower test error on HSI/Logo/MRR than the baselines. For the baselines. the training matrices are required to be normalized to avoid the imbalance in the dataset before training starts. On HSI/Logo/MRI, this pre-processing of data takes 46.55s/ 0555s/44.000 /4/.447.///////// 20.//.77777 After that, the training for the sketching matrix could start. However, for our algorithms,, this pre- processing time can be avoided, because our algorithms are to compute the top-r subspace of the training matrices which remains when the training data scales by constant. On HSI/Logo//MII the tensor-based algorithm takes 0.53s/ 44. 1.7..67, 76s/ 0.23ss for training, which is much faster than /VY, and Butterfly. As result, our algorithm significantly outperforms the baselines much more accurate and faster.
Testing time. Next report running time for the testing process all datasets. Note that the sketching matrix by the tensor-based algorithm is dense, while that of the baselines is sparse. This results in the difference in the testing process, mainly on the matrix multiplication SAA the SCW procedure. The baselines have approximately the same testing time since their sketching matrix has the same sparsity. For the tensor- tensor-based algorithm, we use the built-in functionality in PyTorch, A), to compute S A, which provides great acceleration. On HSI/Logo//RRL
i.e. Norch.matmuile the testing process for the tensor-based algorithm takes 0.52s 1522s/0.99//0. /0.28s. For the baselines, the sketching matrix S is sparse and S is stored using two vectors one for storing the location of non-zero entries, and the other for storing the values of the non-zero entries. Suppose that the location and value vectors are In this way, the testing time for the baselines much longer than that of the tensor-based algorithm, mainly because there is software acceleration
To compute S.A. we can update SA SA j) m. 2ls//00.15//11. 1.1 on HSI/Logo/MRI, which is
7

---

Published as a conference paper at ICLR 2023
025
125
6.5
2 -
322
6.0
Mny (tennel
5.-
PeerShattcD-2jde-- 2jdenne)
TeerhhatSCD- (jdenaa)
Temaace baxed (ours)
033
015
023
328
045
05
365
100
305 300 900
308
06
0855
1802
170,
1850
(b)
Figure 2: Test error per training time compared with the dense baselines. Note that the training of the dense baselines is faster than the original baselines for the use of torch. borchmaatmul() to compute S A.
applied here. However, the testing process for the tensor-based algorithm is accelerated by the use of the built-in functionality corch.matmulf in Py PyToch. If we restore the sparse S in the baselines as compute S.A when testing, the testing time for the baselines on HSI/Logo/MRI is reduced to 0.88s 11117//.////// 00.40s.
the COO format and use norch.sparsc.mit (S A)
In view of the dense structure of our sketching matrix, we implement the baselines as dense ones and compare our algorithm with them, including IVY (dense), /Shot/Vec+// (dense) and FewShhrSGDD-3 (dense). The dense baselines optimize all entries of the sketching matrix, not only the non-zero entries as the original baselines did. We show the results in Figure 2 The test error for the tensor-based algorithm is 0.0198 0..10.00...... 0..149 on HSI/Logo//MRI while the lowest test error that the dense baselines achieve is 0.0191 10191/0001// /0.0/0..12///// 0012/0.0124 on HSI//Looo/MRI With comparable accuracy, our approach has much shorter training time than the dense baselines.
(dense), Few-ShotSGD-2
Experiments for the two-sided algorithm. Finally, we test the performance of the two-sided tensor- based algorithm. This algorithm uses two sketching matrices S, W for computing the low-rank approximation. Table[]shows the test error, the training time and the testing time for the two proposed algorithms, the censor-based algorithm and two-sided version. The tensor-based algorithm achieves 0. 0.29/0.77 0.66 times lower test error HSI//ogo//MRI than the two-sided algorithm. However, the two-sided algorithm has both shorter training time and testing time. These results confirm our analysis in Section
Table 2: Test error, training time and testing time of the tensor- basorr algorithm and the two-sided cessor-based algorithm.
Datasets
Algorithms
error
training time (s)
testing time (s)
tensor-based
0,020
0.53
0.52
HSI
two-sided
0.069
0.39
0.41
tensor-based
0.011
4.76
0.69
Logo
two-sided
0.015
1.36
0.50
tensor-based
0.015
0.23
0.28
MRI
two-sided
0.024
0.17
0.12
Additional experiments. In the experiments above, we only evaluate the algorithms when the sample 20% for HST/Logo//MRI, respectively),
ratio for training is 20% (1004400
100
400
30-112
which we denote as sample_ratio algorithms under different values of sample ratio, including 2%, 20% and 80%. The results show that using only a small number of training matrices (sample_rattee ratiorraiioo 2% for example), our algorithms achieve low enough error. When sample_ aanioe_ratio increases from 2% to 80%, the test error of the tensor- based algorithm decreases by a multiplicative factor of 0.952 0252/0.900 00.117 1091100.0000 6..684 on HSI/Logo/MRI, and for the two-sided tensor-based algorithm, the corresponding factor is 0.873 / 789 60.606 on HSI/Logo/MMI. On MRI, the test error decreases more when the number of training matrices increases compared the other two datasets. In our opinion, this is because there is less stronger
20%. Figure 3 shows the performance of our proposed
8

---

Published as a conference paper at ICLR 2023
ratio=2%
sample ratio=205
Averoge test error
sample_ ratioe
0.06
0.06
0.02
0.02
119t
MRI
19
MAI
Tensor- based
(b) Two-sided tensor based
Figure 3: Test error of the tensor- censor-based algorithm and the two-sided tensor- tensor-based algorithm under different number of training samples.
relevance among matrices MRI. In general, increasing training samples improves the accuracy, but not significantly.
For our approach, one of the limitations is that it is required to load the whole training tensor at once. But for the baselines, the sketching matrix is learned SGD and one of its advantages is that only a few (batch-size) training matrices are required to load in memory at a time. However, the results in Figure show that small number of training matrices are enough to achieve good low-rank approximation for both the censor-based algorithm and the two-sided tensor-based algorithm. As result, the memory usage of the proposed algorithms is also relatively low, comparable the baselines.
5 CONCLUSIONS AND FUTURE WORK
In this work, we propose an efficient and accurate approach to deal with low-rank approximation of data streams, namely the tensor-bart based sketching method. From a subspace perspective, we develop tensor-based algorithm as well as two-sided tensor-based algorithm. Numerical experiments show that the two-sided tensor-based algorithm is faster but attains higher test error than the tensor-based algorithm. Compared to the baselines, both algorithms are not only more accurate, but also far more efficient.
This work mainly focuses reducing the training time for generating the sketching matrix. However, reducing the testing time also of great interest. One of the approaches is to develop pass-efficient sketching -based algorithms for low-rank approximation. In applications, the pass-efficiency becomes crucial when the data size exceeds memory available in RAM. Further, in addition to low-rank approximation, the idea of the tensor-based sketching method can be applied as e-approximation and linear system solutions on data streams. We leave them for future work.
operations such
ACKNOWLEDGMENTS
The work was supported by the High-perfonee pererreeffrm Computing Platform of Peking University. The authors acknowledge it for supporting the computational work sincerely.
REFERENCES
N. Ailon, O. Leibovitch, and V. Nair. Sparse linear networks with fixed butterfly structure: theory and practice. In Uncertainty in Artificial Intelligence, pp. 1174-1184. PMLR, 2021.
D. Carlson. Minimax and interlacing thoerems for matrices. Linear Algebra and its Applications, 54: 153-172, 1983.
A. Cichocki, Mandic, I.. De Lathauwer, G. Zhou, Q Zhao, Caiafa, and Phan. Tensor decompositions for signal processing applications: From two-way to multiway component analysis. IEEE Signal Processing Magazine, 32(2):145-163 2015.
K. L. Clarkson and D. P. Woodruff. Numerical linear algebra the streaming model. In Proceedings of the forty-first annual ACM symposium Theory of computing, pp. 205-214, 2009.

---

Published as a conference paper at ICLR 2023
K. L. Clarkson and D. P. Woodruff. Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63(6):1-45, 2017.
B. Cyganek and M. Wožniak. Tensor-based shot boundary detection in video streams, New Generation Computing, 35(4):311-333 2017.
S. Das. Hyperspectral image, video compression using sparse Tucker tensor decomposition. IET Image Processing, 15(4):964-95) 2021.
C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211-218, 1936.
Q. Guo, C. Zhang, Y. Z.aang and H. Liu. An efficient SVD-hased method for image denoising. IEEE Transactions on Circuits and Systems for Video Technology, 26(5):868-880, 2015.
N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53(2):217-288, 2011.
A. Hyvärinen. Independent component analysis: Recent advances. Philosophical Transactions the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1184):201 20534444 2013.
N. Imamoglu, Y. Oishi, X. Zhang, G. Ding, Y. Fang. T. Kouyama, and R. Nakamura. Hyperspectral image dataset for benchmarking on salient object detection. In 2018 Tenth International Conference Quality of Multimedia Experience (goMEX), pp. 1-3. IEEE, 2018.
Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3)3307-323, 2006.
P. Indyk, A. Vakilian, and Y. Yuan. Learning- low-rank approximations. In Proceedings the 33rd International Conference on Neural Information Processing Systems, pp. 7402-7412, 2019.
P. Indyk, T. Wagner, and D. P. Woodruff. Few-shot data-driven algorithms for low rank approximation. Advances in Neural Information Processing Systems, 34: 16667-166690, 2021.
I. T. Jolliffe and J. Cadima. Principal component analysis: A review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 374(2055):0150202 2016.
S. Karamizadeh, S. M. Abdullah, A. A. Manaf, M. Zamani, and A. Hooman. An overview of principal component analysis. sis. Journal of Signal and Information Processing, 4, 2020.
T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Rev., 51(3):455-500, 2009.
Von Larcher and R. Klein. Approximating turbulent and non non-tuntiitt turbulent events with the tensor train decomposition method. In Turbulent Cascades II, pp. 283-291. Springer, 2019.
L. De Lathauwer, B. De Moor, and J. Vandewalle. multilinear singular value decomposition. SIAM
J. Matrix Anal. Appl., 21(4):1253-1278 2000.
L. De Lathauwer, B. De Moor, and J. Vandewalle. On the best 1 and rank- (R1, R..... RR)) approximation higher-order tensors. SIAM J. Matrix Anal. Appl., 21:1324411211 1342, 2000.
S. Liu, T. Liu, A. Vakilian, Y. Wan, and D. P. Woodruff. Learning the positions in countsketch. arXiv preprint arXiv:2007.0900 0999099 2020.
Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.
D. Saad. Online algorithms and stochastic approximations. Online Learning, 5:6-3, 1998.
R. Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) pp. 143-152. IEEE, 2006.
10

---

Published as a conference paper at ICLR 2023
N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. E. Papalexakis, and C. Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):3551-358) 2017.
Stone. Independent component analysis: An introduction. Trends in cognitive sciences, 6(2): 59-64, 2002.
L. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31:279-311, 1966.
Y. Wang, J. Peng. Q. Zhao, Y. Leung, X. Zhao, and D. Meng. Hyperspectral image restoration via total variation regularized low-rank tensor decomposition. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Semsing, 11(4):2227-1243, 2017.
Woolfe, E. Liberty, V. Rokhlin, and M. Tygert. A fast randomized algorithm for the approximation of matrices. Applied and Computational Harmonic Analysis, 25(3):335-335 2008
G. Zhang, X. Zheng, S. Liu, M. Chen, Wang, and Wang. Three-dimensional wind velocity reconstruction based on tensor decomposition and CFD data with experimental verification. Energy Conversion and Management, 256: 15322, 2022.
H. Zhang, L. Liu, W. He, and L. Zhang. Hyperspectral image denoising with total variation regularization and nonlocal low-rank tensor decomposition. IEEE Transactions on Geoscience and Remote Sensing. 58(5):3071 1-3044 2019.
A APPENDIX
A. PROOF OF THEOREM 1
Proof. The inequality 3.4 will be proved if we prove the following two inequalities.
D
D'
Ax SCW(S, Aar )1F
<
A
(SA
(A.1)
d=1
d' d=11
and
D Ax - (TAA & | ||(SA (1)-11.
(A.2)
First, we consider the inequality in A.I Let E gonk be column-wise orthogonal matrix in the row space of SAd. By definition of SCW, we have
Ar - (S ||r | Q), QT
|A 11
Q1-
(A.3)
Similarly,
|
S"
SAr,, 1| Ar
(A.4)
Combing
A.3 and
A.4
A.I follows immediately if we show
||SAA& < [|
(A.5)
Noting that
SA-Q-UEV'Q-US00
where UEVT is the singular value decomposition of SA. and Q' = V'Q Since V and Q lie in the same row space and are both column- wise orthogonal, easy to see that Q' is didiiensionnal orthogonal matrix. Thus. SA, and S SA& Q share the same singular values. Combining Cauchy interlace theorem (Carlson 1983). we have
[[SAAb]-1 A Q1 < 1]
(A.6)
which proves A.5
11

---

Published as a conference paper at ICLR 2023
We now turn the inequality in A.2 components as
For convenience, rewritten (A and [SA()) with block
(A = | ... ... -....
and
A = [ B2) [b]]
where B; E IR kxn for 1,
We then have
|SA ||2
Σ
||SA
Σ
SAv [SAw]/l
d==1
#=11
D'
|SAr Bx 11
d'=1
|S (1) - A[))\()
where the Eckart- Young theorem is applied. It follows that
D
[SAr), 12 2 [[SA
which is equivalent to in A.2
Hence, we have proved that ||| (1)-11 is relaxation of
Σ ||
Ag
SCW(S, Ar ||.- Therefore, the problem 2.1 be converted minimize ||
||
P.
ie., maximize [[( Due to k > is not difficult verify that sufficient condition for maximizing ( which is equivalent to
1-]--111 maximizing [ [
3.3
As a result, instead
of optimizing problem 2.1 we can covert it to our proposed problem 3.3
Hence, our proof is completed.
A.2 PROOF OF THBOREM 2
Proof. Let ÚFVT be the SVD of the matrix SA. Using the definition of the SCW algorithm, we have SCW (A, r) = [AV), VT. Further, since V is column- wise orthogonal, we have
A - SCW(W, S, 1| A
AV
V = | - 1,
Similarly, we have
A - |A), = || - 1107 A]
Recall that UEVT is the SVD of A, and U* be matrix composed of the first k columns of U. Based on the result result[A.6)in in the proof of Theorem 1, we immediately get
1A > ||SA)|
(A.7)
Thus, we have
A - (C
||A 1A < I AL |SA]
||U] A - SA
=t((A 5 S)A)
(A.8)
- <UUUU S ||
< <UUUU - ST ST ||
S 0(() ||
Hence, proof is completed.
12

---

Published as a conference paper at ICLR 2023
A.3 HOOI ALGORITHM
Algorithm 5 HOO1 algorithm Lathauwer et al. (2000); Kolda & Bader (2009)
Input:
Tensor A E 1R
Truncation (R1, R2 .. Rx)
Initial guess (U6)) 1,2, N
Output:
Low multilinear-rail approximation À 9 x1 U()) X2 U()).... XN U
1: k
2: while not convergent do
3: for all n E
do + Ax (U xn-1 (U
k+1 Xn+1 (Ul ... xN (U%
4:
5:
(m)
B in matrix format
6:
U,E,V'
+ truncated rank-R,, SVD of (1))
7:
k+1 +U
8:
9km <
EVT in tensor format
9: k k+1
10: end for
11: end while
12: g + ΣV" in tensor format
13


Reviews:
[{"review_id": "k6kCwzlJc5b", "reviewer": "Reviewer_8sdZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper introduces a low-rank tensor approximation algorithm intended for data streams applications. \nAccording to the authors, the algorithm fully exploits the structure of data streams and obtains quasi-optimal sketching matrices by performing tensor decomposition on training data. \nThe approach computes the sketching matrix by minimizing a new loss function which is a relaxation of that in the IVY tensor decomposition method. Specifically, the key is that the minimization of this loss function by tensor decomposition on the training set is non-iterative. The authors formulate a couple of theorems that bound the approximation performance and provide empirical analysis on several real data stream datasets.", "summary_of_the_review": "In summary, I am weakly included to accept this paper given that it scores high in terms of clarity and quality. However, my inclination is weak due to some minor concerns regarding its novelty.", "strength_and_weaknesses": "+ \n\n* The paper is well written and clear for the most part. It does need to be proof read for small typos and grammar.\n*  The idea is well grounded in existing methods, e.g. IVY and SCW and the approximation quality is derived in two theorems.\n*  The authors test their algorithm on real datasets and show some improvements. \n\n- \n* Overall I have some concerns regarding the novelty as the proposed algorithms are somewhat straightforward extensions of the existing algorithms, e.g. SCW.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "eZiTaX_F6no", "reviewer": "Reviewer_5H7S", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The paper studies the data-driven low-rank approximation problem on data streams, which has gained attention recently. For a single matrix, some fast algorithms for low-rank approximation are based on sketching, and specifically they choose a sparse sketching matrix with random signs, which is multiplied by the original matrix to reduce its row and/or column dimensions while still allowing approximate recovery of the best low-rank approximation. In a stream of matrices assumed to be related to each other, it has been recently shown that the entries of the sketching matrix can be chosen in a data-driven way based on matrices previously seen on the stream instead of using random signs, in order to improve performance.\n\nThis paper suggests a new algorithm along these lines, that views the stream of matrices as a tensor of order 3, which leads to a formulation of a loss problem that can be solved directly and yields an appropriate sketching matrix, albeit non-sparse.\n\n", "summary_of_the_review": "This is a potentially interesting paper but with flaws in its framing and methodological design, with which I cannot recommend acceptance. I could have recommended accepting a version of the paper with largely the same technical material, but that clarifies properly the departure from prior work, and with a viable experimental design that compares the baselines on a level ground and includes more relevant baselines. I also recommend rewriting the proofs in a clearer way that would assist in verifying the stated theorems.", "strength_and_weaknesses": "The tensor-based approach seems interesting and may lead to useful insights on the problem. However, there is a major issue that makes the proposed algorithm incomparable to prior work, both theoretically and empirically - the lack of sparsity of the output sketching matrix. This unfortunately renders the paper methodologically unviable. \n\nIn all prior work (both oblivious and data-driven), the sketching matrix has a certain structure that allows fast matrix multiplication by it (usually sparsity), while here no such structure is guaranteed. On the theoretical level, this makes the resulting low-rank approximation algorithm asymptotically slower than all of the prior work it is compared to.\n\nThe manuscript is aware of this issue, and finally addresses it on the empirical level, on page 8, stating that even though the asymptotic running time is slower, the proposed algorithm is in fact empirically faster than prior work based on experiments. It goes on to explain this is because the implementation of the proposed algorithm uses the built-in (highly optimized) PyTorch matrix multiplication functionality, while the baselines were implemented with the non-optimized (and inevitably much slower) sparse matrix multiplication code released by the authors of those works. This unfortunately renders the reported testing time results essentially meaningless: the algorithms should be compared in the same experimental setting (software and hardware). Using the same dense matrix multiplication functionality in PyTorch for the sparse baselines would have already improved their running time to the same as the proposed method, erasing any reported advantage in testing time.\n\nTo be clear, it is true that as of now, PyTorch and comparable optimized software packages for matrices do not exploit sparsity, and dense matrix multiplication is as fast as sparse on the datasets considered here. Sparsity is useful theoretically (for getting better asymptotic bounds) and also in practice if the matrices are too large to fit in working memory (which makes dense matrix multiplication slow or infeasible). I do not question the reported results themselves, and one could perhaps make the argument that the sparsity of the sketching matrix is not helpful at all and could be dispensed with, but the current framing and methodological design of the paper are unviable. If sparsity is indeed unhelpful, then the sparse baseline should be implemented as dense ones and not crippled by attempting to leverage sparsity, and dense methods for low-rank approximation could be considered and reported as well (even full SVD). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G4aFrUoRxIf", "reviewer": "Reviewer_337b", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The paper studies the learning-based low-rank approximation problem and proposes a new algorithm, which is based on the tucker tensor decomposition. The new optimization problem based on tensor decomposition can be seen as a relaxation of the original LRA problem. The experimental result suggests that the proposed algorithm has a lower error while having a faster training time. ", "summary_of_the_review": "Overall I think the approach the author proposed is interesting. My main concern is the non-sparse of the sketch matrix so currently I vote as a 5  the paper.  I can raise the score if the author can address this adequately (note that the sparsity property is not the only way to compute $SA$ fast, like the Subsampled Randomized Hadamard Transform(SRHT) matrix is a dense sketching matrix while we can compute $SA$ in $O(nd \\log n)$ time) .", "strength_and_weaknesses": "Strength\n\n1. The paper proposes an algorithm from a new insight, which has not been considered in the literature on the learning-based LRA. The paper also gives a theoretical guarantee.\n\n2. The experimental results are strong and interesting. The proposed algorithm has a lower error while having a faster training time. \n\nWeakness\n\n0. Note that the template of this paper is actually a little different than the ICLR template.\n1. The analysis of the theorem is straightforward. Besides, the Theorem 2 seems only to give an additive error $\\epsilon ||A||_F^2$,  I am wondering that would it be possible to get a multiplicative error $\\epsilon ||A- A_k||_F^2$, which is the common setting in the literature of the sketching-based LRA.\n2. As mentioned in the paper, the new learning-based sketch matrix is a dense matrix, which I think is the main drawback of this paper. The dense sketch matrix seems not to be useful when the size of the data is large. Note that if $S$ is a Count-Sketch matrix, we can compute $SA$ in $nnz(A)$ time. That is one of the reasons that most of the previous works only study the sparse sketching matrix.  As mentioned in the work of IVY19, One applications scenario of the learning-based sketch involves processing streams of data (video, data logs, customer activity etc) by executing the same algorithm on an hourly, daily or weekly basis. Hence in this sense the testing time is more important if the training time is only a little slower as the training process can be done before the new data comes. Also, notice that the sparse matrix has the pass-efficiency property when the data size exceeds memory available in RAM, which is what the author mentioned in the conclusion section. The update time for one update of the Count-Sketch matrix is $O(1)$.\n\n3. The paper mentions the testing time in the experiment section but it seems not to be done in the correct way. It says in the paper that \"have no idea how to accelerate the matrix multiplication SA while exploiting the sparse structure of S\". However, suppose that the position and value vectors are $p$, $v$. Note that if the $t$-th non-zero entries of $A$ is $A_{ij} = c$, we just need to do the update \n$\nSA[p_i, j] = SA[p_i, j]  + v_i \\cdot c . \n$\nwhich means the time to compute $SA$ is the same as to read the matrix $A$. \n\n4. The authors mention the memory usage in the experiment section. Can the author give a detailed result of the memory usage for all approaches?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6zvsxXNW_V", "reviewer": "Reviewer_dbkp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In this work, the authors summarized previous algorithms to recover column/row spaces of a set of matrices fast and introduced Tucker decomposition of tensor into them, which can give a good choice of hyperparameter in those algorithms. ", "summary_of_the_review": "This work should qualify for a conference paper, although there are something which can be improved. ", "strength_and_weaknesses": "Strength: in those previous algorithms, they require the approximation for matrices in the training set to be as accurate as possible and this work provides the method based on Tucker decomposition with theoretical analysis. And the idea of viewing a stream of matrices as a tensor is novel and helpful in finding their common subspaces. \n\nWeakness: the analysis is not complete. It didn’t mention how close is S, the estimator of U_k, in general cases to U_k. Also the bound in theorem 2 is not clear with m and n. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster