Matrix Compression via Randomized Low Rank and Low Precision Factorization
Authors: Rajarshi Saha
Varun Srivastava
Mert Pilanci
Venue: NeurIPS 2023 poster (2023)
Keywords: Matrix compression
Randomized low rank factorization
Randomized SVD
Sketching
Quantized embeddings
Random matrices
TL;DR: We propose a randomized algorithm to compress a matrix by quantizing its low rank factorization.

Abstract: Matrices are exceptionally useful in various fields of study as they provide a convenient framework to organize and manipulate data in a structured manner. However, modern matrices can  involve billions of elements, making their storage and processing quite demanding in terms of computational resources and memory usage. Although prohibitively large, such matrices are often approximately low rank. We propose an algorithm that exploits this structure to obtain a low rank decomposition of any matrix $\mathbf{A}$ as $\mathbf{A} \approx \mathbf{L}\mathbf{R}$, where $\mathbf{L}$ and $\mathbf{R}$ are the low rank factors. The total number of elements in $\mathbf{L}$ and $\mathbf{R}$ can be significantly less than that in $\mathbf{A}$. Furthermore, the entries of $\mathbf{L}$ and $\mathbf{R}$ are quantized to low precision formats -- compressing $\mathbf{A}$ by giving us a low rank and low precision factorization. Our algorithm first computes an approximate basis of the range space of $\mathbf{A}$ by randomly sketching its columns, followed by a quantization of the vectors constituting this basis. It then computes approximate projections of the columns of $\mathbf{A}$ onto this quantized basis. We derive upper bounds on the approximation error of our algorithm, and analyze the impact of target rank and quantization bit-budget. The tradeoff between compression ratio and approximation accuracy allows for flexibility in choosing these parameters based on specific application requirements. We empirically demonstrate the efficacy of our algorithm in image compression, nearest neighbor classification of image and text embeddings, and compressing the layers of LlaMa-$7$b. Our results illustrate that we can achieve compression ratios as aggressive as one bit per matrix coordinate, all while surpassing or maintaining the performance of traditional compression techniques.

Matrix Compression via Randomized Low Rank and Low Precision Factorization
Rajarshi Saha, Varun Srivastava, Mert Pilanci
Department of Electrical Engineering
Stanford University Stanford, CA 94305, USA
frajsaha, psrivaa.illaccieestaanfo
Abstract
Matrices are exceptionally useful various fields of study as they provide a convenient framework to organize and manipulate data in structured manner. However, modern matrices can involve billions of elements, making their storage and processing quite demanding in terms of computational resources and memory usage. Although prohibitively large, such matrices are often approximately low rank. We propose algorithm that exploits this structure obtain low rank decomposition of any matrix A as A R LR, where and R. are the low rank factors. The total number of elements in L and R can be significantly less than that in A. Furthermore, the entries of L and R are quantized to low precision formats compressing A by giving algorithm first computes an approximate basis of the range space of A by randomly sketching its columns, followed by a quantization of the vectors constituting this basis. It then computes approximate projections of the columns of A onto this quantized basis. We derive upper bounds on the approximation error of our algorithm, and analyze the impact of target rank and quantization bit-budget. The tradeoff between compression ratio and approximation accuracy allows for flexibility in choosing these parameters based on specific application requirements. We empirically demonstrate the efficacy of our algorithm in image compression, nearest neighbor classification of image and text embeddings, and compressing the layers of LlaMa-7b. Our results illustrate that we can achieve compression ratios aggressive as one bit per matrix coordinate, all while surpassing maintaining the performance of traditional compression techniques.
low rank and low precision factorization. Our
Introduction
Low-rank structures for matrices have proven to be incredibly valuable and ubiquitous across numerous fields of study. Several real-world matrices approximately exhibit low-rank structure due to inherent redundancy patterns, allowing them to be approximated using low-rank factors. Udell and Townsend [69] provide potential justification by considering generative model with latent variables for real-world matrices. Applications where low-rank structures in matrices are exploited include, but are not limited to, imaging (Lingala et al. [34]). fine-tuning large language models (Aghajanyan et al. [3], Hu et al. [25], Karimi Mahabadi al. [30]. Valipour al. [70], Wang et [76]), compressing neural networks (Ben Noach and Goldberg [8]. Idelbayev and Carreira-Perpinaa [26), Mao et al.
[39], Phan al. [47], Swaminathan et al. [63], Tahaei et [64], Wang et al. [77], Winata al.
[78), Yu et al. [84]), obtaining efficient NN architectures (Jaderberg et al. [27], Tai et al. [65]), etc.
Given a matrix A RRad low-rank approximation is given by LR, where L R=xm R E Rmxdd denote the left and right low-rank factors with m & min (n, d). Since m(n + d) < nd.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Original image
(b) Naive quant.
(c) DSVD
(d) LPLR (ours)
(e) LSVD (ours)
Figure I:
Compression of Shepp- Logan phantom (a standard test image for medical image reconstruction). Naive quant. was done with 2-bits per pixel of this 10 10 image. Quantizing the SVD factors "directly" (i.e.. DSVD) and (our) LPLR/LSVD algorithms, factorize the image into a product tall & wide matrices which reduces the total number of elements, allowing each entry to be represented using upto 8-bits precision per pixel. Despite the increase in precision per pixel, the total number of bits remains the same at 2 10".
the total number of entries in LR can be significantly smaller than A, enabling matrix compression. The need for compression is driven by the overwhelming storage demands and computational complexity linked to large matrices. In comparable but distinct line of work, low-precision (LP) representations have also been studied extensively as a means to reduce the memory footprint. Quantization of continuous valued variable using small number of bits reduces storage requirement while trading off accuracy. In addition, they also facilitate low latency for real-time inference and low energy consumption (see Gholami et al. [21]). Works of Alimisis et al. [4], Safaryan et al. [55] have studied various matrix compression operators for distributed optimization.
In this work, we introduce LPLR: Low-Precision Low-Rank factorization a general matrix com- pression algorithm that simultaneously exploits the low-rank structure of a matrix and quantizes it, to obtain a low-rank factorization, such that the elements of the factors are represented using a small number of bits. Although LPLR can generically refer to a class of algorithms whose main goal is to obtain low- www-prccision representations and exploiting low-rank structures in matrices, in the rest of the paper, we reserve this acronym for our proposed algorithm in Alg. Fig. shows the effectiveness of LPLR in preserving the semantic features in image compression. Other algorithms designed towards achieving the same objective have been named and described appropriately throughout the paper.
1.1 Related Works
The optimal rank-k approximation of a matrix A E Raxd denoted as Aç, can be obtained by performing the singular value decomposition (SVD) of A, which gives A = UEVT. T. To obtain Ag, we keep only the top & singular values along with their corresponding left and right singular vectors, setting the remaining singular values to zero. In other words, A = U, Σ V = > a.u.v, where ai, u,, and v, represent the i-th singular value, left singular vector, and right singular vector, respectively. The matrix Ag minimizes the Frobenius norm |AA A under the constraint that the rank of A is at most This result known as the Eckart- Young-Mirsky theorem [18], which states that ||A - Aull; = =ii> of. However, computing the SVD has high computational complexity of ((dd)) (n 2 d without loss of generality), which can be impractical for large matrices. Therefore, alternative methods such as in Jin et al. [28], Ye and Du [82], Zhang et al. [85] have been proposed which solve variants of the minimization problem. Chi approaches for obtaining low-rank approximation.
Low-rank approximation:
et al. [11] provide a survey of optimization-ban
Along parallel line of work, randomized low-rank factorization algorithms have demonstrated their effectiveness in handling massive datasets efficiently while maintaining competitive accuracy levels. Several works, including those by Derezinski et al. [13], Drineas and Mahoney [16], Drineas et al. [17], Halko et al. [23], Ma and Solomonik [37], Mahoney [38], Martinsson al. [43]. Tropp et al. [67], Witten and Candès [79] have focused on reducing the complexity of computing SVD to approximately O(mm²), where m & These algorithms aim to approximate the range space of matrix A by utilizing a sketched version AS, where S E m a random matrix with m < d. The columns of A are then projected onto this approximate range space. By choosing m k + where p Z 2 is small integer, the resulting low-rank approximation A = LR provided by these algorithms can be proven to be within a small multiplicative factor of the optimal rank-k approximation, stated as E LR- A < (1 5) A AIp The sketching matrix S is typically selected from the

---

