Few-Shot Data-Driven Algorithms for Low Rank Approximation
Authors: Piotr Indyk
Tal Wagner
David Woodruff
Venue: NeurIPS 2021 Poster (2021)
Keywords: low rank approximation
numerical linear algebra
learning-based algorithms
svd
matrix sketching

Abstract: Recently, data-driven and learning-based algorithms for low rank matrix approximation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy.  Those algorithms are based on the optimization of sparse sketching matrices, which lead to large savings in time and memory during testing. However, they require long training times on a large amount of existing data, and rely on access to specialized hardware and software. 

In this work, we develop new data-driven low rank approximation algorithms with better computational efficiency in the training phase, alleviating these drawbacks. Furthermore, our methods are interpretable: while previous algorithms choose the sketching matrix either at random or by black-box learning, we show that it can be set (or initialized) to clearly interpretable values extracted from the dataset. 

Our experiments show that our algorithms, either by themselves or in combination with previous methods, achieve significant empirical advantage over previous work, improving training times by up to an order of magnitude toward achieving the same target accuracy.

Few-Shot Data-Driven Algorithms for Low Rank Approximation
Piotr Indyk MIT indykdmit.. edu
Tal Wagner Microsoft Research Redmond tal www.wwawggaaaa..oomm com
David P. Woodruff Carnegie Mellon University dwoodruf@cs cmu. edu
Abstract
Recently, data-driven and learning-based algorithms for low rank matrix approx- imation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy. Those algorithms are based on the optimization of sparse sketching matrices, which lead to large savings in time and memory during testing. However, they require long training times on large amount of existing data, and rely on access to specialized hardware and software.
In this work, we develop new data-driven low rank approximation algorithms with better computational efficiency in the training phase, alleviating these drawbacks. Furthermore, our methods are interpretable: while previous algorithms choose the sketching matrix either at random or by black-box learning, we show that can be set (or initialized) to clearly interpretable values extracted from the dataset.
Our experiments show that algorithms, either by themselves in combination with previous methods, achieve significant empirical advantages over previous work, improving training times by up to order of magnitude toward achieving the same target accuracy.
introduction
Low-rank approximation (LRA) of matrices is fundamental operation in data analysis and machine learning, forming the basis for many efficient algorithms that involve storing and analyzing large matrices. Its importance has led to a large body of work on algorithms for computing LRA. While it well-known how to find an optimal LRA of a given matrix in polynomial time using the Singular Value Decomposition (SVD), the degree of that polynomial makes the algorithm too slow for large matrices, defeating the purpose of leveraging it to design fast and scalable algorithms. With this motivation in mind, long and prominent line of research has discovered fast approximate LRA algorithms, laying the foundations for rich and expansive theory fast algorithms for numerical linear algebra (e.g., [26. 51, 15, 16, 18, 24]). Due to their strong practical performance, these algorithms have become standard and widely used tools in machine learning over massive datasets (e.g., [57, 30, 43, 27, 13, 53]). See the surveys [41, 56, 42] for comprehensive overview of this area.
These algorithms are mostly based on sketching. In its most basic form, the input matrix A E Raxd left-multiplied by carefully chosen sketching matrix m whose row dimension much smaller than that of A (i.e., & n)). Then, good low rank approximation to A can be com- puted from SA. Reducing the row dimension from to m improves the algorithmic efficiency in multiple ways. First, SA can be stored using less space than A, which is important in the con- text space-efficient streaming algorithms. Furthermore, the dimensionality reduction step can be combined with other steps to obtain LRA algorithms with running time nearly linear in the size of A. Identifying suitable sketching matrices is highly non-trivial task, and by now there are several
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

known randomized constructions, including sparse sign matrices [15, 16, 43, 46], random projection matrices [51, 2]. and subsampled Hadamard matrices [21, 13].
Unfortunately, a notable downside of sketching- algorithms is that they lead to a larger approx- imation error than the optimal LRA,, due to the lossy nature of sketching. Since this error propagates downstream to all tasks that use LRA as subroutine, minimizing this error is highly important. This raises the question the sketch width m and the approximation quality? Such an improvement would directly translate into a more accurate (or alternatively, more space efficient) streaming algorithm for LRA (see Sec- tion 1.2 for more details). Furthermore, it would also be an important step towards obtaining more time-efficient algorithms as well.
can we design better sketching matrices, that offer better tradeoff between
Data-driven approach to LRA. A natural approach to the above challenge is to rely on the fact that in many cases, we have access to large quantities of past data (seen as training set), which is related to the future input matrices (seen as a test set). In such a scenario, we could potentially use preprocessing (or learning) stage on the past data in order to better handle future data. This approach, often called data-driven or -aggmented algorithm design, has gained increased popularity lately, and led improved algorithms for host of classical problems (see Section 1.3).
For low rank approximation, this line of work was recently pioneered by [33], who proposed a data- driven LRA algorithm that refer to henceforth as IVY. Specifically, IVY learns the values of the non-zero entries in a sparse sketching matrix S, instead of choosing them at random (as in classical LRA, e.g., [16]). Learning is done using stochastic gradient descent (SGD), by minimizing the empirical (normed) difference between matrices from the training set and their corresponding L.RAs computed using S. Computing gradients for this loss function is highly non-trivial operation, but nonetheless, [33] show it can be made tractable by exploiting modern auto-gradient software and GPU hardware, which are typically used nowadays to train deep neural networks.
Challenges and limitations. Despite its improved accuracy, the IVY algorithm has several draw- backs related to its computational cost. First, it requires differentiable implementation of the SVD, which is slower than standard implementations, leading to long training times. Second, it relies on specialized software and hardware (automatic gradient computation in PyTorch, and access to GPU). Third, in order to gain significant improvement over the oblivious inon-data-drive it requires training over dozens of existing matrices, which may not necessarily be available. Fourth, it chooses the sketching matrix in a black-box, non-interpretable way. using black-box learning. All these limitations are also shared by [3, 38). This leads to consider whether much more efficient data-driven algorithms can attain a comparable advantage in their LRA accuracy.
baseline,
1.1 Our Results
In this work, we propose a new approach to data-driven LRA, motivated by a different and more analytic-minded viewpoint. As mentioned above, previous work takes "black-box" approach to the problem, directly minimizing the empirical loss via SGD. However, since LRA is a well-studied topic with rich underlying mathematical structure, is worth to consider alternative approaches that make direct use of our analytic understanding. This may allow us to simplify the learning algorithm for example, by devising more effective loss functions and perhaps even eliminate the heavy learning machinery altogether, in favor of analytic techniques.
This approach leads us to data-driven algorithms that are considerably faster to train than IVY, do not necessarily require access to specialized hardware and software, and use only one or few training matrices (thus, they perform few-shot learning). Specifically, give the following two algorithms:
One-shot closed-form algorithm: Our first algorithm does not require learning all; it only picks a random matrix from the dataset, and extracts a sketching matrix by an analytic computation. It requires neither GPU access nor autograd functionality.
Few-shot SGD algorithm: For our second algorithm, we use a new loss function for learned LRA (given in eq. (3) in Section 2). It is faster to compute and differentiate than the empirical loss used in [33], being low degree polynomial, and can (locally) optimized with only 2 or 3 steps of SGD, requiring only that many randomly chosen matrices from the dataset.
2

