Range-Net: A High Precision Neural SVD
Authors: Soumyajit Gupta
Gurpreet Singh
Clint N. Dawson
Venue: ICLR 2022 Submitted (2022)
Keywords: SVD
Eigen
Interpretable
Neural Nets
Streaming
Big Data

Abstract: For Big Data applications, computing a rank-$r$ Singular Value Decomposition (SVD) is restrictive due to the main memory requirements. Recently introduced streaming Randomized SVD schemes work under the restrictive assumption that the singular value spectrum of the data has an exponential decay. This is seldom true for any practical data. Further, the approximation errors in the singular vectors and values are high due to the randomized projection. We present Range-Net as a low memory alternative to rank-$r$ SVD that satisfies the lower bound on tail-energy given by Eckart-Young-Mirsky (EYM) theorem at machine precision. Range-Net is a deterministic two-stage neural optimization approach with random initialization, where the memory requirement depends explicitly on the feature dimension and desired rank, independent of the sample dimension. The data samples are read in a streaming manner with the network minimization problem converging to the desired rank-$r$ approximation. Range-Net is fully interpretable where all the network outputs and weights have a specific meaning. We provide theoretical guarantees that Range-Net extracted SVD factors satisfy EYM tail-energy lower bound with numerical experiments on real datasets at various scales that confirm these bounds. A comparison against the state-of-the-art streaming Randomized SVD shows that Range-Net is six orders of magnitude more accurate in terms of tail energy while correctly extracting the singular values and vectors.

Under review as a conference paper at ICLR 2022
RANGE-NET: A HIGH PRECISION NEURAL SVD
Anonymous authors
Paper under double-blind review
ABSTRACT
For Big Data applications, computing rank-r Singular Value Decomposition (SVD) is restrictive due to the main memory requirements. Recently introduced streaming Randomized SVD schemes work under the restrictive assumption that the singular value spectrum of the data has an exponential decay. This is seldom true for any practical data. Further, the approximation errors in the singular vectors and values are high due to the randomized projection. We present Range-Net as a low memory alternative to rank-r SVD that satisfies the lower bound on tail -eneryy given by Eckart- Young-Mirsk, (EYM) theorem at machine precision. Range-Not Net is a deterministic two-stage neural optimization approach with random initialization, where the memory requirement depends explicitly the feature dimension and desired rank, independent of the sample dimension. The data samples are read in streaming manner with the network minimization problem converging the desired rank-r approximation. Range-Net is fully interpretable where all the network outputs and weights have specific meaning. We provide theoretical guarantees that Range-Net extracted SVD factors satisfy EYM tail-energy lower bound with numerical experiments on real datasets at various scales that confirm these bounds. A comparison against the nate-of-the-art streaming Randomized SVD shows that Range-Net is six orders of magnitude more accurate in terms of tail energy while correctly extracting the singular values and vectors.
INTRODUCTION
Singular Value Decomposition (SVD) is pivotal to exploratory data analysis in identifying an invariant structure under minimalistic representation (assumptions on the structure) containing the span of resolvable information in the dataset. Finding low rank structure is a fundamental task in applications including Image Compression (de Souza et al. 2015), Image Recovery (Brand) 2002)) Background Removal (Wang et al. 2018), Recommendation Systems (Zhang et al.] (005) and as a pre- re-processing step for Clustering Drineass et al. 2004) and Classification (Jing et (017)) With the advent of digital sensors and modern day data acquisition technologies, the sheer amount of data now requires that revisit the solution scheme with reduced memory consumption as the target. In this work, we reformulate SVD with special emphasis on the main memory requirement, with no loss in accuracy, that precludes it's use for big data applications.
It is well known that natural data matrices have a decaying spectrum wherein saving the data in memory in its original form is either redundant or required from an application point of view. However, any assumption on the decay rate can only be validated if the singular value decomposition known priori, which is seldom the case in exploratory data analysis (see Fig. 3). Visually assessing a rank-r approximation for image processing applications might seem correct qualitatively (see Fig. 4 but are still prone to large errors due limited human vision acuity (see Fig. 6). This further exacerbated when the application at hand is associated with scientific computations wherein the anomalies or unaccounted phenomena are still being explored from large scale datasets. The reader is preemptively referred to Fig. 19 where the high frequency features related to turbulence cannot be disregarded. Furthermore, for classification and clustering problems where feature dimension reduction is desirable it is imperative that low-rank approximation of dataset contains most (2 90%) of the original information content without altering the subspace information. In this case, an over-sampled rank can exceed the feature dimension of the data itself (see Section 4.2

---

Under review as a conference paper at ICLR 2022
1.1 PROBLEM STATEMENT
Let us denote the raw data matrix as X E Rmxxn of rank / S min(m, n) and its approximation as X, Rmxx" The SVD of X is X UEVT, where U E RRxx = =[u1,-- [z] and V R
[vi,".. : .yy] are its left and right singular vectors respectively, and E E TR/x/= diag( ,01) are its largest non-zero singular values. The rank (r - f) truncation of X is then X, U, V." where Σ, = Ejr.j are the top singular values, and U, = Up and V, = Viri are the left and right singular vectors. In other words, X = UEVT = U,E,V² + Uv Ar Ar X, + Xyrr Here, Up Vnr are the trailing f left and right singular vectors.
Theorem 1. Eckart- Young-Mirsly Theorem (Eckart & Young 1936 Mirsky 1960 Let X E R be a real, rank-f, matrix with m 2 n. with the singular value decomposition as X -UVV where the orthonormal matrices U, V contain the left and right singular vectors of X and E is diagonal matrix of singular values. Then for an arbitrary rank-r, S f matrix B, E RRxx,
|| - Brllr ||X X
where X, = U,E,V with E, is the diagonal matrix of the largest r singular values and Up, Vr are the corresponding left and right singular vector matrices.
The problem statement is then: Given X E R Ruxn find X such that,
arg min &ERTXn ran
(I)
In effect, the minimizer X. of the above problem gives us the rank-r approximation of X such that X, X., In this work we utilize the minimizer of the above problem to extract the top rank-r SVD factors of X without loading the entire data matrix into the main memory. Note that the minimizer naturally gives the lower bound on this tail energy addition to being a rank-r approximation.
1.2 MAIN CONTRIBUTIONS
Data and Representation Driven Neural SVD: The representation driven network loss terms en- sures that the data matrix X is decomposed into the desired SVD factors such that = UVVT, In the absence of the representation enforcing loss term, the minimizer of Eq. I results in an arbitrary decomposition such that X = ABC different from SVD factors.
A Deterministic Approach with GPU Bit- Bit-precision Results: The network can be initialized with weights drawn from a random distribution where the iterative minimization is deterministic. The streaming order of the samples is of no consequence and the user is free choose the order in which the samples are processed in a batch-wise manner (indexed or randomized).
First Streaming Architecture with Exact Low Memory Cost: Range-net requires an exact mem- ory specification based upon the desired rank-r and data dimensions X E = given by r(n+ + r), independent of the sample dimension m. This is the first streaming algorithm that does require the user to wait until the streaming step is complete, contrary to randomized streaming algorithms. Layer-wise Fully Interpretable: Range-Net is low-weight, fully interpretable, dense neural net- work where all the network weights and outputs have a precise definition. The network weights are placeholders for the right (or left) orthonormal vectors upon convergence of the network minimization problems (see Appendix D). The user explicitly plug ground truth solution verify the network design and directly arrive at the tail energy bound.
2 RELATED WORKS
The core idea behind randomized matrix decomposition is to make one or more passes over the data and compute efficient sketches. They can be broadly categorized into four branches: 1) Sampling based methods (Subset Selection (Boutsidis et al.) 2014) and Randomized CUR (Drineas et al. 2006)); 2) Random Projection based QR (Halko et al.) 201 ID; 3) Randomized SVD (Halko et al. 2011); and 4) Power iteration methods Musco & Musco, 2015). The sketches can represent any combination of row space, column space the space generated by the intersection of rows and columns (core space). However, all of these methods require loading the entire data in memory. Readers referred to Kishore Kumar & Schneider (2017): Ye al. (2019) for expanded survey.
2

---