widely used class of sample Gaussian matrix where each entry Si ~ (O, :
(JL) embeddings. A popular choice when A is dense is
Randomized quantization: JI. embeddings also have practical uses in vector quantization. this context, when quantizing vector Re instead of quantizing directly, the encoder quantizes Sx, and then the decoder obtains an approximation of x through S Q(Sx) 2 x. This randomized transformation equalizes the coordinate values of allowing for smaller range of values and higher precision for the quantizer Q under a fixed bit-budget. As a result, it leads to a smaller &2 error compared to independently quantizing each coordinate in a naive manner. Works such as Chen et al. [10], Lyubarskii and Vershynin [36], Mayekar and Tyagi [44], Safaryan et al. [54], Saha et al. [56, 57, 58], Studer et [60], Suresh al. [61, 62], Vargaftik et al. [71, 72], Young al. [83] explore different variations of this concept for different applications.
2 Proposed Algorithm
Prior to detailing our algorithm, we first review the characteristies of the uniformly dithered quantizer that we employ within our approach. Uniformly dithered quantization has been utilized in various prior works Alistarh al. [5], Bernardo et al. [9], Gray and Stockham [22], Mayekar and Tyagi [44), Suresh et al. [61, 62], and is succinetly described in $(2.1) below.
2.1 Uniformly dithered quantizer
Let us consider quantizing scalar with |x]| S R. Given bit-budget of B bits, the scalar quantizer with dynamic range R is described by first specifying the M = 2 quantization points as:
Q1 - R, = R + A,
R + 2A, fas = R + (M 1)A.
Here, the resolution is given by A M-I.
2n and the quantizer operation is defined as:
gk+1 with probability T,
QR,((T)
qu with probability 1 1-
where & = arg max, S x.. i.e. x E [yk. (6+1). and
デー Such quantizer satisfies
2
R²
E [R.B(=))= x and E (QR,B(x) =)²
(2)
4
(2B 1)2
iee, it is unbiased and the quantization error variance is dictated by R and B. Here, the B(-) is over the randomness from dithering in (1) (ref. App. C). If the input æ to the quantizer falls outside this range, i.e., > R or < -R, the quantizer is said be saturated. Finally, quantize any matrix X, we obtain QR, by quantizing each entry independently, i.e., [QR,((X)], A (X.s)...)).
2.2 Proposed algorithm: LPLR
In order to comprehend low precision and low rank representations, we first introduce a simple strategy, which we name direct-SVD quant. This method involves two main steps: It first computes the optimal rank-k decomposition A = U₁ V
k. and then, it quantizes the low-rank factors independently, namely. L = E+ and R = Q'(VT). Here, Q and Q'' are uniform scalar quantizers with respective bit-budgets B and B'. A detailed analysis of this direct-SVD quantization approach can be found in Appendix H, along with pseudocode provided in Algorithm 2. Despite its simplicity, this not the optimal strategy due two reasons. Firstly, it necessitates computing the SVD of A, which is computationally expensive at O(nd²). Secondly, let us consider improving the approximation to A when the first factor fixed to Q(U+) by solving the optimization problem:
X"
arg min [|Q(U,)X A Qt
XERixd
This computes the projection of the columns of A onto the range space of Q(U+). Suppose the resulting projection coefficients are further quantized to get Q' (Q(U,)tA Since X is the solution of (3), for a sufficiently large value of B', is evident that (QQUU=QQ(QQLL)) () Al S IQ(U,, Q'(VV) - l[ and hence, better than direct-SVD quant. However, this approach of projecting onto the range space of QUU+) (which we refer to as LPLR-SVD and analyze in App. D) still requires the computation of Ug. we can replace Ug by AS, i.c., an approximation of the
3

---

Algorithm 1: LPLR: Randomized Low-Precision Low-Rank factorization
Input :Matrix A E IRaxd, sketch size m, Quantizers Q Q' with dynamic ranges RQ. Ro and
bit-budgets B, B' respectively.
Output: Factorization:: LR where L E R=*m, R E R
Sample Gaussian sketching matrix S E Rd with entries Siy ~ ~ (o. ).
2 Compute an approximate basis of column space of A by forming the sketch: AS.
3 Quantize the approximate basis with Q to get Q(AS).
4 Find W = arg minw [[Q(S)) - All
Quantize W* uuinn quantizer Q' to get Q'("".
return Low-rank and low-precision approximation LR where Q(AS), R Q'WW").
range space obtained through random linear combinations of the columns of A (also known as a randomized rangefinder [42]. This leads us to our LPLR algorithm, described in Alg. 1, which finds W arg min gi [[AASW - All and forms the low-rank low-precision approximation Q(AS)Q(W)) where Q Q' are quantization operators. While the solution of this problem is available in closed form as W = Q(AS) A, one can also use an approximation of W by solving this least-squares minimization using iterative method such as conjugate gradient descent.
In addition to the above argument supporting the superiority of LPLR compared to other baselines (ref. to Tabs. and 2), there exists another essential reason why LPLR outperforms them. This reason directly relates to the selection of S as a Gaussian matrix, which is an integral component of LPLR. Random Gaussian matrices are JL. embeddings and possess an equalization property that enhances the precision of uniform quantizers. In particular, let us consider an arbitrary vector x E R and obtain an estimate as x = S Q(Sx) using a uniform quantizer Q. It can be shown that the vector quantization error remains constant and does not grow with the dimension d, expressed as - x12 = O(1). This represents a substantial improvement compared to the naive strategy of independently quantizing each coordinate of x, which lcads to a quantization error growth rate of (d)). We provide a detailed explanation of this phenomenon in App. D. Furthermore, even when the quantization is 1-bit per coordinate, e.g., ((Sx) Sign(Sx) (Sx), this embedding provides strong near-isometric embedding properties due to the properties of random hyperplane tessellations [50].
While the strong equalization property of Gaussian embeddings is known result, certain works such as Saha et al. [57, 58), Suresh et al. [61, 62] opt for using randomized Hadamard embeddings instead of Gaussian ones. The reason behind this choice is twofold: (i) Gaussian matrices are dense, requiring ((d) multiplications when computing Sx, and (ii) the entries of S are floating point numbers that must be stored in full precision, contradicting the objective of quantizing x using fewer bits. However, these concerns are not problematic for LPLR because the effects of S in the first low-rank factor neutralized by the second low-rank factor, and S does not need to be stored. In fact, we exploit both the equalization property and the subspace approximation property of Gaussian matrices to derive a superior upper bound for the approximation error, discussed next in $3.
3 Approximation Error Analysis
We are now in position to state the approximation error guarantee of LPLR Let us denote the zth row of our input matrix A as a For convenience of analysis, we make the following assumption.
Assumption 3.1. Rows of matrix A have bounded norm, i.e., ||a(0) < R for some known R > 0.
The following result gives an informal upper bound on the expected Frobenius norm error of the factorization returned by Alg. 1.
Theorem 3.2. LPLR approximation error (Informal) Suppose our inpul matrix A E B with || < R O(1) has singular values 01y-.-,0, Tr with = rank( () and target rank as k. Let <(A) = = 0 and ki (((A)) = 01/0g respectively be the condition numbers of A and the best rank-k Furthermore,
approximation of A, and let us denote K = min { [((A), n(A)) (1 cLok41/ow /ow)
for sufficiently small constant > 0, suppose the dynamic range of Q is set be ci Vlog (n/E) /m.

---

and that of Q' is set to hi/mmdd. Then, the LPLR factorizziiiiionn returned by Alg. I satisfies
EILRR - 1
m- k- (1+m-
k
||As - All tc,
while utilizing a total budget of log2 and are constants that depend on R.
cn((A))
Vi V log mm²)) bits for n d. Here, Co Cz cg.
We provide less formal version of our main result here, suitable for interpretation. The formal statement of this result, including specific constant values, can found in Thm. G.2 of App. G. It does not necessitate the assumption n z d and provides distinct thresholds for B and B'. Thm. G.2 asserts that, for a target rank-A; as long as m k + 2, one can ensure an arbitrarily small approximation error of by selecting the number of bits to be at least above certain threshold budget. The threshold depends on the error tolerance e, dimensions n and d, the sketch size m, and the spectrum of A. The value of is determined by taking the smaller of two quantities. In the case of matrices with a sharp decline in singular values (e.g., matrices exact rank-k), where the ratio 0 approaches zero,
R xAA)). For matrices with smoother spectrum (e.g., all singular values are equal), A = x(A). the condition number of the input matrix A.
Remark 1. We consider two distinct scenarios based on Asm. 3.1. The first case assumes that the row norms are bounded by a constant, represented by R = O(1). This assumption is reasonable when the rows of A correspond to different normalized features of a data point. The second case assumes that the individual entries of A are bounded by a constant, i.e., A.j O(1). This implies that R = O(vd), d), which is reasonable assumption for scenarios like images, where it is known that each pixel value is bounded. In Tab. we compare the performance of the algorithms when 011,, while in Tab. 2, we assume R O(vd). Thm. 3.2 assumes that O(1). The expressions in Tab. 2 can be obtained in similar manner from the formal version in Thm G.2.
3.1 Analysis outline
The derivation of the upper bound on the approximation error of LPLR is presented in App. G. In this section we outline a brief proof sketch that highlights the main challenges the proof. As mentioned already in $2.2, the analysis of LPLR utilizes the subspace embedding and equalization properties of random Gaussian matrices. A key component in Alg. the choice of dynamic range for quantizers assume that when either Q Q' gets saturated in lines 3 and 5 of Alg.
Q and Q'. In our analysis, 1, a trivial factorization of LR = 0 is returned. We choose the dynamic ranges Ro and Ro to be sufficiently high enough so that this happens with very low probability. Formally, for quantizer Q, Lemma E. states the following:
2 log 16
||S||
R1
with probability exceeding 1
m
8nR2
Here, ||S||| max is max-norm the matrix AS, i.e., the coordinate with maximum magnitude. This concentration result is consequence of the equalization property of Gaussian matrix S.
On the other hand, the input the second quantizer is Q(AS)' A and Lemma E.2 provides concentration result for the max-norm of this matrix. Although in a general worst-case scenario, the coordinate values of the pseudo-invers [6]), because we compute the pseudo- inverse of the matrix AS, which is rectangular (m & n) and with random Gaussian entries, (I(A)) ||2 does not shoot up arbitrarily shown by Rudelson and Vershynin [53]. We then show that [[Q(A))|l ||2 is not too far from (AS))112, allowing us to derive
of a matrix with small entries can be large (Alon and Vu
2 log
an expression for Ror. We get for 7 and t
m
192
2n
[[QAS)) All max 1--1-t with probability exceeding 1 4n
The second part of the analysis deals with upper bounding the approximation error when the second low-rank factor is unquantized, i.c., [[((S)((AS)) A A conditioned on the event that Q and Q' are unsaturated, We reduce this problem analyzing the solution of the following:
X
arg min
X T A - Q(A))
(4)
5

---

Table I: Comparison with baselines (row-norm bound is constant, ie.. ||a O(1). k, m & min(d, n).
w: no, of rows, d: no. of columns, me sketch size, e: error tolerance. 8 = k/(m k 1). The expressions for bit-budget (per entry) ignores constant multiplicative factors inside the loga(.). We assume 2 d.
Algorithms
Approximation error
Bit-budget (per entry)
Computation
Naive uniform
logu
nd
(
Direct-SVD
A All t
log2
nd
O
LPLR (ours)
(1 + 6) |A+ Ale te
loga
A(Ae)e
log
max2
(nddm)
2
vd
Table 2: Comparison with baselines (individual entries of A are bounded by a constant, i.e. A., = O(1))
Dimension dependent terms are color highlighted for ease of comparison with Tab, 1.
Algorithms
Approximation error
Bit-budget (per entry)
Computation
Naive uniform
loga
nd
(nd)
Direct-SVD
All +E (1+)) A Alp +E 1 1oog2
AA
log2
ko Vnd
((nd²)
LPLR (ours)
s/Ai le nm
dllog
?d?
(Idd)
We refer to (4) as the sketched least squares problem with quantized response as it is a variant of the generalized least squares problem, X arg minx [X] A A ll This is potentially a problem of independent interest, and we analyze the solution (4) in detail in App. Exploiting the subspace embedding property of S we show that
m -
A 10--Al [I quantization error term.
x A A
< E
X
A
A
S
m
This leads us to the proof of Lemma G.1 which gives the approximation error of LPLR when Q and Q' are unsaturated. Finally, taking into account the low-probability saturation events, for which the error is ||A|] I??. we derive our main result in Thm. G.2. Subsequently, we discuss the approximation made in App. G.2 and arrive at the informal result of Thm. 3.2.
3.2 Comparison with baselines
We are now in a position to compare the performance with baselines in Tabs. 1 and 2.
Naive quantization: The most straightforward bascline for matrix quantization is naïve quantization where each coordinate of the matrix is quantized independently, agnostic to any low-rank structure in the matrix A. In this, we allocate B3 bits to each coordinate of A and since there are nd entries in the matrix, from (1), the Frobenius norm error is upper bounded by (28-1)²- Note that this holds
R²nd
true irrespective of whether that the error is within certain tolerance c, we then require 5 loga (nd) bits. In this, and also other expressions for bit-budget requirements of algorithms in Tabs. and 2, we have ignored the multiplicative constant factors inside the log2(.) for simplicity of exposition. The exact expressions can be found in the corresponding appendices where we derive them.
0(1) or O( O(vd) because [|a(*) S R implies Aij S R. To ensure
One of the primary reasons why both direct-SVD and LPLR are expected to perform better than naive is that the former strategies exploit the low-rank structure of the matrices to reduce the total number of parameters being quantized, i.c., k(n + d) for direct-SVD and m(n + d) for LPLR, vs. nd for naïve. Given a total bit-bu for the entire matrix A, since we now quantize fewer parameters than before, we can allocate higher number of bits to each parameter, enabling higher precision. The price we pay for exploiting the low-rank structure of matrices is the additional ||A Al dependent term, which usually very small for matrices that can be well approximated by a low-rank structure. For matrices that are exactly rank k. this term is O. As we see in our numerical simulations in $4, several real-world matrices can be well-approximated by a low-rank structure.
Direct-SVD quant.: From Tab. 1, we see that to achieve an e-quantization error, direct-SVD requires logz(k bits per entry, which greater than 2 loge
am
required by LPLR (ignoring the Vd

---

logarithmic terms). Evidently, LPLR demands fewer bits than direct-SVD because ks m < min(n, d} for inherently low-rank matrices. For the regime presented in Tab. 2. the bit requirement for direct-SVi remains unchanged. However, LPLR now requires 2 logz (nmvd), slightly more than direct-SVD, due to the additional vn factor. Thus, it makes sense expect that direct-SVD can perform better in this regime. This is supported by our numerical experiments in Tabs. to 7, where direct-SVD indeed outperforms L.P.R in certain scenarios. Nevertheless, it is crucial emphasize that direct-SVDD necessitates computing the SVD, which can be prohibitive for very large matrices due to the current memory limitations of available GPUs, making L.PRR the only viable option.
Unsurprisingly, naive quant. requires the least computation, i.c., (nd)), as it just does single pass over all the elements of A. The O(nd²) complexity of direct-SVD quant. stems from the requirement of computing SVD (assuming n 2 d). LPLR the best of both worlds for the same bit-budget, LPLR has smaller approximation error than both direct-SVD and naive, and a complexity of ((dd),, arising from the requirement to compute AS, i.c., a product of two dense matrices of dimensions n x d and d x m, which is better than direct-SVD, since < d.
Computational complexity:
4 Numerical Simulations
4.1 Overview
We evaluate the robustness of LPLR multiple tasks, namely, image compression, binary, and multi-class classification across disparate domains including vision, text and raw images, and neural network weight matrices. We consider range of input configurations to showcase the performance and non linear effects of joint quantization and low rank approximation on a given dataset, especially lower bit budgets. IPLR provides competitive results bit budgets as low as single bit, providing extreme model compression while maintaining non trivial performance for the task at hand.
Baselines. We employ naive quantization, which quantizes the input matrix by rounding to the nearest scalar in the underlying data type's quantization grid, as our primary benchmark. Naive quant. and its variants - Dettmers et al. [14], Yao et al. [81]. are the most popular method in use across domains, as their memory and computational run time requirements scale extremely well with model and dataset sizes. In addition, we also evaluate the performances of direct-SVD quantization and LPLR-SVD to disambiguate between the entangled effects of quantization and exploiting low rank structure.
Metrics. We evaluate LPLR performance using task specific goodness of fit metrics, as well as relative Frohenius norm error between the original and matrix reconstructed from its low-rank factors, i... LR- - A l|- In addition to this, we enforce parity between the number of bits used by all quantization schemes, so that the total space required (in bits) for storing the approximated matrix is identical across LPLR, LPLR-SVD, direct-SVD quant., and naïve quant.
Notation. In all our experiments, we denote the bit budget for the left low rank factor L as B, for the right low rank factor R as B', and the corresponding bit budget for naive quantization as Buq- For simplicity, we maintain equal bit budgets B- = B' for both quantizers Q and Q'. Wherever necessary, we also abbreviate direct-SVD quant. as DSVD, L.LR-SVD as LSVD, and naive quant. as NQ.
The main algorithm is implemented in Pytorch (Paszke et al. [46]), and utilizes Hugging Face [80] implementations of all datasets and large language models. All experiments were performed on single GPU NVIDIA TITAN RTX. Further simulations and experimental details can be found in App. J. Our code is available https: btttps//gitthb.
4.2 Image Compression
Image compression is a prototypical application of low rank matrix compression, as images are known to be significantly rank deficient in many practical scenarios (Zhang et al. [86], Zhou et al. [87]). In this task, we apply LPLR on 1000 x 1000 dimensional Shepp Logan phantom images from Gach et al. [20]. These are set of synthetic 2D images designed to simulate the typical characteristics and structures found in computed tomography (CT) scans. They consist of geometric shapes, including circles and ellipses, representing different tissues organs within the scanned object.
The main results are summarized in Tab. 3. To ensure a fair comparison, we adjust the sketch sizc/target rank that bit budgets are identical between naïve quant. and LPLR. This allows
7

---

us to preserve the original datatype of the image (consequently large dynamic range). while substantially reducing the pixels used for representing the image to as low as 1 bit per pixel (on average). Specifically, in Figure 1, we can observe the least visual distortion in the case of LPLRR, which preserves critical semantic features of the images, such as the small ellipses. that LPLR outperforms both techniques at lower naive quantization bit budgets. We attribute the better visual and quantitative performance to the higher dynamic range available to LPLR as well as structure preserved in the low rank decomposition.
is clear
Table 3: Comparison of LPLR and LPLR-SVD (LSVD) Frobenius norm errors with baselines, for different input LPLR bit budgets. Each triplet (B, B', BBa)) of configurations has an identical compression ratio. Here,
B = B'. The second column specifies the sketch size m for LPLR, and target rank k for DSVD or LSVD. We
provide results for input bit budgets a finer granularity to identify regimes where naive quant. is outperformed.
Target Rank (
Target Rank (b)
13
Sketeh Size (m))
Bag
LPLR
DSVD
LSVD
NQ
Size (7c)
B.g
LPLR
DSVD
LSVD
NQ
32
0.610
0.553
0.506
0.532
32
31
0.447
0.523
0.392
0.312
28
0.557
0.546
0.490
0.532
28
35
0.434
0.521
0.380
0.312
24
20
0.540
0.537
0.454
0.532
24
41
2
0.401
0.517
0.358
0.312
20
25
0,485
0.529
0.426
0,532
20
50
2
0,371
0,513
0.331
0,312
0.447
0.523
62
0.509
0.308
0.312
12
41
1
0.402
0.518
0.360
0.532
12
83
2
0,310
0.506
0.286
0.312
0,340
0.508
0.326
0.532
125
0.267
0.499
0.284
0.312
4.3
Embeddings extracted from pre-trained models
The efficacy of pre-trained embeddings is well established in vision (Li ct al. [33], Parisi et al. [45]. text (Qi et al. [51], Rezaeinia et al. [52]) for rapid feature computation as input to a variety of downstream tasks. Embeddings also play crucial role in a number of software applications, including but not limited to, open source vector search libraries (Liu [35], Marqo [41]), semantic search engines (Amazon AWS [7]), vector databases (Pinecone [49]). Since most applications rely on proximity in "embedded space", it is essential that common operations
embeddings be computationally efficient. Specifically, one would like to optimize nearest neighbor (NN) searches which solve the optimization problem arg min; ||x; yl2 (reducible to arg max; Xy where X is the matrix with training vectors {x,} as its rows, and y is the query vector). The time complexity of NN search scales linearly with dimensions of X E Raxd and number of neighbors (k). By embedding the data matrix in a dimension m < d, we directly speedup the run-time and reduce storage costs. Moreover, as datasets grow exponentially in size (especially document databases) and transfer learning becomes the dominant modality of training new models, embedding compression becomes a necessity for storing data without a corresponding exponential increase in hardware requirements.
4.3.1 Embedding Classification
In this experiment, we evaluate several embeddings of standard datasets, namely CIFAR-IO, 10, CIFAR- 100, IMDB and Emotion datasets. CIFAR-10 10 consists of 60,000 color images divided into 10 classes, with each class containing 6,000 images. The dataset is split into 50,000 training images and 10,000 test images, with a resolution of 32x32 pixels. CIFAR- 100 increases the number of classes to 100 categories for an identical training and test size CIFAR-10. 10. The IMDB (mte [2]) dataset consists of 25,000 train and test sentences containing annotated binary sentiment labels for movie reviews, plot summaries and other rating information. The Emotion (mte [1]) dataset is a sentiment analysis dataset, containing 16,000 train and 2000 test sentences, each exemplifying a singular emotion, which represents the sentiment label for that sentence.
For CIFAR-10 and CIFAR-100 we embed the entire dataset using MobileNet v3 (Howard al. [24]) pretrained on ImageNet (Deng et al. [12]) producing an embedding matrix of dimension 60000 1024, which we compress using LPLR and compare with the baselines 1. To evaluate the goodness of embeddings, we build 3-NN, KNN Classifier using K = 3 nearest neighbors under Euclidean distance). We report the performance of the model using standard classification metrics classification accuracy and weight averaged FI score. We utilize a uniform bit budget = B' bits for the quantizers Q, Q' across all cases. Tabs. and present our results under this setup. For each case we benchmark absolute performance using 3-NN classifier on the training set.
8

---

Similarly, we embed text sentences from IMDB and Emotion databases using BeRT (Devlin et al. [15]) into 512 dimensional vectors, and construct 3-NN classifier using Euclidean distance to perform binary and multi-class classification on the respective embeddings, and report classification metrics in Tabs. and We see that LPLR outperforms direct-SVD quant. and naïve quant. lower bit budgets, and has performance parity as we increase Bnq to bits. We find that we match (and even exceed) the unquantized benchmark at single bit precision, which we attribute to the dominating low rank factorization, and its regularizing effect on data under extreme rank constraints. It is important to note that performance parity with direct-SVD quant. is also a successful outcome, since LPLR provides runtime improvements over taking an SVD to compress the data.
Table 4: CIFARIO embeddings generated MobileNet with an unquantized accuracy and Fl score 91%:Results LPLR and LPLR-SVD with B B
bits
Frobenius Norm Error
Accuracy (%)
Weighted FI Score (%)
B
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
1.05
1.08
1.09
7.17
92
92
92
92
92
92
1.08
2.29
92
92
91
92
23
1.1
1.11
1.11
1.15
91
92
91
91
92
91
91
Table 5: CIFARIO0 embeddings generated by MobileNetV3 with unquantized accuracy and F1 score
Re%utssslts on LPLR and LPLR PVD with B = B' bits
Frobenius Norm Error
Accuracy (%)
Weighted Score (%)
B
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
1.04
1.08
1.09
6.75
79
82
82
79
82
82
0
2
1.08
1.1
1.12
2.18
80
80
80
1.7
80
80
80
1.3
1.11
1.12
1.14
1.17
79
78
77
79
78
78
75
Table 6: IMDB embeddings generated by BERT with an unquantized accuracy and Fl score 75% and
74% respectively: Results on LPLR and LPLR-SVD with B = B' = 8 bits
Frobenius Norm Error
Accuracy (%c
Weighted F1 Score (%)
Bon
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
0.313
0.241
0.229
6.63
73
74
75
50
74
74
75
33
2
0.235
0.178
0.161
1.016
74
74
74
50
74
74
74
50
4
0.148
0.122
0.098
0.417
75
74
75
73
74
74
75
73
Table 7: Emotion embeddings generated by BERT with unquantized accuracy and F1 score 13% and bits
10% respectively: Results on LPLR LPLR-SVD with B B
Frobenius Norm Error
Accuracy (%)
Weighted Fl Score (%)
Bag
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
LPLR
LSVD
DSVD
NQ
0.383
0.296
0.286
5.109
29
38
40
40
0.291
0.215
0.202
1.561
42
33
39
40
40
0.187
0.137
0.121
0.367
42
43
43
41
39
40
40
38
4.3.2
Compressing Weight Matrices of a Large Language Model
In this section, we present results on a major application of matrix compression - compressing the weight matrices of deep neural networks. We choose LlaMa by Touvron et al. [66], a popular foundation Large Language Model (LLM) as the network of our choice. LLMs are natural candidate for matrix compression, due to their massive stacked transformer layers, rendering them difficult to deploy on several GPUs, let alone a single GPU. Many methods have emerged to quantize and compress these models in order to make them amenable to single GPU deployment and inference, including naive quantization with outlier exclusion (Dettmers et al. [14]), second order methods (Frantar et al. [19]), low rank parameter reduction (Hu et al. [25]), amongst others.
We apply LPLR to the 2-dimensional weight tensors, i.e., matrices in LlaMa, leaving any other tensor, which does not lend itself to low rank decomposition, unquantized. Figs. 2a and 2b (better
'LPLR-SVD used in the simulations computes the left low-rank factor L Q(U.S) where Sy (00 1/m) instead of simply Uş in order exploit the equalization property of Gaussian embeddings.

---

Naive LPLR
LPLR
Naive SVD
12
Relative Frobeerbbbiiee norm
Relative Frobentus
(a) B = B' = 8 bits, Bnq 4 bits
(b) B = B = Bng 4 bits
Figure 2: Comparison of LPLR and LPLR SVD on LlaMa weights, ordered by the original sequence of layers
Table 8: Average relative Frobenius norm error on LlaMa weight matrices
B = B'
bits, Bag 4 bits
B B' Bug = bits
Metric
LPLR
LPLR-SVD
Naive Quant.
Metric
LPLR
LPLR-SVD
Naive Quant.
Mean
0.672
0.537
0.836
Mean
0.548
0.540
0.836
Std Dev
0.080
0.079
0.470
Std Dev
0.053
0.055
0.470
resolution in App. J) showcase our results on applying LPLR and LPLR-SVD with bit budgets of bits and 4 bits respectively, using relative Frobenius norm error as the metric. While it is clear that LPLR and LPLR-SVD perform significantly better across all layers (on average), there are outliers where naïve quant. is the better choice. We naïve quant., implying that the low rank structure a function the index attention layer in transformer blocks. It is important to note that low Frobenius norm error is not direct indicator of performance for other task specific metrics. It is possible to construct a holistic compression strategy using error profiles similar to Figs. and 4 to adopt per-layer quantization strategy, minimizing both task specific metrics as well as relative Frobenius norm error. We discuss this further in Appendix K.
observe periodic structure in the error profile of
5 Conclusions
In this work, we have considered the problem of obtaining low-precision and low-rank factorization of matrix. Such factorization of matrix into product of tall and wide matrices has several advantages, including compression of the original matrix. We propose fast randomized algorithm to obtain this factorization which requires ((nodd) computations considerably faster than alternative methods. Our algorithm employs a Gaussian sketch to estimate the range space of matrices that are approximately low-rank. By utilizing the properties of subspace approximation and equalization in Gaussian embeddings, we establish an upper bound on the approximation error attained by our algorithm, and show that it can be significantly smaller than its counterparts. Finally, empirically evaluate our method on several vision and text datasets, where we show significant task performance highly compressed bit budgets low as single bit. This provides novel pragmatic approach to work with large datasets and models in real world settings, making them more accessible to researchers and deployment on regular consumer hardware.
Acknowledgments and Disclosure of Funding
This work was supported in part by the Air Force Office of Scientific Research (AFOSR) under Award #002484665; in part by National Science Foundation (NSF) CAREER Award under Grant CCF-2236829, Grant AMS-2134444 and Grant ECCS-2037304 in part by the U.S. Army Research Office Early Career Award under Grant W911NF-211-1-022.. in part by the Stanford Precourt Institute; and in part by the ACCESS AI Chip Center for Emerging Smart Systems through InnoHK, Hong Kong, SAR. The authors would also like to thank the anonymous reviewers whose comments and suggestions helped improve the presentation of this work.
10

---

References
[1] mtcb/cmotion datasets at hugging face.
emotion, (Accessed 05/16/2023). (Cited on page
[2] mteb/imdb datasets at hugging face. doi=true, (Accessed on 05/16/2023). (Cited on page 8)
[3] A. Aghajanyan, L. Zettlemoyer, and S. Gupta. Intrinsic dimensionality explains the effectiveness of language model fine-tuning, 2020. URL https http::///axxii org/ abs//ass....///////// 13255. (Cited on page 1)
[4] F. Alimisis, P. Davies, and D. Alistarh. Communication--eficiene distributed optimization with quantized preconditioners. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learn- ing Research, pages 196-206. PMLR, 18-24 Jul 2021. URL btttp:://proceeee press/vee /ates//v//////// aalaaammisii..mm...........ii.ie siss html. (Cited on page 2)
mlr.
[5] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication--fficiinn SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, volume 30, pages 1709-1720 Curran Associates, Inc., 2017. (Cited on page 3)
[6] N. Alon and V. H. Vu. Anti-hadamard matrices, coin weighing, threshold gates, and inde- composable hypergraphs. Comb. Theory Ser: A, (9(1):133-160, jul 1997. ISSN 0097-3165. doi: 10. 1006/jccaa 1997.2788 2780. URL https://doi. org/10...///////.. wt..////caaa... 199.. (Cited on page 5)
[7] Amazon AWS. Enterprise Search Engine Amazon Kendra AWS, 2023. URL. https:
//aws. amazon cwm/kendmaa (Accessed on 05/16/2023). (Cited on page 8)
[8] M. Ben Noach and Y. Goldberg. Compressing pre-trained language models by matrix decom- position. In Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Lan- guage Processing, pages 884-889, Suzhou, China, Dec. 2020. Association for Computational Linguistics. URL https: httpe///acaaaaahhaaaeoee
org//0200002/ aalal-mminn... 88. (Cited page 1)
[9] N. I. Bernardo, J. Zhu, Y. C. Eldar, and J. Evans. Hardware- non-uniform task-based quantizers. In ICASSP 2023 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5, 2023. doi: 10. N0.1009/CASSP499555..000 2023 2099004 10094884. (Cited on page 3)
[10] W.-N. Chen, P. Kairouz, and A. Ozgur. Breaking the communication-priveee prrivcy--acurrayy trilemma. In Neural Information Processing Systems (NeurIPS) 2020, 2020. (Cited page 3)
[11] Y. Chi, Y. M. Lu, and Y. Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20):5239-526) 2019. doi: 10. 10.1 TS9.2019. (Cited on page 2)
[12] Deng, W. Dong, R. Socher, L.JJ. K. Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255, IEEE, 2009. (Cited on page 8)
[13] M. Derezinski. F. T. Liang, Z. Liao, and M. W. Mahoney. Precise expressions for random projections: Low-rank approximation and randomized Newton. In Ad- vances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2020. URL https: htap::://prooco https::/pproceedingg htwp://cceednnnnn..unu.eue.eeeee www.rip..c/pppppeeeeeeeeeeeeeeee cttccc//pppaoa lappr_fpleesssss/p///rrprarpppee /ptpprrriieee/pppp/////////////e pappr//000/ffile/
449333388:12441133660557882. Paper. pdf. (Cited on page 2)
[14] Dettmers, M. Lewis, Belkada, and L.. Zettlemoyer. L.L. (): 8-bit matrix multiplication for transformers at scale. arXiv preprint arXiv:2208.073339 2022. (Cited on pages 7 and 9)
[15] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 110 2018. (Cited on page 9)

---

[16] P. Drineass and M. W. Mahoney. RandNLA: Randomized numerical linear algebra. Commun.
ACM, 59(6):80- 90, may 2016. ISSN 0001-0782. doi: 10.1145/2842622. URL https:
//doi.org/11 1145/2842600 (Cited on page 2)
[17] P. Drineas, R. Kannan, and M. W. Mahoney. Fast monte carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. SIAM Journal on Computing, 36(1): 158-183, 2006. doi: 10.1137/50097539704443333
URL https://don org/10.1131
$0097539704442896 (Cited on page 2)
[18] C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psy- chometrika, 1:211-218, 1936. doi: http://tbi.org//...00////2222222 brddu..b/dcbK3 (Cited on page 2)
URL https:
[19] E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210.17323, 2022. (Cited on page 9)
[20] H. M. Gach, C. Tanase, and F. Boada. 2D & 3D shepp-logan phantom standards for MRI. In 2008 19th International Conference on Systems Engineering, pages 521-526. IEEE, 2008. (Cited on page 7)
[21] A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer. A survey of quantization methods for efficient neural network inference, 2021. URL wwt.h:ttt////ittii http://aaxii..o/aa////l//a 13630. (Cited on page 2)
[22] R. Gray and T. Stockham. Dithered quantizers. IEEE Transactions on Information Theory, (3)8855-813 -12, 1993. doi: 1.11099/88.256499 (Cited page 3)
[23] N. Halko, P. G. Martinsson, and J. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53(2):217-288, 2011. doi: N0.1133/090771800 URL https: org/oo.g///ooo/.ooooooooooo1 117701111180/9 (Cited on pages and 29)
[24] A. Howard, M. Sandler, G. Chu, L.-C. Chen, B. Chen, M. Tan, W. Wang, Y. Zhu, R. Pang, V. Vasudevan, Q. V. Le, and H. Adam. Searching for mobilenetv3, 2019. URL https: //arxiv. orgg/bs/////////o/oe/ooooeee
02244. (Cited page 8)
[25] E. J. Hu, Shen, Wallis, Z. Allen-Zhu, Li. S. Wang. L. Wang, and W. Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022. URL pages and 9)
(Cited
[26] Y. Idelbayev and M. A. Carreira- Low-rank compression of neural nets: Learning the rank of each layer. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8046-8056, 2020, doi: 10.1099CVVR-2260.00000886
(Cited on page
[27] M. Jaderberg. A. Vedaldi, and A. Zisserman. Speeding up convolutional neural networks with low rank expansions, 2014. URL https: wtrpaaiwwwaaaaaaaaaaeeeeeeooleee hts//bb///444/ 1405. .8666. (Cited on page I)
(28) D. Jin, X. Bing, and Y. Zhang. Unique sparse decomposition of low rank matrices. In Advances Neural Information Prucessing Systems, volume 34, pages 523-535. Curran Associates, Inc., 2021. URL htt.:httts:::/ctttttteee iew.eeeeeeeedeeeeeeeeeeeee..eeee neurips... cc/paper__ppppp...eet. files/ee//ee www.ssipppeeeeee pptp//pepppp////////e/
08192811667/000050000110444 Paper. pdf. (Cited on page 2)
[29] G. K. Karagiannidis and A. S. Lioumpas. An improved approximation for the gaussian Q- function. IEEE Communications Letlers, 11(8):644-666, 2007. doi: 10.1 1090 0704700. (Cited on page 24)
[30] R. Karimi Mahabadi, J. Henderson, and S. Ruder. Compacter: Efficient low-rank hypercomplex adapter layers. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 1022-1035. Curran Associates, Inc., 2021. URL http:::ttt//ttttttt http:tttt///p neurips.. cc/paper. cace/appr_fileese files/ haterr/22......eaaaaattrtr000o00 Paper .df.. (Cited on page
12

---

[31] X. Li and P. Li. Generalization error analysis of quantized compressive learning, Advances in Neural Information Processing Systems, 32, 2019. (Cited on page 45)
[32] X. Li and P. Li. Random projections with asymmetric quantization. Advances in Neural Information Processing Systems, 32, 2019. (Cited on page 45)
[33] X. Li, X. Yin, C. Li, P. Zhang. X. Hu, Zhang, L.. Wang, H. Hu, L. Dong, Wei, et al. Oscar: Object-semantics aligned pre-training for vision-language tasks. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXX 16, pages 121-137. Springer, 2020. (Cited page 8)
[34] S. G. Lingala, Y. Hu, E. DiBella, and M. Jacob. Accelerated dynamic MRI exploiting sparsity and low-rank structure: k-t SLR. IEEE Transactions on Medical Imaging, 1455410421114, 2011. doi: (100///TM..1102200080833
(Cited on page
[35] J. Liu. Llamalndex, 11 2022. URL htttp:////itthbbb http:///wwbb.cco/yrryyy///////a/ page
(Cited
[36] Y. Lyubarskii and R. Vershymin. Uncertainty principles and vector quantization. IEEE Transac- tions on Information Theory, 56(7):3491-33 --501, 2010. (Cited on page 3)
[37] Ma and E. Solomonik. Fast and accurate randomized algorithms for low-rank tensor decompo- sitions. In Advances in Neural Information Processing Systems, volume 34, pages Curran Associates, Inc., 2021. URL https: / //ttppe://prooceedingss neurips. cc/paper mameerffille files/ paper/2021/file///eee htt.a//eeeeeeeeee122222222262600 http://cc..222200000000002262663
Paper. pdf. (Cited on page 2)
[38] M. W. Mahoney. Lecture notes on randomized linear algebra, 2016. URL https:///aaxiv
org/ 1608. 04481. (Cited on page 2)
[39] Y. Mao, Y. Wang, C. Wu, C. Zhang, Y. Wang, Q. Zhang, Y. Yang. Y. Tong, and J. Bai. LadaBERT: Lightweight adaptation of BERT through hybrid model compression. In Proceedingy of the 28th International Conference on Computational Linguisties, pages 3225-3234, Barcelona, Spain (Online). Dec. 2020. International Committee on Computational Linguistics, doi: 10.18653/ cl/2020.colinng m8in URL https:/ haaps////cclathloogyoyoo org/2020 wttp/020..cooonn.o.oo......o.... (Cited on page
287.
[40] K. Mardia, J. Kent, and J. Bibby. Multivariate Analysis. Academic Press, 1979. ISBN 978-0-12-471250- (Cited on page 21)
[41] Marqo margo-ai/marro: Vector search for humans, 2023. URL https://github. com/ marqo-ai ai//arqo. (Accessed on 05/16/2023). (Cited page 8)
[42] P.-G. Martinsson and A. Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29:403-572, 2020. (Cited on page
[43] P.-G. Martinsson, V. Rokhlin, and M. Tygert. A randomized algorithm for the decomposition of matrices. Applied and Computationnal Harmonic Analysis, 30(1):47-68 2011. I. ISSN 1063-5203. doi: wttp///i.ooo..1011............o.
URL https: //ww://www//... wcwencedireetet.c..cmm.......... com/
(Cited on page 2)
[44] Mayekar and H. Tyagi RATQ: A universal fixed-length quantizer for stochastic optimization. IEEE Transactions on Information Theory, 67(5):3130-3154, 2021. doi: 10.1109/TT..201. 3058663, (Cited on page 3)
[45] S. Parisi, A. Rajeswaran, S. Purushwalkam, and A. Gupta. The unsurprising effectiveness of pre-trained vision models for control. In International Conference on Machine Learning, pages 17359-17371. PMLR, 2022. (Cited page 8)
[46] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, Desmaison, Kopf, E. Yang, DeVito, M. Raison, Tejani, S. Chhlamkkuthyy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high- performance deep learning library. Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. URL http: http://paprr.....nipppppp neurips. cttpppprcccppp///cccppp 9015-pytorch- an- imperative-styyle wtwpig---prrorraa-e-eeeeeeeeeeee Learning- Lea. library. pdf. (Cited on page otgprpaeeeeesteleeeeeeperrprrrrr
13

---

[47] A.-H. Phan, K. Sobolev, K. Sozykin, D. Ermilov, J. Gusak, P. Tichavský, V. Glukhov, I. Os- eledets, and A. Cichocki. Stable low-rank tensor decomposition for compression of convolu- tional neural network. In A. Vedaldi, H. Bischof, T. Brox, and J.-M. Frahm, editors, Computer Vision ECCV 2020, pages 522-539, Cham, 2020. Springer International Publishing. (Cited on page 1)
[48] M. Pilanci. Lecture notes: Large scale matrix computation, optimization, and learning (ee 270), 2020. URL https:/ //web. stanford... caannorrdedu/ccllee eeba:cllassaee277/Lectrree pdf. (Cited
page 29)
[49] Pinecone. Vector database for vector search pinecone. (Accessed on 05/16/2023). (Cited on page 8)
io/, 2023.
[50] Y. Plan and R. Vershynin. Dimension reduction by random hyperplane tessellations. Discrete & Computational Geometry, 51(2)438-461, 2014. (Cited on page 4)
[51] Y. Qi, D. S. Sachan, M. Felix, S. Padmanabhan, and G. Neubig. When and why are pre-trained word embeddings useful for neural machine translation? arXiv preprint arXiv: 803336333, 2018. (Cited on page 8)
[52] S. M. Rezaeinia, R. Rahmani, A. Ghodsi, and H. Veisi. Sentiment analysis based on improved pre-trained word embeddings. Expert Systems with Applications, 11:119--47,, 2019. (Cited on page 8)
[53] M. Rudelson and R. Vershynin. Smallest singular value of a random rectangular matrix. Communications Pure and Applied Mathematics, 62, 2008. (Cited on page 5)
[54] M. Safaryan, E. Shulgin, and P. Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for optimal compressor. Information and Inference: A Journal of the IMA, Apr 2021. (Cited on page 3)
[55] M. Safaryan, R. Islamov, X. Qian, and P. Richtárik. FedNL: Making newton-type methods applicable to federated learning. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 18959-19010. PMLR, 2022. URL https: https://proceeedngg mlr. press/v162/ wtt.///aaaaran///// html. (Cited page 2)
[56] R. Saha, M. Pilanci, and A. J. Goldsmith. Minimax optimal quantization of linear models: Information-theoretic limits and efficient algorithms, 2022. URL https://arxiv. org/ abs/ 2202. 11277. (Cited on page 3)
[57] R. Saha, M. Pilanci, and A. J. Goldsmith. Efficient randomized subspace embeddings for distributed optimization under a communication budget. IEEE Journal on Selected Areas in Information Theory, ((2):183-119))) 2022. doi: 00.1109//AATT.2222.39998 (Cited pages
and 4)
[58] R. Saha, M. Pilanci, and A. J. Goldsmith. Low precision representations for high dimensional models. In ICASSP 2023 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5, 2023. doi: AAL1199CAASPP995552203101999999. (Cited on pages 3 and 4)
[59] V. Siskind. Second moments of inverse wishart-matrix elements. Biometrika, 99916 12 1972. ISSN 0006-3444. doi: 10. 00.109//biomet59.3.6000 URL biomet/99. 3. 690. (Cited on page 21)
[60] C. Studer, W. Yin, and R. G. Baraniuk. Signal representations with minimum norm. In 2012 50th Annual Allerton Conference on Communicution, Control, and Computing (Allerton), pages 1270-127 1277, 2012. (Cited on page 3)
[61] A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 3329-3337 JMLR.org, 2017, (Cited pages 3 and 4)
14

---

[62] A. T. Suresh, Z. Sun, J. Ro, and F. Yu. Correlated quantization for distributed mean estimation and optimization. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 20856-20877 PMLR, 17- 23 Jul 2022. URL wwwhhhtt////p/t ptsttp::/proceedingg mlr wtt......s/..//////// hwwee////sueese2aaaa html. (Cited on pages and 4)
[63] S. Swaminathan, D. Garg, R. Kannan, and F. Andres. Sparse low rank factorization for deep neural network compression. Neurocomputting 398:185- 2020. ISSN 0925-2312. doi: URL https: / /wwp.scieeceeiieecttttt com/ (Cited on page 1)
sci ccc.ac////ttiicee///////22222200
[64] M. Tahaei, E. Charlaix, V. Nia, A. Ghodsi, and M. Rezagholizadeh. KroneckerBERT: Significant compression of pre-trained language models through kronecker decomposition and knowledge distillation. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2116-2127. Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. 18653/v1/ 1022.naacl-man main. 154. URL https: http::/:o///lllahoooogogoo. org/2022. nwacl mann- 154. (Cited page 1)
[65] C. Tai, T. Xiao, Y. Zhang, X. Wang. and W. E. Convolutional neural networks with low-rank regularization, 2016. URL https: //axivv.//rii/a//aa http//aaaivi.raaaaaa//a httg/abs/1550 wttp:/5511.00000 (Cited on page 1)
[66] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro. F. Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023. (Cited on page 9)
[67] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher. Practical sketching algorithms for low-rank matrix approximation. SIAM Journal on Matrix Analysis and Applications, 38(4):1454-1485, 2017. doi: 10.1137/17M111 URL https: http://///oooo/....//// 1137/ 171111199. (Cited on page 2)
[68] A. Tropp, A. Yurtsever, M. Udell, and V. Cevher. Streaming low-rank matrix approximation with an application to scientific simulation. SIAM Journal on Scientific Computing, 4 A24: A2463, 2019. doi: 10.1137118M1201068. URL / org/10. 1137 11111111111/188100066. (Cited on page 45)
[69] M. Udell and A. Townsend. Why big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 1(1):144-160, 2019. doi: 18.1480 URL https://doi. otg/10.g//oo.... 1ttg/10..1377/8811184833 (Cited on page 1)
[70] M. Valipour, M. Rezagholizadeh, I. Kobyzev, and A. Ghodsi. DyLoRa: Parameter Efficient Tuning of Pre-trained Models using Dynamic Search-Free Low-Rank Adaptation, 2023. URL https:://arati
htrrg/bbs/22100 07558. (Cited on page
[71] S. Vargaftik, R. Ben-Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzenmacher. DRIVE: bit distributed mean estimation. In Advances in Neural Information Processing Systems, 2021. URL /tttps:///pppt http::///pe/e/eeeeee net/ www./eerrrrrrr. form?iddmid KXRTmcv3dQ8. (Cited on page 3)
[72] S. Vargaftik, R. B. Basat, A. Portnoy, G. Mendelson, Y. B. Itzhak, and M. Mitzenmacher. Eden: Communication-efficice. and robust distributed mean estimation for federated learning. In International Conference on Machine Learning, pages 21984-22014, PMLR, 2022. (Cited on page 3)
[73] R. Vershynin. Introduction the non-asymptotic analysis of random matrices, 2011. URL attps://arxiv. org/ absp//11...a//...e..aea1aa1..a.t (Cited on pages 21 and 22)
[74] R. Vershynin. High- Dimenssoonl Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 10.1017/9781 108231596 (Cited on page 22)
[75] M. J. Wainwright. Basic tail and concentration bounds, page 21-57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 1017/ 978 1781108627771.00 1.000. (Cited page 21)
15

---

[76] R. Wang, D. Tang, N. Duan, Z. Wei, X. Huang, J. Ji. G. Cao. D. Jiang, and M. Zhou. K- Adapter: Infusing Knowledge into Pre-Trained Models with Adapters. In Findings of the Association for Computational Linguisties: ACI/IJCNLP 2021, Online Event, August 1-6, 2021, volume ACI/IJCNLP 2021 of Findings of ACL, pages 1405-1418. Association for Computational Linguistics, 2021. doi: 10.18653/v1 1/221 fiiniings-acl. 121. URL. https: //doi.org// htwpg//.....653/1111 116538/1//022// www.iiiiniiinngdeeeee 121. (Cited on page 1)
[77] Z. Wang. Wohlwend, and T. Lei. Structured pruning of large language models. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, 2020. doi: 1118633//122220.coomo eannp-main.n..m. 496.
URL wtw.h:tttpsooloo org/ 10. 18853//2V1/2222022 emnlp-main main. 496. (Cited page 1)
[78] G. I. Winata, A. Madotto, J. Shin, E. J. Barezi, and Fung. On the effectiveness of low-rank matrix factorization for LSTM model compression, 2019, URL https://arxiv.. org abs/ 1908. 09982. (Cited on page 1)
[79] R. Witten and E. Candès. Randomized algorithms for low-rank matrix factorizations: Sharp performance bounds. Algorithmica, 72(1):264-25) may 2015. ISSN 0178-4617. doi: 10. 0007/s004330014-980
URL htt.ttt/p/:/a... http:////......//.....///////o 1ttp://0.1007/00453----1 9891-7. (Cited
page 2)
[80] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, et al. Huggingface's 's transformers: State-of-the-art natural language processing. arXiv preprint arXiv:1910.03777, 2019. (Cited page 7)
[81] Z. Yao, R. Yazdani Aminabadi, M. Zhang, X. Wu, C. Li, and Y. He. ZeroQuant: Efficient and affordable post-training quantization for large-scale transformers. Advances in Neural Information Processing Systems, 15:27168-27188 2022. (Cited on page 7)
[82] T. Ye and S. Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Prucessing Systems, volume 34, pages 1429-1439, Curran Associates, Inc., 2021. URL https: http::////ppooeeeinnneeeeee neurips. cc/paper ffles/pappel pdf. (Cited on page 2)
[83] S. Young, Z. Wang, D. Taubman, and B. Girod. Transform quantization for CNN compression. IEEE Transactions Pattern Analysis and Machine Intelligence, pages 1-1, 2021. doi: 10. 10.1 1011000mmm.22211..3 3.304439. URL https: / org/ 11092////tt 20... 3084839. (Cited on page 3)
[84] X. Yu, T. Liu, X. Wang, and D. Tao. On compressing deep models by low rank and sparse decomposition. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 67-76, 2017. doi: 10.11009/VP..2217..15. (Cited on page 1)
[85] H. Zhang, Bi, and Lavaei. General low-rank matrix optimization: Geometric analysis and sharper bounds. In Advances in Neural Information Processing Systems, volume 34, pages 27369-27380. Curran Associates, Inc., 2021. URL https: httpps://proceeednngg/ neurips cc/ paper_ffl wwl.ffllllllereeee http://///.../sooc////..////et// (Cited on page 2)
Paper .dff
[86] Y. Zhang, Z. Jiang, and L. S. Davis. Learning structured low-rank representations for image clas- sification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 676-683, 2013. (Cited on page 7)
[87] X. Zhou, C. Yang, H. Zhao, and W. Yu. Low-rank modeling and its applications in image analysis. ACM Computing Surveys (CSUR), 47(2):1-33, 2014. (Cited on page 7)
16

---

Contents
Introduction
1.1
Related Works
2
Proposed Algorithm
2.1
Uniformly dithered quantizer
2.2
Proposed algorithm: LPLR
3
Approximation Error Analysis
3.1
Analysis outline
3.2
Comparison with baselines
Numerical Simulations
4.1
Overview
4.2
Image Compression
4.3
Embeddings extracted from pre-trained models
4.3.1
Embedding Classification
4.3.2
Compressing Weight Matrices of Large Language Model
5
Conclusions
10
Notations
19
Preliminaries
20
B.1 Linear algebra inequalities
20
B.2
Probability and random matrix theory
21
B.2.1
Tail bound for Gaussian distribution
................................
B.2.2
Inverse Wishart distribution
B.2.3
Random Gaussian matrices
21
B.2.4
Subgaussian random variables
22
C Quantization error of uniformly dithered sealar quantizer
22
Gaussian embeddings: Application of equalization to vector quantizers
23
Dynamic range quantizers
25
E.1 Quantization for the first low-rank factor
25
E.2 Quantization for the second low-rank factor
25
F Sketched least squares with quantized response
28
LPLR algorithm:
Approximation error analysis
30
G.1 LPLR approximation error: Proof of Thm. 3.2
33
17

---

G.2 Informal version of Thm. G.2
34
H Direct-SVD Quantization: Approximation error analysis
35
I LPLR-SVD algorithm: Approximation error analysis
37
L.1 Informal version of Thmm. 1.1
41
J Additional numerical simulations
J.1 Image Compression
41
J.2 Wall-clock time for compressing image embeddings
J.3 High-resolution figures for Llama weight compression
K Limitations and further discussions
44
18

---

A Notations
We first gather some common notations in linear algebra and probability theory that have been used throughout the paper. Boldface upper and lowercase letters, A and a denote matrices and vectors respectively. La denotes the d x d identity matrix. The subseript may be dropped if the dimension clear from the context. For any matrix A, its 7th row and jth column are denoted by a and a respectively. The singular values of A are denoted by muxx m 01 Z 02 ... 0, min (A). where r = rank(A) Similarly, the eigenvalues are denoted as A1 (AA), (A)..... (A). The max- norm of A is defined ||A]|max max; jl Atjl. the spectral norm of A is defined |
1/2
| ||Ax|| max (A), and the Frobenius norm is ||A|| (E A
Tr [AT
1/2 For any vector ||x|| (x?) 1/2 denotes the fz-norm, and ||x|| max; |zy]
(kEIr) oR
denotes the -norm. We use the notations and & for the positive semi-definite (PSD) cone ordering (or the Loewner ordering) of symmetric matrices, i.e., for any symmetric matrices and Y, X > Y + X Y is PSD. X denotes the Moore-Penrose pscudo-inverse of a matrix X. log(-) denotes the natural logarithm, i.e., base e. log2()), i.e., with base 2 is specified explicitly. A normal distribution with mean μ and variance o² is denoted as NO, a²), while a multivariate normal distribution in Rd is denoted as (1,, E). E[|] denotes expectation of a random variable. The probability measure
which the expectation is taken is described in text. We also use big-'oh' notation O()) that hides constants for asymptotic expressions, while Ö(-) also hides terms that depends logarithmically on dimension.
We now list some notations that are either less commonly known or used specifically in this paper, along with some remarks such as their occurrence in the paper. Several of these notations have also been introduced in-context, but they are additionally collected here for easy reference.
Table 9: Notations used in this paper
Notation
Description
Remarks
A, L,
Input matrix, left and right L.PLR factors
LR is an approximation of A. Entries L and R are represented in low-precision formats
n. &
Dimensions of input matrix
Band
Target rank
Often, k < min d). but not necessarily.
A UEV
Full SVD of the matrix A e Roxd Best rank-k approximation of
U Raxn E Baxd and V Rdddd
A U V
U E Raxk and V mR** consists of top- k left and right right singular vectors respectively. E R consists of top-k singular values. = + p. where is the target rank, and p is the oversampling factor. In this work, S.y N (0, 1.
m
Sketch size
S E dm
Sketching matrix
Q. Q'
Quantizers for the first and second low-rank factors with bit-hudgets B and B', and dynamic ranges RQ and Roy respectively.
x(A)
Condition number input matrix A Condition number of best rank-k ap- proximation A
<(A) = σ1, Dr K( = 01/0x
R(Ax)
A quantity that depends on the spec- trum of A
K min <(A), (1-001)0s1/aa))) de-
k(Ag)
fined in Thm. G.2
Aspect ratio of the sketch Target rank and sketch-size depen- dent quantity
defined Thm. G.2. I-
5
8
w(
Wishart distribution with covariance matrix y and degree of freedom
Refer $B.2.
19

---

B Preliminaries
B.1 Linear algebra inequalities
We state (with proofs) some standard inequalities from linear algebra that will be useful in proving our main results.
Lemma B.1. (Frobenius norm of matrix products) For any matrices and B, we have
| |r I || B
Proof. Note that:
ABB| - Σ (AAB)) S Σ EIAB,
S ||
B DBBB
| BI
(5)
Here, (i) follows from the definition of spectral norm of a matrix, and this completes the proof.
Lemma B.2. (Loewner ordering for matrix products) For any matrix A and B, we have
min (A) B B B
AB AT
o max (A) B B.B. B.
Proof. For any vector x * O, we have,
B A ABx ||Axx] 1 min (A) x (omin (T)
(6)
The other direction holds similarly. This completes the proof.
Lemma B.3. (Max-norm spectral-norm inequality) For any matrix A Raxd ||| max
|| l12-
Proof. Let e; E IR" and öj E Rd denote the 7th and jth canonical basis vectors in IR" and Rdd respectively. Then, using Cauchy-Schwarz inequality, have,
||A]] = max e Aē, < max | ||ē max | || S sup
||A|| = ||ll2 (7)
||x|==
completing the proof.
Lemma B.4. (Submultiplicaiivity of spectral norm) For any two matrices A and B, we have ||A||2 S || [Bl]p.
Moreover, an analogous "reverse-submulii sueeereesuumuliipiicativyyy result for the minimum singular value of matrix product also holds true, i.e.,
Ouin (AB) Omin (A)o (B).
Proof. Using Lemma B.2, we have,
(i) < || Amax (B (B = |A I
|ABI Amax (B AB
(8)
where (i) follows from Lemma B.2, completing the proof. The lower bound on omin (AB) also follows similar argument.
Lemma B.5. (Lower bound on minimum singular value of matrix sums) For any matrices A and B, we have
Umin +B) amin (A) |B
Proof. We have the following chain of inequalities,
(
J (A+ B)
inf ||||== [[AA + B)
x||
2
inf (||xx| [xx])
||x|=1
inf
A
sup
|Bx| o (A)
-|[Bl22
||||==
|x||=
where (i) is the reverse triangle inequality. This completes the proof.
Lemma B.6. (Rotation invariance of singular values) For given matrix A, oa(AA (UUA for all i I,..., (A) for any unitary matrix U.
20

---

Proof. For i I,..., rank(A A), since U U = I, we have
o. (UA) = (ATUTAA) = -ATAA)=0;((
/ =
completing the proof.
Lemma B.7. (Rotation invariance of Frobenius norm) For given matrix A. ||UA|| for any unitary matrix U.
|Al|
Proof. We have,
|UA|| = Tr TT(ATU =T A [
||A|
B.2
Probability and random matrix theory
We restate some results from probability and random matrix theory which will be useful in deriving the main result of our paper.
B.2.1 Tail bound for Gaussian distribution
Gaussian distributions have strong concentration properties which we exploit in deriving the results of this paper. The following tail bound on a Gaussian random variable can be found in standard texts such as Wainwright [75, $2.1.2), and is restated here.
Lemma B.S. (Chernoff bound for centered Gaussian) For N (0, we have,
Pr ([X] 2 1) 2e 20
(10)
The proof of this follows from direct application of Chernoff bound.
B.2.2 Inverse Wishart distribution
Consider a matrix S E Rd each row of which is drawn independently from the distribution N (0, )) where E mm Then, the probability distribution of the m x m random matrix S S is called the Wishart distribution with d degrees of freedom, denoted as W ( d). Moreover, the distribution of the matrix (ST called the inverse Wishart distribution and is denoted by W- ( -1 d). These distributions have been studied extensively and further details can be found in Mardia et al. [40] or Siskind [59].
Lemma B.9. (Expected trace of inverse Wishart matrix) Suppose S Rdxm matrix, each entry of which is drawn independently from N (0, J.). Then, the matrix S E mmxm follows the Wishart distribution W Im, d) that satisfies,
E (ST
m
(11)
d
Proof. From Mardia et al. [40, eq. 3.8.3,, if ~ W- (v-1,d)
d). then,
L -1
E
SS T S)
(12)
Here, L 1 Im. implying Tr [v]'] = m which completes the proof.
m
B.2.3 Random Gaussian matrices
The spectral norm of random matrices with Gaussian entries have interesting concentration properties. In this section, we present lemma from Vershynin [73] that formally states this result.
Lemma B.10. Let the entries of matrix S E IRd be distributed according to Sig ~ N (0. 1
Then for every 2 0, with probability at least 1 2c mn?
we have,
d
t t o minn (S) < o Tmax (S) +1 +1+t
(13)
m
21

---

The above lemma is straightforward modification of the result in Vershynin [73, Corr. 5.35], which states the concentration result when the entries are distributed according N (0, 1). Note that given with entries Sij ~ .V (0. ))) as above, the matrix = vm S will have entries Sig ~ N (0, 1). Furthermore, of (S) / m a; (S) and the conclusion is immediate.
B.2.4 Subgaussian random variables
Subgaussian random variables refer to a class distributions that are dominated by the distribution of centered Gaussian random variable. There several equivalent ways characterize subgaussian random variables which can be found in several textbooks (see for example, Vershynin [74, Prop.
2.5.2]). We will focus on the following definition. More formally, the distribution of random variable X is subgaussian the moment generating function X² is bounded at some point, i.e.,
k 2 2.
E
(14)
Definition B.11. (Subgaussian norm) The subgaussian norm of subgaussian random variable X, denoted by ||X is defined to be the smallest K in (14). In other words,
X 1/2
inf
t z 0
E
x²/// /r/ <2)
(15)
It can be shown that any bounded random variable X is subgaussian, and satisfies,
|
|
(16)
log
We next present result that upper bounds the spectral norm of a matrix with subgaussian entries. Lemma B.12. (Vershynin [74, Thm 4.4.5l) Let X be d x random matrix whose entries Xij are independent, zero-mean, subgaussian random variables. Then, for any 0, we have,
| S CK (vd+ vm +1)
with probability exceeding 2e Here, K maxi, [|A and C is absolute constant.
C Quantization error of uniformly dithered scalar quantizer
For a scalar æ E [-R, +RJ, let us denote the quantization error of uniformly dithered scalar quantizer with bit-budget of B bits The following result further characterizes its mean and variance of this error.
QR.
Clearly, the quantization error is bounded as A.
Lemma C.1. The uniformly dithered scalar quantizer as described in (1) satisfies.
R²
[E] and Var (E))
11
where the B(.) is over the randomness due dithering in the quantizer operation.
Proof. Suppose [qu, 11++1 and qu++1
4/k + A, where A
2R Then, 2n-I
E QR,B(I) g++1
E 9k + qu 1 I
9k
[Tk
A) (x 9x) + (A + 9k)
A
A
To evaluate the variance,
Var (Q), x²² (9x+1 2)2 20 9k)
+ (gt - x)² (1 1 9k
A
A
< (gx+1 x)) (x - 9k)
< sup (gk+1 2) (xr qkk)
9k + 9k+1
4l + 9k-1
A
R²
gk+1
4
4
(2 1)
This completes the proof.
22

---

D Gaussian embeddings: Application of equalization to vector quantizers
In this section, we show a result on how Gaussian embeddings help in reducing the 22-quantzzation eπror of a uniformly dithered vector quantizer. We consider a clipped version of the uniform scalar quantizer with bit-budget B described in $2.1 and App. C. In order to quantize vector x R" with ||x|| < R using uniform scalar quantizer (as described above), the quantization operation is applied to each coordinate of the vector independently, i.e.,
QR = [Q((z))......))
QR(22)).
(17)
Here, the subseript B is dropped because the bit-budget evident from the context. Furthermore, since ||x||2 2 R implies æ; E [-R, +R] for every i [d]. the quantizer QR does not saturate. From
Lemma C.I, the expected quantization error is given by,
R2d (2B - 1)
[R( x11
Σ E [(R(()) - cc(d]
(18)
Quantizing Gaussian embeddings: Suppose instead of quantizing x E Rd directly, we quantize = Sx E R", where S E Rmxd with Siz ~N (0, )) Note that for every [m], we have Uj N (0. = Ix1(). Since uj can be anything in (-20, +o0), there is finite probability that the uniform scalar quantizer might get saturated. For this reason, for any scalar (-00, +oo), define the clipped uniformly dithered quantizer with clipping parameter t as follows:
Qr(() if ju| st
Q(u) if u u<
u u>1
(19)
The dynamic range of the quantizer is parameterized by f, which is to be chosen appropriately. Note that it is just for this section for the purposes of illustration, that we choose the clipped variant of the quantizer. In LPLR, we choose the dynamic range to be high enough so in practice it remains unsaturated with very high probability. The following proposition upper bounds the quantization error of quantizing Gaussian embeddings.
Proposition D.I. For given vector E Rdd with ||x|| R, the clipped uniformly dithered quantizer described in (19) with
R. vm
satisfies
R²
R²
E [[((s)== Sx
(2B
1)
Vie'
where the expectation is over the randomness in the construction of S and the quantization dither.
Proof. Since [ui]ie(m] independently and identically distributed, let denote the distribution as f(u) = ov2n e 202 where o = ||x| The expected quantization error for the clipped quantizer is then given by,
Es.q. [(((u) ((((u)=u))
/ /u|ge
Eq. [(((u) w]1] f(u)du +2 (t (t- f(u)du
(20)
u>1
Here, the expectation is over the stochasticity of the quantization dither, as well as the random matrix S. The factor of 2 in the second term appears due to symmetry of clipping and that of Gaussian distribution. Using (18), the first term on the R.H.S. can be upper bounded as,
LT EQ. [[Q(w) w (u)ddu <
t
[(u)du S
(21)
(2B - 1)² Julse
(2B - 1)²
To analyze the second term, note that,
2 J. (t- - (t-u)²e 2 du
1 (0² + +2) (1 (I-orf ( (111))
at
v 4 Vt, (22)
2
v 2
where ez) denotes the error function defined as,
crf(2) = VT e -x2 dx
(23)
23

---

Simple calculation would show, (t,
Oo
0v22/ ) of
2
t
t2
12
t
1 orf
20
c
20
20
2t
22T
0²
2m
r2
/2v2n
2T
=0
- erf erf
ov22
20. 0.
(24)
Since (t.or.o)
2 0. (l, is non-decreasing function of a. Since o²
|
R
we have the
de upper bound,
2 2 (1 u)² [u)dda
R² (1- erf
(2)
tym
RIv2
m 2n
Nut
m
RV2
mm
R
8
erfe
I ftmm
Rtv2
m2 2017
(25)
Rv2
mm
where erfe(z) -1- -cr((z) is the complementary error function.
Quantization error of a scalar Gaussian sketch: Since x E Rd with ||x||] S R. lets ~ NNO, m La).
We first consider the quantization of x 8. and upper bound the error E (Q(x 8) -xxxx x 8) } Clearly,
2
x ~ NO, n²
Consequently, using (21) and (25), for any 2 0, we have.
E [Q(x 8) - xx xT5)
<
ta
R²
+
erfe
t tym
Rtv2 mm
e 2n
mr2
(2B
RV2
t
+
R²
+ 6
R
ma3 20
Rt
m2? 2127
(2B 1)
W
Vam
t
R3v2
mur
e
2R
(26)
(2B 1)²
1/3/21
3 Here, (1) follows from the upper bound erfc(=) S V=z from Karagiannidis and Lioumpas [29].
Quantization error of vector Gaussian sketch: We now consider for any > 0, the expected
quantization сттоr for x E R2 with ||x||2 < R and S E Ruxd with Sty ~ (0, 1 Each row of S now independently plays the role of in (26). Using (26), the vector quantization error is simply m times the scalar quantization error, and is now given by,
ml2
R3
IE [[Q(Sx) - Sx11 <
+
(27)
(2B 1)
L
Tm
Choice of dynamic range l: Setting /. =
R vm in (27) yields,
R²
R2
[[([xx) -Sx112 <
(28)
(2B 1)²
Viee
This completes the proof.
Note that since E[S S) is an identity matrix, an estimate & of x can be recovered from Q(Sx) as
ST Q(Sx). We can use the O(1) bound on ||Q(Sx) Sx| to get a bound on (S(x)) - x|| as
follows:
TSQ(SS)
x < [[Q(Sx) Sx|| + || Q(Sx) [[x() |||| ||Sx|| ||
< [[Q(Sx) 2 Q(Sx) ||X|2
< [((x)) - Sx||2 + (o max (S) 1)
(29)
From properties of random Gaussian matrices, we know that 2 (S) S m with high probability. Hence, the error ||S Q(Sx) - x11 only depends on the aspect ratio d/m. and not the dimension directly. Although the reconstruction error ||S Q(Sx) - æ=|2 scales as d/m, it does not necessarily increase with d if we choose the sketch size m to be proportional to d, i.c.. O()).
24

---

Despite this, Gaussian embeddings are not used practically for vector quantization because S is dense matrix and computing Sx entails complexity of O(2). The entries of themselves are floating point numbers that have to be stored in full precision, hence this defeats the whole purpose of quantizing x using fewer bits. However, this not an issue for matrix compression because in LPLR, we do not explicitly compute the S Q(SA) anywhere. In other words, the effects of S in the first low-rank factor is nullified by the second low-rank factor. Unlike vector quantization, the corresponding sketch size for LPLR only needs to be the same order as the inherent rank k, which can be much smaller than min(n, d}. i.e., the dimensions the matrix being compressed.
E Dynamic range of quantizers
We now derive high probability upper bounds on the maximum magnitude of the input to uniform quantizers Q and Q'. Choosing these upper bounds to be the dynamic range the uniform scalar quantizers will ensure that the quantizer remains unsaturated with a high probability, which is our desired regime of operation.
E.1 Quantization for the first low-rank factor
We first look the choice of dynamic range for the quantizer Q, which is used to obtain the first low-rank factor. The input to the quantizer is AS E R=x" where A E Raxd and S E Rdxm and the entries of S i.i.d. as S,y ~ (0, +). Lemma E. below gives a high probability upper bound on the max norm of AS. This probability is computed over the randomness in the construction of S.
Lemma E.1. (Max norm of AS) Given matrix A Ranxd with bounded row norms, i.e., and S E ddxm with entries distributed as Sig iid. N (0, ih), with probability exceeding the max norm of AS satisfies,
||a()] R.
SAR*
2 2 16
AS
R
(30)
max
m
Proof. Since (AS).) = =sJ ()), where ( E Rd is the th row of A and E Rd is the jth column
of S, have (AS).. N (o. | Using Lemma B.8 and application of union bound gives,
me? *||a(0
Pr (AS) 22)
2e
ll S 2e
m22 .
(31)
subsequent application of union bound over all the entries of AS yields,
Pr AS
2nme
2R
(32)
2oo
Setting & RV
in the above completes the proof.
m
E.2
Quantization for the second low-rank factor
We now obtain a gigh--robability upper bound on the max norm of Q(AS)+ A, which is the input to the second quantizer Q'. Let us define Q to be the event that the quantizer Q does not saturate. From Lemma E. Q occurs with a sufficiently high probability. An appropriate choice of dynamic range for Q' will ensure that conditioned on the event that @ occurs, the quantizer Q' also does not saturate with high probability. The following lemma states this formally.
Lemma F.2. (Max norm of Q (AS)² A) Let our imput matrix A E RRnd have non-zero singular where = rank(AA), and bounded row norms ||a[0] < R. Let x(A) = 01 0 and R6 r((AR)= = 01/o o
values 01, kh: Oktls...,,0000
01/0k respectively be the condition numbers of A and the best rank-k k
approximation of A, and for some small e 0, let denote
2 log 32nll2
R(AA)
K min k(A),
(33)
m
Th+1
V--I-1
25

---

where 7 d/m m is the aspect ratio of the sketching matrix S E Rdxm with Siz
sid N (0. )
2ngg 16R2n
Furthermore, suppose the dynamic range of the quantizer Q is set to RV
as dictated
by Lemma E.I, and suppose for some absolute constant C, the bit bit-budget B satisfies,
4CR
V v7+1+1/v2
16R
B 2 logz
2 log
+1
max (0r, Jut1 (Vi-1-t) log2
-1-1-t
(34)
Then, we have,
2x
[[Q(AS) A| max
with probability exceeding 1
(35)
-1-1-t
4nR²
Proof. We have the following chain of incqualities:
((A))) A
(AA)))
(1) Al. - Q (A))
(A).
(36)
max
where (i) and (ii) follow from Lemmas B.3 and B.4 respectively. We now need to upper bound
QQ (AA) which done as follows:
(i) (1) (amin (Q (Q(AS))) (amin (AS + E)) S (Amin (AS) - [|112)) (37)
Q (AS)
Here, E Q(AS) -AS E R is the quantization error matrix from Q, (1) follows because the singular values of Q (AS) are inverses of the singular values of Q (AS) (assuming Q (AS) is invertible), and (ii) follows from Lemma B.5.
Lower bounding min (AS): It now suffices to derive the a lower bound on Fmin (AS), which we do next. We derive two different lower bounds, either of which could be tighter depending the singular value profile of A. The final lower bound will be the maximum of both.
For the first lower bound, let A UEV be the full singular value decomposition of A, where U E _axxn E E Ruxd and V E Raxd Then, denoting S SS we have,
O Juin (AS)= = Omi (A&S + (A S)) 2 min (A,S) - (( A1)
min (A,S) o++1 ||
(38)
where A is the best ra approximation of A. Here, once again, (i) follows from Lemma B.5 and (ii) follows from Lemma B.4. In order to further lower bound min ( S), let us denote the SVD of A as A₁ = UE& VT. Since the best rank-k approximation is obtained by retaining the top-k singular values A and zeroing out the rest, we have E Raxx, Σn E guxk and VR E gaxk Let us further denote S V S. Then we have
mmin (A+S) = miin (UE VTS) = Omin (UΣLS)
!1)
Umin Eg.
(i) 2 T Tko (2.min(S) (S),
(39)
where (i) follows from Lemma B.6, and (ii) follows from Lemma B.4. Note that the (i, entry of is S.j = v. sy. where v, is the th column of Vv. Clearly, Siy is a Gaussian random variable with mean, E [ Ee Ve E[S,,] = O, and variance, Var (3,g Ee Va (Stz) = 1 Ee Vi I where the last equality follows from the fact that the columns of Va are orthonormal. In other m
words, the entries of S ædxm are distributed according to 3.y N (o, H.) Using (39), (38) can be further lower bounded as
Tmin (AS) 2 O.. ($) x ||S||| T (S) - J S|l|
(40)
where (i) once again follows from the rotation invariance of spectrum, i.c., Lemma B.6.
On the other hand, let r rank (A) and o, by the smallest non-zero singular value of A. Then, A- UEVT_ UΣ, V and using the same arguments as in (39), we also have
uiin (AS) = Gmin TUE.V.S. Omin E V.V.S) S) 2 muin (S)
(41)
26

---

Combining (40) and (41), we get min (AS) (a, (S) 0k00minSS 0e+1 S
(42)
All we are left with now is to utilize the concentration bounds on the singular values of S. As
consequence of Lemma B. and recalling d/m, with probability exceeding - 2e" ma?
VT - - f S min (S) - || - v7 +
(43)
Substituting this (42), with probability exceeding 2e _
Miin (AS) 2 max {a, (VT - - , (V7 - - 1) - xl [v7+1+1]}
(44)
Upper bounding E 2. Finally, conditioned on the event Q. the entries of E are bounded. Choosing
the dynamic range of Q dictated by the upper bound on |AS| I in Lemma E.1, we have, with probability exceeding SMR
2R
2 log
Egy S
for all i E [r|] and j E [m].
(45)
(2 1)
m
Since Egy is a bounded w.h.p., it is also subgaussian w.h.p. (ref. eq. (16)) with subgaussian norm given by,
2R log (log 2) (2B 1)
2 2 116
Eis 0/ - From Lemma B.12 we get for some absolute constant C,
(46)
2CR Vd + vm+
log 1GR2nAm
E 2 S
w.p. exceeding 1
2e-
(2B 1) log
8nR2
2CR (V7 + 1 8)
16R2n2m
or, E
22log
w.p. exceeding 1
2e mi?
(2B 1) log2
8nR²
(47)
Completing the proof: Finally, combining (36), (37), (44) and (47), we get with probability exceed-
ing
SnR 2e _n²
2e 2mmm" mF²
[[QA))) A Alma So [maxfor (V7 1- ,) (V7- 1 1) Oh+ (V7 1 t)
(48)
2CR (V7+ +1)
16R2n2m
2log
(2B - log
[v++1+4 (x++1+t)
01
max or, Or, Ok - ok+1
V7
f
V7 -
2CR
V (
16R 2
2
(2B - 1) log
1 1
01 V7 -t
2CR
V
n
(2B 1) log
-1
22lg
(49)
where denote μ = max
Ør. Tk Tk+1 (
}.
Let us choose our bit-budget B of quantizer
Q to be such that it satisfies
|Bll S $4 i.e.,
4CR
V wイ-1-1)
1662n22
B log2
2
+11
(50)
log?
E
Then,
201
[[Q(AS)AA
mmx 5 ([7
(51)
27

---

Setting
2 log
33nRR2
log 32nR2
and,
(52)
m
m
v2
follows that with probability exceeding
AnTEZ
2
x(AA)
[[((A)) A
min k(A);
(53)
V7 - This completes the proof.
max
1x
v1+1+
V--1-1
F
Sketched least squares with quantized response
Since the approximation error guarantees of sketched least squares with quantized response might be problem of independent interest, this is standalone section, and the notations used in this section are independent of the rest of the paper.
Consider the generalized least squares problem
X arg min (x Y
(54)
xERxxU
where E Rex and Y E Rex The sketched variant of (54) with quantized response is given by,
X arg min || Q(GY)
(55)
Xeßexq
where E mm is Gaussian sketch matrix with entries are distributed as Gij ~ ~N (0, ) and Q = QRB is the uniformly dithered quantizer as described in (I). We assume that the dynamic range R 2 |Y| so that Q is unsaturated. The solution (55) can obtained in closed form as,
X ( Q(YY)
(56)
The following lemma provides a characterization of the accuracy of X with respect the original problem (54).
Lemma F.1. Let G & Rmxt be a random Gaussian matrix with entries distributed as Gij ~ N' (0, ). and Q = QR, be uniformly dithered quantizer with dynamic range R and bis-budget B. Furthermore, suppose $ E RExP and Y E Rxx be given, and let denote
X = arg min ΦX -YI and arg min X
|G QQGYY)
XERexq
Let = Q(YY) GY be the quantization error matrix. Then, if
|GY
Imaas we have
Ox
Y <
< xx
Y
m
4x -
9 o
m
o min (e- 1)²
m
where r = rank 3 and Fmax and Gmin are the maximum and minimum singular values of + respectively.
Proof.
The solution of the generalized least squares problem (54) can be written as:
X X ......... xqI. where, x = arg min (x - yyll?
(57)
xER*
where y; E R2 denote the th column of Y. Consequently, we will first analyze the standard least squares problem
arg min ④xx - yy
(58)
xEB
and generalize the results by concatenating x to obtain X The sketched variant of (58) with quantized response is given by.
X = min G - Q(
(59)
xEB
The solution of (59) is available in closed form as ス (Gb)*Q(Gy)) Let us denote the quantization error as 2 Q(Gy) Gy TM We then have,
E -
y E ( y E (Gy + E) - -yl12
28

---

E ( Gy yll + + el (60)
Here, (i) follows as the cross term disappears because,
[ (G)) Gy y) 4 (G = Eg ( Gy y) T ( = 0, (61)
where the last equality follows from (2), since Eo(c] = 0 when Q is uniformly dithered quantizer.
Let us denote the quantization error matrix by E Q(GY) GY Rm*x, Generalizing (60) to the generalized least squares problem by treating each column y; separately and adding, we have,
E
Y
E. (GG
GY Y - + + (G
m m-
4
YI + + (
(62)
Here, (i) follows from known results on the approximation error sketched generalized least squares Halko et al. [23], Pilanci [48], and r is the rank of A.
Upper bounding E|
G
1 The remainder of the proof concerns upper bounding the final for any matrix X, using the cyclic property of trace,
term (62). Since
X
= Tr
[XX
X
E
G
Tr E ((G
((G
F
E ((G
+ TJ ( 'E''
EG Tr (()
T 4 (
EE '
(63)
Since 2
|GY maxe from (2), the (i.j) - of the quantization error matrix E satisfies,
A
R
E [E,y] = 0, and Var(En)) s
(64)
(2B 1)2
So,
E Esu q Var Var(Eik)
2 for i =
E (EE)
(65)
for + j.
k=1
In other words, Eq]
EE is diagonal matrix whose diagonal elements are upper bounded by 24"
Let us denote A ((G+b) T + (GG Then, (63) simplifies to,
9 EG [T(())
Eg Tr (A EQ
E []]] EG
Au (Eq E EE],
(66)
Furthermore,
(i)
Ea [Tr (A)] = EG |
[|
S EG
(Gb)) 7
x (Φ)
-]]
Ea
Tr
G GT)
02 - (+)
0 max
+
Tr E (GGT) "|)
min
m²
max
(67)
(t m - 1)
min
Here, (i) follows from Lemma 1. (ii) is consequence of Lemma B.2, and (iii) follows from Lemma B.9. Combining (63), (66) and (67) yields,
9A² o
m2
E (GG)
<
(68)
4 o² (1 - m - 1)
This completes the proof.
29

---

G LPLR algorithm: Approximation error analysis
To prove Thm. 3.2, we will first prove the result when both quantizers Q and Q' are unsaturated. We first prove Lemma G.1, which gives us upper bound on the approximation enror when Q and Q' are unsaturated. Since we can ensure that they remain unsaturated with high probability (with appropriate choices of dynamic ranges), the final approximation error upper bound in Thm. 3.2 is slightly worse than Lemma G.I.
Lemma G.1. Let our matrix A Rnx have non-zero singular values o1,...,, Gk. 0k+1, Or where rank(As A), and bounded row norms | S R. Let k(A) 0 and k(As) = 01 / respectively the condition numbers of A and the best rank-k approximation of A, and let us denote
log 322RR
m(AA)
t
K min k(A),
VT+I+ 41-1-r
S
ok
S 4nRRaa(A)2 Here 7 d/m m is the aspect ratio for some sufficiently small that satisfies O < of the sketching matrix S Rdxm with Sig v.1.d. N (0, h)) Suppose the dynamic ranges of the quantizers Q and Q' are to R.V respectively, and suppose their bit-budgets B and B' satisfy
2 2log 10R2n2m
and 1タ-1-t
2x dictated by Lemmas E.1 and E.2
4R
nd
B 2 max (B1, B2}
and, B' log2
+ +1
(VT
t)
where,
2R (Re(AK) An)V2n
16R2n2m
B1 loga
log
+1
Ve(T -
and B2 is equal to max
4CR
V++1+1/V2
16R2n2m
logz
2
+1
Jr, 0k ok+1
( (v-1--1)
log2
---1-6
Furthermore, let E be the event that both quantizers Q and Q' are unsaturated. Then,
E [|Q((A)Q' (Q(AS) A) All 18 s 1 m 1: - - ||A+
3e
A
4
where I (() is the indicator function.
Proof. Let us denote the quantization eгror matrices from Q and Q' as E E Ruxm and E' E mxd respectively, i.c., Q(AS) AS and E' QL' (Q(AS) A A. Since 1g implies that Q and Q' are unsaturated, E|E] 0 and E 0. Then,
E [IIQ(A))Q' (Q(AS)+A) A) A 1s IEs [ [[Q(AS)Q' (Q(AS) A) A 1
Then,
Eq. [IQ(AS)Q' (Q(AS) A) A 1 Eq.q' [IQ(AS) (Q(AS) A + E') A 1g Eq [IQ(AS)Q(AS) A A 1 EE [IQ(AS)ET]]]
(69)
Ti
T.
The cross terms disappear in (i) because,
Eq.q' Tr (Q(AS)Q(AS)AA A) Q(AS)E 1s
= Tr EEQ [Q(AAS)((AS) A-)) T Q(AS) Egy [E1) 11g
18)
0,
(70)
where, (ii) follows from EQ E'] 0 as the quantizer Q' is unbiased when unsaturated.
30

---

Analyzing the term T1: Recall that A₁ is the best rank-k approximation of A obtained using computing the full-SVD of A and subsequently making all singular values of A less than σ% as We next analyze the first term in (69) as
AlE S (Q, A - A
= (S ( Q A - A
-AAX - IE
(71)
where X - arg minx [ST -
This minimization problem Gaussian sketched variant of a generalized least squares problem with the response matrix quantized as seen in App.
Corresponding to the notations in App. F, here we have S instead of G, A instead of and A instead of Y. As consequence of Lemma F.I, we have the upper bound,
1 m k |
n of
m²
EQ [IQ(AS)Q(AS)) A A 1 S
A +
(72)
of
(d - m - 1)
Analyzing the term T2: The term T2 can be written as, Eq.a [[Q(AS)
1
Eqqq
[I(AS
E) E
Eqr ||ASE")
1. + EQ.
EE' [
1. + Tr (Eo (ASE') T
Eq E
E'
1
① |ASE' ||
+ EE
EE'' 11g,
(73)
where, (i) follows once again since Eqy
E 11
O. The first term in (73) can be rewritten as
|ASE'
1|2 1
=
E
Tr (E'TsT "ASEE) 1g]
E [Tr (ST A ASE'E E
Lg]
-Tr (Es [S A AS Boy
E''' 1&])
EEs [Tr (S A AS E.y
[E' [e)]
(74)
Similar to (65) in the proof of Lemma F.1, Eq E''ET Ig is diagonal matrix with
f d Var(Ex) dA for jj.
for i =
Eq
EE'E'
1.
Σ
Eo
En
E
1s
(75)
ij
1=1
Let us denote
r - STATAS AS. Then using the fact that 0. S 1, we get,
Es [r (T Eq' E'''
Ls)]
Es
Fu (Eor [E'E' D)'' 1s
dA
Tr (EsT)
dA
( dA
Tr (A AES [SS] ]]
4 ||
(76)
Here, the last equality follows as Es [SS
= Iq. This is because the (i, entry of Es SS is
vm E [ Var (Siz) =1 for i=
E (SST) )n
Σ E Spp
J[SA -0
for i
Furthermore, the second term Eqqq
E | 1s can be simplified as follows,
Eq.q' [EE'|] le = Eq.ar [Tr
E
E EE
1s =
Eq
Tr E
E
Eqy
EE'E })] de
EQ
E
EEq'
EE'E
E
18
31

---

dA
IQQ
[(ET E),
==1
mmdA A
(77)
16
Here, (i) follows since Eq E'E'T] 1g is diagonal matrix as seen before, and (ii) follows from the upper bound derived on E Combining all the above, the approximation error of our low-precision low-rank approximation scheme can be upper bounded as,
E B),, 1. in (65).
BIQ((A))Q' (Q(AS)(A) A)
AlE
(m
A
AlE
RA
0
m
dA
|
amdA2
(78)
m k
m
4
16
To
Here, the first term T3 is the low-rank approximation error, whereas the remaining terms, i.e., T4, Ts and T6 appear due quantization. We now analyze each them separately.
2
1,
Analyzing the term Tę Since we choose the dynamic range of quantizer Q to be RV (ref. Lemma E. 1), we have
m
n of of
m
2m log 116
(79)
(d
1) (2 - 1)2
4
Here, we can ensure (i) holds true, i.e., that this term does not exceed e/4 if we set the bit-budget B satisfy.
2R (1-11-
116R222m
B 2 loga
log
+
(80)
E
Analyzing the term Tş: Since we choose the dynamic range of the quantizer Q'' be equal to 2x (ref. to Lemma E.2), where and are defined as in (33), we have
---1-
d2 2
ndR²
2x
5 e
(81)
4
(2 1)² (V7 - 1 t)²
4'
where have made use of Asm. 3.1. Once again, in order to ensure (i), suffices choose the bit-budget B' to be
4Rx
nd +
B' loga
(82)
(VT-1-
Note that in order for the dynamic range quantizer Q' hold true in Lemma E.2, we also require to satisfy (34), i.e.,
4CR
v++1+1/VV2
16R2n²m
B logz
2
+1
( log?
---1-t
max or, 0& oht1
(83)
Analyzing the term Te: Using bit-budgets B and B' as in (80) and (82), the final term is
amd A A
nmdd (? (2-1- 1- m mmmsss A&))
e ())
(84)
4ndR 16nR ml (A)) 4
Here, (i) is ensured by choosing to be sufficiently small specifically, e An)² 7
32

---

Tying it all together: Combining (79), (81), and (84), with the bit-budgets set appropriately as dictated by (80), (83), and (82). eq. (78) simplifies
3e
BII((ASQQ (Q(AS) A) A 1+
A|
Al 2
(85)
--1
4
This completes the proof.
G.1 LPLR approximation error: Proof of Thm. 3.2
We now formally state our main approximation result.
Theorem G.2. (LPLR approximation error (formal)) Let our matrix A E Raxd have non-zero ..... Kk 0kt-1..... Cr. where rank(A) (A), and bounded norms ||al|| R.
singular values o1,....
Lel s(A) /or and K( (Aa) 01/0% respectively be the condition numbers of A and the best rank-k approximation of A, and let us denote
log (32nR²)
x(AA)
K min ((A))
v++++ VT-I-r
1 On
for some sufficiently small that satisfies O < S 4nR²x((A²² Here 7 d/m m is the aspect ratio of the sketching matrix S ıdxm with Siy iid. N (0, h)) Suppose the dynamic ranges of the quantizers Q and Q' are set RV bit-budgets B and B' satisfy
2 2 1m
and マー-1- respectively, and suppose their
(VT 4Rx
nd
B2 (BI, B2} and, B' logg
+1
1)
where,
2Rn(A 22
16R2n
B1 loga
log
+1
Ve(7 -
and B2 is equal to
4CR
V++1+1/V2
16R2n2m
logz
2 log
+1
max
[r, (Tr ak ak+1
F++ W--1-i
log2
---1-6
Then, the low-precision and low-rank factorization returned by Alg. satisfies
(1 (0055(+10) (1+m-k-)
- ||A: - A +
k
E EILR- - FI
(86)
where the expectation is over the random sketching matrix S, as well as the inherent stochasticity from quantizers Q and Q'
Proof. For the purpose of analysis, we assume that Alg. returns L O and R = 0 if either quantizer Q Q' gets saturated. In practical implementation, it can easily be checked if either quantizer Q or Q' gets saturated or not, and the algorithm can be repeated again with a new realization of the sketching matrix S and stochastic quantizer Q. Since the choice of dynamic ranges for Q and Q' ensures that they remain unsaturated with a high probability. "reasonably few" realizations of S would suffice get least one good realization which Q and Q' are unsaturated.
However, in what follows, we assume that that if either quantizer Q or Q' gets saturated, then the algorithm returns 0 estimate of A, resulting in Frobenius norm error of |||| Since this happen with a very small probability, we show that its contribution to the expected Frobenius norm error of Alg. 1 is small well. With this in mind, the expected approximation error can be written as
LR A = ((A)) Q' (Q(AS)) A) - A 1s +
| 1g
33

---

@ _ (AS) O' (Q(A))' A)
-
18 + nR² Pr (1ge).
(87)
Inequality (i) follows from Asm. 3.1 and the fact that the expectation of indicator function of an event is the probability of the event. From Lemma G.I, the first term can be upper bounded as:
E [[Q())) (Q(AS) A) - All Le -
11+ (1 (1+ m m-k-1 ||
Al
3e
(88)
4
Since Lemmas E.1 and E.2 state the probabilities of quantizers Q and Q' being unsaturated, Pr (1ge) can be obtained by an application of union bound as
Pr (1ge) =
SnR² + E
(89)
8nR²
4nR²
Then, (87) can be written
k
E | A
||As
All +
(90)
m71
This completes the proof.
G.2 Informal version of Thm. G.2
From Thm. G.2, we can get a (simplified) asymptotic dependence of the bit-budgets B and B'. We have 2 ma B2}.
2R Av v 2n
16R2n
B1 = log2
Ve - 1- + V
llog
+ +1
i
x(AA))?mm) 2mm
mn?
log2
log
2
e (d - m 1)
(
*((A)²² nm
mn²
loga
log
(91)
2
d
where have ignored the constant terms inside the log2(-) in (i) and considered the regime d (ii). Furthermore, B. is
4CR
V++ 17+1+1/V2
16R2n
B2 loga
2
+
max Tr,
ok+1
Vr+1+1 V--1-r
log
V7 -
mn?
2 Logz
log
(92)
(max (0r, xxt)
where c' is approximately constant. Here, (i) follows because when < d, we have
+ Vd + / + O
(V (+)
0(1)
(93)
V 1-t Vd vm
log (*)
Similarly,
V5+1+t/V2 V9-1-1
(11). Comparing (91) and (92), we have
x(AA) 1
mn?
B log2
log
(94)
Moreover, the bit-budget B' is
4Rx
nd
B' 2 loga
+1
(Vr t)
KV vnd
(II
Tum
loga
loga
(95)
Ve
Vd
Vm
where once again, get (i) we have ignored the constants, and (ii) holds true when m < Moreover, suppose n as d (if they not equal, then the total bit-budget should be computed
34

---

weighted average, since the L has nm elements and the second low-rank factor has md elements). Then, for some constant C3 that depends on R. the total bit-budget is
(x(AA) n²m?
mn? log (mm))
))
1
(ax(Aa)r am
mn?
B
log2
log2
log
e
2
vd
Furthermore, the dynamic range quantizer Q is e1 V log and that of quantizer Q' when m <
2k
2v m d min x(A),
K6
k((A)
for constants C1, and that depend on R. where additive logarithmic terms are ignored with respect to m. This gives us the result in Thm. 3.2.
H Direct-SVD Quantization: Approximation error analysis
In this section, we consider the baseline scheme for obtaining (ow-precision low-rank factorization by first computing the optimal low-rank factorization using SVD and individually quantizing the low-rank factors with uniform scalar quantizers. For any given matrix, A E Rnxd compute the full SVD as A UΣVT. The best (unquantized) rank-k approximation can be obtained from this by considering the singular vectors corresponding to the top-k singular vectors, and constructing the matrix A (UE), ) VT_ Here, (UE); E R= the sub-matrix obtained by selecting the first columns of UE and V E k is the sub-matrix obtained by selecting the first k rows of VT. Subsequently, these low-rank factors are quantized with uniform scalar quantizers Q and Q' (having bit-budgets B and B' respectively). The algorithm pseudocode is given in Alg. 2 and we provide an upper bound to the approximation error in Proposition H.1. We use the notation U = UE Raxd
Algorithm 2: Direct-SVD quant.: Directly quantizing the optimal low-rank factorization
Input :Marrix E Raxd, target rank k. Quantizers Q and Q' Output:Factorizznt
Factorization: LR where L BR* E Rexd
Compute SVD and get A UTVT
2 Extract the top-k left (scaled) and right singular vectors and get Ü2 = (UE), and V Quantize the factors individually and get L +- Q(Ux) and R +- Q' (V+)
return L E Ra R E Raxd
Proposition H.1. (Direct-SVD quant. approximation error (formal)) Let our matrix A E gaxd have maximum singular value σ1. Suppose our target rank is k, and for some small such that 0 E < 3ko the dynamic ranges of quantizers Q and Qf are be σı and 1 respectively with bit bit-budgets satisfying
3nk
3dk
+1 +1)
B logz
0
+1
and, B' logz
01
Then, the factorization returned by direct-SVD quantization in Alg. satisfies
E EILR- AlE S ||A A +e,
where the expectation is over the inherent stochasticity of the quantizers Q and Q'.
Proof. Let denote the quantization error matrices E Q(Ūx)) Ug and E' Q(VV)) V..
The approximation error is given by
E Q(ūwQ' (vT)= A
2 = E ( (Vī + E') - A l
F
F
i Q(ū
1 + E
Q J
(96)
35

---

where the cross term disappears in (i) because when Q' is unsaturated, Eqy [E*] 0, and
Byy Tr ((QU)))V -A) Q(Üs) Boy (8")
Analyzing term T₁ The first term in (96) can be upper bounded as
E Q(U - I|
U +
V A
2
||
A 2 +
EV ll
(97)
Here, in (i), we utiliie the fact that A₁ Q is unsaturated, i..., E and,
U V and the cross term vanishes once again quantizer
(ÜAV] A) Eo EIV O.
Tr
The second term in (97) is
(I)
A
E EVE E.
[T EV V&ET)] VxE) Tr E E])
EE EJ)
nk 4
(98)
Here, (i) follows because V Vv Ig. and (ii) follows because E E Ej is diagonal matrix
n Var (E I Dd²
for i = j. for + j.
E EI)
10 EIEE
(99)
t=1 E
E& = 00
So, (97) can be upper bounded as
2
E
QQ A
S | A+
Ale
nk
(100)
4
Analyzing term T2: We upper bound the second term in (96) as
E QQ = E (Üx+E)
E'
2
(
U
E'
2
+
E
EE
(101)
F
F
where the cross term vanishes (i) because Egy Tr ((ÚRE)T (101) is
Bq
E
E' )]
The first term in
E
U
2
E
Tr
E U U
E
Tr
U Un)
(E('EET))
(8)
(
(i))
Σ
of
< dko
2
(102)
1=1
i=1
Here, (i) and (ii) follow because E E' T is diagonal matrix following the same argument as (99). ie.,
d Var E2 DE
d
for = j,
(EE'E Do Σ EEE
(103)
EEE
=0
for +
Finally, (iii) follows because the th column of U is ouu, (ū,Ü)), (o,u,) (a,u,)
of 1 = of.
The second term in (101) is
E EE'
TT
E
EE')
EQ
Tr E
E
Byy
E'E'T]
EQ
Σ
E
EQq
EEE
36

---

2 k
(6)
n
d 1
EQ (
JEBB E),
S
(104)
4
4
1=1
Here, (i) and (ii) follow because E EEE'E' and E
E] are diagonal, which can be seen using
similar arguments as in (99). So, (101) is
B Q(0 (VI) A I A All nk A + dkop
A A A
ndk
(105)
4
4
Choice of dynamic range for quantizers Q and Q': Using Lemma B.3, the max-norm of the input to the first quantizer can be upper bounded as ||U S ||U 01, and that of the second quantizer is V max I V l22 = Therefore, choosing the dynamic ranges of Q and Q' be a and respectively, would ensure that they remain unsaturated, and (105) can be rewritten as dkoi
2 S A AlE
nko
nA² dA
E Q(U (VT) A
+
+ h
(106)
(2
1)
(2 1)2
Choice of bit-budgets B and B': For given
O, suppose we choose B and B' so that
3nk
3dk +1
logg
+1
and,
B' loga
With such a choice, the second and third terms in (106) would not exceed e. Furthermore, the last term of (106) will be
n
2
S dnk
whenever e < <3ko]
3nk 3dko?
This completes the proof.
Prop. H.1 states that when s d, in order to guarantee an e-additive enror approximation with respect the best rank-k approximation, we require (ignoring constant multiplicative factors inside the lo)2(-)), total budget (ref. to Tab. 1) of
11
B' (B+ BB) d
3kot Vnd
loga
bits.
(107)
n 1 d
n
I LPLR-SVD algorithm: Approximation error analysis
LPLR-SVD a simpler variant of our LPLR algorithm in which instead of approximating the range space of A using AS, we compute the full-SVD of A E Raxd as A UΣV T where U e R=*x" Σ E gaxd and V idddd The pseudocode of LPLR-SVD provided in Alg. 3.
We first compute the SVD, A = UEVT, followed by quantizing the singular vectors corresponding to the top-k singular values, scaled by the singular values. We denote = UE, and the sub-matrix formed by the first & columns as Üz. We quantize this basis to get L Q(Ū,)) as the first low-rank factor. Subsequently, we project the columns onto the subspace spanned by this quantized basis, i.e, we solve the optimization problem
QQ( l
min We
(108)
The solution of this is given by W - t( The second low rank factor is given by quantizing it again as R Q' (Q(Ū+)+A).
The following result provides upper bound the approximation error of LPLR-SVD. The proof of this result is similar to Thm. 3.2 without the complications arising from Gaussian concentration.
Theorem L.I. (LPL.--VD approximation error (formal)) Let our matrix A E Raxd have singular 2 ... and bounded row norms [ < R. ((t)) oi /a be the condition
values 2 number of the Ag, i.e., the best rank-k approximation of A. Consider some sufficiently small e that
satisfies 0 < 4kof, and suppose the dynamic ranges of quantizers Q and Q' are set to be on and
37

---

Algorithm 3: LPLR-SVD: LPLR factorization via Singular Value Decomposition
Input :Matrix A E Rnxdd target rank k. Quantizers Q and Q'
Output :omput:Factriina Factorization: LR where E RR* R R
Compute SVD and get A UEVT
2 Extract the top-k left to get an approximate basis for the range space of A as U (UΣ)
Quantize and get an approximate basis Q(Ük)
Find W arg minw Q(Ū - A
Quantize W using quantizer Q' to get Q'("")
return Low-rank and low-precision approximation LR where L Q(Ūx), R= Q'(W")
(x((As) respectively. Furthermore, suppose the bit-budgets of the quantizers satisfy
dk B' z 40In(As))
B > max B2) and,
logz
+1
where,
nk
+1)
2011 B1 log2
c
and,
ACk(AA)
(v Vie Vi++ V logg
8nR2
+1 +1).
B2 = loga
log2
Then, the low-precision and low-rank factorization returned by Alg. 3 satisfies
E BRLR-
AlF I || - Ali +e.
Proof. Since the solution of W arg minw |Q(ū | is available in closed form as w (t A, we have the low rank factorization A Q(U,)Q' (Q(ū+)tA), Let denote
the quantization error matrices as E' Q' (Q((W)A)) Q(ūx)* A. and E Q(Ūx) Úg. Then, the approximation error is
E ||QūO)Q' (Q(ū.)AA) l e Q(ū (o(U.)' E') A
F
E Q(T ' Alle + Q
E F'
(109)
T2
where the last equality follows the because the quantizer Q' is unbiased. Here, the over the stochasticity of the quantizers. This decomposition is similar to (69), and can be treated similarly. The term T, consists of the low rank approximation error and the error from the first quantizer, whereas the term Ta consists of error from the second quantizer. We follow steps similar to the proof of Lemma G.I which are detailed below.
Analyzing term Tr: Using similar reasoning as (71), this term can be written as E (( - | < e B( - A = E Q(U - A 1
(110)
This is the same as (100) the analysis of direct-SVD quant., and hence can be upper bounded as E Q(..)
1 2 < | A + nk A
(111)
4
38

---

Analyzing term T2: This term is again the same as (101) in the analysis of direct-SVD quant., and can be upper bounded as
1
n
d
E Q
E
S dkot
+ k
(112)
4
4
4
Using (111) and (112), get:
Q(ūw)Q) (Q(Ü)) A
2 | ||
All
+
nk
A
+
dki
A
dA
(113)
4
4
T3
Ts
Choice of dynamic range for quantizers Q: Since the input to the quantizer is UR, we need an upper bound on [Ux |mxx/ The 8th column of Us is (Ux); u, where 1 s S. k. From Lemma B.3.
|| I | 01. Note that this upper bound is tight in the worst-case sense, i.e., if we consider all matrices with bounded spectral norm, we have supx X-UEVT L=UEV,,[XI,, | mma r. Hence, the dynamic range of quantizer Q is set as di
(114)
Choice of dynamic range for quantizers Q': On the other hand, the input to quantizer Q' is Q(Ux)f A. We adopt an approach similar to the proof of Lemma E.2 to upper bound the max-norm of =fUx)* + A follows:
QQ(w)) A
(115)
where (i) and (ii) follow from Lemmas B.3 and B.4 respectively. We upper bound (((ū,)* as:
(i) | x mmin (Q(ūw)))
mmin [Üx + E))
mmin (x) - [E||2) = (ax, 107-|EEg E122)
(116)
Here, (i) follows because the singular values of Q(Üx)) are inverses of the singular values of Q(Ū,), and (ii) follows from Lemma B.5.
We are now left with upper bounding Ellp. Since a choice of 01 for the dynamic range Q ensures that quantizer Q remains unsaturated, the entries of E are bounded as:
201
E.yl < A
for all E [n] and j [k]].
(117)
2
Since Egy is a bounded w.h.p., it is also subgaussian w.h.p. (ref. eq. (16)) with subgaussian norm given by,
201 (2B
E
(118)
1) log
From Lemma 12 we get for some absolute constant C.
2C01
[El1 S (2 1)
vk++) Vv
with probability exceeding -1
(119)
log?
Setting t / log 8nR2)
we get:
2Co1
8nR²
2 < (2B log
V Vk
log
with probability exceeding
4nR²
(120)
Let us choose our bit- bit-budget B of quantizer Q to be such that |E|| S ok i.c.
(4C((A))
(va+ v
log (8R2²
B > log2
+
(121)
log
39

---

where x(Aa) = 01/0 is the condition number of the best rank-k approximation of A. Then, using (116), we have:
Q(U)))
< 2x({A))
with probability exceeding
(122)
4nR
So, if we choose the dynamic range of quantized Q' be 2x(Aa), it will remain unsaturated with probability exceeding (121).
4nRz provided that the bit-budge of first quantizer satisfies B satisfies
Choice of bit-budgets and B': Referring to (113), the term T3 is,
A
of
nk +1).
ru
= nk
S
if B 2 log2
201
(123)
4
(2B - 1)
4
The term T4 is:
2 A
4k(An) (2 1)
dk +1)
dko1
dkot
S
if 2 log2
(124)
4
With the above choices of В and B', the term T5 is:
A A
ndk
S ndk 4nk 4dko
S if c 4kof
(125)
4 4
Tying it all together: Similar to what is done in the proof of Thm. G.2, for the purpose of analysis. we assume that Alg. 3 returns L = 0 and R 0 if quantizer Q' gets saturated. In practical implementation, can easily be checked if either quantizer Q or Q' gets saturated or not, and the algorithm can be repeated again with new realization of the stochastic quantizer Q. Since the choice of dynamic ranges for Q ensures that it remains unsaturated with high probability, "reasonably few" realizations would suffice get least one good realization in which Q unsaturated.
assume that that if quantizer Q gets saturated, then the algorithm returns 0 as an estimate of A, resulting in a Frobenius norm error of ||Al| Since this happen with very small probability, we show that its contribution the expected Frobenius norm error of Alg. is small as well. Let us denote the event that quantizer Q is unsaturated as E. Then, the expected approximation error can be written as
However, in what follows,
LR - A E
@(Üw)' (Q( - A
1
+
|
Tec
( < E
||orōaa (Q(ŪW)A))
A
1g
+RR²
Pr (1ge)
A |A 1/2 + nk dkot
A
d2
+
+ nR Pr (Igge), (126)
where inequality (i) follows from Asm. 3.1 and the fact that the expectation of indicator function of an event is the probability of the event, and (ii) follows from (113). Using appropriate choices of and B' and small enough from (122), (123), (124), and (125), we have
E [LR A <
||A+ AIE -
nR² 4nR² ||Ar Ali
(127)
Note that from (123) and (121), the bit-budget of the quantizers must satisfy:
dk (+11)
B 2 max (B1, B2), and B' 2 log, (401k(An)) (Ax))
(128)
where,
nk 2011 e +1).
B1 loga
(129)
and,
4Ck(AA) log
8nR²
Bg = logz
(v++ Vk+ V loog
+1
(130)
This completes the proof.
40

---

I.1 Informal version of Thm. 1.1
Consider d. From Thm. I.1, we can get a (simplified) asymptotic dependence of the bit-budgets В and B3, In what follows, we ignore the constant multiplicative factors inside 1og2(-). Comparing the expressions for B1 and B2, we have
nuk:
2 log2
011
(131)
and,
ck oIR(AR))
B' 2 log2
(132)
This gives a total bit-budget of
log2 (ofn(Ar)) k. Vnn
bits.
(133)
Additional numerical simulations
J.1 Image Compression
In addition to Fig. in the main paper, we also provide additional image compression experiments on images of different dimensions Figs. 6, 5, 7, and The values of and B' are provided in the respective captions of these figures. For every image, the sketch size/target rank and the bit-budgets and are chosen so as to ensure parity with a naive quantizer with bit budget Bnq. In other words, for an d dimensional image, B nun + B' md Bpq nd. The values of and d are also provided the corresponding captions.
For image compression, we also perform a normalize and shift operation of our DSVD/LPLR/LSVD output order adjust the scale and bias of the output image, described next.
Normalize and shift: Let us denote the factorization obtained from executing DSVD//PLL//LYT on the input matrix X Rexd by Y LR. Then, factorization by considering a + x The overhead in storing these two additional scalars in full-precision is negligible when and d are large. The optimal values of and 3 can be found as:
improve the estimate provided by this
(a" (*) arg min ||a .I - -
(134)
a,
Closed-form expressions for (*) can be obtained by equating the derivatives of ||aY + AI X| zero, and solving the resulting linear equations. Doing this algebra yields,
a" |
1Y,1)
(X Y) (X,)
nd
nd
8r (X,I) (Y a*
and,
(135)
nd
nd
J.2 Wall-clock time for compressing image embeddings
We now report the wall-clock time for computing the low-rank quantized factors via LPLR, LSVD, and DSVD for embedding compression Tab. 10. This reinforces the validity of our theoretical assertions concerning the computational advantage of LPLR when compared to its alternative methods.
J.3 High-resolution figures for Llama weight compression
We now provide higher resolutions figures of Figs. 2a and 2b as Figs. 3 and 4, respec- tively. The code to reproduce these numerical simulations available at our github repository https:// hts//giitit httpe///mmpaaaaaiaaaaaaaatiiiiia compre/eee..ttiicroooooooooooor
41

---

LPLR
Naive Quant
LPLR SVD
Relative Frobenius norm error
3.5
3.0
2.5
2.0
1.5
0.5
0.0
Layer
Figure 3: Comparison of LPLR and LPLR-SV SVD on LlaMa weight matrices with B = B' = 8 bits, Bug = bits, ordered by the original sequence of layers the "Layer" axis. We observe consistently better Frobenius error using L.LRR and LPL.-SVD, with the exception of specific layers which lend themselves naïve quantization.
LPLR
Naive Quant
LPLR SVD
Relative Frobenius norm error
3.5
3.0
2.5
2.0
1.5
1.0
0.5
Layer
Figure 4: Comparison LPLR and LPLR-SVD on LlaMa weight matrices with = Bag 4 bits. ordered by the original sequence of layers on the "Layer" axis. LPLR and LPLR-SVD demonstrate equivalent performance on a uniform compression budget of 4 bits, while outperforming naïve quant. on almost all layers.
42

---

Table 10: Comparison wall-clock for computing low rank quantized factors via LPLR, LSVD and DSVD. Each image embedding forms row of the input matrix, with low rank factors computed for each class of the input datasct. Bit- Bit-budgets used are B = B' = 8, Buq 1. We report mean and standard deviation.
Dataset
LPLR
DSVD
L.VDD
CIFAR-10
71 + ms
306 26 ms
312 + ms
CIFAR- 100
14 + ms
51 3 ms
+ 3 ms
(a) Original image
(b) Naïve (0.312)
(c) DSVD (0.507)
(d) LPLR (0.264)
(c) LSVD (0.260)
Figure 5: Compression Shepp-Logan phantom standard image for medical image reconstruction,
courtesy: Phantominator, PyP[). 4,
8, Baq 2, m 166. Orig. image dim.: 1000 x 1000
(a) Original image
(b) Naïve (0.508)
(c) DSVD (0.508)
(d) LPLR (0.311)
(c) LSVD (0.301)
Figure 6: Compression Shepp-Logan phantom standard test image for medical image reconstruction,
courtesy: Phantominator, PyPI). B' B.g 1,m Orig. image dim.: 1000 1000
(a) Original image
Naive (0.701)
(c) DSVD (0.724)
(d) LPLR (0.346)
(e) LSVD (0.351)
Figure 7: Compression Jupiter image showing its Great Red Spot and Ganymede's shadow (courtesy:
NASAJESA Hubble Space Telescope).
B' Bug 1.m 110. Orig. image dim.: 1102 x 1102
IN
Original image
(b) Naive (0.711)
(c) DSVD (0.556)
LPLR (0.329)
(c) LSVD (0.321)
Figure 8: Compression of an MR image of the human brain (courtesy: User Asnaebsa, Wikipedia). B = 4.
B 8, Bug 1, m 124 maintains parity. Orig. image dim.: 1534 x 1433
43

---

K Limitations and further discussions
On uniformly dithered quantizer: We would like to point out that the approximation error upper bound for our algorithm (derived in Thm. G.2), as well as for the baselines such as direct-SVD quantization (refer to Prop. H.1) holds true only for randomized rounding, uniformly dithered quantizers. Dithering is preferred due to its ability to produce an unbiased estimate of the input. It offers an advantage by introducing non-zero probability of quantizing an input to either its ceiling or floor, resulting in reduced variance when averaging multiple independent realizations. Moreover, the unbiasedness of the quantizer output simplifies the analysis. In our experiments, we did not observe any difference while using deterministic rounding instead of dithered rounding.
Comparison with LPLR with direct-SVD and LPLR-SVD: As we see from the numerical eval- uations (ref. to Tab. 6 and Tab. 7), direct-SVD quant. and LPLR-SVD performs better than our proposed LPLR algorithm (that computes a Gaussian sketch). Intuitively, one would expect the performance of LPLR-SVD. and LPLR (with Gaussian sketch) to be similar because the core idea behind both of them is the same Quantize the first low-rank factor, and then project the columns of A onto the quantized (first) low-rank factor. For LPLR-SVD the basis being quantized (top-k singular vectors) is the exact top-k rangefinder (for the column space of A), whereas in LPLR, we sketch using the Gaussian matrix to get an approximate rangefinder. This sketching error might make LPLR worse over LPLR-SVD. But because sketching also introduces "equalization effect of the Gaussian matrices", we can improve the resolution of the uniform scalar quantizers by choosing a smaller dynamic range. Hence, there is a tradeoff when comparing LPLR and LPLR-SVD tradeoff between sketching error and the quantization error.
Let now focus LPLR-SVD and direct-SVD quant. We will extrapolate this intuition comparison between LPLR and direct-SVD quant. The factorization obtained using direct-SVD quant. is A = Q(Ux)Q((V where the approximation obtained using LPLR-SVD is A P Q(Ü,)Q' (((.))A) Here, Un is the n x k matrix obtained using the first & columns of UE, where A = UEV is the full SVD of A. Let us assume B' + oo so that we don't 't have to worry about the second quantizer. Then, we are left to compare the approximations: A Q(ÜR)V? and x Q(Ux))((x2(A A. Clearly, the latter has smaller Frobenius norm error because
the minima of the minimization problem arg minw Q(Ú.) -A -wWll"" So, for B' - Do, it is evident that direct-SVD can only perform as good as LPLR-SVD, and not better than that. Furthermore, note that this difference in performance will be small when the bit-bu of the first quantizer, B is large, and it will be large when B is small. When B + 20, this difference will be exactly zero. In other words, direct-SVD quant. and LPLR-SVD will be the same factorization when B - 3o and B' oo. When both B and B' are finite, direct-SVD can outperform LPLR-SVD depending on which one out of Q' (Q(ū))) A) and Q'(VI) is closer to the optimal solution, i.e., Q(Ūs)) A. A limitation of our analysis is that we cannot always definitively predict which one will perform better, because derive upper bounds on the approximation error.
In Tables 1 and 2, we have compared LPLR with other benchmarks. In the column denoting approximation errors, aside from the common quantization еrror present across all rows, DSVD and LPLR introduce an additional term representing the error from low-rank approximation. Consequently, it might appear that naive quantization consistently outperforms these methods. However, it's essential to recognize that compression techniques based on low-rank factorization hold value exclusively when the matrix being compressed is inherently low-rank, meaning that || Al starts off as small. If || A|IF O. LPLR can achieve identical error levels as naive quantization, while demanding fewer bits than the latter. In other words, given the same bid-bu, LPLR can achieve lower level of error compared to naive quantization.
Comparison of LPLR with naive quantization:
Matrix compression with and without any computation constraints: In situations where com- putational resources are limited, employing the naive strategy emerges as the most cost-effective approach for matrix quantization. Nevertheless, due to its failure to capitalize on a matrix's inherent low-rank arrangement, naive quantization may prove considerably suboptimal. As matrices increase in dimension, accommodating them memory becomes impractical, rendering approaches like DSVD or LSVD unviable. In such scenarios, our LPLR method stands as viable alternative,
44

---

demanding slightly more computational effort than naive quantization, yet capable of harnessing the low-rank structure for improved approximation accuracy.
there no scarcity of computation resources in being able to compute the SVD, and our goal is to just compress input matrix A, then it is possible to compress the matrix with all the strategies, and choose the best one. However, it must be kept in mind that LPLR provides significant savings with respect computational complexity, i.c., ((nd)), compared LPLR-SVD, which has a complexity of (ndd).. Consequently, if the matrix being compressed is very large, it might not even be feasible do direct-SVD quant. or LPLR-SVI given the current memory limitations of available GPUs, and LPLR (with Gaussian sketch) becomes our only option.
Furthermore, careful examination of Tabs. 6 and shows that even though LPLR-SV SVD and direct- SVD quant. have a smaller Frobenius norm error than LPLR, the accuracy and weighted F1 scores still comparable. One aspect of quantization that we have not studied in detail is its inherent regularization effect when testing the performance on test datasets. Whether L.LRR leads to a better regularization effect that the other baselines an open question that will be studied in future works.
Comparison with existing works on quantized random projections for approximate nearest neighbor search: Prior works of Li and Li [31] and Li and Li [32] consider the idea of quantized random projections specifically for the the application of approximate nearest neighbor search. Although related, the goals of these works are different from matrix compression considered in work. These prior works approximate the matrix vector product Ax by Q(AS)Q( x). For their setup, in addition Q( AS). ), the random matrix S needs to be stored in full-preeiin full-precision, in order to process an incoming query x. So, their storage requirement is nm quantized and dm full-precision parameters. In contrast, LPLR stores only the quantized entries of L and R. i.e., m(n d) quantized entries, and A sy LRx, implying smaller storage requirement. Furthermore, since LPLR involves computation of Rx, where R consists of md quantized values, it can leverage modern advancements in hardware primitives for speeding up low-precision computations, such as half and mixed-precision compute.
Extension to streaming settings: LPLR as presented in this paper, is used for compression when the entire matrix A is available. An interesting extension is to consider variant of LPLR streaming data settings in order to handle new data points. It is possible to do so using sketching based low rank approximations [68]. The left factor L is updated with the concatenation of additional row corresponding to the newly arriving datapoint. The second factor R, which the solution of a new least squares minimization problem, can be updated using Woodbury matrix inversion lemma.
45


Reviews:
[{"review_id": "17Ojwmvmy8", "reviewer": "Reviewer_D7Xb", "summary": "The paper introduces a low rank, quantized/low precision matrix factorization which decomposes an n x d matrix A in the form A= LR, where L (of size n x m) and R (of size m x d) are low rank factors. L and R are computed using a random projection matrix S in the form L = Q(AS) and R = Q'(W^*) where W^* is the matrix minimizing the squared Frobenius norm ||Q(AS)W− A||. Q and Q' are two independent quantizers with specified budgets. \n\nThe authors contrast their method with an SVD based method for computing the quantized low rank approximation which instead sets L = Q(U_k S_k) and R = Q'(V_k), where U_k/V_k and S_k are the singular vectors/values respectively. The paper has a theorem deriving a bound on the Frobenious norm of the factorization eror. They apply the approximation on image data (for image compression) and embedding matrices (for an embedding classifation task).\n", "questions": "* In Table 3, why are the SVD and Naive quant. Frobenious norm errors the same for different rank choice? Is it because the matrices are really low (<15) rank? \n\n* I think Table 3 may be expanded to a set of figures to better convey the message (with potentially more bit budgets).", "limitations": "This is an optimization paper and as such the limitations are not immediately obvious, though the eventual use of the model for downstream compression/computation speed up could be quite broad. The societal impact could also be positive given the matrix compression can lead to compute/energy savings. The paper doesn't have a dedicated discussion/section on any limitations. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ The paper is very well written and very clear in its presentation\n+ Clear technical presentation incl. theorems, algorithms etc.\n+ Novel idea, providing good review of relevant literature (different matrix sketching approaches, quantization etc.)\n+ Thoughtful experiments to demonstrate real world application (using embedding compression)\n", "weaknesses": "I don't see any weaknesses that need to be addressed at this moment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe are grateful for the valuable time you spent in reading our paper and writing the review. The voluntary nature of the review process is truly valued. In what follows, we address your questions:\n\n> Similar Frobenius norm errors for different rank choice\n\nFor naive quantization, the Frobenius norm is not influenced by the rank but is exclusively determined by the allocated bit budget, denoted as $B_{nq}$. As a result, it maintains a consistent value when the bit budget for naive quantization remains unchanged. \n\nRegarding the low-rank methods, namely Direct SVD and LPLR, we identified (and fixed) a software bug in the parameter enumeration code, which led us to mistakenly assess all outcomes under a fixed sketch size equivalent to a rank of 200. This caused a lack of parity with respect to the bit requirement for naive quantization, and the comparison was unfair. Consequently, the Frobenius norm values appeared relatively steady; the slight variance in LPLR stemming from distinct samples of the sketching matrix. We sincerely apologize for this error and present revised outcomes in Table 1 of the global response PDF, now encompassing a significantly broader range of bit budgets. \n\nIn Table 1, we assess the performance of LPLR, Direct SVD, and LSVD across a uniform range of bit budgets (including many that are not hardware primitives). This approach enables a more comprehensive examination of the approximation error and its variability when employing different low-rank approximation techniques with varying bit budgets. One can clearly observe that LPLR and LSVD (LPLR-SVD) outperform naive quantization for $1$ -- bit quantization, except in the extreme instance of $\\rm B = 32$. This trend persists even as bit budgets increase. For higher bit allocations, the superiority of LPLR (and LSVD) over NQ in terms of approximation error is apparent when the bit allocation $\\rm B$ is sufficiently low. This allocation strategy permits a greater allocation of storage to capturing higher-rank components. This delicate balance lies at the core of leveraging the effectiveness of LPLR, which excels in finding the optimal compromise between capturing the optimal number of low-rank factors with precision. We hope that this clarifies the rationale behind the scenario in which LPLR outperforms standard techniques, namely naive quantization.\n\n> Table 3 may be expanded to a set of figures to better convey the message\n\nThank you for suggesting this. We concur completely, and are forced to prioritize due to the limited number of pages available. We will certainly add a number of figures to the appendix to better convey the efficacy of our method. We have included additional results involving a wider range of bit budgets in the global response PDF (ref. Table 1), which provides a clearer picture of the method's benefits.\n\n> Dedicated discussion/section on limitations.\n\nWe have discussed some limitations in Appendix K.\n"}, {"review_id": "icOo6ZRBxl", "reviewer": "Reviewer_DCJv", "summary": "The paper studies the low-rank factorization of the matrix in the low-precision setting and proposes a new algorithm which is a combination of randomized low-rank approximation method and quantization.  The paper formally analyzes the guarantee of the proposed algorithms and also give experiments on real world dataset which demonstrate the advantage of the proposed algorithm.", "questions": "1. Theorem 3.2 shows the guarantee of the proposed algorithms. However, would the sketch size $m$ also have the requirement given the accuracy parameter $\\epsilon$ and $k$? Also in experiment it may be a factor that affects the runtime and accuracy a lot, is there some place indicating the choice of $m$?\n\n2. I am a little confused about the naive quantization baseline. Can this way make the matrix be low-rank?\n\n3. As mentioned in the paper, the sketching-based method is popular in randomized low-rank approximation. I think in the experiment the baselines should also include it (with the naive way of quantization).\n\n4. The paper discusses the runtime complexity. Hence, I think it would be better to include the runtime in the experiment section.", "limitations": "See the above questions.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The presentation of the paper is good. The writing of the paper is clear and easy to follow.\n\n2. To get the formal guarantee, the authors do a careful analysis, which I think is non-trivial.", "weaknesses": "1. Technical novelty: the main algorithm (Algorithm 1) seems to just be the standard way in randomized numerical linear algebra then plusing the quantization. Can you authors give more explanations about the technical novelty? (though the analysis I think is not standard)\n\n2. Experiment: I have some questions about the setting and details of the experiments section. See the next question.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, \n\nThank you for the time you invested in reading our paper and writing the review. We appreciate that reviewing is a voluntary effort and below, we address each of your concerns to resolve your queries. \n\n> Choice of $m$\n\nIndeed, the sketch size $m$ is an important design parameter. We have explained our choice of $m$ for experiments in lines $269$ -- $276$, where we mention that $m$ is selected so that the bit-budgets are identical between naive quantization and LPLR, i.e., parity is ensured. In Table $3$, the choice of $m$ are the values mentioned in the {\\it Rank} column. Note that the values of $m$ satisfy $(nm + dm)\\cdot{\\rm B} \\leq nd\\cdot {\\rm B_{nq}}$, i.e., $m = \\left\\lfloor \\frac{nd \\cdot{\\rm B_{nq}}}{(n+d)\\cdot{\\rm B}} \\right\\rfloor$. We optimize the choice of $m$ so that the bit requirement of LPLR does not exceed that of naive quantization. The same holds true for embedding classification experiments. \n\nTheoretically, if the matrix $\\mathbf{A}$ has approximate rank $k$, i.e., $\\lVert \\mathbf{A}_k - \\mathbf{A} \\rVert_F$ is sufficiently small, it suffices to choose $m$ to be slightly larger than $k$, such as $m = k + p$, where $p \\geq 2$ is the oversampling factor. The impact of the oversampling factor $p$ has been extensively studied in previous works, for example, see references $[16]$ and $[74]$.\n\n> Can naive quantization make the matrix be low-rank?\n\nNaive quantization *does not* make the matrix low-rank. We have included it as a baseline since the primary goal of the paper is to compress the matrix, and naive quantization, which does not exploit low-rank structure, is a standard practice in existing literature. In our comparisons, we show that there is a better way to compress the matrix, namely, LPLR, which exploits the low-rank structure and attains a smaller error than naive quantization, while maintaining parity w.r.t. the bit-requirement.\n\n> Sketching + Naive quantization as baseline\n\nUtilizing sketching along with naive quantization would sketch the columns of $\\mathbf{A}$ as $\\mathbf{AS}$, and find the right factor as $argmin_{\\mathbf{W}}\\lVert \\mathbf{ASW - A} \\rVert_F^2 = \\mathbf{(AS)^{\\dagger}A}$. A subsequent naive quantization would give the factorization ${\\rm Q}({\\bf AS}){\\rm Q'}(({\\bf AS})^{\\dagger}{\\bf A})$. This is indeed an alternative benchmark, although it cannot achieve a lower error compared to LPLR because:\n$\\lVert{\\rm Q} ({\\bf AS}){\\bf W}^* - {\\bf A}\\rVert_F^2 \\leq \\lVert {\\rm Q}({\\bf AS}){\\rm Q'}(({\\bf AS})^{\\dagger}{\\bf A}) - {\\bf A}\\rVert_F^2$, as ${\\bf W}^* = argmin_{\\bf W}\\lVert {\\rm Q}({\\bf AS}){\\bf W} - {\\bf A}\\rVert_F^2 = {\\rm Q}({\\bf AS})^{\\dagger}{\\bf A}$. If ${\\rm B'}$ is sufficient so that ${\\rm Q}'({\\rm Q}({\\bf AS})^{\\dagger}{\\bf A})$ is closer to ${\\rm Q}({\\bf AS})^{\\dagger}{\\bf A}$ than ${\\rm Q}'(({\\bf AS})^{\\dagger}{\\bf A})$, then LPLR will have a smaller error. \n\n> Novelty\n\nWe propose an idea which is simple in its execution and pragmatic in its implementation. Our idea is well supported for modern linear algebra libraries, while offering theoretical analysis to effectively identify the regime in which it offers value over conventional, standard methods. Moreover, our method offers a tunable knob to achieve effective bit-rates in software, not currently supported by hardware. For example, in Table $3$, using LPLR with appropriate parameters bits is equivalent to operating at $1$ or $2$-bits per pixel, despite hardware working with a higher bit precision. Moreover, our method is adaptable to future hardware advancements, such as the emergence of $4$-bit GPUs, which can significantly speed up our technique's primitive operations. We believe that the simplicity of our algorithm adds to its appeal and makes it a valuable contribution to the literature, bridging the fields of matrix compression, quantization, and sketching while ensuring compatibility with upcoming hardware developments.\n\n> Runtime experiments\n\nThank you for the valuable suggestion. As a response, we have included some additional experiments on the wall-clock runtime comparison of our method. They can be found in Table 2 and Fig. 3 of the global response PDF.\n\nTable 2 now presents the wall-clock time required for compressing the embeddings of the CIFAR-10 and CIFAR-100 datasets. It is evident that LPLR significantly outperforms DSVD and LSVD in terms of speed. Fig. 3 complements the tabulated data by visualizing the runtime involved in two scenarios. The first scenario involves computing the matrix-vector multiplication $bf Ax$ directly. The second scenario involves approximating this multiplication using a low-rank factorization, specifically $\\bf L(Rx)$, where matrices $\\bf L$ and $\\bf R$ are tall and wide matrices, respectively. This low-rank factorization strategy reduces the overall number of multiplications from $nd$ to $(n + d)m$. "}, {"review_id": "76gtntSpd5", "reviewer": "Reviewer_z4CA", "summary": "The paper proposed a memory efficient approach to approximate a matrix $A$ by: low-rank approximation $A=LR$ and quantization. The LPLR algorithm first applies a quantized random projection (RP) as the $L$, and then solve a minimization problem for the right loew-rank factor $R$, which is also quantized afterwards. Theoretical approximation error is obtained and compared with an alternative approach that quantized SVD low rank factors instead of RP. Experiments are conducted on image approximation and embedding classification, to show the effectiveness of the proposed method.", "questions": "1. Proposition D.1 only bounds the error between $Q(Sx)$ and $Sx$. How does it imply $||S^TQ(Sx)-x||^2$ is also a constant?\n\n2. What solver is used to solve Algorithm 1 line 4? This should be clarified. Is closed-form feasible?", "limitations": "NA.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-organized and easy to follow. The theoretical analysis seems rigorous.\n\n2. Experiments on multiple ML tasks and datasets are provided which make the results more grounded.", "weaknesses": "In my understanding, the main idea of the paper is to waive the need to compute the SVD of A, by using random projection (RP) as a surrogate. I have the following concerns and suggestions:\n\n1. At line 220, the authors wrote that the bits per entry for SVD-quant is $O(nd\\sqrt k)$, but in Table 1 and Table 2, it is $O(k\\sqrt{nd})$. Please double check and clarify. Also, the authors simply stated that LPLR is better than SVD-quant in terms of bits per query, which is not true with some n, d, m, k (comparing the results in the table). I suggest the authors to carefully compare the results and state the regimes when LPLR is better, and when it is worse.\n\n2. In the main Theorem 3.2, $\\kappa$ could be negative, right? Is $1-c_4\\sigma_k/\\sigma_{k-1}$ bounded? Or do we need to further assume an eigen gap for this result to hold?\n\n3. I understand that the main usage of LPLR is for matrix (data) approximation, so the first experiments (Figure 1 and Table 3) make sense to me. However, for the second set of experiments on classification, why not directly using $Q(AS)$ (i.e., the quantized random projections)? This saves the storage for W (in other words, we may increase the sketch size m when using Q(AS) only). Some recent references on this include\n\nRandom projections with asymmetric quantization, Li and Li NeurIPS 2019\n\nGeneralization error analysis of quantized compressive learning, Li and Li, NeurIPS 2019 \n\nIndeed, the research on QRP is highly related to this submission, since LPLR essentially does an optimization on W to recover the data from QRP. I suggest to add some discussion on this direction in the paper and some empirical comparisons.\n\n4. Also, if LPLR is used for processing or storing the data for classification or search tasks, it might be inconvenient to handle new data points (e.g., in a streaming setting). Thus, it may not be suitable for such tasks. On the other hand, recently people are using low rank approximation in LLM fine-tuning frequently. Experiments related to fine-tuning language models could be a better application scenario for the proposed method.\n\n5. Some references on similar results are missing. A similar result as in Appendix D that $S^TQ(AS)$ with uniform quantization has approximation error independent of $d$ has been established in [EDEN: Communication-Efficient and Robust Distributed\nMean Estimation for Federated Learning, Vargaftik et al., ICML 2022] (or maybe some even earlier paper) for rotation matrix $S$. This related result should be cited. Also, Eq. (2) is a standard result for uniform stochastic rounding. A reference should be added there.\n\nIn all, I think the paper proposes a simple but intuitive method for low-rank low-precision matrix approximation from QRPs. The idea is clear, the analysis seems sufficient (despite the above and below questions).The experiments can be improved, but the current results on several tasks and datasets are convincing enough to show the effectiveness of LPLR in matrix approximation. For now, I would recommand borderline accept. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe are grateful for the time you spent in reading our paper and writing the review. We address your concerns below. \n\n> $Q(AS)$ for classification\n\nThe works of Li & Li (2019), although related, are different from matrix compression addressed in our work. They study nearest neighbor search by approximating $Ax$ by $Q(AS)Q'(S^Tx)$, where rows of $A$ are datapoints, $x$ is the query vector, and $S$ is a Gaussian sketching matrix.\n\n1. Storage: In Li & Li, in addition to $Q(AS)$, $S$ needs to be stored too, to process an incoming query $x$. So, the storage is $nm$ quantized and $dm$ full-precision (FP) entries. $S$ needs to be stored in FP because incoming $x$ needs to be processed. In contrast, LPLR stores only the quantized entries of $L$ and $R$, i.e., $nm + md$ quantized entries, and $Ax \\approx LRx$. Hence, storage of LPLR is smaller.\n\n2. Computation: In Li & Li, a computation of $S^Tx$ is needed for every query $x$. This requires $md$ FP mults, and computing $Q(AS)Q(S^Tx)$, i.e., $nmd$ quantized mults. In contrast, for LPLR, we compute $LRx$ with $m(n + d)$ mults, which is faster.\n\nNevertheless, we acknowledge that these very interesting works and will definitely cite them.\n\n> Regimes when LPLR is better\n\nThank you for pointing this out. The bit requirement is indeed $O(k\\sqrt{nd})$ for direct-SVD quant., and line 220 is a typo which we will rectify. Tables 1 and 2 represent two distinct regimes. In Table 1, we assume that the $\\ell_2$ -- norm of the $i^{th}$ row of matrix $A$ is bounded by a constant, denoted as $||a^{(i)}|| = O(1)$. Conversely, in Table 2, we consider that each entry of matrix $A$ is bounded by a constant, indicated by $A_{ij} = O(1)$.\n\nFor the scenario described in Table 1, the bit-requirement for direct-SVD is $0.5\\log_2(O(k\\sqrt{nd}))$. Meanwhile, for LPLR, the bit-requirement is $0.5\\log_2(\\tilde{O}(nm/\\sqrt{d}))$, disregarding the logarithmic terms. Evidently, LPLR demands fewer bits than direct-SVD because $k$ and $m$ are much smaller than $min(n,d)$, given that $n$ and $d$ can be substantially larger than $k$ and $m$ for inherently low-rank matrices. In the regime presented in Table 2, the bit-requirement for direct-SVD quantification remains $0.5\\log_2(O(k\\sqrt{nd}))$, unchanged from before. However, LPLR now requires $0.5\\log_2(\\tilde{O}(nm\\sqrt{d}))$, slightly more than direct-SVD due to the additional $\\sqrt{n}$ factor inside the logarithm. Thus, it makes sense to expect that direct-SVD can perform better in this regime.\n\nThis observation is further supported by our numerical simulations in Tables 4 to 6, where direct-SVD indeed outperforms LPLR in certain scenarios. Nevertheless, it is crucial to emphasize that direct-SVD necessitates computing the SVD, which can be prohibitive for very large matrices due to the current memory limitations of available GPUs, making LPLR the only viable option. As discussed in lines 1204 to 1210 of App. K, if our objective is merely to compress an input matrix $A$ without concerning ourselves with the computational effort needed for compression, we can try all compression techniques and choose the one that yields the minimum Frobenius norm error.\n\nThank you for raising this concern and we will definitely add these discussions to our main text.\n\n> Thm. 3.2, $\\kappa$ could be negative?\n\nNo, $\\kappa$ is always positive. Yes, $(1 - c_4\\sigma_k/\\sigma_{k+1})$ can be negative in the statement of Thm. 3.2, but we do not need to assume an eigen gap for this result to hold true. If $1 - c_4\\sigma_k/\\sigma_{k+1} \\leq 0$, we should set $\\kappa = \\kappa(A)$. This is evident from the proof of Lem. E.2 in lines 868 to 873. Our correct expression for $\\kappa$ would be $\\kappa = min(\\kappa(A), \\kappa(A_k)(1 - c_4\\sigma_{k+1}/\\sigma_k)^{-1})$ if $1 - c_4\\sigma_k/\\sigma_{k+1} > 0$, and $\\kappa = \\kappa(A)$, otherwise. Thank you for pointing this out, and we will rectify it in the statement of the theorem.\n\n> Streaming setting & LLM fine-tuning\n\nThis is a very interesting point. It is possible to extend LPLR to streaming data settings using sketching based low-rank approximation. In this regard, LPLR is easier to convert to a streaming algorithm than direct SVD based quantization. A recent work on sketching based streaming low rank approximation is *Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation*, Joel A. Tropp et. al., SIAM Journal on Scientific Computing (2019), url = [https://doi.org/10.1137/18M1201068](https://doi.org/10.1137/18M1201068). Experiments related to fine-tuning large language models is also a potential application scenario we can consider. We will add related discussions on these in App. K.\n\n>  Prop. D.1\n\nNote that: $||S^TQ(Sx) - x||^2 \\leq ||Q(Sx) - Sx||^2 + ||S^TQ(Sx)||^2 - ||Q(Sx)||^2 + ||x||^2 - ||Sx||^2 \\leq ||Q(Sx) - Sx||^2 + ||S^TQ(Sx)||^2 + ||x||^2 \\leq ||Q(Sx) - Sx||^2 + {\\rm R}^2(\\sigma^2_{max}(S) + 1)$.\n\nWe know that $\\sigma^2_{max}(S) \\leq \\frac{d}{m}$ with high probability for Gaussian $S$. The error only depends on the aspect ratio $d/m$, and not $d$ directly. Although we provide the above justification as a response to the question, in LPLR we do not explicitly compute the $S^TQ(AS)$ anywhere. The effect of sketching $AS$ in the first low-rank factor are nullified by the second low-rank factor.\n\n> Solver for $W$\n\nYes, the solution of this problem is available in closed-form as $W^* = Q(AS)^{\\dagger}A$, used in the analysis and also in the numerical simulations. We prefer to keep the general form in line 4 of Alg. 1 because one use an approximation of $W^*$, obtained using conjugate gradient descent, instead of the closed form expression.\n\n> Missing references\n\nThank you for pointing out this nice work by Vargatik et. al. (2022). We have discussed the literature related to this in Sec. 1.1 (lines 76 to 84), which includes the work DRIVE [67], by the same set of authors. We will add the new reference to the list as well."}, {"review_id": "EyPyWLrlJ8", "reviewer": "Reviewer_WupA", "summary": "The paper studies compression of low-rank matrices by simultaneous low-rank factorization and quantization. It proposes a method that first quantizes the randomized rangefinder as the first low-rank factor and then quantize the minimizer of reconstruction error with respect to the remaining factor as the second. Randomized rangefinder uses random Gaussian matrix which possesses the equalization property to maintain low quantization error, compared to naïve quant. Experiments are provided to demonstrate the benefits of the proposed algorithm.", "questions": "1. what is the difference between LPLR and LPLR-SVD in experiments?\n2. Accuracy seems to decrease with bits for some cases in experiments. Why?", "limitations": "No limitations are addressed in the paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. provide a low rank factorization algorithm that come with quantization for further reducing memory footprint.\n2. experiments demonstrate the advantage of the algorithm.", "weaknesses": "1. experimental settings should be made clearer. the current description is a bit confusing. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe are grateful for the time you spent in reading our paper and writing the review. We address your concerns below:\n\n> Difference between LPLR and LPLR-SVD in experiments\n\nLPLR refers to our main algorithm in Alg. $1$, in which the left low-rank factor is $Q(AS)$, where $S$ is the Gaussian sketching matrix. On the other hand, LPLR-SVD computes the left low-rank factor as $Q(U_kS)$, where $U_k$ is the matrix of top-$k$ singular vectors. Obtaining $U_k$ requires computing the SVD of the matrix which can be computationally prohibitive. LPLR-SVD is described in footnote $1$ on page $9$, and also in lines $111$ to $117$. LPLR-SVD is analyzed in detail in Appendix $I$.\n\n> Accuracy seems to decrease with bits for some cases in experiments.\n\nIn cases where accuracy increases with decreasing number of bits, we believe that the quantization noise adds an inherent regularization effect. This conjecture is worth exploring in detail and we have acknowledged this in Appendix $K$ (lines $1211$ to $1215$).\n\n> No limitations are addressed in the paper.\n\nWe have mentioned some limitations and further discussions in Appendix $K$.\n\n> Experimental settings should be made clearer. the current description is a bit confusing.\n\nWe would be extremely grateful if you could kindly indicate any sections that require further clarity. We are more than willing to provide explanations and make any necessary edits. Furthermore, we have also done additional experiments which have been added to our global response, along with corresponding discussions."}, {"review_id": "XGPRQ8V56E", "reviewer": "Reviewer_L5cK", "summary": "The authors investigate combining low-rank matrix factorization and (uniform scalar) quantization.\nThrough theoretical analysis and experiments they demonstrate that this can yield much higher accuracy than directly quantizing the input matrix. One natural choice is to compute the SVD of the matrix and quantize the two factors independently. It's shown that quantizing the left factor first and then computing a new right factor that best approximates the input when multiplied with the quantized left factor yields much better result. The choice of SVD is not critical and could be replaced by randomly mixing the columns of the input matrix, i.e. random sketching. In fact sketching has provable benefits as the entries of sketched matrices are bounded with very high probability. This bounded range improves quantization theoretically. The authors prove several theorems (their proofs are in the extensive appendix) and conduct detailed empirical evaluation.", "questions": "1) Line 226 and Theorem 3.2: For (1+eps') relative Frobenius error approximation LPLR requires m=O(k/eps') >> k columns, which the text seems to overlook. Could you please discuss?\n2) Table 3: Could you also add LSVD to this experiment too? DSVD's Frobenius error is always the same 0.496, and LPLR's error is the same  the bottom of the table, when the bit budget is doubled, as in the top of the table. Could you discuss why? What was the rank (k) of DVSD, was it the same as m of LPLR? I.e. could you make Rank column header precise?\n3) Matrix entries are typically rescaled to [0,1] before quantization as it's cheap to store their min/max (or some very low/high quantiles), even for each row (or column) of a matrix. How would such rescaling change your theoretical and empirical results?\n\n4) Line 77: Sx -> x\n5) Table 1, row of LPLR: delta is undefined\n6) Lines 219-222: missing log2(), 4 times\n\n", "limitations": "Yes, limitation section is adequate.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) All the key ideas of the paper (low-rank approximation, sketching) are sound.\n2) Detailed theoretical analysis with rigorous proofs.\n3) Extensive experiments.\n4) Compression of neural network weights and embeddings via low rank approximation and quantization are popular and impactful topics both to reduce memory usage and to speed up training and inference.\n", "weaknesses": "1) Neither the ideas nor the analysis are particularly inventive in my opinion. It's self evident that optimizing the second factor after quantizing the first (LSVD) is superior to independent quantization (DSVD), in fact the process could be iterated further. While I appreciate the 30+ pages of proofs provided by the authors it seems as if they rely on chaining known results and techniques for sketching and random matrices combining with patient algebra.\n2) Despite its seemingly weaker theoretical bounds LSVD is always one of the most accurate method in the experiments (see Tables 4-7). This is also clearly highlighted by the authors in the limitations section. \n3) Quantization aware training (not considered in the paper) is highly likely to produce equivalent or better results.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for the time you invested in reading our paper and writing the review. We appreciate that reviewing is a voluntary effort and below, we address each of your concerns to resolve your queries.\n\n> $1 + \\epsilon'$ relative Frobenius error approximation LPLR requires $m=O(k/\\epsilon') \\gg k$\n\nIndeed, increasing the sketch size $m$ leads to a reduction in the relative error concerning the best rank-$k$ approximation, denoted as $||A_k - A||_F^2$. However, it is crucial to consider that low-rank approximations of a matrix are valuable only when the matrix is inherently low-rank approximable, i.e., $||A_k - A||_F^2$ is already sufficiently small to begin with (and precisely zero if $A$ has a rank less than $k$). In such cases, selecting the sketch size $m$ to be slightly larger than $k$, such as $m = k + p$, where $p \\geq 2$ is the oversampling factor, ensures that $\\delta$ does not become arbitrarily large. Consequently, the additional approximation error introduced by sketching, denoted as $\\delta||A_k - A||_F^2$, is of the same order of magnitude as the best rank-$k$ approximation error. This observation aligns well with practical applications where low-rank approximations of matrices are beneficial. The impact of the oversampling factor $p$ has been extensively studied in previous works, for example, see references [16] and [74]. Moreover, from a theoretical perspective, the relative error can be improved to $(1 + \\delta)^{1/(2q + 1)}$ with $q$ power iterations, though this comes at the expense of increased computational complexity. In our numerical simulations, we have chosen the value of $m$ to ensure that given the values of $B$ and $B'$, the number of parameters being quantized results in a total bit requirement that achieves parity with the naive quantization benchmark.\n\n> Matrix entries are typically rescaled to [0,1]\n\nWe have taken into theoretical account this specific scenario in Table 2, where we make the assumption that each element of the matrix adheres to $A_{ij} = O(1)$. This is achieved by appropriately adjusting the scale of the matrix entries. In our image compression experiments, we have also practically accounted for this rescaling, as we are aware that pixel values within images fall within the range of 0 to 255.\n\nIt's crucial to emphasize the contrast between the scenarios depicted in Tables 1 and 2. In Table 1, we make the assumption that the matrix's rows are normalized, denoted as $||A^{(i)}|| = O(1)$. This assumption is particularly relevant when performing nearest neighbor classification, where each row of $A$ represents an embedding vector. In this context, scaling the norm doesn't alter the cosine similarity, which is why this normalization is appropriate.\n\n> Accuracy of LSVD\n\nIndeed, in Tables 4 to 7, LSVD stands out as one of the accurate methods. This should not be interpreted as a drawback; instead, it serves as a valuable insight. In fact, even theoretically, LSVD does not have weaker bounds than LPLR (cf. Thm. I.1 vs. Thm. 3.2) -- there's no $(1 + \\delta)$ factor present for LSVD. LSVD precisely calculates the left low-rank factor as $Q(\\widetilde{U}_k)$, where $\\widetilde{U}_k \\in \\mathbb{R}^{n \\times k}$ is derived from the first $k$ columns of $U\\Sigma$. This requires computing the SVD of $A$, which is computationally intensive. On the other hand, LPLR delivers comparable performance to LSVD while demanding significantly less computation. When computing the SVD is practical, LSVD is as a strong contender and deserves consideration as an option. However, in cases where matrices become exceedingly large and SVD computation becomes infeasible, LPLR offers a viable solution to overcome this limitation. We discuss this in lines 1204 to 1210 of App. K.\n\n> Quantization aware training\n\nWe are not really sure what is meant by quantization-aware training (QAT) in the context of low-rank approximation for matrix compression. For training a neural network, QAT adds quantize/de-quantize nodes, and treats the quantization loss as part of the training loss. Subsequent fine-tuning of the parameters makes the model more resilient. For QAT in matrix compression, did you mean treating $L$ and $R$ as functions of some trainable hyper-parameters, which are subsequently optimized? If so, yes, it could possibly decrease the approximation error, at the cost of additional computation (which can potentially be prohibitive).\n\n> Neither the ideas nor the analysis are particularly inventive in my opinion.\n\nWe believe that the simplicity of our algorithm adds to its appeal and makes it a valuable contribution to the literature, bridging the fields of matrix compression, quantization, and sketching while ensuring compatibility with upcoming hardware developments. Embracing simplicity and clarity can play a crucial role in achieving scalability and facilitating future adaptability. Additionally, such basic principles serve as foundational building blocks that can be further optimized to support more sophisticated developments.\n\nWe propose an idea which is simple in its execution and pragmatic in its implementation. Our idea is well supported for modern linear algebra libraries, while offering theoretical analysis to effectively identify the regime in which it offers value over conventional, standard methods. Moreover, our method offers a tunable knob to achieve effective bit-rates in software, not currently supported by hardware. For example, in Table 3, using LPLR with appropriate parameters bits is equivalent to operating at 1 or 2-bits per pixel, despite hardware working with a higher bit precision. Moreover, our method is adaptable to future hardware advancements, such as the emergence of 4-bit GPUs, which can significantly speed up our technique's primitive operations. \n\n> Table 3:\n\nWe have rectified this in the last point in global response (and Table 1 of the PDF). Rank column refers to sketch size $(m)$ for LPLR and target rank $(k)$ for DSVD or LSVD."}, {"review_id": "5msOVKQA8s", "reviewer": "Reviewer_ipPc", "summary": "This paper introduces a novel low-rank matrix factorization algorithm that is using sketching matrix idea and quantization, such as they do:\n\n1. Use Gaussian RV to generate sketch of the matrix and compute the approximate basis\n2. Use Quantization with Q - to get Q(AS)\n3. Use Q(AS) and Q' to get  Q'(W)\n4. Return Q(AS) and Q'(W)\n\nAuthors provide theoretical and numerical analysis of their idea.", "questions": "Table 1 & 2  is a bit puzzling me - it seems that Approximataion Error of Naive Uniform is smaller than LPLR and with cheaper computation cost. Do you think that you can clarify in the table itself  - why LPLR is better ? because it seems to be confusing in the first glance.", "limitations": "The are many sketching / matric factorization algorithms, i am puzzled why we only presented Naive Uniform and Direct SVD algorithms as comparison points.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- introduction section written very well & and very informative and to the point, such as introducing LPLR algorithm briefly, talking about Low-rank approximation and Randomized quantization.\n\n- the introduced algorithm clearly communicated and results are theoretically sound.", "weaknesses": "- Abstract seem to be a bit wordy - it would be nice if there were formulations and numbers that grabs readers attention with resutls.\n\n- i like the way motivating the work - with memory constraints - but i am curious is there any application in real life for low rank decomposition that actually saves memory. some examples would be good\n\n- the paper doesn't exactly introduce a new direction - rather seems to be using existing ideas and put them together.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe are grateful for the valuable time you spent in reading our paper and writing the review. We value the fact that the review process is a voluntary endeavor, and in the sections below, we tackle each of your concerns to address and clarify your questions.\n\n> Table 1 & 2 is a bit puzzling me\n\nTables $1$ and $2$ present the approximation error guarantees for three different compression methods: $\\rm (i)$ naive quantization with an error of $\\epsilon$, $\\rm (ii)$ direct SVD with an error of $\\lVert \\mathbf{A}_k - \\mathbf{A} \\rVert_F^2 + \\epsilon$, and $\\rm (iii)$ LPLR with an error of $(1 + \\delta)\\lVert \\mathbf{A}_k - \\mathbf{A} \\rVert_F^2 + \\epsilon$. At first glance, it might appear that naive quantization is always superior to LPLR since the latter contains additional terms in the approximation error. However, it's crucial to consider that naive quantization also demands more bits than LPLR.\n\nWhile we do not claim that LPLR will consistently outperform naive quantization, LPLR exhibits better performance when dealing with matrices that are inherently low-rank to begin with. In the case of low-rank matrices $\\mathbf{A}$, the first term, $(1 + \\delta)\\lVert \\mathbf{A}_k - \\mathbf{A} \\rVert_F^2$, representing the error of the best rank-$k$ approximation, is very small (and becomes zero if $\\mathbf{A}$ is precisely rank $k$). In such scenarios, both naive quantization and LPLR yield an approximation error of $\\epsilon$. However, LPLR achieves this error with fewer bits compared to naive quantization. On the other hand, for matrices that are close to full rank, i.e., with singular values decaying slowly, the term $\\lVert \\mathbf{A}_k - \\mathbf{A} \\rVert_F^2$ will not be negligible. In other words, given the same bit-budget, LPLR can achieve a lower level of error compared to naive quantization. We will highlight this in the caption of the tables.\n\n> Why only presented Naive Uniform and Direct SVD algorithms as comparison points.\n\nIn this study, we have focused on matrix factorizations that are well-suited for achieving low-rank approximations. To obtain the best rank-$k$ approximation for a given matrix $\\mathbf{A}$, we first compute the Singular Value Decomposition (SVD) and then retain the top-$k$ singular values along with their corresponding singular vectors. When considering both low-rank and low-precision requirements, SVD + quantization emerges as a natural benchmark. On the other hand, for matrix quantization, the standard practice is to use naive uniform quantization due to its simplicity. Although other matrix factorizations like $\\mathbf{QR}$ or $\\mathbf{LU}$ decompositions also provide low-rank approximations, they are suboptimal compared to the SVD-based low-rank approximation method (which is optimal). Hence, they are not expected to outperform direct-SVD when combined with a naive application of uniform quantization. Moreover, concerning matrix compression, it is essential to achieve parity in terms of bit-requirements among various benchmarks for a fair comparison. To accomplish this, direct-SVD, LPLR, and LSVD offer tunable parameters, which can be adjusted. These parameters include the target rank $k$ and the sketch size $m$, which allow us to control the compression ratio and maintain the desired parity.\n\n> Application in real life for low rank decomposition that actually saves memory\n\nLow rank decomposition has found a contemporary use in conserving memory, particularly in compressing neural networks. Besides the sources cited in the initial passage, additional references include:\n\n1. Y. Idelbayev and M. Á. Carreira-Perpiñán, \"Low-Rank Compression of Neural Nets: Learning the Rank of Each Layer,\" CVPR, 2020.\n2. T. N. Sainath, B. Kingsbury, V. Sindhwani, E. Arisoy and B. Ramabhadran, \"Low-rank matrix factorization for Deep Neural Network training with high-dimensional output targets,\" ICASSP 2013.\n\nThe importance of compressing neural networks stems from several factors, including the need to decrease memory usage, enhance inference speed, and facilitate deployment on devices with limited resources. Low rank decompositions play a pivotal role in achieving these goals by breaking down the initial weight matrices into smaller, organized matrices with fewer parameters.\n\n> The paper doesn't exactly introduce a new direction\n\nWe propose an idea which is simple in its execution and pragmatic in its implementation. Our idea is well supported for modern linear algebra libraries, while offering theoretical analysis to effectively identify the regime in which it offers value over conventional, standard methods. Moreover, our method offers a tunable knob to achieve effective bit-rates in software, not currently supported by hardware. For example, in Table $3$, using LPLR with appropriate parameters bits is equivalent to operating at $1$ or $2$-bits per pixel, despite hardware working with a higher bit precision. Moreover, our method is adaptable to future hardware advancements, such as the emergence of $4$-bit GPUs, which can significantly speed up our technique's primitive operations. We believe that the simplicity of our algorithm adds to its appeal and makes it a valuable contribution to the literature, bridging the fields of matrix compression, quantization, and sketching while ensuring compatibility with upcoming hardware developments.\n\n> Abstract seem to be a bit wordy\n\nWe appreciate your input on improving the abstract's appeal to readers. We concur with the idea of emphasizing the main outcomes derived from Tables $1$ and $2$, which involve contrasting our novel algorithm with other benchmarks. This contrast could be established through aspects like computational complexity (e.g., highlighting the ${\\rm O}(ndm)$ of LPLR in contrast to the ${\\rm O}(nd^2)$ of direct SVD quant.). Moreover, we intend to incorporate specific numerical results obtained from our simulation efforts."}, {"review_id": "HPvobsAh87", "reviewer": "Reviewer_2AWv", "summary": "This work studies the problem of computing a low rank approximation when the low rank factors are under a bit budget constraint, that is, we must output factors L and R with bounded bits such that LR approximates a given input matrix A in the Frobenius norm. The authors show that by incorporating sketching into the quantization procedure, one can get improved bounds, due to the fact that a Gaussian sketch can “flatten” the entries of a vector, which is advantageous when rounding (Appendix D). Empirical results show that this algorithm indeed gives improved results over other naive implementations such as directly rounding SVD factors. ", "questions": "* Should put A \\approx LR in the abstract\n* Some of the references in the Related Works section for Low-rank approximation seem inappropriate for the context. Candes-Tao and Recht et al are not focused on faster algorithms for SVD, but rather a related but different problem of matrix completion. Gradient descent on the low rank factors is indeed one way to solve approximate SVD, which I agree Zhang et al captures, but there may be more appropriate references such as https://arxiv.org/abs/2106.14289 and references within.\n* Line 58: you should first establish that n >= d, or else the SVD time should be O(min{nd^2, dn^2})\n* Typo (line 77): should be “instead of quantizing x directly”\n* Is the randomized rounding in Section 2.1 necessary? Can you get better results with naive rounding?\n* Line 177: what do you mean by “saturated” and “unsaturated”? Please define this term, it is unfamiliar to non-experts.", "limitations": "Discussion of limitations is limited. This work is mainly theoretical, and there are no potential negative societal impacts.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of efficiently quantizing low rank approximations is an extremely important problem given that both low rank approximations and low precision is gaining popularity for compressing massive neural networks (https://papers.nips.cc/paper/2020/file/13b919438259814cd5be8cb45877d577-Paper.pdf, https://arxiv.org/abs/2302.03764). This work offers an interesting new method which takes advantage of the “flattening” property of Gaussian sketches in order to obtain improved results for quantization in the context of low rank approximation. This idea is conceptually simple yet interesting. Empirical results are also convincing.", "weaknesses": "The contribution is already quite nice, but there are several followup investigations that could strengthen this work much more:\n* Are there any lower bounds on the trade-off between the approximation accuracy and the bit budget?\n* There are structured sketching transforms such as the Subsampled Randomized Hadamard Transform (see Theorem 2.4 of http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/wNow3.pdf) which also have the “equalizing” or “flattening” type of behavior, yet can be applied in much faster time, and furthermore also save on the storage of the sketching matrix since it is an integer matrix. Can this be used to get faster implementations in theory/practice? \n* Can you report the running time of the experiments?\n* Can you comment on whether the bit bounds imply actual savings in the memory usage, or are the practical implementations of bit complexity too crude to capture these improvements? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for reading our paper and writing the review. We hold in high regard the voluntary nature of the review process, and in what follows, we engage with your concerns.\n\n> Structured sketching\n\nWe agree that SRHT sketch also have an equalizing effect, and can indeed lead to faster algorithms to compress a matrix than computing a Gaussian sketch, as Hadamard transform can be computing recursively. We experimented with SRHT but decided not to include the results in our paper for two reasons:\n\n1. SRHT sketch did not perform better than LPLR with a Gaussian sketch in terms of Frobenius norm error.\n2. We have done our theoretical analysis with Gaussian sketch.\n\nMore importantly, computing the sketch $AS$ is not the most time-consuming step. Solving the minimization problem $argmin_W ||ASW - A||_2^2$, either in closed form or with conjugate gradient descent, is the slowest step. Furthermore, once the low-rank factors $L$ and $R$ are found, only these factors are stored, and not the sketching matrix. We will add a discussion relation to this in App. K as well.\n\n> Lower bounds on the trade-off\n\nThis is a very interesting question. It might be possible to derive lower bounds on this tradeoff using covering and packing arguments for the space of all rank-$k$ approximations of a matrix. Such lower bounds are non-trivial and we will mention this in App. K.\n\n> Do bit bounds imply actual savings?\n\nPractical applications of quantization for hardware storage often necessitate working within specific bit budgets, such as 16-bit or 32-bit precision. With this in mind, when implementing our algorithm LPLR in practical contexts, we set values for variables $B$ and $B'$ to align with these hardware precision limitations. Subsequently, the parameter sketch size $m$ becomes an adjustable parameter, allowing us to regulate the compression of the total parameter count, denoted as $(n + d)m$. Given that the total parameters in matrix $A$ amount to $nd$, we show that for sufficiently low-rank matrices, it is feasible to choose $m$ in a manner such that $Bnm + B'md = B_{nq}nd$, where $B_{nq}$ can be as minimal as $1$ bit. This implies that $B_{nq}$ can take on values that are unattainable owing to the inherent hardware limitations.\n\nMoreover, in other scenarios where implementations of bit complexity need not be too crude, the quantization codebook can be customized beyond the confines of non-traditional hardware limitations, we are not restricted solely to the choices of $B$ and $B'$. For instance, when transmitting a matrix over a communication channel, we can employ modulation techniques like amplitude or frequency shift keying. This enables us to use $B = B' = 2$, effectively achieving $4$ quantization levels ($2^2$). Considering that a greater number of amplitude or frequency levels necessitate larger channel resources, the bit bounds derived in our paper reveal the potential for conserving these resources in such situations.\n\n> Randomized vs. naive rounding\n\nRandomized rounding, also known as uniformly dithered quantizer, is preferred due to its ability to produce an unbiased estimate of the input. Dithered quantizers offer an advantage by introducing a non-zero probability of quantizing an input to either its ceiling or floor, resulting in reduced variance when averaging multiple independent realizations. Moreover, the unbiased nature of the quantizer output simplifies the analysis. In our experiments, we did not observe any benefits of using deterministic rounding instead of dithered rounding.\n\n> Saturated and unsaturated quantizer\n\nThe dynamic range of a scalar quantizer is defined to the the interval $[-{\\rm R}, +{\\rm R}]$ as defined in Sec. 2.1. If the input $x$ to the quantizer falls outside this range, i.e., $x > {\\rm R}$ or $x < -{\\rm R}$, the quantizer is said to be {\\it saturated}. We want $\\rm R$ to be sufficiently large so that $-{\\rm R} \\leq x \\leq {\\rm R}$ is satisfied, so that the quantizer is {\\it unsaturated} and the quantized output is an unbiased estimate of the input with bounded variance. We will define this in the main paper.\n\n> Runtime of the experiments\n\nPlease refer to the global response (specifically Table 2 and Fig. 3). In Table 2, we compare the wall-clock CPU time for computing the low-rank quantized factors of CIFAR-10 and CIFAR-100 datasets via LPLR, LSVD and DSVD. Each image embedding forms a row of the input matrix, with low rank factors computed for *each* class of the input dataset. It is evident that LPLR significantly outperforms DSVD and LSVD in terms of speed. \n\nFig. 3 complements the tabulated data by visualizing the runtime involved in two scenarios. The first scenario involves computing the matrix-vector multiplication $\\bf Ax$ directly. The second scenario involves approximating this multiplication using a low-rank factorization, specifically $\\bf L(Rx)$, where matrices $\\bf L$ and $\\bf R$ are tall and wide matrices, respectively. This low-rank factorization strategy reduces the overall number of multiplications from $nd$ to $(n+d)m$.\n\n> Misc typos\n\nThank you for pointing them out. We will proofread and rectify them."}]

Author rebuttal:
Dear Reviewers, 

We greatly appreciate the time you invested in reviewing our paper and sharing your concerns. As part of the global response, we have included deliberations regarding the scenarios in which LPLR demonstrates its practical utility and potential advantages over established baselines. Furthermore, we report additional experimental evaluations pertaining to image compression, along with wall-clock runtimes for LPLR and alternative baselines. 

**Comparison between LPLR and baselines**: In Tables 1 and 2, we have compared LPLR with other benchmarks. In the column denoting approximation errors, aside from the common quantization error $\epsilon$ present across all rows, DSVD and LPLR introduce an additional term representing the error from low-rank approximation. Consequently, it might appear that naive quantization consistently outperforms these methods. However, it's essential to recognize that compression techniques based on low-rank factorization hold value exclusively when the matrix being compressed is inherently low-rank, meaning that $\lVert \mathbf{A}_k - \mathbf{A} \rVert_F^2$ starts off as small. If $\lVert \mathbf{A}_k - \mathbf{A} \rVert_F = 0$, LPLR can achieve identical error levels as naive quantization, while demanding fewer bits than the latter. In other words, given the same bit-budget, LPLR can achieve a lower level of error compared to naive quantization.

**Computation-constrained compression**: In situations where computational resources are limited, employing the naive strategy emerges as the most cost-effective approach for matrix quantization. Nevertheless, due to its failure to capitalize on a matrix's inherent low-rank arrangement, naive quantization may prove considerably suboptimal. As matrices increase in dimension, accommodating them in memory becomes impractical, rendering approaches like DSVD or LSVD unviable. In such scenarios, our LPLR method stands as a viable alternative, demanding slightly more computational effort than naive quantization, yet capable of harnessing the low-rank structure for improved approximation accuracy.

**Compression without any computation constraint**: If there is no scarcity of computation resources in being able to compute the SVD, it is possible to compress the matrix with all the strategies, and choose the best one.

**Benefits beyond compression**: A low-rank and low-precision factorization $\mathbf{A \approx LR}$ also enables us to approximate the matrix-vector product $\mathbf{Ax}$ by $\mathbf{L(Rx)}$, which can be computed much faster as $\mathbf{L}$ and $\mathbf{R}$ are tall and thin matrices. This is shown in Fig. 3 of the PDF.

**Clarification to Table 3 of the main paper**:  Regarding the low-rank methods, namely Direct SVD and LPLR, we identified (and fixed) a software bug in the parameter enumeration code, which led us to mistakenly assess all outcomes under a fixed sketch size equivalent to a rank of 200. This caused a lack of parity with respect to the bit requirement for naive quantization, and the comparison was unfair. Consequently, the Frobenius norm values appeared relatively steady; the slight variance in LPLR stemming from distinct samples of the sketching matrix. We sincerely apologize for this error and present revised outcomes in Table 1 of the global response PDF, now encompassing a significantly broader range of bit budgets.

In Table 1, we assess the performance of LPLR, Direct SVD, and LSVD across a uniform range of bit budgets (including many that are not hardware primitives). This approach enables a more comprehensive examination of the approximation error and its variability when employing different low-rank approximation techniques with varying bit budgets. One can clearly observe that LPLR and LSVD (LPLR-SVD) outperform naive quantization for $1$ -- bit quantization, except in the extreme instance of ${\rm B} = 32$. This trend persists even as bit budgets increase. For higher bit allocations, the superiority of LPLR (and LSVD) over NQ in terms of approximation error is apparent when the bit allocation $\rm B$ is sufficiently low. This allocation strategy permits a greater allocation of storage to capturing higher-rank components. This delicate balance lies at the core of leveraging the effectiveness of LPLR, which excels in finding the optimal compromise between capturing the optimal number of low-rank factors with precision. We hope that this clarifies the rationale behind the scenario in which LPLR outperforms standard techniques, namely naive quantization.

Meta-review: The reviewers unanimously recommended acceptance of this paper since it contributes a nice and simple solution to the important problem of matrix compression via low-rank approximation and quantization. The paper is well-executed and well-written.

We encourage the authors to take the reviewers' various suggestions into account when revising the paper. Notably, a reviewer noticed a bug in the experiment results, which requires updating to revised results. 

The AC also would like to point out a minor presentation issue: one should never write log_2(O(f(params)). O(f(params)) is a statement about the asymptotic growth rate of f with respect to params. It is not a numerical quantity that you can take the log of. It would be acceptable to write log_2(c*f(params)) for some sufficiently large constant c, or something similar.
Decision: Accept (poster)