---

Both algorithms achieve significantly better sketch length to accuracy tradeoff's than data-oblivious LRA. When compared to IVY and its variants, they do attain similar (and eventually better) ac- curacy than our algorithms if allowed to run for sufficiently many SGD iterations, but with much longer training times and many more training matrices. In addition, our closed-form algorithm also interpretable, as it computes sparse sketching matrix S with clear mathematical meaning- Specifically,, the non-zero entries of S are set to be singular vectors of a block partttiiatt randomly chosen training matrix, with a block partition determined by the sparsity pattern of S. The singu- lar vectors each block are chosen either greedily, or at random proportionally to their squared singular values.
Finally, we experiment with combining our approach with IVY, by initializing the weights of the sketching matrix according to our one-shot algorithm, instead of at random as in [33]. The result an algorithm that uses the same memory, time and training samples as IVY, with significantly improved accuracy.
One takeaway message for designing data-driven algorithms, is that while may seem tempting to invoke heavy-weight machine learning technology, there are possibly much simpler algorithms that attain similar performance with significantly reduced computational cost, and an analytic understanding of the problem may help us arrive at those algorithms.
Limitations of our approach. Like most previous methods [33, 2], we focus on optimizing the non- zero entries of a sparse sketching matrix with a fixed sparsity pattern (chosen at random). Learning the sparsity pattern from data during training may improve performance even further. However, since the search space is discrete and very large, it is not clear how to do so without a very large increase in training time (more in section 3). We leave this as important direction for future work.
Broader impact. Incorporating data into algorithms entails risks related to bias and fairness, as well as environmental effects of massive processing, Our methods carry benefits of interpretability and of significantly reduced GPU utilization, which may help alleviate these concerns. However, our work is focused generic algorithmic operation, and any application to a specific data domain would require further consideration of possible bias in the data as well as of privacy concerns.
1.2 Preliminaries
Low rank matrix approximation. In the LRA problem, the input a matrix A Raxd, say with > d, and integer 0 < k < d. The goal is to output matrix A' E Randd of rank & which minimizes the approximation error ||A - A'I where |1-I| denotes the Frobenius matrix norm. is standard fact (known the Eckhart- Young-Mirsky Theorem) that an optimal solution, often denoted as Ag, can be computed deterministically in time O(nd²) via the singular value decompo- algorithms that incur slightly larger approximation namely || - A + [| or better yet (1 + ++ A-| A& 12.. for an arbitrarily small >> 0 0- and run in time nearly linear in the size of A, and polynomial in k and c See [56] for survey.
sition. A long line of work has focused
The SCW algorithm. The data-oblivious LRA algorithm used as the basis for [33], henceforth called SCW, is due to [16]. building on [51, 15]. It uses random sketching matrix S E mx (where m & n is called the sketching dimension), chosen such that each column contains one non- zero entry at uniformly random row, with value which is uniformly random in {-1, 1}. Given an input matrix and the sketching matrix S, SCW computes the best LRA of A in the rowspace of A. This can be computed in several equivalent ways, for example, by Algorithm I below.
Algorithm 1: Sketch- based matrix low-rank approximation
Input: Input matrix A E Rnxd sketching matrix S E Rx Output: Rank-k approximation Á E gaxd of A. Procedure SCW(S, A):
ÚΣVT SVD of SA
[AV]; <- Optimal rank-k approximation of AÀ (computed by full SVD)
return [A
3

---

It is proven in [16] that sketching dimension of m poly(k, suffices for the output rank-k matrix A' to satisfy ||A - 3 S (1 + e) A As o with high probability. Furthermore, the algorithm can be implemented as two-pass streaming algorithm, using space ((m(n . + d)). Thus, reducing the sketch length m directly reduces the storage requirements of the algorithm.
The data-driven version of the LRA problem, introduced in [33], has two phases. In the training phase, we are given training set of matrices, Ataain C xxx Our goal to construct, or learn, a sketching matrix S. In the testing phase, we are given a test set of matrices, Atest C Rnxd We compute rank-k approximation for each of them using the SCW algorithm (Algorithm 1), but with the learned sketching matrix from the training phase instead of a random sketching matrix. The goal is to choose S so as to minimize the testing error,
Data-driven LRA.
Err(S, Asest) == E
(S,(SS,
(I)
AEAuctt
The IVY algorithm. In [33], S is initialized by sampling it from the same distribution as SCW - sparse random signs. The sparsity pattern (i.e., the locations of the non-zero entries in (S) remains fixed, while the values of those entries are learned by SGD over the training loss,
S argming Err(S" .ttest) argming g
Σ SCW(S, A)
AEAr
This requires computing gradients over the steps of SCW, which in turn uses two invocations of the SVD (in steps 2 and 3 of Algorithm 1). While not all implementations of the SVD are differentiable, IVY employs differentiable one which is based on the power method.
Safeguard guarantees. A common desideratum of data-driven algorithms is to guarantee they never perform much worse than their data-oblivious counterparts (see, e.g., [47, 44]). which could happen for example by over-tailoring to an irrelevant training set. For IVY. [33] note this can be achieved by simply concatenating oblivious sketching matrix the learned sketching matrix. This property is shared by subsequent work on data-driven LRA [3, 38] as well as by our algorithms.
1.3 Related Work
Most relevant to are the recent papers [3, 38), who proposed modifications to IVY. Ailon et al. [3] study replacing dense linear layers in deep networks by butterfly gadgets, which are dense matrices with an implicit sparse decomposition (see Section 3 for details). For data-driven LRA, they propose replacing the random sparsity pattern used in IVY with the butterfly (implicit) sparsity pattern.
Liu et al. [38] suggest several extensions to [33]. First, they apply the IVY learning scheme to the LRA algorithm of [6], which has better asymptotic running time than SCW. Second, they suggest a greedy initialization method for S, instead of the random initialization used in IVY. Third, they apply the method to several other linear algebraic problems, for which they provide provable guarantees.
An LRA algorithm by [18] forms a data-dependent sketching matrix SA from A by taking the top k right-singular vectors of the product SA, where 5 is oblivious sketching matrix, and returns A as an LRA of A. Though not intended as such, it can be viewed as a data-driven LRA algorithm, if one forms SA from A and then returns BSAST A as the LRA for a different input matrix B. However, this method cannot be safeguarded for worst-case guarantees as discussed above, and thus can perform arbitrarily poorly for B.
In [19], the random sketching matrices used by SCW are derandomized in data-dependent fashion. While this leads to a data-dependent LRA algorithm, its goal is not to improve the error achieved by SCW, but rather to match it without using randomness. Indeed, its output sketching matrix is from the same set as SCW (sparse with 11's in its nonzero entries), while the data-driven LRA algorithms study reduce the error by optimizing the non-zero values of the sketching matrix beyond +1.
In a broader point of view, our work belongs to a recent trend of improving the performance of cesource-constraingg algorithms by taking data-driven approach, which allows the algorithm to "prepare in advance" on a training set. In addition to LRA, other problems studied in this setting include caching [40, 50], scheduling [47, 37], data indexnng [36, 25J. set membership [44, 49, 54], frequency estimation over data streams [31, 1, 34, 17], clustering [8, 38), similarity search [20], support size estimation [22], multigrid methods [39], and more [29, 11, 9, 10, 5, 28, 35, 12, 55).

---

2 Few-Shot LRA Algorithms
In this section we present our proposed algorithms for few-shot data-driven LRA. The starting point of our algorithms is the same as IVY, in that they choose sparse matrix So E R=xx where each column contains a single non-zero entry in a uniformly random row. The goal is to use the given training set to set the value of the non-zero entries.
2.1 One-Shot Closed-Form Algorithms
Our first approach involves no learning mechanisms - instead, it operates in a closed-form manner on single randomly chosen matrix A from the training set. We describe two algorithmic variants of this approach, leading to two of our algorithms, which we call 1Shot1 Vec and 1Shot2Vec.
The sparsity pattern of So partitions the rows of A into blocks, A ..... A(m,, follows: Let I, = {j S( = 1}. i.c., 4 contains the non non-zero column indices in row i of S. The block A E glaixd; is the sub-matrix of A that contains the rows whose indices are in 4, Observe that in the product matrix SA (which is computed in the first step of SCW(S, A)), each row i 1,...: is a linear combination of the rows of A with the coefficients {S(i.)) : [.}. regardless of the remaining rows of A. Therefore, we can now handle every block separately and independently of the others. Our goal, for each block ( is to choose (non-sparsed one-dimensional sketching matrix, or just a sketching vector, 8; E I Our final output matrix S would be obtained by assigning the entries of s; to the non-zero entries in row i of S, for every 1,...,
How should we choose 8;? Two natural approaches come to mind. The first is to preserve as much of the Frobenius mass of A possible, i.c., to maximize || (00 This is attained by setting 8, to be the top left-singular vector of ( This is the algorithm call 1Shot1
The second approach is to choose a left-singular vector of A at random. The main advantage of this approach over the previous one is that it endows the algorithm with provable guarantees on the LRA error. To get the benefits of both approaches we can naturally combine them, leading to the algorithm we call Vec. Let Sj 2 be vertical concatenation of two copies of So. meaning that each row sparsity pattern is now repeated twice. Si induces the same partition of A into m blocks as Su (despite having twice as large of sketching dimension), but now we may choose two sketching vectors s/ S [ per block instead of just one. In 1Shot2Vec, we set of be the top left-singular vector of A and s² to be random left-singular vector from the remaining ones, chosen with probability proportional to its squared corresponding singular value. The algorithm in summarized in Algorithm 2.
These two approaches to choosing &; can be grounded in formal analysis. In brief, the rows of A can be partitioned into heavy and light according to their squared Euclidean norm relative to || The top singular vectors of each block help preserve the heavy rows, and the random singular vectors of each block help preserve the light rows. A formal statement is given below in Theorem 2.1. A more detailed overview of the analysis is given in Section 2.3, and a formal proof appears in the appendix.
Consistency. We call data-driven LRA algorithm consistent if sketching matrix S computed from a data matrix A indeed yields a good LRA when applied to A. This is a natural desideratum for data-driven LRA algorithms, guaranteeing success in the naive case where the test matrix is identical to the data matrix. The next theorem states that 1Shot2Vec is consistent we apply twice, with two similar but different sketching dimensions. (This duplication is due to technical reasons in the proof see Section 2.3 - and is not needed in practice.)
Theorem 2.1. Let m 2 poly (k log(n)/e) /c) and m' = (poly((( (I log(n)/c)-mm Let S E (mm+mm x be given by concatenating the sketching matrices computed by two calls to IShot2Vec, once with m and once with m', on given input matrix A E xad Then, with probability 0.99 over the random choices of 1Shot2 Vec, have." | SCW A) 1
Ax + A||A
'Scaling row of We remark that the guarantee of Theorem 2.1 is often referred to in the low rank approximation literature as an additive error LRA guarantee. The stronger relative error guarantee, I|A SCW A) < (1 + I|A All (see Theorem 2.2), in fact does not hold for 1Shot2Vee.
constant does not change the SCW output, so may assume s; has unit length.
5

---

Closed-form computation of a sketching matrix from a training matrix Input: Input matrix A E Roxd, sketching dimension m.
Algorithm 2:
Output:
Sketching matrix S.
Initialize S", S" E Rmmxn as zero matrices
Choose EI,..., En E ( m) independently and uniformly random
3 for i 1...., do
I = {j: =
A restriction of A to rows in 4
UEVT= + SVD of A
Denote by u1..... Uy the columns of U and by 01,..., oy the diagonal entries of Σ Choose à from {uz,.... 3 random with probability proportional o .... o
S"ii, [1] 6 uf
10
Sii [ + aT
1 Note that u2 and à are column vectors in RR4 w/
return 5' for 1Shot Vec or the vertical concatenation of S for 1Shot2Vec
2.2
Few-Shot SGD Algorithm
Our next algorithm, FewShotSGD, shares with IVY the following counts we learn the non-zero entries of the sketching matrix by optimizing a certain loss function with SGD, and we use the auto- grad mechanism to compute gradients. However, instead of minimizing the empirical training loss (Equation (2)). we use different loss function, motivated by the theoretical analysis of oblivious fast LRA algorithms. This loss function is considerably faster to optimize than Equation (2), par- ticularly since it does not require a differentiable implementation of the SVD, allowing us to use faster non-differentiable implementations, Furthermore, empirically, optimizing this loss with SGD arrives at local minimum after just 2 or 3 iterations, allowing us to use only that many random matrices from the training set.
To specify the loss function, let U denote the set of all left-SVD factor matrices of our training set:
(U A T is the SVD of some A).
Recall that k denotes the target low rank of the LRA algorithm. Let UR <Ra* denote the sub- matrix of that contains its first columns. Recall that the matrices in A are order n x d where l < d < n. Let Io R denote the result of augmenting the identity matrix of order & with d k additional zero columns on the right. The loss we minimize in FewShotSGD is:
Σ UEU
DISS
S SU - Toll?
(3)
where the variables are the non-zero entries of S E Rm (whose locations are given by So)- This loss function is motivated by the analysis of prior LRA algorithms that use random sketching matrices, see the last paragraph of Section 2.3 for further explanation.
To minimize Equation (3) with SGD, in each round we pick uniformly random A E A. compute its SVD to obtain U, and update S according to the gradient of |UT S SU - loll ? at the current setting of S. Importantly, unlike IVY [33],
SVD implementation need not be differentiable. The reason IVY requires differentiable SVD is that in each iteration, due to the term SCW(S,, A) in eq. (2), it computes a (partial) SVD of SA and of AÀ - both of which involve variables in S. Our loss computes the SVD of A, which independent of S, and thus no gradients flow through it.
The motivation behind the choice loss function Equation (3) is the following theorem, which can be viewed statement of consistency for FewShotSGD: If the loss is small, then SCW provably computes a good low rank approximation of A using S.
Theorem 2.2. Let A UEV be a matrix with its SVD. For a sketching matrix S E Rm let |1, ST SU 1o Then, || SCW(S, A) (1 + O()) ||A Ag l
As result, the loss minimized in eq. (3) is directly related to the empirical loss (eq. (2)).

---

2.3 Overview of Analysis
The proofs of Theorems 2.1 and 2.2 are quite involved and appear in full in the appendix. In this section we give an intuitive overview of the main ideas in their analysis.
One-shot algorithm: Theorem 2.1. Recall that Vehot2 partitions the rows of A into blocks according to So. and takes the top left-singular vector and random left-singular vector from each block. Let e' = poly(e/k k log n). To analyze the algorithm, we classify the rows ai, ... Un of A into three types, according to their relative mass || /2/l1 A|| (note that the masses sum to I):
Heavy rows, whose mass is at least 1/(c'm).
Light rows, whose mass is at most é' /m.
Medium rows, whose mass is between e'/m and 1/('m)).
The mass of each top-k direction of A, which we aim to preserve in the sketch, is distributed some- how over the rows of A. We show how the mass recovered by the sketch for each type of row,
Consider heavy row as Since each heavy row has mass at least 1/(e'm), there can be at most e'm of them. Since 1Shot2Vec partitions the rows of A into blocks at random, by standard hashing arguments, with high probability there will be no collisions, and thus a, would be the only heavy row in its block. Since its mass is significantly larger than the non-heavy rows, it can be shown that is highly correlated with the top-singular vector of the block, which the algorithm takes into the sketch. Thus, a, is well-represented in the sketch.
Next, consider the light rows. Here we use the notion of projection-cost preserving sketches (PCPs) [23, 18, 14, 45], and specifically, the additive-error PCPs introduced by Bakshi and Woodruff [7]. A (k, of A is a matrix B (with many fewer rows) that approximately preserves the Frobenius norm of A under every projection away from a k-dimensional subspace. Namely, || BP ||A - APII? + el A|.A for every rank-k projection P. The connection to LRA that the LRA problem A is equivalent to argminp A API]: and the PCP property implics that can find an approximate LRA for A by solving LRA on the (much smaller) matrix B.
In [7]. it is shown that a (k, c)-PP of A can be computed with high probability by sampling each row o; of A with probability least (1/c')[la=113 / A|. For light rows as defined above, this bound is at most 1 1/m. Since 1Shot2Vec partitions the rows of A into blocks uniformly at random, each block contains each light row with probability 1/m, and thus forms (k, c)-PCP for the light rows of A with high probability. As a result, the light rows are well-represented in the sketch.
Finally, handle the medium rows. Here we make use of the fact that Theorem 2.1 invokes 1ehot2Vec twice, once with sketching dimension m and once with m' = m//". and concatenates the resulting sketches. If a row a; medium in the first invocation, then its mass least e' é//m- 1/(e'm'), rendering it heavy in the second invocation. Thus, row a, is well-represented in at least one of the two sketches. Overall, the fact that every row is well-represented in the sketch implies that each of the top-k directions is approximately preserved in the resulting LRA, as needed.
Few-shot algorithm: Theorem 2.2. The theorem is based the original analysis of the data- oblivious SCW algorithm in [15, 16]. The main point is that the loss can be written as the sum of contributions of the first & columns and the last d columns, as follows:
(4) where I is the identity of order k; Ua- is U without its top-k columns, and 0 is the all-zero matrix of order l (d k). The first term, | S SU, T. measures how well the sketch preserves the top-k space of (note that U,_ Un = 1). The second term, [ "TTSSt SU Olp measures how well the sketch keeps the top-k space of A orthogonal to its bottom-(d (d-ddd-k k) space (note that U. Ua- = 0). By eq. (4), each of the terms is bounded by e, which is sufficient for low rank approximation with relative error O(c).
E = =IU S SU - loll3 = || S SUx - 11 + || ST SUa-x
3 Experiments
We evaluate our algorithms empirically and compare them to previous work on data-driven L.A.. For direct comparison, we use three datasets from [33], with the same train/test partitions - -Logo,
7

---

Logo Dataset
-0-IV
Buterfly
1ShottWeec [sun]
04
3.4
Fwuchatsti-3 (ound)
FewShorSCD
0.3
(ours)
5-0-0-0
0.1
700
Time (scconds]
(tecondd)
Hyper Dataset
16
Summury of dalasel properties:
14
Name
Type
Dimension
Traln # Test
Eagle
Video
3240 1920
400
100
Logo
Video
3240 x 1920
400
100
Hyperspectaal images
Hyper
x024x 768
3860
973
(swcond)))
Figure 1: Test set error per training time, with target rank 10 and sketching dimension m 40.
Eagle and Hyper [32]. All are publicly available, The performance of a sketching matrix S on set of input matrices measured similarly to [33], as
1 err ( = IAI
Σ AEA
(IAA SCW(S, I| A 12))
where we recall A₂ denotes the optimal rank-k approximation of A. This measures the additive gap between the sketch-bard based LRA and the optimal LRA of each matrix, averaged over the test set matrices. Experiments were on an NVIDIA GeForce RTX 2080 TI graphics card.
Our algorithms. To our feo-shot algorithms, training matrix, and FewShotSGD with either 2 or 3 randomly chosen training matrices (that is. 2 or 3 steps of SGD). addition, we incorporate our approach into a many-shot algorithm, by initializing the sketching matrix of IVY using our method 1Shot1 Vec instead of a random sign matrix.
evaluate 1Shot2 with randomly chosen
Baselines. As baselines, evaluate three methods: IVY [33], Butterfly [3], and Greedy [38].²
Butterfly. For integer k: > 0, butterfly gadget is matrix B R²2 222xx* x2* formed the product of k sparse matrices,
k-1 B,, where B, E 222xx2 x2 has in entry (J.J') if either j = j or j ④ 2 j (where @ denotes XOR), and otherwise. These well-known gadgets arise in the context of the Fast Fourier Transform. Ailon et al. [3] suggest using them for learned LRA, by forming sketching matrix from m rows of B, and learning new values for the non-zero entries of the B, 's by minimizing the empirical loss with SGD, similarly to IVY.
Greedy. Liu et al. [38] suggest initializing the sketching matrix by the following greedy procedure. Choose set V of 10 uniformly random values in [-2, 2]. Starting with zero matrix So E mm we fill column by column.
I..... n, let S.j.r denote the matrix obtained from S,-1 by putting in entry (j. t). Choose S; as the best performing matrix among {Si.j. E m.,, U V} over some subset the training set (say, a single random matrix).
step
Training times. We measure the error per training time for each method. The results are reported in Figure/ and in Table 1. We do not include Greedy in these results, since its training time is much longer than the other methods (35-40 minutes per matrix, versus up to 4 minutes for the other
We remark that [38] also proposed four-sketch alternative to IVY, based on [6]. which has faster asymp- totic running time. However, they reported that falls short of IVY empirically in its attained error.

---

methods), due to the sequential grid search it performs. We report its performance later in this section, where we measure the error per number of sampled training matrices.
The experiments show that our few-shot algorithms, 1Shot2Vec and FewShotSGD, achieve low error much faster than IVY and Butterfly, on all datasets. Table 1 lists the time it takes the baselines to reach the same error. Note that 1Shot2Vec is somewhat slower and less accurate than Few- ShotSGD with 2 iterations; nonetheless, it has the advantage of being "closed-form" algorithm that does not perform learning at all and does not require automatic gradient computation.
If IVY and Butterfly are allowed to run longer, and use sufficiently many training matrices, they eventually attain lower error than Aee and FewShotSGD. This is our motivation for intro- ducing 1Shot1 Ve (which we recall is the initialization of IVY with (ee), way to use our techniques to also improve the many-shot algorithms. This algorithm significantly outper- forms IVY, and outperforms Butterfly Logo, Eagle, and the small time/sample regime of Hyper.
Note that while the initial error of 1Shotl Vec+ is similar to IVY, the former error improves much faster in subsequent iterations. This is related to the formal guarantee of the oblivious SCW initialization, by which almost all of its initial #1 choices hit its target loss, irrespective of their location with respect to the local minima of IVY. There are exp(n) such initial choices even for a fixed sparsity pattern. Our deterministic data-tai taito-tailord initialization, on the other hand, is better positioned to choose point which, while having similar loss to SCW, is nearer to local minimum.
Remark. In light of the strong performance of 1Shot Vec+IVY, it may seem natural to apply the same initialization to the Butterfly. This turns out to not be possible. The trained parameters of Butterfly are not entries of S as IVY, but implicit parameters that make up S by multiplying a sequence of sparse matrices. Since a general sketching matrix is specified by nm parameters, whereas a butterfly gadget truncated to m rows is specified by only Onn log m) parameters [4, 3], arbitrary initializations of the sketching matrix cannot be realized by the butterfly gadget.
Testing times. Next we report the running times of the testing phase on each dataset, to substantiate the claimed advantage of sketch- based approximate LRA over exact LRA by SVD. Note that all of the algorithms evaluated above (IVY, Butterfly and our methods) have the same runtime in the test phase, since in this phase they all perform the same SCW procedure (Algorithm 1).
We measure the total runtime of computing LRA the test matrices by SVD versus baaee LRA. On Eagle/ / Logo / Hyper, LRA by SVD takes 88.8s/ / 89.7s / 190.7s, while sketch-based LRA takes 6.6s 7.0s/ / 22.1s, respectively. The average speed-up is by multiplicative factor of 11.6.
Sample complexity. Finally, we measure the error achieved by each method when given access to only small number of random matrices from the dataset (i.e., we evaluate each method in the few-shot setting). The results are reported in Table 2. They show that our methods obtain better performance than the baselines, with the exception of Greedy, which achieves lower eπrors on two of the datasets, even with just one sample matrix. However, we note that the training time of Greedy is few orders of magnitude larger: 2306.4 seconds Logo, 2325.5 seconds on Eagle, and 953.1 seconds on Hyper, for a single training matrix. In contrast, our few-shot methods train for up to 10 seconds up 3 matrices (on either dataset), and the many-shots methods train for up to 30 seconds. Determining whether it is possible to obtain fast algorithms that also learn the sparsity pattern is an important direction for future work.
Additional experiments. In the experiments above, our learned sketching matrices have only one non-zero entry per column. Recent work has suggested that using more non-zero entries per column (up to 8) can be more beneficial [52, 42]. The appendix includes some experimental results with sparsity 8.
is also possible to consider learning the sketching matrix on one dataset and applying it to another (transfer learning), or to learn it jointly from two different datasets (mixed learning). Transfer learn- ing in the context of LRA has been recently considered in [48]. the appendix we include some preliminary result in this vein, which suggest that these approaches can be useful for some datasets.

---

Table 1: Training time comparison of few-shot to many-shot data driven LRA algorithms. For each of our few-shot algorithms (1Shot2Vec and FewShotSGD with and iterations), we report the error attains each dataset, and the training time it takes. Then, for each of the many shot algorithms (IVY, Butterfly and IShot Vec+IVY), we report the training time takes to achieve the same error. N/A means the algorithm did not attain the error in the time allotted to the experiment.
Time to error for many-shot algorithms 1Shot Vec+IVY
Few-shot algorithm
Dataset
Few-shot error
Time
IVY
Butterfly
Eagle
1.14
8,892s
56.56s
30.34s
12.47s
Vehot2Vec
Logg
0.232
10.06s
143.75s
26.86s
22.43s
Hyper
1.04
0.78s
N/A
22.35s
9.36s
Eagle
0.563
6,417s
N/A
42.09s
18.81s
FewShotSGD-2
Logo
0.161
6.17s
N/A
45.14s
30.16s
Hyper
0.99
0.5s
N/A
22.35s
13.66s
Eagle
0.467
8.879s
N/A
53.26s
25 25.05s
FewShotSGD-3
Logo 0.155
9.65s
N/A
45.14s
30.
Hyper
0.98
0.99s
N/A
22.35s
13.66s
Table Error attained by each method on the test set each dataset, after training on and random matrices from the training set.
Matrices
Dataset
Vehot2Vec
FewShotSSD
1Shot Vec+IVY
IVY
Butterfly
Greedy
Eagle
1.14
1.888
2.172
2.163
0.062
Logo
0.232
0.397
0.485
0.51
0.23
Hyper
1.04
1.241
1.573
1,491
0.364
Eagle
0.563
0.65
1.864
2.036
0.047
2
Logo
0.161
0.289
0.427
0.468
0.263
Hyper
0.99
1.106
1.559
1.444
0.393
Eagle
0.467
0.507
1.617
0.785
0.064
3
Logo
0. 155
0.165
0.398
0.223
0.371
Hyper
0.98
1.015
1.538
1.271
0.367
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their useful suggestions. This research supported in part by the NSF TRIPODS program (awards CCF-174075) and DMS- 20224402444 NSF awards CCF- 2006798 and CCF-1815840, Office of Naval Research (ONR) grant NO00 100014-18-1-2566 and Simons Investigator Awards.
References
[1] Anders Aamand, Piotr Indyk, and Ali Vakilian. (learned) frequency estimation algorithms under zipfian distribution. arXiv preprint arXiv: (00.:::990.009988, 2019.
[2] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson- lindenstrauss transform. In Proceedings the thirty-eighth anmual ACM symposium on Theory of computing, pages 557-563, 2006.
[3] Nir Ailon, Omer Leibovich, and Vineet Nair. Sparse linear networks with a fixed butterfly structure: Theory and practice. arXiv preprint arXiv:2007.08864 2020.
[4] Nir Ailon and Edo Liberty. Fast dimension reduction using rademacher series on dual bch codes. Discrete & Computational Geometry, 42(4):615, 2009.
10

---

[5] Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, and Ellen Vitercik. Learning prune: Speeding up repeated computations. arXiv preprint arXiv: /175, 2019.
[6] Haim Avron, Kenneth L Clarkson, and David P Woodruff. Sharper bounds for regularized data fitting. arXiv preprint arXiv:1611.03225. 2016.
[7] Ainesh Bakshi and David P Woodruff. Sublinear time low-rank approximation of distance ma- trices. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3786-3796, 2018.
[8] Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. arXiv preprint vrXiv:/977.00533 2019.
(9] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik, Learning to branch. arXiv preprint 1rXiv:1803.10133 2018.
[10] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pages 603-614. IERE, 2018.
[11] Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning- theoretic foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pages 213-274. PMLR, 2017.
[12] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems, 2020.
[13] Christos Boutsidis and Alex Gittens. Improved matrix algorithms via the subsampled random- ized hadamard transform. SIAM Journal on Matrix Analysis and Applications, 34(3):1301- 1340, 2013.
[14] Agniva Chowdhury, Jiasen Yang, and Petros Drineas. Structural conditions for projection- cost preservation via randomized matrix multiplication. Linear Algebra and its Applications, 573: 2019.
[15] Kenneth I. Clarkson and David Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 205- 214, 2009.
[16] Kenneth L Clarkson and David P Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings of the forty-fifth annual ACM symposium Theory of Comput- ing. pages 81-90, 2013.
[17] Edith Cohen, Ofir Geri, and Rasmus Pagh. Composable sketches for functions of frequencies: Beyond the worst case. In International Conference on Machine Learning. PMLR, 2020.
[18] Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Di- mensionality reduction for k-means clustering and low rank approximation. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 163-172, 2015.
[19] Daniel Dadush, Cristóbal Guzmán, and Neil Olver. Fast, deterministic and sparse dimensional- ity reduction. In Proceedings of the Twenty-Ninth Anmual ACM-SIAM Symposium on Discrete Algorithms, pages 1330-1344 SIAM, 2018
[20] Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2020.
[21] Petros Drineas, Michael W Mahoney, Shan Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische mathematik, 117(2):19-244,22) 2011.
[22] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wag- ner. Learning- support estimation in sublinear time. International Conference on Learning Representations, 2021.

---

[23] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: constant size coresets for k-means, pea and projective clustering. In Proceedings of the twenty- fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1453, 2013.
[24] Xu Feng, Yuyang Xie, Mingye Song, Wenjian Yu, and Jie Tang. Fast randomized pea for sparse data. In Asian conference on machine learning, pages 710-725. PMLR, 2018.
[25] Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. Why are learned indexes so effec- tive? In International Conference on Machine Learning, pages 3123-3132. PMLR, 2020.
[26] Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM), 51(6): 1025-101,, 2004.
[27] Alex Gittens and Michael Mahoney. Revisiting the nystrom method for improved large-scale machine learning. In International Conference on Machine Learning, pages 567-575. PMLR, 2013.
[28] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319-2327, 2019.
[29] Rishi Gupta and Tim Roughgarden. A pac approach to upplication-speeee algorithm selection. SIAM Journal on Computing, 46(3):992- 2017.
[30] 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.
[31] Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estima- tion algorithms. In International Conference on Learning Representations, 2019.
[32] Nevrez Imamoglu, Yu Oishi, Xiaoqiang Zhang, Guanqun Ding, Yuming Fang, Toru Kouyama, and Ryosuke Nakamura. Hyperspectral image dataset for benchmarking on salient object detection. In 2018 Tenth International Conference on Quality of Multimedia Experience (QoMEX), pages 1-3, IEEE, 2018
[33] Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning- based low-rank approximations. In Ad- vances in Neural Information Processing Systems, pages 7402-7415 2019.
[34] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P Woodruff. Learning-ait aagmented data stream algorithms. In International Conference on Learning Representations, 2020.
[35] Rohan Kodialam. Optimal algorithms for ski rental with soft machine-learned predictions. arXiv preprint arXiv: arXiv:1903.000 11993300999 2019.
[36] Tim Kraska, Alex Beutel, Ed Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489-504, 2018
[37] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourleenth Annual ACM-SIAM Sym- posium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
[38] Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, and David P Woodruff. On learned sketches for randomized numerical linear algebra. arXiv preprint arXiv:2007. 099900 2020.
[39] Ilay Luz, Meirav Galun, Haggai Maron, Ronen Basri, and Irad Yavneh. Learning algebraic multigrid using graph neural networks. In International Conference Machine Learning, pages 6489-6446 6499. PMLR, 2020.
[40] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3296-3305, 2018
[41] Michael W Mahoney. Randomized algorithms for matrices and data. arXiv preprint arXiv: 104.555,, 2011.
12

---

[42] Per-Gunnar Martinsson and Joel A Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29:403-572, 2020.
[43] Xiangrui Meng and Michael Mahoney. Low-distortion subspace embeddings in input- sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth anmual ACM symposium on Theory of computing, pages 91-100, 2013.
[44] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, pages 464 473, 2018.
[45] Cameron Musco and Christopher Musco. ronjiection-costppeeeevve sketches: Proof strategies and constructions. arXiv preprint arXiv:2004, 08434, 2020.
[46] Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pages 11 117-126. IEFF, 2013.
[47] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predic- tions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018.
[48] Christoph Raab and Frank-Michael Schleif. Low-rank subspace override for unsupervised domain adaptation. In German Conference on Artificial Intelligence (Künstliche Intelligenz). pages 132-147. Springer, 2020.
[49] Jack Rae, Sergey Bartunov, and Timothy Lillicrap. Meta-learning neural bloom filters. In International Conference on Machine Learning, pages 5271-5280, 2019.
[50] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 1834-1845. SIAM, 2020.
[51] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 143-152. IEEE, 2006.
[52] Joel A Tropp. Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Streaming low-rank ma- trix approximation with application scientific simulation. SIAM Journal Scientific Computing, 4 ((4::A2430-A2463 2019.
[53] Madeleine Udell and Alex Townsend. Why are big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 1(1):144-160, 2019.
[54] Kapil Vaidya, Erie Knorr, Tim Kraska, and Michael Mitzenmacher. Partitioned learned bloom filter. In International Conference on Learning Representations, 2021.
[55] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. Advances in Neural Information Processing Systems, 33, 2020.
[56] David P Woodruff. Sketching as a tool for numerical linear algebra. arXiv preprint 1rXiv:1411.4357, 2014.
[57] Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. A fast randomized algorithm for the approximation of matrices. Applied and Computational Harmonic Analysis, 25(3):335- 366, 2008
13


Reviews:
[{"review_id": "j5LpaXDNnje", "reviewer": "Reviewer_hcCP", "summary": "The paper proposes two simple methods to learn the sketching matrix in low-rank matrix approximation. They serve as strong baselines to compare against other data-driven methods that learn the sketching matrix from training data.\nThe first method (one-shot), 1Shot1Vec / 1Shot2Vec, sets the sketching matrix using the singular vectors of blocks of the matrices in the training data.\nThe second method (few-shot), uses a different objective from the usual data-driven low-rank approximation that avoids costly calls to the SVD.\nThe paper empirically validates these two approaches, showing that they are fast and are competitive with more complex methods.", "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": "Strengths:\n1. Both of the proposed methods are simple and fast. They avoid costly calls to the SVD. Moreover, the sketching matrix learned is interpretable, unlike the black-box nature of existing methods.\n2. The modified objective of the few-shot method sheds light on the nature of low-rank approximation, pointing out more precisely what we need in a sketching matrix.\n\nWeaknesses:\n1. The motivation for the methods are not very strong. The paper motivates the method by arguing the existing methods requires auto-differentiation, GPUs, and long-training time. The first two conditions are now quite accessible in machine learning (or almost ubiquitous), so it's not clear to me when one would use the proposed methods instead of the existing methods.\n2. The advantage compared to existing methods isn't very noticeable. The two proposed methods can be seen as better initialization for the sketching matrix before running SGD. However, as seen in Figure 1, after some iterations of SGD (around 3x the amount of time of the proposed methods), existing methods also find sketching matrices that are just as good. So it seems one would need to run SGD anyway, and I'm not sure how much benefits these few-shot algorithms would bring.\n\n============== Post-rebuttal\n\nThank you for the response to my questions. That has helped me understand the method better.\n\nI've increased my rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "QZjARRq8E1_", "reviewer": "Reviewer_sJ5B", "summary": "Problem: Sketching based techniques (such as randomized algorithms, etc) is the go to approach for deriving a low rank approximation. Despite their power in terms of space and speed to deduce the solution, these algorithms induce large approximation errors, which regresses at the downstream tasks and need to be addressed\nSolution: A data-driven approach for low rank approximation -- A low rank representation is learned by optimizing a frobenius loss function over the input training and approximation. There are some challenges with this approach. The proposed algorithm is less data hungry with a two step analytical approach.\nResults: Significant gains in terms of accurate low rank approximations with less resource usage. \n", "questions": "", "limitations": "", "rating": 7, "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": "Distinction from state-of-the-art:\nProviding a low rank approximation is a handy technique, especially in the big data world. Given that, the proposed model clearly positions w.r.t the state-of-the-art methods such as IVY and addresses some of the limitations of the earlier method. \n\nPros:\nThe paper is well written with a few to no grammatical errors, easy to follow and understand.\n\nAn effective analytical approximation which performs better even with small amounts of data.\n\nCons:\nFirst of all, the abusive use of the word “latter” is really confusing, sometimes IVY is latter and other times it is the new method, please be consistent.\n\nSince the proposed method is so fast, I wonder, what is the effect of multiple random initializations? If you repeat the experiment for multiple runs will the results still hold on an average? Even an average of these runs can help close the gap further, can you check?\n\nI agree the method looks better over the state-of-the-art, however, can we add more value by exploring a different dimension in this space of research? That is, can the proposed approach be considered as a general enough for multiple inputs? Of course, the ranks are not the same for all the inputs. For example, what if you can synthesize the same rank benchmarks from different distributions and apply this method either individually or by mixing them? In the individual case, can the result of one benchmark be used as the initial point for a different benchmark (a form of transfer learning)? In the mixing case, can the solution be general enough?\n\nBased on the response, willing to up the score.\n\n\n### Post author response\n\nSatisfied with the author response and increase the score to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Providing a low rank approximation is a handy technique, especially in the big data world. Given that, the proposed model clearly positions w.r.t the state-of-the-art methods such as IVY and addresses some of the limitations of the earlier method. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns to the best of my evaluation.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 -- 4 hours"}, "extra_text": {}}, {"review_id": "DasnWUXd-D", "reviewer": "Reviewer_oFt2", "summary": "This work is about the optimization of sparse sketching matrix in randomized low-rank matrix approximation. The data-driven low rank approximation algorithms are developed with better computational efficiency in the training phase. The experiments show the proposed algorithms are empirically advantageous over previous work with improved training time.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "1.The sparse sketching matrix considered in this work contains a single non-zero entry in each column. This is not a widely-used sketching strategy and would lead to relatively large error in the produced randomized LRA. Allowing 8 nonzero entries in each column is more practical which makes similar accuracy of approximation to that employing Gaussian random matrix, as suggested in J. A. Tropp and Martinsson’s recent work. \nThe above sparse pattern (8 nonzeros in each column) in the sketching matrix should be considered in experiments. And, it seems the proposed method does not work in this scenario, while the method in [32] is able to handle it.\n\n2. In Section 2.1, the idea of preserving as much of the Frobenius mass in 1Shot1Vec is not explained. By the way, do you assume that 2-norm of s_i is 1? Otherwise, it cannot infer that s_i should be the top left singular vector. This strategy and that randomly selecting singular vectors in 1Shot2Vec should be supported with more solid theoretic analysis and discussion.  \n\n3. In the experiments, what’s the Error in Fig. 1? Is that the formula after line 292 on Page 7? The value of that formula depends on the norm of the data matrix and is not very good. A dimensionless value to measure the error is preferable.\nAlthough some matrix data are tested in Section 3, the application scenarios of them are not explained. And, the size of test matrix is small. Why is computing the LRA of them important?\n\nSome minor concerns.\n1. Algorithm descriptions should be given in Section 2.\n2. Eq. (2) is wrong?\n3. Step 2 of Alg. 1, alternatively, QR factorization can be applied.\n4. The references are not complete, and several recent work very relevant to randomized LRA are missed, e.g.\n[1] Randomized numerical linear algebra: Foundations and algorithms\nPG Martinsson, JA Tropp - Acta Numerica, 2020 - cambridge.org\n[2] Fast randomized PCA for sparse data\nX Feng, Y Xie, M Song, W Yu… - Asian conference on …, 2018 - proceedings.mlr.press\n\n------\nAfter reading the authors' response and the paper again, I'm willing to raise my review score. This work is good and can be accepted, providing that the presentation is improved to address the review concerns. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new data-driven approach for low rank approximation. Similar to previous works, it is based on the optimization of sparse sketching matrices, which leads to important reductions in computation and memory at test time. The proposed algorithm, significantly improves the computational efficiency in the training phase.

The authors provided a high quality rebuttal including new experiments and clarifying several points raised by the reviewers. All reviewers increased their scores by one and consequently all reviewers recommend accepting the paper. 

All reviewers consider that the work makes an interesting contribution to the field. The proposed algorithm is simpler than previous work, but is able to achieve similar performance while being computationally more efficient. The method is well motivated from an analytic perspective providing several insights on the problem. For instance, the sketching matrix learned is interpretable and can be set with meaningful values extracted from the dataset.

Overall the AC considers that the paper makes a solid contribution to the field and recommends its acceptance. The authors should incorporate the several clarifications provided to the reviewers (in particular those of Reviewer oFt2).

Decision: Accept (Poster)