Under review as a conference paper at ICLR 2022
Conventional SVD although deterministic and accurate, becomes expensive when the data size increases and requires r passes over the data (see Table I.. The two branches of interest to us are the randomized SVD and Power iteration Methods for extracting SVD factors. Randomized SVD algorithms (Halko et al. 2011 are generally a two stage process: 1) Randomized Sketching uses random sampling to obtain reduced matri(x/ces) which covers any combination of the row, column and core space of the data; and 2) Deterministic Post-processing performs conventional SVD on the reduced system from Randomized Sketching stage. These approaches make only one pass over the data assuming that the singular value spectrum decays rapidly.
Power iteration based approach (Musco & Musco 2015) requires multiple passes over the data and are used when the singular value spectrum decays slowly. This class of algorithm constructs a Krylov matrix inspired by Block Lanczos (Golub & Underwood 1977) to obtain polynomial series expansion of the sketch. Although these algorithms achieve lower tail-energy errors, they cannot be used in big-data applications when X itself too large to be retained in the main memory, Here, constructing a Krylov matrix with higher order terms such as (AA" or A A) is not feasible
Table 1: Current best randomized SVD Methods. k. 1, are overestimated sketch sizes for a rank-r estimate s.l. kt 8, >> r. Note that Range-Net has an exact memory requirement (as conventional SVD), unlike order bounded Randomized methods. Note that deterministic implies the solution obtained upon convergence is deterministic.
Metbod
Halko et al.
2011
Upudbyay 2016
Tropp al. (0177)
Tropp al. 2019
Range Net
Conventional SVD
Space Complexity
O + n)]
OiM(n +:) +
O(km + ml)
Obi(m + + <(n r)) $
n/m 26)
# Passes
1
Type
Randomized
Randomized
Randomized
Randemized
Deterministic
Deverministic
Due to main- memory restrictions on remote compute machines, streaming (Clarkson & Woodruff 2009 Liberty 2013) algorithms became popular. For low-rank SVD approximations these involve streaming the data and updating low-memory sketches covering the row, column and core spaces. Existing randomized SVD capable of streaming include Halko et al. (201T); [Upadhyay| (2016): Tropp) ct al. (2017a 2019). each with different sketch sizes and upper bounds on approximation errors (Table
SketchySVD (Tropp et al. 2019) is the state of the art streaming randomized SVD, with sketch sizes comparable to it's predecessors and tighter upper bounds on the tail energy and lower errors. As two stage approach, SketchySVD (Alg. D constructs an overestimated rank- (k, s) sketch of the data based on row, column and core projections. A QR decomposition on the row and column sketches gives an estimate of the rank-k subspace. This is followed by a conventional SVD on the core matrix to extract it's singular values and vectors. Finally, the singular vectors are returned after projecting them back to the original row and column space. The time cost of SketchySVD is O(k3 (m + n)) with memory cost Olk(m + n) + 5²) with oversamling parameters k 4r 1 and s 2k
2.1 LIMITATIONS OF RANDOMIZED SVD APPROACHES
We discuss a few limitations that led us to reformulate the problem in the spirit of EYM theorem. The reader is referred to Appendix A for a detailed discussion and supporting numerical examples to further enunciate these limitations.
Tall and Skinny Matrices: For rank-r approximation of X E Rm of rank-f. Randomized SVD methods rely upon rank-k (k > r) sketches of X. However, these methods are useful only when k 2 but for practical datasets f < min(m, n.) and therefore the memory requirement can still be overbearing. The reader is referred to Section 4.2 for a practical example.
Exponential Decay of Singular Values: Assuming exponential decay implies the rank of X itself is such that f < min(m (m, r2). For real world applications, the data matrices are almost full rank f= min (m, n)., where a rank r truncation is chosen such that the desired dominant features are accounted for. Appendix[A A shows a synthetic case with non -on-exponettial decay of singular values where sketching accrues substantial errors. Further, it is difficult to assume that the decay rate will follow strict functional form: mixture of linear, exponential and others (see Fig. 3
Upper Bound on Tail Energy: The problem statement in Eq. suggests finding minimum with the minimizer providing lower bound on the tail-energy. Even if the solution scheme is upper bounded Halko et al. 2011 Upadhyay 2016
Tropp et al. 20 2019), the minimizer X, in Eq.
(c) and Fig. 8 for performance comparison between power iteration schemes and Range-Net for mid-sized real and synthetic dataset that can be loaded on our compute machine.
Readers are referred to Fig. 5
3

---

Under review as a conference paper at ICLR 2022
equivalently achieving the lower bound is necessary.
Approximation Errors: A low-rank SVD solver that does not iteratively compute the projection (left or right) while solving Eq. [ cannot extract SVD factors with low errors with multiple passes over the data matrix or multiple runs. As shown later in Theorem 2 any subspace projection (left or right) of the original data matrix that does not correspond to the minimizer in Eq. [ increases the tail energy and therefore results in incorrect low-rank SVD factors (singular values and vectors). Memory Requirement: Randomized SVD requires an optimal choice of hyper-parameters (sketch sizes etc.) that are subjective to the dataset being processed. In a practical, limited memory scenario, this entails tuning the
for optimal trade-off between memory requirement, compute time and an approximation error that does not violate the upper bound on the tail energy.
Remark. A low relative error in tail energy does not imply the extracted singular values and vectors will have similar relative ervors at scale. The issue has been raised by Musco & Musco (2013), that merely upper bounding the tail energy equipped with Frobenius spectral norm does not bound the approximation errors the extracted singular values or vectors. Therefore, for a fair comparison we show error metrics the extracted singular factors for all our numerical experiments.
RANGE-NET: A 2-STAGE SVD SOLVER
We present Range-Net that explicitly relies upon solving the minimization problem in Eq. | to achieve the lower bound on the tail-energy for a desired rank-r approximation of a data matrix X under streaming setting. The readers are referred to Appendix [B for the preliminaries followed by proofs of theorems and lemmas associated with each of the two stages.
Rank Approximation
X
XVV.
XV.
XV.
XV.
V.0
Stream
Dump
Dump
Data
Image/Graph/Matrii
Figure An overview of the low- wow-memory. two-stage Range-Noc SVD for Big Data Applications. Stage 1 identifies the span of the desired rank-r approximation. Stage rotates this span align with the singular vectors while extracting the singular values of the data. The input data can be streamed from either server secondary memory. If the target is just rank-r compression then Stage-2 he discarded without any loss in accuracy. Stage-2 only orders the rank-r features based upon their respective tail energies.
3.1 NETWORK ARCHITECTURE
The proposed network architecture is divided into two stages: (1) Projection, and (2) Rotation, each containing only one dense layer of neurons and linear activation functions with no biases. Fig. 2 shows an outline of the this two-stage network architecture where all the weights and outputs have specific meaning enforced using representation and data driven loss terms. Contrary to randomized SVD algorithms the subspace projection (Stage 1) not specified preemptively (consequently no assumptions) but is computed by solving iterative minimization problem following EYM theorem corresponding to Eq. [ The rotation stage (Stage 2) then reuses the EYM theorem again in a modified form to extract the singular vectors and values.
The projection stage constructs an orthonormal basis that spans the r-dimensional sub-space of data matrix X E pmxnn of unknown rank < min(m, n). This orthonormal basis (V) is extracted the stage- network weights once the network minimization problem converges to fixed-point. The representation loss ІV Trll lr in stage-1 enforces the orthonormal requirement on the projection space (even when r >> f) while the data- driven loss || XVVT F minimizes the tail energy. Although the minimization problem is non-convex, the tail-energy guaranteed to converge to the minimum at machine precision. The reader is referred to Appendix for a discussion on the minimization problem (bi-quadratic loss function with 2" global minima) for details regarding the convergence behavior.
Stage 1: Rank-r Sub-space Identification:
Theorem 2. For any T, Z+, 0 <T f. if the tail energy of a rank-f matrix X E pmxx f min(m, n)), with respect an arbitrary rank-r matrix B, XV, V.T is bounded below by the tail
4

---

Under review as a conference paper at ICLR 2022
Linear
Linear
Projection
x
Rotation
Y = x
Vune
0rxr
-1 -idight yy xV
Loss
IVTV- LII
XXPV XII
y y ding(Y YYill
Fiods
Figure 2: Network Architecture:
Projection (Stage-I) and Rotation (Stage-2) for 2-stage SVD
energy of X with respect to it's rank-r approximation X, XV,VT as, ||X BrllE 2 I|X 1 where, V, = span(v1, "2, [ and v.s are the right singular vectors corresponding to the largest r singular values then the minimizer of arg min X XVVVI is V. such that V.V." = V,V""
VE3(mXn)
As per Theorem 2 the equality holds true only when [B, [X,) Further, define B, as, B, XVVT then, V.V.T VT and V.V, I, where V, is rank-r matrix with column vectors as top-r right singular vectors X. The minimization problem then reads,
min V
|| XVVT s.l. セV==
with a minimum the fixed point V, Sponffj...... where Ui=1..... are the right singular vectors of X,.. This minimization problem describes the Stage I loss function of our network architecture. Upon convergence, the minimizer V. is such that V.V. = V.V."' following Theorem where V, is the matrix with columns as right singular vectors of X corresponding to the largest singular values of X.
Lemma 2.1. If VVV,V, = I, and V,VT = =VVV then VTV==I,
Lemma 2.2. If X E mm is rank f matrix, then for any rank r > f, where (r, f) S min(m, n). VV = I, and V. = V.V²² then V² Iy.
Remark. Note that for f. the orthonormality constraint is trivially satisfied as shown in Lemma 2.1 However for >> f, the orthonormality constraint ensures that the column vectors in V,, are orthonormal (see Lemma 2.2) allowing us extract orthonormal right singular column vectors of V, from the Stage 2 minimization problem.
Stage 2: Singular Value and Vector Extraction: The rotation stage then extracts the singular values by rotating the orthonormal vectors (V.) to align with the right singular vectors (V, V.O,). From the fixed point of the Stage-1 minimization problem Eq, 2 we have V, V V.V.T. According to
the EYM theorem the tail energy of a rank-r matrix X XV,C,, where C, is an arbitrary rank-r, real valued, square matrix, with respect to XV, now bounded below by 0 or |XV, - XV,CrIle 2 0.
Theorem 3. Given a rank-r matrix XV, R and an arbitrary, rank-r matrix C mxrr follow- ing Theorem
7 the tail energy of XV, with respect to XV.C is bounded as, ||XV, XV.C 2 0, where the equality holds true if and only C I,-
Lemma 3.1. IfC = 0,0%, where O E Rrxr is a rank-r matrix such that C = I,, then θ, is real- valued unitary matrix an r-dimensional Euclidean space.
V.VT where V, is a matrix with column vectors as the top-r right singular vectors of X, and a real-valued unitary matrix O, B then (XV.0,)² (XV.0,, is diagonal matrix Σd where Σ = diag(of,o oo. .oo)) and a, are the top-r singular values of X if and only VV V
Theorem 4. Given a rank-r matrix XV, E Rmxx such that V.VT
From Theorem 3 and Lemma 3.1
we know that, C, = O, where θ, is a rank-r, unitary matrix an r-dimensional Euclidean space. Further, from Theorem 4 we have that (VV,,))((VV,e) is diagonal matrix Σ diag(oñ. oo)), where o,s the top-r singular values of X if and only V.O,, = V,, Assuming Y -V, the minimization problem now reads:
min | XV.IIF s.t. YTY diag ( (Y) =0
33)
5

---

Under review as a conference paper at ICLR 2022
Remark. Note that stage can be verified numerically independently of stage 2 by checking whether the orthonormality condition is met in addition to minimization problem converging to the tail-energy bound. Similarly, stage 2 minimization problem will return rotation matrix O O, = 0, = -r. de)(())) = 1) upon convergence that can again be verified numerically.
As discussed previously, this choice of loss terms equipped with Frobenius norm ensures rank-r approximation in accord with the Eckart- Boung-Mirsky (EYM) theorem. We therefore state that the expected values of the stage-1 loss term at the minimum must correspond to the rank (n r) tail energy. Further, the stage-2 loss is expected to reach a machine precision zero at the minimum. Once, the network minimization problems converge, the singular values are extracted from Stage network weights θ Σ (XV. o, (.V. (XV, G,). The right singular vectors using Stage layer weights given by V, = v. Once V, and Σ, are known, left singular vectors U, XV,0, E, Please note that for implies inverting the non-singular values using a threshold of 10-$
be extracted
f. f singular values zero and therefore Σ,-
Implementation Details: A detailed discussion and justification of our implementation choices given in Appendix E These include a) Activation: all the activation functions are linear with no biases, since SVD requires linearly separable orthogonal features; b) Data Split: do not perform any split of the training data, since SVD factors are unique to the full data only; c) Data Streaming: we stream data from HDD into main memory to avoid data sample load; d) Training and Setup; e) Error Metrics; and f) Loss Profiles. Note that Range-Net has no hhper--prrmnan parameters and therefore does not require any post-hoc tuning or adjustments.
4 RESULTS
We present numerical experiments for three datasets: (a) Parrot image, (b) MNIST, and (c) hurricane Sandy. The reader is referred to Appendix E.5 for the definitions of the error metrics used. Note that, these error metrics rely upon conventional SVD the baseline for a fair comparison. For additional numerical experiments on sparse graph datasets and other low rank approximations see Appendix F SketchySVD's algorithmic implementation (Alg. T can be found in Appendix
30
10-1
10-
200
10-2
10"
12-0
337
30
18
167
10'
10'
(a) Parrot
(b) MNIST
(c) Sandy
Figure 3: Singular value spectrum for the three practical datasets considered in this work. One can visually assess that the decay rate of the singular values is non-exponential.
4.1 IMAGE COMPRESSION; PARROTS (SVD)
As an example for SVD of natural images, we use the well known Parrots image from the image processing domain. The original image is in RGB format, converted gray scale for demonstra- tion purposes followed by normalization between [0, 1]. This 1024 x 1536 data matrix is then used to compute rank 20 approximation for comparison and numerical analysis. Fig. 4 shows the result of the low rank reconstruction for SVD, SketchySVD and Range-Net. Visually one can verify that Fig. 4 (b), (d) are similar while Fig. 4 (c) is different. To make the error approximation more clear, we plot the absolute difference of SketchySVD and our net from the truncated rank image. Fig. 4 (e), (f) shows the the corresponding plots with heatmaps imposed for clarity. Notice that while the reconstruction error for our network (>x 10-7) is close to the GPU precision, SketchySVD has significantly higher error scale (> 10-1), validating the artifacts the approximated image.
The singular value spectrum does not decay exponentially (Fig. 3 and the data matrix is near-full rank (f ~ 1024). Fig. 55 (a, b) shows the scree error as the absolute difference between the predicted and the true singular values. For SketchySVD, the error fluctuates across the top 20 values, but also the scale of fluctuations is around 1. Comparably, Range-Net incurs significantly lower errors in singular values (scale of 10 40-). Fig. 5 (c) shows the reconstruction errors in Frobenius norm for SketchySVD (Tropp et al., 2019) (red line), Block Lanczos with Power Iteration (Musco & Musco
2015) (black line), Skleamn' 's randomized SVD (skr) implementation Halko et al. (201)) with (solid

---

Under review as a conference paper at ICLR 2022
(a) True Image
(b) SketchySVD 20
(c) Range-Net 20
44
3 0u.07
20w0r
2.0.30
(d) X, 20
Sa X-1
(1) [
X,]
Figure 4: (a) True image, rank-20 reconstruction using (b) SktechySVD (oversampled rank k = 81), (c) Range-Net (5-passes), (d) conventional SVD. Note that Sketchy SVD reconstruction error (10-1) ")0") is orders of magnitude apart from Range-Net's reconstruction error (10-?) w.r.t the true X, from conventional SVD.
cyan line) and without power iteration (dashed blue line), and Range-Net (green line) over 1000 runs on the Parrot data. This shows that in order to gain lower reconstruction errors power iteration is necessary that quickly becomes intangible big-data setting. Further, note that the expected error (upper bound) multiple runs of Randomized SVD algorithms does not contract (reduce).
0.0075
0,2034
10-1
10
Sdeam KandavD
Lanrzes houer teaatin (Per-
3.0
6.0022
0.0031
(a) SketchySVD
(b) Range-Net
(c) Reconstruction Errors
Run
Figure 5: Scree in the extracted singular values from (a) SketchySVD 1) and (b) Range-Net 10-*),
Notice scale errors. (c) Reconstruction errors (rank r = 20) for Range-Net randomized SVD schemes (with and without power iterations) for Parrot image over 1000 runs.
Fig. 6 shows the cross-correlation between extracted right singular vectors from SketchySVD (left) and Range-Net (right) against conventional SVD for a rank-20 approximation. SketchySVD oversampled rank
and still the extracted right singu- lar vectors deviate substantially. This implies that the extracted vectors from SketchySVD do not span the top rank-20 subspace of X as opposed to Range- Net where stage-1 explicitly ensures this span with- out any oversampling. The higher the vector index, the higher the spread owing to random projections. Range-Net has near-perfect cross-correlation with the true vectors, indicated by the solid diagonal and zero off-diagonal (near GPU-precision) entries.
(a) SketchySVD
(b) Range-Net
Figure 6: Cross-correlation between true (conven- tional SVD) and extracted right singular vectors from (a) SketchySVD (b) Range-Net for rank-
approximation of Parrot image.
We tabulate error metrics (see Appendix for definitions) for SketchySVD and Range-Net for various ranks in Table. Note that all errors are reported w.rt. the true SVD, where err and errsp denote the frobenius and spectral errors respectively. One can easily see that as the rank increases, SketchySVD's performance keeps on deteriorating for the X metric (measure of correlation
between true and estimated vectors), also evident from Fig. 66 Range-Net on the other hand has consistent lower errors in all metrics while simultaneously being memory efficient.
Table 2: Metric Performance and Memory of SketchySVD Range-Net, for Parrot image
Rank
SVD
RangeNet
errfr
x
Mem (MB)
Time
ertyr
etTap
X
Mem (MB)
Time
27.904
0.33
20
11.974
2,201
0.662
21.69
14
0
0
0.023
0.69
26
2.772
59.87
30
1.91e-7
100
0.614
2.14c-2
0.923
139.9
63
2.32o-7
1.08c-7
0.033
3.6
72
7

---

Under review as a conference paper at ICLR 2022
4.2 DIMENSION REDUCTION: MNIST (EIGEN/ / PCA)
Principal Component Analysis (PCA) is a special variant of Eigen decomposition, where the samples are mean corrected before constructing a feature covariance matrix followed by Eigen decomposition. Note that Range-Net does not require construction of the feature covariance matrix and can directly extract the eigenvectors and values without any modification. This due to the fact that the Eigenvalues are the square of the singular values for any non-square data matrix X E R=*" where right singular vectors are exactly the same as the eigenvectors.
MNIST has 60k images of size 28 x 28 in the training set. We reshape each image into a 784-dim vector obtain the data matrix X 8,0000 x 784, as a tall skinny matrix. In a streaming setting, the mean feature vector computation requires one pass over the data matrix. This can be subsequently used during the network training (Stage-1) 1) to mean correct streamed input vectors.
Table 3: Metric Performance and Memory of Sketchy vs. Range-Net, for MNIST
Rank
Ske
RangeNet
errye
erPap
Xarr
Mem (GBB)
Time (s)
er
erTap
Xerr
Mem (MB)
Time (s)
r=
20
1.0933
8.2922
1.34
0.47
216
0
0.012
0.51
416
50
1.0333
8.25c2
2.14
1.18
384
0.025
1.33
552
100
1.053
8,4722
2.03
2,38
702
1.22-7
1.0e-7
0.052
2.83
776
200 L.4e3
8.62e2
4.84
2.36e-7
2.52e77
0.071
6.29
1256
For this dataset, it is well known that r = 200 captures 2 90% variance in the dataset. For
SketchySVD, this results in projection matrices of ranks k 4r + 801 and 2k: + 1602. Since MNIST only has n = 784 features, SketchySVD (Alg. D is almost equal if not more memory intensive than conventional SVD for such tall and skinny matrices. Table. Stabe.Bjshowe shows the error metrics under different rank setting, where even with oversampling, SketchySVD's errors are high. Range-Net on the other hand with an exact memory requirement (r(n + +)) can handle much larger full rank tall and skinny matrices without incurring extraneous memory load. As discussed before, since this data matrix tall and skinny (60A 784) we already know that for SketchySVD any rank-r s.t. (r 2 196) will result in the oversampling parameters & 2 784 and 2 1569. SketchySVD will now extract lower-error SVD factors since the oversampled rank redundantly exceeds the feature dimension.
4.3 SCIENTIFIC COMPUTING: SANDY BIG DATA (SVD)
Satellite data gathered by NASA for Hurricane Sandy over the Atlantic ocean represents the big data counter-part for scientific computations. The data-set openly available and comprises of RGB snapshots captured at approximately one-minute interval. The full data-set consists of 896 x 719 pixel images for 1208 time-instances is of size 24 GB. We chose this particular big data so that conventional SVD can be performed on our machine (16 GB RAM) for benchmarking. Please note that this restriction is imposed by conventional SVD method due to its high main memory requirements. In contrast, our neural SVD solver can handle data sets that are orders of magnitude larger in size with the same hardware specification.
Range-Net Net can not only handle larger datasets than SketchySVD, but also ensures lower errors in approximating the SVD factors. Tab. [shows the error metrics for Range-Net with a comparison of peak main-memory load between SketchySVI and Range-Net for ranks [10, 50, 100). Appendix shows a comparison of dynamic mode reconstructions obtained from SketchySVD. conventional full rank SVD, and Nenge-Net and the associated scree errors in the computed singular values.
Table 4: Metric Performance and Memory of Sketchy SVD vs. Range-Net, for Sandy
Rank
SkelchySVD
RangeNet
errye
erTap
x
Mem (GB)
Time (s)
crrfe
ertay
X
Mem (MB)
Time (s)
1.3e3
7.72a2
2.56
0.011
0.39
r 50
7.18c2
18162
2.04
12.48
507
0
0.018
2.01
607
-=
100
4.32e2
6.68c1
3,022
24.91
792
1.12-77
1.24-77
0.021
4.19
779
Randomized SVD extracted factors deviate quite substantially when the user specified rank r is such that the oversampled rank k is much lower than the unknown rank ff of given data matrix. The reader is also referred to the additional experiment in Appendix F.4 where a low rank (r = 10) approximation is extracted. Here, SketchySVD deviates quite substantially after rank-3 while Range- Net still remains in excellent agreement with the baseline singular vectors and values.
8

---

Under review as a conference paper at ICLR 2022
4.4 STORAGE COMPLEXITY ANALYSIS
To estimate the memory efficiency of Range-Net, let us consider the peak main memory (RAM) requirement for the compuation of SVD factors. Range-Net has two layers in succession, one corresponding to the low-rank projector Şrx" and the rotation matrix @rxr, For Sketchy SVD, the peak memory load occurs during the construction that the two projection matrices Φ TTax= decomposition Qm paxk and the core matrix Caxs, be present in the memory simultancously. The memory efficiency factor (Se)s) for rank-r approximation with k 4r + 1,8 2k + is: 12(m + n) + 128r
core matrix C* (see Alg. one projected data matrix z* and two rank-k
[.. This requires
SkotchySVD
na + ms + 20 + mk + nk
(m + m)(k + a) 20
Seff Range Net
r(n +1)
(n +
F2 7.67e2 for MNIST( = 60R, n 784, = 200)
To validate the ratio, we constructed synthetic dataset of m = 50k rows and the number of columns were varied starting 10k with increments of 10k. The expected rank was held at r = 200. Fig. showss the memory allocation (in MegaBytes
Merroy (98)
(MB) of SketchySVD vs. Range-Net, while varies between 10k 150k]. When m 50k, n = 150k: and r = 200, SketchySVD has peak memory consumption of 14GB due to oversampling parameters of k 801, 1603, while Range- Net only requires 916MB. Since Range-Net has an exact memory requirement of r(n + r) for rank-r SVD, it always occupies main lesser memory than oversampling of SketchySVD (or any other randomized method) by two orders of magnitude, and scalable to larger datasets.
125
Pangeles
2.5 5.2
Pouture 11
10002
Figure 7: Peak memory load of Range- Net vs. SketchySVD synthetic data.
DISCUSSION
From the numerical experiments is evident that Range-Net performs at par with conventional SVD with GPU bit precision results, while being extremely memory efficient. Range-Net constructs the rank-r projector VVT iteratively to reach the tail energy lower bound given by EYM. Alternatively, the rank-r minimizer V of Eq. | gives the correct rank-r right projector VVT of X. Any arbitrary (random) projection of X onto an oversampled rank-k k subspace (A >> r). rather than the tail energy minimizing subspace VVT, can inadvertently annihilate the desired top ranking singular features resulting in irreducible approximation errors.
This issue is specially important in exploratory data analysis for scientific computing, where one is not only interested in the top-most singular values of the dataset but also the dominant phenomena (singular vectors). Furthermore, with increasing digital sensor resolution the focus now is to isolate and study the lower energy (high frequency/ small spatial scale) features as in the case of Hurricane Sandy, where turbulence manifests low rank features (see Figs. 19 24 in Appendix).
We again point out that accuracy is gained by achieving (or finding) this minimizer or lower bound of the rank-r tail-energy of X and therefore the upper bound on this tail-energy is of no consequence to Range-Net. As pointed out by Musco & Musco (2015), upper bounding the tail energy does not ensure that the approximation errors in the extracted singular values or vectors will reduce. Therefore, small relative tail energy errors can mislead the reader that the singular factors are equivalently accurate wherein the absolute errors can still be substantially large.
CONCLUSION
fully interpretable neural SVD solver for big data applications that is independently verifiable without performing a full SVD. We show that our solution approach achieves lower errors metries for the extracted singular vectors and values compared to Randomized SVD methods. A discussion is also provided on the limiting assumptions and practical consequences of using Randomized SVD schemes for big data applications. We also verify that our network minimization problems converges to the EYM tail energy bound in Frobenius norm at machine precision. number of practical problems are considered, where SVD or Eigen decompositions required, that demonstrate the applicability of Range-Net to large scale datasets. fair comparison is provided against the state of the art randomized, streaming SVD algorithm with conventional SVD solution the baseline for benchmarking and verification.
We present Range-Net as low-weight,

---

Under review as a conference paper at ICLR 2022
REFERENCES
Gephi data sets.
Lev muchnik's 's data sets web page. http::/www...mmmaaaaa.eee///eeer
NetworkData.html
James Baglama and Lothar Reichel. Augmented implicitly restarted lanczos bidiagonalization methods. SIAM Journal on Scientific Computing, 27 2005.
Christos Boutsidis, Petros Drineas, and Malik Mamaon-Ismail. Near-optimal column- bassdd matrix reconstruction. SIAM Journal on Computing, 43(2):687-717, 2014.
Matthew Brand. Incremental singular value decoopoosition of uncertain data with missing values. In European Conference on Computer Vision, pp. 707-720. Springer, 2002.
François Chollet. keras.
2015.
Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 105-214, 2009.
Julio Cesar Stacchini de Souza, Tatiana Mariano Lessa Assis, and Bikash Chandra Pal. Data compression in smart distribution systems via singular value decomposition. IEEE Transactions on Smart Grid, 8(1 8(1):275-28) 284, 2015.
Petros Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, and V Vinay. Clustering large graphs via the singular value decomposition. Machine learning, 56(1-3):9-33 2004.
Petros Drineas, Ravi Kannan, and Michael W Mahoney. Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix. SIAM Journal on computing, 36(1):158-18) 2006.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, (19:221-218, 1936.
Gene H Golub and Richard Underwood. The block lanezos method for computing eigenvalues. In Mathematical software, pp. 361-377. Elsevier, 1977.
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.
Liping Jing, Chenyang Shen, Liu Yang, Jian Yu, and Michael K Ng. semi-supervised singular value decomposition. IEEE Transactions on Image Processing, 26(10): 4612-4625, 2017.
Multi-label classification by
2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6980, 2014.
Kishore Kumar and Jan Schneider. Literature survey on low rank approximation of matrices. Linear and Multilinear Algebra, 65(11):21222244 2017.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: stsaap.stafforddoooo www.attadddordddddddadd........d edu/datal June 2014.
Edo Liberty. Simple and deterministic matrix sketching. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 581-588. 2013.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterly journal of mathematics, 11(1):50-59, 1960.
Cameron Musco and Christopher Musco. Stronger approximate singular value decomposition via the block lanezos and power methods. arXiv preprint arXiv: 154400557 16:27, 2015.
10

---

Under review as a conference paper at ICLR 2022
Lloyd N Trefethen and David Bau III. Numerical linear algebra, volume 50. Siam, 1997.
Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Fixed-rank approximation of positive-emiddffnite matrix from streaming data. In Advances in Neural Information Processing Systems, pp. 1225-1234, 2017a.
Joel Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Practical sketching algorithms for low-rank matrix approximation. SIAM Journal on Matrix Analysis and Applications, 38(4): 1454 1485, 2017b.
Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Streaming low-rank matrix approximation with an application scientific simulation. SIAM Journal on Scientific Computing. A14))22330A2443,, 2019.
Jalaj Upadhyay. Fast and space-optimal low-rank factorization in the streaming model with application in differential privacy. arXiv preprint arXiv: 02499, 2016.
Shuqin Wang, Yongli Wang, Yongyong Chen, Peng Pan, Zhipeng Sun, and Guoping He. Robust pea using matrix factorization for background/foregrruund separation. IEEE Access, 6: 1945--88953, 2018.
Haishan Ye, Shusen Wang, Zhihua Zhang, and Tong Zhang. Fast generalized matrix regression with applications in machine learning. arXiv preprint 1100000912..2008, 2019.
Sheng Zhang, Weihong Wang, James Ford, Fillia Makedon, and Justin Pearlman. Using singular value decomposition approximation for collaborative filtering. In Seventh IEEE International Conference on E- E-Commerce Technology (CEC'05), pp. 257-264. IEEE, 2005.

---

Under review as a conference paper at ICLR 2022
A NEED FOR RANGE-NET
To illustrate the limitations of current streaming randomized SVD approaches, we consider synthetic data matrix with slow decay in the singular value. The numerical results section later presents number of these singular value spectra for different practical datasets (Fig, 3 to demonstrate that the decay rates are subjective the problem at hand.
X diag(450, 2,, 1.01 0...0.....0 .0
1=150
500 with rank f 450, where the singular value spectrum decays linearly. Fig. [ shows a comparison of reconstruction errors (see Metrics in Appendix E.5 for the definition) for SketchyS (Tropp al. 2019) (red line), Block Lanczos with Power Iteration (Musco & Musco| 2015) (black line), Sklearn's s randomized SVD (skr)
Here X E R is strictly diagonal matrix with
implementation (Halko al.
2011) with (solid cyan line) and without power iteration (dashed blue
line), and Range-Net (green line) over 1000 runs for this synthetic dataset.
Reconstruction Error (Frob)
10a
10a
SketchySVD
10-3
Los Power Iteration ()ter=5)
RandSVD (iter=0)
10-3
Skleern RandSVD (iter
10-1
Range Net(pass=33
10-7
10a
10a
Run
Figure 8: Reconstruction errors 20) for Range-Net and randomized SVD schemes (with and without power iterations) the non-exponentially decaying singular value spectrum over 1000 runs.
Please note that although power iteration improves the reconstruction error for both Block Lanczos (Musco & Musco, 22155) and Sklearn's ' RandSVD (Halko et al. 2011), power iteration itself requires persistent presence of the data matrix X in the main memory. For practical big data scenario, power iteration is therefore not a feasible alternative when the data matrix X or it's sketch itself too big be loaded into the main memory. Note that the error expectation (upper bound) over multiple runs of Randomized SVD algorithms does not reduce. We further identify the following requirements for SketchySVD return SVD factors with relatively lower approximation errors:
1. Decay rate of singular values of a dataset must be exponential.
2. For rank-f matrix, the desired rank must be chosen such that the oversampled rank k is strictly greater than (k N f) to achieve lower errors at scale compared to other runs.
We suggest that the reader also attempt the case where all the diagonal entries are strictly ones and zeros under a high rank setting.
10>
Sinuar Valler (00)
6x100
Reserve Ertor
Truch R:441
4xx00
Trah
30-1
K=
201
122
121
B1
161
100
202
201
201
10
10'
Ranktr
Bank(r)
Estimated Singular Values
(b) Tail Energy
(c) Relative Tail Energy
Figure 9: SketchySVD approximation emrrrs for synthetic dataset with linear decay in singular value spectrum, corresponding to r = [10, 20, 30, 40, 50] with corresponding oversampled rank [41,81 121, 161, 201]. Since the decay is non-exponential, SketchySVD accrues large approximation errors, hence impractical for real datasets with similar behavior.
Fig. shows the singular values extracted by SketchySVD for a linearly decaying spectrum with corresponding errors in absolute and relative tail energies. The reader is referred to Appendix
12

---

Under review as a conference paper at ICLR 2022
B.1 for the definitions of tail energy and relative tail energy. Note that the synthetic data is diagonal matrix chosen specifically so that the exact tail energies can be computed using Frobenius
1
norm as
Σ
2
For a rank-r approximation, SketchySVD suggests oversampling by a 1
i-r+1
factor of k = 4r + to extract the rank-r factors correctly. Hence for an oversampled rank
k [41, 81, 121, 161,,,12000 201] the corresponding top rank [10, 20, 30, 40, 50] extracted singular values and vectors will have the lowest approximation errors. However as shown in the Fig, 9 (a) the extracted singular values have an order of magnitude difference w.r.t. the ground truth. Consequently, Fig. (b) shows that the absolute tail-energies of the extracted features deviate quite substantially from the true tail-energy. Furthermore, we also notice that the deviations remains large long as the oversampled rank-k is such that k < f. For practical dataset f is either unknown or almost full rank f S min(m, (m, n) or both and can only be detected by performing a full SVD on the dataset. This poses serious restriction on SketchySVD's reliability for a realistic big data application, due to an exponential decay assumption.
We also notice that for smaller values of r, the accrued error in both the extracted singular values and tail energy error is worse. Fig. (b) shows that for different rank approximations SketchySVD tail energy deviates from the truth quite substantially. This is due to the fact that the oversampled rank == 4r + < f. as pointed out before. Note that for oversampling parameter < f. although the error decreases I > the memory requirement increases correspondingly Okk) for extracting low rank-r approximation. This implies that for slow decaying spectrum optimal values of k are such that k: 2 f even when rank-1 approximation is desired. In Fig. 9 (c). one can observe relative errors between 10-2 and 10". Although this implies that the actual rank-r tail-energy approximation error off by 1% at the best, the extracted singular values and vectors are off by one order of magnitude. As consequence, the extracted singular vectors no longer represent the features of the dataset.
Remark. For a randomized SVD algorithm to converge (without power iterations) to a rank-r approximation X, over multiple runs, we posit that a rank-r sketch matrix X for a given rank-f dataset X, for J 2 r, be such that P(spant X} ensuring this requires substantial amount of prior knowledge or intelligent sampling (a multipass iterative algorithm).
} n span{X,) = span (X.)) 2 0.5. However,
Range-Net with it's explicit minimization of tail energy is capable of intelligent sampling on an arbitrary matrix without requiring any prior information. The key point to note here is that Range-Net relies upon an iterative computation of a near optimal projector instead of arbirraryluse--seccffee projectors used in Randomized SVD schemes. Even if the tail energy is theoretically upper bounded for some of the Randomized SVD schemes, the target is to find the lower-bound (minimizer) on the tail energy discussed in Section 1.1 Furthermore, since none of the randomized SVD schemes construct the projector in an iterative manner while minimizing Eq. [ the relative error in the tail energy remains high. Even multiple runs of SketchySVD or Sklearn's RandSVD are performed, the reconstruction errors in tail energies remain the same at scales shown in Fig. 8 We would also like to point out that although one must strive for lower errors (relative or otherwise) and tighter theoretical upper and lower bounds, in practice we should also closely monitor if these theoretical bounds deliver us the desired solution.
B THEORETICAL GUARANTEES
B. PRELIMINARIES
The Frobenius norm of matrix A is given by,
|||||
ΣΣ
(Tr(AT (I){ (IY(AA))
Further, the Frobenius norm can be used to bound Trefethen & Bau III 1997 the norm of matrix product as,
|AB|| S ||||||| Bl
13

---

Under review as a conference paper at ICLR 2022
For Frobenius norm we have that,
|| A B|| S ||A|| |
||4 B 2 |||||e |
Also the Frobenius norm rank-/ matrix A,
|| = |
where y = diag(oi, 22 ". , and 03 are the f non-zero, singular values of A. Let A, B, C' be matrices such that the following matrix products feasible. The cyclic property of the linear trace operator is,
T+ = TBBCA) = Tr(CAB)
Definition The tail energy of an urbitrary matrix RRmx with respect to a given matrix X E mg equipped with a Frobenius norm is defined as,
| B
Definition 2.
Letr, f E Z be positive integers such that 0 < S f. then a rank-r truncation X, of a rank-fmati matrix X is defined as,
X, U,E,V XV,V
where, E, diag(o),02; σ,) and 0,s are the top T singular values of X and Vr [U1, "2....,,p,, and U, [u1, U2 Up] are matrices such that v,s and u,s the corresponding right and left singular vectors, respectively.
The relative tail energy of rank-r matrix B, with respect to rank-f matrix X (r S f) is then defined as,
X B
Trel,r
X - 1Xxxll
B.2 STAGE
Proof of Theorem 2. For any f E
if the tail energy a rank- X E RRxx S min(m, n), with respect an arbitrary rank-r matrix B, -V, VT is bounded below by the tail energy of X with respect to it's rank-r approximation X, = XV.V as,
X Brlle ||X-1
where, V, = span(1i, V2,". .. } and v,s are the right singular vectors corresponding to the largest r singular values then the minimizer of arg min ||X XV is V. such that V. V.V² V, V. VgR(axr)
From Theorem I we have,
|X B,IFF - 20
(4)
{ui, U2. u singular values,
Let V,,
2/} be the top-r, right-singular vectors of corresponding the largest
X, XVVV = VVV
=
(5)
Also let B, = XV.VT where V, is an arbitrary rank-r matrix. From triangle inequality we have that,
[XVVV, D 2 IX V, [ V.V.T )
(6)
Combining Eq. 4 and Eq. o we get,
|X(VVV
- -V.
14

---

Under review as a conference paper at ICLR 2022
Additionally,
| -VVV" |[VVV -V,
(8)
Using the above two inequalities we arrive at,
|| 1
(9)
Since |X > O, equality is achieved when V.VT = V.V." = V,,,"" In other words, span V. = span V.} since (V,,),V),)))) the top rank-r subspace of X.
V.V." for any rank-r, real valued, unitary matrix O spanning
Remark. Theorem aetorem@alse pasoo implies that any matrix V V.V? that does not span the same rank-r subspace of X as VVV," will result in higher tail-energy than given by the EYM tail-energy bound equipped with Frobenius norm.
Proof of Lemma 2.1. V, I, and V.V," = V.V. then V V, I,-
Let us assume VłV, = I, then,
IV, - 1, = 0 Tr (V. (I.) - 2Tr (V.V,) Using the cyclic property of the trace operator we have,
Tr VVVV"V; Tr,) 2Tr (V.V,")
Using Theorem 2. V.VT = VVV
Tr (V.V.V.VV.) + (T,) 2Tr (V.V.) =0
Again using the cyclic property of the trace operator we now get,
Tr VV.VVVVVV.) + Tr (I,) - 2Tr VV. =
Hence, V.V. = I, This shows that following Theorem 2 the matrix V. comprises of orthonormal column vectors spanning the same top rank-r subspace X the orthonormal column vectors V,..
Proof of Lemma 2.2. If X E Rmxn is rank f matrix, then for any rank > f. where {r min(m,n). VTV, I, and V.V."" V2 then V Lr.
VV 1,113 Tr (V.VVVVVVV + (T,) 2Tr (V. =0 Using the cyclic property of the trace operator we have,
Tr (VVVVVVVVVV + Tr,) - 2Tr (V.V.T) =
Using Theorem 2 V.VT= VVV.
Tr (VVV, + (T,),) - 2TH (V,V,) =
Again using the eyclic property of the trace operator,
Tr (v,V V.) + Ir (4.) 2Tr (V,TV, =0
Ir (V,TV,V VVV.V, + -V,7V, =
VVVTV, - ++1F==0
Hence V.T V, I,.
Remark. Lemma 2.2 shows that for a rank-r approximation of a rank-f matrix such that r > the extracted right singular vectors are orthonormal when VTV, = I,- This justifies the constraint VTV = for the stage-l minimization problem in Eg, 2 and is numerically verified in Appendix D
Remark. Note that Lemma and does not imply that V. = V, instead V, v, = V,, where O,
any real valued unitary matrix for the equality to hold true.
15

---

Under review as a conference paper at ICLR 2022
B.3 STAGE
Proof of Theorem 3.
Given a rank-r matrix XV. & Ruxr and an arbitrary, rank-r matrix the tail energy of XV. with respect XV.C is bounded as, |XV, - XV,C 2 20
C Rmxr, following Theorem 7
where the equality holds true if and only if = 1r-
|XV, - C) 20 |X |F114 ClI 2 [VV. -
|XVV||=||,, -CIF 2
Since XV, > 0, this implies equality is achieved if and only =
Proof of Lemma 3.1 IfC 0,07, where Or gr is a rank-r matrix such that Ly, then i is a real-valued unitary matrix in an r-dimensional Euclidean space.
0,0 L,
1 - 1,
Tr (9,6 +,, 20,0,)
Tr (0,0, + Tr - (0,0,) Using the cyclic property of the trace operator,
Tr (o0 + (I,) 2Tr (0)0,)
Tr ((0,0, (,) 0, - 1,)²) 00
100 o, - 1,,11=== =0
This implics O, = Iy.. Since θ, = -,0, I, this implies that O, a valled unitary matrix in the r-dimensional Euclidean space.
Proof of Theorem 4. Given a rank-r matrix XV. E R such that V.V = V,V where V, is a matrix with column vectors as the top-r right singular vectors of X, and real-valued unitary matrix i I Rx then "i,,,,,(((VV 9, a diagonal matrix Σ, where Σ = diag(o,, ... and a the top-r singular values of X if and only V. V,.
(XV.0.) Σ
(x" =
V XV
XV = -,0,E,0
Using V.VT V,V, from Theorem
2
V,V"" X XVVV V.O,
V.E,V -V.,,,)E
(V, - VV,,) v,0,)= =0
[IVV, - VoO,) V.O,) ||= 0
Using Frobenius norm to bound the matrix product,
> V.O, v.O, 2
Since ||Σ [| > 0, equality is achieved if and only if V,e, =
Remark. Note that O is rank-r unitary matrix wherein both rotation (det(Or) 1) and reflection (det(()) 11) are valid since the order of the orthonormal vectors in the matrix V_e,- V, do not alter |V, v,O, In practice O, manifests itself predominantly as a rotation matrix during the iterative minimization using gradient descent.
16

---

Under review as a conference paper at ICLR 2022
C ENERGY MINIMIZATION LOSs SURFACE GEOMETRY, AND CONVERGENCE
In this section, we consider the energy minimization problem that constructs the projection space spanning the rank-r sub-space of given data matrix. For case of visualization, consider 2 x 2 matrix X = diag(5, 1) with singular values 5 and 1 corresponding to right singular vectors U1 = approximation of this rank ff = 2 matrix X. Certainly, this corresponds to identifying the right singular vector 0i with singular value 5. The tail-energy surface (log-scale) corresponding the X X is shown in Fig. 10 Here, ē is the test vector for a rank approximation of X. The tail-energy is a bi-quadratic function in with maximum, 2" minima and 2" saddle points, where the desired low-rank approximation of a given data matrix. Furthermore, all minima have the same tail energy: property of bi-qu bi-quadratic functions. For the current specific example, the two equal tail tail-energy minima correspond to 0 and -1,, respectively.
[1. OJ and 12 [0, 1)" respectively. Our objective here is to extract rank
1011
22
3#
Surface plot for the bi-quadratic tail energy (log-scale) with minima, saddle points, and maxima for X diag(5, 1).
Figure 10:
Although the minimization problem is non-convex, convergence guaranteed since any perturbed- gradient descent approach converges to either of the stable fixed points (minima). In other words, any test vector é other than U1 or - will increase the tail-energy and hence will not be the solution. The same argument applies for a high-dimensional dataset X where low rank-r approximation desired with the number of equal tail-energy minima corresponding to 2" for all possible negative and positive combinations of the r right singular vectors ti=1,-..., In effect, the stage minimization problem constructs a right projection space V = span(u,, sp.., )r that spans the top rank-r subspace of given dataset X. A similar line of argument then applies to our stage 2 minimization problem as well. A mild limitation, that will be addressed in our future work, occurs when X diag(5, + e). 0 << 1, wherein the two right singular values cannot be resolved accurately (still better than Randomized SVD methods) without further considerations. This latter case, with near algebraic multiplicity in singular values is special case for conventional SVD well.
D NETWORK INTERPRETABILITY
As described before in Fig. 2 our network weights and outputs are strictly defined and incorporated as losses in the network minimization problem. We therefore refer the problem informed (SVD) restrictions on the network weights as representation driven losses. This is in contrast to kernel regularization loss often considered to impose weak requirement on the network weights to be small. The representation driven, orthonormality loss term, Stage enforces that the weights V must be orthonormal or (VTVV = I,)) for a desired rank-r which is greater than the rank- of the data matrix X. We numerically verify the interpretability of the layer outputs and weights by considering two networks: (1) with, and (2) without the aforementioned orthonomality loss. For each of these two cases, two synthetic datasets are considered corresponding to r < f and r > f. Please note that in practical scenario of is an unknown and can be determined only by performing full SVD of X. Therefore, numerically testing this aspect for our solver is necessary.
For the first case, we consider synthetic data matrix X15x15 where the top 5 singular values positive (f = 5) while the rest are zero. The objective is to extract the top 10 (r = 10) singular vectors where the desired rank is higher the the rank of the system itself. A total of four training runs
17

---

Under review as a conference paper at ICLR 2022
1.00
0.75
0.50
Figure 11: Synthetic Low Rank Case: Correlation Map of extracted vectors V. over four runs. Orthonormality is imposed for the first run resulting in diagonal structure. Absence of this condition results in scatter.
are considered: one run for a network with the orthonormality condition imposed and three runs for another network without this additional constraints. Fig. 11 shows the correlation map between the recovered vectors V. for each of the four runs, Notice that only when the orthonormality criteria is not imposed, we get scatter away from the diagonal matrix, although all four converged the same tail energy. Since the true rank of X is 5, the null space of X is of dimension 10. The absence of this orthonormality imposing, representation loss results in non-orthonormal vectors V, spanning the low-rank range space.
1.00
0.50
0,25
Figure 12:
Synthetic Full Rank Case: Correlation Map of extracted vectors over four runs. Orthonormality loss now does not contribute and therefore all runs have diagonal structure.
For the second case, we consider full-rank, synthetic data matrix X15x15 with f = 15. As before, with and three without
extract the top 10 singular vectors (r 10) using four training imposing the orthonormality loss. Since the desired rank 10 system now itself is full rank, this additional loss term does not contribute, as desired. Fig. 12 shows that the extracted vectors V. minimize tail energy ([
remain orthonormal, for all the four runs, described in Section [3.] above. In fact, for any rank r approximation of a rank / system such that S J. arbitrary non-orthonormal matrix V. will increase the tail energy and hence will not be fixed point (solution) of our network minimization problem.
I))l as
E IMPLEMENTATION DETAILS
E.
CHOICE OF ACTIVATION FUNCTIONS
All the activation functions in both stages are Linear with no biases. One might argue that this choice a neural approach, since all the activations linear. However, please note that singular vectors are linearly separable orthogonal features of a dataset, and therefore any other choice of activation function will result in approximation errors. Since the elements of singular vectors are in [-1,]], 1]. choice of relu activation is problematic. A simple verification is to approximate straight line segment in [-1,1] with tanh activation, only to realize that the approximation error -> as the number of neurons -> xc. These arguments can also be verified by replacing linear activation in Stage by any non-linear activation only to find that the tail energy bound cannot satisfied. Note that given small matrix, one calculate the right singular vectors and substitute them directly as our network weights to confirm this tail energy bound.
E.2 TRAINING, VALIDATION, AND TESTING SPLIT
An issue with training and validation split in matrix decomposition problems is that the error norm cannot be bounded in deterministic manner computationally verified. For Singular Value Decomposition of given data matrix X differs from SVD truncated dataset X in it's singular triplets (singular values and vectors). Ensuring these triplets do not change over an arbitrary split is non-trivial computational task.
18

---

Under review as a conference paper at ICLR 2022
Remark. For dataset X, an arbitrary training/validationn split results in a varying dataset X wherein the norm [[Xyred X|| F changes according the split. Since the desired features are unknown priori, a consistent truncated dataset Xe that spans the same space as the full data X cannot be obluined using an arbitrary split.
26
52
04
02
42
04
4.
46
45
00
46 0.4
0.
82
54
0.
09
485
68
-36
-04
4.3
82
04
06 68
24
36
Figure 13: Variation in extracted right singular vectors (dashed green lines) for three runs with each run comprising of 200 different train/test data splits with an 80/20 ratio. The solid red lines indicate the ground truth singular vectors when using the entire unsplit dataset (red dots). Extracted singular vectors deviate increasingly from left right over the three runs.
This results in a large variance in extracted features over multiple training/testing splits since the span of X itself is changing with each split. Fig. 13 shows numerical experiment with a synthetic (rank-2) dataset containing 100 samples drawn (red dots) from a 2D ellipse with major and minor axes and 1, respectively. The ground truth right singular vectors over the unsplit dataset are computed using conventional SVD (solid red lines). Next the dataset was split with an 80/20 ratio as the training/testing split for 200 different realizations per run. The mean/expectation of the extracted right singular vectors (dashed green line) over the 200 realizations are then reported. One can easily see that the expected right singular vectors vary quite substantially compared to the ground truth over the three runs indicating that arbitrary split of the dataset does not ensure accuracy.
E.3 DATA STREAMING
Given a data matrix X"x*, we stream the data along the smaller dimension assuming the user prescribed rank-r is such that I min(m, n). For the sake of simplicity we assume that the data matrix has m samples and n features, where m > n, and consequently feature vectors of samples are streamed in batches. We rely upon the built-in Keras fit_generator class for data streaming from the secondary memory (HDD). For a big data matrix that cannot be loaded into the main memory, this allows us mimic the modality of data residing data, the function yields batch of specified size for the network to train on for specific epochs. This ability saves main memory load and allows us process bigger datasets on smaller main-memory machines than reported in prior works.
external server. Thus, given pointer the
Note that for the stage-1 network to converge a desired tolerance, we require multiple passes (empirically < 5) over the original data streamed batchwise. Therefore for Stage 1, the input data is never persistently present in the main memory the remote machine. The output data is dumped onto the secondary memory assuming that storing low rank approximation is still main memory intensive. For Stage 2. this low rank approximation in the secondary memory is streamed as input, and the extracted singular values and vectors are saved in main memory.
E.4 SETUP AND TRAINING
All experiments were done on a setup with Nvidia 2060 RTX Super 8GB GPU, Intel Core i7-9700F 3.0GHz 8-core CPU and 16GB DDR4 memory. We use Keras (Chollet 2015) running a Tensorflow 2.0 backend with Python 3.7 to train the networks presented in this paper. For optimization, we use AdaMax (Kingma & Ba 2014) with parameters (I== 0.001) and 1000 steps per epoch.
E.5 ERROR METRICS
As discussed before in Section 2.1 since relative errors in tail energies do not imply similar errors at scales in extracted singular factors, we rely upon additional error metrics on the extractor factors for
19

---

Under review as a conference paper at ICLR 2022
performance comparison and benchmarking. In the following X and X are used to denote the true and the reconstructed data matrices.
Scree Error: Absolute difference between true and approximated singular values.
screeerr (r) = (x,(X) (X)) Vi [1,r]
Reconstruction Error: Frobenius norm error of the true data and its rank-r approximation.
froberr (r) = || - XI
|X - X
Spectral Error: 2-norm of the singular value of the true data and its rank-r approximation.
spectralerr(11 ||X - X1 - || X,
Chi Square Statistic: Deviation between the true and approximated singular vectors.
xerr(r) =1 - (o) 0f,)
Here, 0,8 the true singular values and X, is the desired rank-r approximation of X using conventional SVD as the baseline for benchmarking. Under perfect recovery. all error metrics are expected approximately achieve performed on a GPU using single (32-bit) precision floating point operations. Therefore, the tail energies are expected be correct to up significant digits all the subsequent calculations. In the following sections, X is replaced by approximations from SketchySVD and Range-Net.
machine precision. All of our numerical experiments
E.6 LOSs PROFILE
400
Energy
Range-Net Stage-1 Minimization
Training Loss
300
100
Epoch
Figure 14: Range-Net Stage-1 I training loss for Parrot image. The network minimization loss converges to the
EYM Tail Energy bound within five epochs and stabilizes for further epochs.
F ADDITIONAL EXPERIMENTS
F.1 FEATURE EXTRACTION: GRAPH (EIGEn)
Table 5: Description and Metries of the Network Graphs for Range-Net
Dataset
Nodes
Edges
rank
erTfr
eTTsp
2
Airlines ain Twitter air
235
2101
200
0
0.011
3556
188712
200
0
0
0.014
Wikivote
[Leskovec
Krevl
2014)
8297
103689
200
0
0
0.027
Wikipedia lley
49728
941425
100
4.27e-6
1.23e-7
0.034
Slashdot
Leskovee & Krevl
2014
82168
948464
8.56e-6
6.92e-7
0.045
Large scale networks occur in many applications where SVD is primarily used to identify the most important nodes or as a pre-processing step for community detection. For these kind of graph based datasets, we either perform SVD or Eigen decomposition on the graph, depending on the format in which the data arrives. We demonstrate results on the following graphs varying size, tabulated in Table If the data arrives directly in the form of adjacency matrix, can perform SVD or Eigen decomposition on directly. For cases, where an adjacency list is provided, a pre-processing step required to convert the list representation in sparse vector.
20

---

Under review as a conference paper at ICLR 2022
Since Eigen decomposition problem is special case of SVD, where the data matrix is symmetric positive semi-definite, Range-Net is directly applicable. The benchmark was generated for smaller graphs using conventional SVD solver. For larger graphs, similar benchmark using the irlba routine by |Baglama Reichel 2005). Table. shows the error metrics for all the graphs, where consistently low values are observed for Frobenius and Spectral error metries.
constructed
F.2 NAVIER-STOKES SIMULATED DATA (SVD)
For our next numerical experiment, we rely upon synthetic data generated using a Navier Stokes flow simulator for an incompressible fluid. The flow data is available on tensor-product grid on two-spatial 200). For each point on the grid,
and one temporal dimensions of size (w, h, t) (100 velocity vector values are available in both and y spatial dimensions for 200 time instances. The fully-developed, flow pattern exhibits a periodicity the time dimension at approximately every ~ 60 time step that can be identified using SVD as characteristic modes. The data is therefore reshaped into a spatial vector for each time instance resulting in a spatio-tempol matrix E IR x For comparison purposes, use only the x-direction stream velocity.
Figure 15: From left right: x-direction stream velocity times 0, 100, and 200
(a) SketchySVD
Truth
(c) Range-Net
Figure 16: Reshaped indicative dynamic modes, corresponding to top six right singular vectors for 5.
Fig, shows the evolution of the stream velocity over three time instances and the inherent time- periodic nature of the data. Notice the central-left region of primary flow across all three images. Fig. 16 shows the reshaped U vectors for SketchySVD, conventional SVD and Range-Net. Notice that the images corresponding to the first left singular mode (also called dynamic modes) captures notion of the primary flow the left-center part. The second one captures spatial variations of the flow as time progresses. For all the three methods, all the modes have similar solution visually. Note that
21

---

Under review as a conference paper at ICLR 2022
Truth
SketchySVD Range-Net
0.8
Singular Value
Skeethh SVD vectors
0.6
10
0.2
10
Index
SVD vectors (V)
(a) Singular Values
(b) Correlation
Figure 17: SketchyS and Range-Net (a) extracted singular values and (b) cross correlation between estimated and true (conventional SVD) right singular vectors for 5 on the Navier-Stokes data.
Range-Net computes rank r 5 approximation without oversampling, wherein SketchySVD relies upon memory intensive sketchy projections of ranks k: 21, 43 to arrive at the solution. Overall, for this low-rank dataset both SketchySVD and Range-Net perform reasonably well qualitatively looking at the features in Fig. 16 and the singular value spectrum in Fig. 17 because this synthetic dataset is extemely low-rank (J 10).
For given data matrix X E T of rank-f (f S. min(m, n)) SketchySVD generates low error approximations if the oversampled rank k such that le 2 f. For full rank tall skinny matrices, this implies that k. 2 min(m, n). For cases where & < (full rank or otherwise), SketchySVD accrues large approximation errors resulting in incorrect SVD factors.
Remark.
From a use-case point of view, randomized SVD generates low-error factors for full-rank, tall skinny matrices (X e R= only when the oversampled rank & 2 This poses serious limitation for all applications where this requirement is not met and consequently randomized SVD algorithms accrue large approximation errors in SVD factors as shown in the Sandy Big Data
study below and Appendix F.4 Note that given big data matrix X determining the rank f of X is unknown and impractical in such cases.
therefore selecting an oversampled rank such that
Remark. Once the SVD factors are extracted, SketchySVD cannot be independently verified without performing full SVD. In contrast, Range-Net is independently verifiable since Stage-1 of Range-Net cannot return orthonormal vectors if the vectors do not span the rank-r subspace of a given data X.
F.3 HIGH RANK APPROXIMATION: SANDY BIG DATA
This section provides an addendum to the numerical results presented Section 4.3 the main text. Fig. 18 shows evolution of Hurricane Sandy for two time instances. Similar to the Navier-Stokes simulation data, Fig. 19 shows three dynamic modes corresponding to rank 1, 20, 50, 100 singular values. As shown, results in good agreement with conventional SVD whereas, Sketchy SVD shows substantial deviations after the first 50 dynamic modes. Fig. 20 shows the scree-error in the singular values extracted by SketchySVD and Range-Net.
Figure 18: Satellite image captures of hurricane Sandy over the Atlantic ocean at f 0 (left) and f = 200 minutes approximately (right).
Fig. 21 shows the cross correlation of the right singular vectors and scree-error in the corresponding
singular values extracted by SketchySVD and Range-Net. Note that for a rank-100 approximation. SketchySVD extracted right singular vectors start deviating after rank-10 shown in Figs. 21 while the singular values deviate quite substantially from rank-1. Range-Net on the other hand is in excellent agreement with the right singular vectors and values for all desired 100 indices.
22

---

Under review as a conference paper at ICLR 2022
(a) SKetchySVD
(b) Truth (c) Range-Net
Figure 19: Reshaped U, indicative of dynamic modes. corresponding to i 1, 20, 50, 100 for r 100 (oversampled rank k 401 for SketchySVD. The dynamic mode approximation error stand out visually for SketchySVD for indices 20, 50, 100. Our method does have such artifacts.
0.003
22
20
30
03
30
80
70
20
200
10
33
30
42
50
00
300
(a) SketchySVD
(b) Range-Nee Net
Figure 20:
Scree-error in singular values for (a) SketchySVD and (b) Range-Net where a conventional SVD
used as the baseline in scree-error metric.
We point out that accuracy is matter of special concern in scientific computations. Any compression that results in substantial loss information or obscuring an otherwise identifiable feature in recorded observations directly culls capacity make scientific improvements. Consequently, any exploratory data analysis, however big or small, must accurately identify the underlying features. Range-Net achieves the lower bound tail-energy given by EYM theorem to ensure accurate resolution in big data setting. Note that increasing the sensor resolution implies that we are interested in exploring and understanding the high-frequency features (lower singular values) of the data.
F.4 Low RANK APPROXIMATION: SANDY BIG DATA
In this experiment, we extract the rank-10 SVD factors using SketchySSD and Range-Nee Net for the Sandy dataset. The oversampled ranks for sketchy SVD are 4r + 1 41 and = 2k + 1 83 where k, s < min (m, n²).
As before, Fig. 22 show the cross-correlation between the extracted and true (conventional SVD) right singular vectors using SketchySVD and Range-Net. Fig. 23 shows the scree error in the extracted singular values for the two methods with singular values from conventional SVD as the baseline. Finally, Fig. shows a comparison between extracted dynamic modes corresponding to indices i
[1, 4, 7, 10 from SketchySVD, conventional SVD, and Range-Net. One easily see
23

---

Under review as a conference paper at ICLR 2022
Range-Nel (Vort)
Sketchy SVD vectors
20
20
0.6
0.4
80
0.4
80
0.2
98
0.2
20
60 SVD vectors
80
20
40
60 vectors
80
(a) SketchySVD
(b) Range-Net
Figure 21: Cross-correlation between extracted and true (conventional SVD) right singular vectors for (a) SketchySVD and (b) Range-Net for rank 100 approximation. SketchySVD deviates substantially after index 10 (although sketching at sizes l: 401 and 803) while Range-Net is in good agreement for all the
indices.
Bange Not victor (Vnet)
Skotchy SVD vector
0
SketchySVD
Range-Net
Figure 22: Cross-correlation between extracted and true (conventional SVD) right singular vectors for (a) SketchySVD and (b) Range-Net for rank 10 approximation. SketchySVD deviates substantially after index while Range-Net in good agreement for all the 10 indices.
that Sketchy SVD extracted dynamic modes/right singular vectors deviate quite substantially for [4, 10).
1.50
100
50
0
10
10
(a) SVD
(b) Range-Net
Figure 23: Scree-error in singular values for (a) SketchySVD and Range-Net where conventional SVD used as baseline scree-error metric, Note that for Range-Net error at scale of orders of magnitude apart from SketchySVD (10").
F.5 PARROT: ADDENDUM CORRELATION OF LEFT SINGULAR VECTORS
In the following, we show the deviation of left singular vectors, computed using Range-Net and Sketchy SVD, from the conventional SVD computed left singular vectors baseline. As shown before, random sketching introduces irreducible errors in randomized SVD methods resulting in this unchecked deviation. Fig. 25 shows a comparison of the cross-correltton against the common baseline for both Range-Net and Sketchy SVD.
24

---

Under review as a conference paper at ICLR 2022
(a) SVetchySVD
(b) Truth
(c) Range-Net
Figure 24: Reshaped U; indicative of dynamic modes, corresponding to = 1, 10 for = 10. The dynamic mode approximation error stand out visually for SK for indices 1, 4, 7, 10. Our method does not have such artifacts.
(Uee))
12
-0.4
0.4
0.2
19
SVD vectors
(a) SVDtchySVD
(b) Range-Net
Figure 25: Cross-correlation between true (conventional SVD) and extracted left singular vectors from (a) SKetchySVD (b) Range-Net for rank-r 20 approximation of the Parrot image.
25

---

Under review as a conference paper at ICLR 2022
G SKETCHY SVD IMPLEMENTATION
brief outline the single-pass Sketch-SVD algorithm from Tropp et al. (2019). Note that for the numbers reported in terms storage, we implemented this code with additional memory optimization and sparse matrices.
Algorithm Sketchy SVD)
Input: X I mx expected rank
Output: X E mR the approximated rank k-dim data
I: Initialize
+ 1,8 2k:
b Oversampling parameters
2: Projection maps: T E R ft R**= E Raxm E R
3: Projection matrices: A R R**" B Bixk % Rax* empty
4: for 1: do
Streaming Update
Form H R=*x sparse empty matrix
6:
H(i::) = :(.
Streamed columns
7:
A + A
b. Update Co- Range
8:
B- HΩT
Update Range
Update Core Sketch
10: D qr ccon B)
Basis for Range
11: P PER + _c__ AA")
b Basis for Co-Range
12: C & ((OQ) (VP(P))
Core Matrix
13: U.E.VT) & SV)(C)
Full SVD Core Matrix
14: RXxr t Σ[1 :r, 1:
b Pick top
U ER Up]l
b Pick top
16: VT x <- [T r.
b Pick top Project Row Space
17: U X QU
V" ER"x PVT
b Project Column Space Approximation
19: X E mm t U.VT
26


Reviews:
[{"review_id": "Opci_iG2oNf", "reviewer": "Reviewer_vVFi", "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": "- The extent to which the choice of the hyper-parameters of AdaMax (l_r and #steps per epoch) affects the result should be made more clear. Currently, the authors simply state those choices in the Appendix without justifying them. Also, the robustness of the underlying methodology w.r.t. the exact choice of optimization framework is also not clear (e.g., AdaMax or some other variant).\n\n- There is very limited discussion motivating the target use cases; it'd be helpful if the authors could add more detail in terms of ensuring the usefulness of having those low-rank approximations computed is clear to the reader (e.g., Sandy Big Data use case).\n\n- The authors could add more detail on why only SketchySVD was used as a baseline; also I believe the following work is a fundamental one in the area, so might worth citing that for the reader to get a more complete view of the topic [not my paper]:\nLiberty, Edo. \"Simple and deterministic matrix sketching.\" Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 2013.\n\n- Not clear if the Range-Net being \"fully interpretable\" is well-justified; I am not sure of the practical significance of this statement.\n\nAdditional Comments:\n- The improvement in terms of memory requirements should be highlighted more in the description of the results (e.g., Section 4.3, where SketchySVD requires 24.91GB when only 4.19MB are required by RangeNet).\n\n- Description of the exact methodology proposed (i.e., what are precisely the steps / optimization problems) should be highlighted more clearly in the main paper. Currently, a lot of the details are compressed as part of the Implementation Details subsection, and pushed into the Appendix which is not ideal.\n\n- \"It is well known that natural data matrices have a decaying spectrum wherein saving the data in memory in its original form is either redundant or not required from an application point of view.\" It'd be useful if the authors could provide with some concrete example use cases here.\n\n- The \"no loss in accuracy\" statement in the last sentence of the first paragraph of the Introduction is quite unclear to me; any useful approximation through SVD for data matrices is by definition lossy.\n\n", "summary_of_the_paper": "The paper presents a streaming method to compute an approximate Singular Value Decomposition, without requiring to load the entire data matrix into the main memory. The first stage of the method identifies a basis optimizing for the constraint of orthonormality, as well as minimizing the error between the input and the reconstruction of the input based on the learnt basis. The second stage corresponds to a rotation step, which aligns the low-rank approximation extracted with the SVD factors.", "summary_of_the_review": "Strong results in terms of memory efficiency, which do justify consideration for acceptance in my view; however, the paper could improve in terms of clarity of exposing experiment setup details and choices of hyper-parameters, description of the main methodology, and having stronger application use cases.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9rO8SADFYKX", "reviewer": "Reviewer_YsEC", "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": "##########################################################################\n\nSummary: This paper offers an interesting approach to scaling rank r approximation of a matrix.\n\n##########################################################################\n\nReasons for score: I am inclined to voting for a reject (borderline). The proposed algorithm is intuitive and simple - but I think the experimental sections could be augmented with more results. I am open to changing the rating, pending the authors' responses.\n\n##########################################################################\n\nPros:\n1. Proposes an interesting algorithm for solving a problem widely applicable in machine learning.\n\n\n##########################################################################\n\nCons:\n1. It seems the trained neural network is specifically tied to a particular dataset. Can a trained neural network be reused for another dataset of the same size? (e.g. time series data)\n\n2. There are some lingering questions on experiments. Why does range-net require more memory than sketchy SVD on dimension reduction (Table 3)? How much is the deviation in the computed singular vectors from orthogonality?\n\n3. How is the neural network trained? I did not see much description in the submission.\n    \n\n##########################################################################\n\nQuestions during rebuttal period:\n\nPlease provide clarifications for the points in the previous section. I also did not see an appendix in the submission which I wanted to glance at.\n\n#########################################################################", "summary_of_the_paper": "This paper proposes a neural network architecture for computing a rank-r approximation of a matrix. The first part consisted of learning the projection and the second part consisted of learning the rotation. An experimental comparison against the state-of-the-art Sketchy SVD algorithm is provided on three datasets. The authors claim that the proposed method is extremely memory efficient compared to previous approaches.", "summary_of_the_review": "While the paper proposes an interesting algorithm, in the end I did feel much void in the experimental section. Perhaps adding more dimensions in terms of algorithm comparison (one more algorithm in addition to sketch SVD) / adding more datasets could help. In addition, the authors could clarify how trained neural network can be adapted to not just one dataset but a dataset that may be related (time series).", "strength_and_weaknesses": "", "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": "4e9I4B_dFUv", "reviewer": "Reviewer_uKtm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The main selling point of the algorithm is that the memory needed is only O(rn), as opposed to O(r(m+n)) for competing algorithms and the result is exact as opposed to approximate.  The way this reduction is achieved is by allowing multiple streaming passes over the rows of X, whereas the competing algorithms only allow 1 pass.  This would be useful when the dataset is so large that storing a copy of the data is prohibitive and that is a realistic setting in the modern data-science workflow.\n\nIndeed, for the purpose of dimensionality reduction it might even be sensible to only to complete stage 1.  That's because many algorithms, e.g. linear/logistic regression, kernel methods with the Euclidean kernel, and many neural network architectures, will be agnostic to the rotation H.\n\nOne small theoretical disadvantage is that the number of passes required is not known.  The authors state at most 5 passes are necessary, but actually that number was determined empirically and your number of passes depends on the number of epochs to convergence in stage 1.\n\nTable 1 states that Range-Net space complexity is r*(n+r), however Appendix E.3 states that the implementation dumps XV*, an intermediate mxr matrix, to disk.  Specificly E.3 states \"The output data [of stage 1] is dumped onto the secondary memory assuming that storing a low rank approximation is still main memory intensive. For Stage 2, this low rank approximation in the secondary memory is streamed as input, and the extracted singular values and vectors are saved in main memory.\" so the authors' implementation actually requires r*(m+n) storage.\"\n\nI think it is misleading that the implementation does not obey the claimed memory bound.  It is true that the algorithm can be implemented without dumping XV*, but it requires more compute and passes to recalculate XV* during stage 2 and still more to compute the actual singular values.  How this extra compute affect the time required for the approximation?\n\nIn terms of writing, I think that the paper is poorly organized.  The main drawback is that there is no clear and concise description of the algorithm.  Parts of the algorithm are described in Section 3 and Appendix E, but Section 3 also contains the statements of correctness interspersed with the description.  There are terms left undefined and dimensions of matrices are only identified haphazardly.\n\nOther notes:\n. Please formally define tail energy.\n. Section 1.2.  \"In the absence of ... different from SVD factors\".  I didn't understand this sentence at all and Equation (1) does not include any decomposition.\n. I found the description of the algorithm as a neural network confusing. The network is two layers that each consist of a single matrix multiplication,  it's two single matrix multiplications which are solved for independently.\n. Figure 4 caption does not match the subfigure captions\n\n", "summary_of_the_paper": "The paper presents a multipass streaming algorithm for rank-r SVD.  Given an input matrix X in R^{mxn} the algorithm identifies two matrices V* in R^{nxr} and H in R^{rxr}. V* has orthonormal columns that span the top r right singular vectors.  H rotates V* so that V*H = Vr, where Vr in R^{nxr} is the matrix of the top-r right singular vectors.  V* and H are computed by minibatch gradient descent, trained until convergence with custom loss functions.  V* is computed in the first stage and then H in the second stage. \n\nThe algorithm is accurate and uses very little storage.", "summary_of_the_review": "The algorithm is interesting and practical for is extremely small memory footprint, but organizational problems prevent a higher score.", "strength_and_weaknesses": "", "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": "0_c7_jKwVPz", "reviewer": "Reviewer_MNXm", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths:\n\tRangeNet just costs O(nr+r^2) space to calculate truncated SVD, which is memory optimal. Besides, RangeNet produces the nearly accurate results with no more than 5 passes on matrix, which is pass efficient.\n\nWeakness:\n1. No time analysis of real runtime is listed in this paper. Once this algorithm costs much time to produce results, it is not feasible in real applications.\n2. There is no dataset shown which can be handled by RangeNet but cannot be handled by classical algorithms for truncated SVD. Experiments on large dataset will make this work more solid.\n3. It is not fair to compare RangeNet with SketchSVD, RangeNet just produces the right singular vectors while SketchSVD produces both left and right singular vectors. Besides, the experiments in paper just compare them on matrix with size m >> n.\n\nSome recent work on randomized truncated SVD should be compared, like:\n\nEfficient randomized algorithms for the fixed-precision low-rank matrix approximation\nW Yu, Y Gu, Y Li - SIAM Journal on Matrix Analysis and Applications, 2018 - SIAM\n\nFast randomized PCA for sparse data\nX Feng, Y Xie, M Song, W Yu… - Asian conference on …, 2018 - proceedings.mlr.press", "summary_of_the_paper": "In this paper Range-Net is proposed for calculating the right singular vectors and singular values, which produces nrealy accurate results with less memory cost than existing SkectchSVD. However, no time analysis or real runtime is listed in this paper, which is an important shortcoming of this paper.", "summary_of_the_review": "Without runtime listed in this paper, although this algorithm is memory optimal, it is not good enough. Besides, using linear optimizer to solve the truncated SVD seems not a novel idea.", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: The reviewers were fairly consistent in agreeing that this is a reasonable paper with an interesting idea.  However, the use-case is fairly narrow, as the main benefit is less intermediate storage (and only significant for very rectangular matrices) but compared to alternatives it require many passes over the data (usually 5 or so). So it's a narrow use-case and many of the comparisons are not apples-to-apples since the accuracy, time, space-complexity and number of passes differ from algorithm to algorithm.

So while acknowledging the potential benefits of the method, there are downsides too, and thus a clear presentation is very essential. The reviewers mention that presentation (listing the algorithm, clear experiments) could be improved.

On my own reading, I noted that the choice of SketchySVD as the dominant baseline is misleading. SketchySVD is for streaming data (more restrictive than single-pass) so this is an unfair comparison. The appendix does a better job of including other baselines (block Lanczos), though it mischaracterizes them (it says "BlockLanczos requires persistence presence of the data matrix X in memory", but this is not true, the method could easily be implemented in a matrix-free fashion). Another method to compare with is the single-pass algorithm randSVD in Yu et al., who show how to implement one of the Halko et al. 2011 2-pass methods in just one-pass.  Other reviewers mention baseline algorithm issues too.  I do acknowledge the improved accuracy of your method over all these baselines for some matrices, in terms of the Frobenius norm (or tail error); however, I'm not sure the differences in spectral norm are are great, and see Remark 2.1 in Martinsson and Tropp '20 for arguments about why Frobenius norm guarantees are often not as desirable as spectral norm guarantees.

Another issue is related to the left vs right singular vectors. A reviewer noted: "It is not fair to compare RangeNet with SketchSVD, RangeNet just produces the right singular vectors while SketchSVD produces both left and right singular vectors." The authors respond "Range-Net computes both left and right singular vectors but does not consume main memory to store left singular vectors at run-time". However, if we allow another pass over the matrix to find the left singular vectors, this post-processing can be applied to *any* technique that approximates the singular values and right singular vectors, hence PCA methods are applicable, including deterministic methods like the "Frequent Directions" method (Ghashami et al. '16).  

In summary, this method is high-accuracy and low-memory, yet it also has downsides compared to other methods, and the paper could use some improvement.  I don't think the paper is ready at this time for acceptance, but given the advantages of the method, I encourage the authors to make changes and resubmit an improved version to ICLR next year or other similar venue.


References:

Yu, Gu, Li, Liu, Li, "Single-Pass PCA of Large High-Dimensional Data". IJCAI '17, https://doi.org/10.24963/ijcai.2017/468

Ghashami, Liberty, Phillips, Woodruff, "Frequent directions: Simple and deterministic matrix sketching". SIAM Journal on Computing. 2016;45(5):1762-92.

Martinsson, Tropp. "Randomized numerical linear algebra: Foundations and algorithms". Acta Numerica. 2020 May;29:403-572.
Decision: Reject