Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
Authors: Yi Li
Honghao Lin
David Woodruff
Venue: ICLR 2024 poster (2024)
Keywords: Sketching
Residual error
Low-rank approximation
sparse recovery
Primary area: optimization

Abstract: We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more expensive low-rank approximation computation will be. The matrix case concerns the Frobenius norm and the task is to approximate the $k$-residual $\|A - A_k\|_F$ of the input matrix $A$ within a $(1+\epsilon)$-factor, where $A_k$ is the optimal rank-$k$ approximation. We provide a tight bound of $\Theta(k^2/\epsilon^4)$ on the size of bilinear sketches, which have the form of a matrix product $SAT$. This improves the previous $O(k^2/\epsilon^6)$ upper bound in (Andoni et al. SODA 2013) and gives the first non-trivial lower bound, to the best of our knowledge. 
In our algorithm, our sketching matrices $S$ and $T$ can both be sparse matrices, allowing for a very fast update time. 
We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. 

For the vector case, we consider the $\ell_p$-norm for $p>2$, where the task is to approximate the $k$-residual $\|x - x_k\|_p$ up to a constant factor, where $x_k$ is the optimal $k$-sparse approximation to $x$. Such vector norms are frequently studied in the data stream literature and are useful for finding frequent items or so-called heavy hitters. We establish an upper bound of $O(k^{2/p}n^{1-2/p}\operatorname{poly}(\log n))$ for constant $\epsilon$ on the dimension of a linear sketch for this problem. Our algorithm can be extended to the $\ell_p$ sparse recovery problem with the same sketching dimension, which seems to be the first such bound for $p > 2$. We also show an $\Omega(k^{2/p}n^{1-2/p})$ lower bound for the sparse recovery problem, which is tight up to a $\mathrm{poly}(\log n)$ factor.

Published as a conference paper at ICLR 2024
OPTIMAL SKETCHING FOR RESIDUAL ERROR ESTIMA- TION FOR MATRIX AND VECTOR NORMS
Li
Honghao Lin, David P. Woodruff
Nanyang Technological University yi vili@ntu. edu.8g
Carnegie Mellon University (honghaol, dwoodruf) @andrew. edu
ABSTRACT
We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more expensive low-rank approximation computation will be. The matrix case concerns the Frobenius norm and the task to approximate the k- residual ||A A& of the input matrix A within (1 + é =ffactor,, where A& is the optimal rank k approximation. We provide a tight bound of e O(k²) /E*) on the size of bilinear sketches, which have the form of matrix product SAT. This improves the previous O (10 upper bound in (Andoni et al. SODA 2013) and gives the first non-trivial lower bound, to the best of our knowledge. In our algorithm, sketching matrices S and T can both be sparse matrices, allowing for a very fast update time. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work.
For the vector case, we consider the fy-norm for p > 2, where the task is to approximate the k-residual ||. øsllp up to a constant factor, where Fy the optimal k-sparse approximation to Such vector norms the data stream literature and are useful for finding frequent items or so-called heavy hitters. We establish an upper bound of (l.2/Pn, 1-2// poly ploy n)) for constant e on the dimension of a linear sketch for this problem. Our algorithm can be extended to the E, sparse recovery problem with the same sketching dimension, which seems to be the first such bound for p > 2. We also show an O(kk/Pn 1 22rr) lower bound for the sparse recovery problem, which is tight up to poly(log n) factor.
frequently studied in
INTRODUCTION
Low-rank approximation is fundamental task for which, given m matrix A, one computes a rank-k matrix B for which ||A- B is small. This works well in practice since it is often the case that matrices are close to being low rank, and only have large rank because of small amount of noise. Also, B provides a significant compression of A, involving only (m + +n)h parameters (if B is represented in factored form) rather than mn, which then makes it quicker compute matrix-vector products and so on.
However, computing a low-rank approximation can be expensive if m and are large. While there exist fast sketching techniques, see, e.g., (Woodruff, 201 2014a), such techniques would still require ((k(mm + v))) memory even to write down the output B in factored form, and a stronger lower bound of Q(k(m + r=) exists in the data stream model (Clarkson & Woodruff, 2009), even if the rows or columns appear in order (Woodruff, 2014b). Here the desired accuracy, so one should have 1|A-B|| B| < (1 + -ell As Ir. where A₃ is the best rank approximation to A in Frobenius norm. ||
Given that it is expensive both in time and memory to compute a low-rank approximation, it is natural to first ask if there is value in doing so. We would like || B] to be as small as possible, and much less than || F so that accurately represents A. One way to do this is to try to first estimate the residual error of A Ax which potentially one can do with an amount of memory depending only on and e. Indeed, this is precisely what (Andoni & Nguyen, 2013) show, namely, that by computing sketch SAT,, where S and T are random Gaussian matrices each with small dimension OkkE²)), ignoring logarithmic factors, that AT) - (SAT)& = (1 + E) |) A ll p. Note that it is important that S and T' do not depend on A itself, one may not have access the parts of

---

Published as a conference paper at ICLR 2024
A in stream needed when applying S and T, or A may be distributed across multiple servers, etc. That is. S and are said to be oblivious sketches, which is the focus of this paper. Thus, with only O(k2/E9) memory words in stream, one can first figure out if it is worthwhile to later compute low-rank approximation to A.
There several weaknesses the above result. First, it is unclear if the O(k/e9) dimension bounds are tight, and optimizing them is especially important for small e. Can the upper bound be improved? Also, the only known lower bound on the small dimension of sketches S and T and even when one requires an estimator of the form [I())T) - (S AT)) | as far as we are aware, is S2(k: + 1/=²). This follows from both S and T needing to preserve rank and preserve the norm of fixed vector. Such a lower bound is even more unclear if we are allowed an arbitrary recovery procedure f(S. T", SAT). Second, the running time is not ideal, as each entry of A in the stream needs to be multiplied on the left and right by dense Gaussian sketches
Residual error not only useful concept for matrices, but can capture how useful a sparse approxi- mation is for vectors, which is the standard way of compressing vector using compressed sensing. In this case, one would like to compute sketch S x of an underlying n-dimensional vector x so that one can output a k-sparse vector 2 for which || dllp S (I e)| =xllp. where 2i is the best k-sparse approximation to z, namely. the vector formed by taking the coordinates of x of the largest absolute value. Here ||=||p = (Ei= [2 is the vector p-norm. Just like for low-rank approximation, one could ask if it is worthwhile to compute é, and that can be determined based on whether || - z&slp. is small. This is also useful in the data stream literature, and is referred to as the heavy hitters estimation problem with tail error, and p > 2 enables to find heavy hitters that are even "less heavy" than those for lz, see, e.g., (Berinde et al., 2010), or residual heavy hitters, see, e.g., Section 4 of (Harvey et al., 2008) for applications to entropy estimation in stream as well as (Indyk, 2004) for applications to computational geometry in a stream.
For S. p S 2 there are very efficient sketches compute & itself, which are sparse and only involve a sketching dimension of (kk/=²) up to logarithmic factors (Price & Woodruff, 2011). Notably, for the Ep sparse recovery problem where p E (1,2), and we are required to output a vector á, an Okk log(n/k)) lower bound on the sketching dimension holds (Ba et al., 2010; Price & Woodruff, 2011), while if we only need to estimate ||æ - z* llp.. following the idea of (Indyk et al., 2011) where we first perform a dimensionality reduction to poly(k/s) dimensions, one can show that O(k log (k)) measurements suffice, which shows separation between the two problems. Motivated by this, we focus on residual norm estimation for p >> 2, which is choice of that has been the focus of a long line of work on frequency moments in a data stream, starting with (Alon et al., 1999). For such p. it is not even known what the right dependence on and k is, we focus constant e for this problem.
1.1 OUR CONTRIBUTIONS
For residual norm estimation for low-rank approximation by sketches of the form SAT and estimators improve the bound of (Andoni & Nguyen, 2013), showing that
of the form A|SA [S { llr,, both S and T can have small dimension O(k/e²), )), up to logarithmic factors, rather than (kk/²2) Moreover, our sketch can be the composition of CountSketch and a Gaussian matrix (Clarkson & Woodruff, 2013), or use OSNAP (Nelson & Nguyen, 2012) as analyzed by Cohen (Cohen, 2016) to achieve faster runtime or update time in stream. We complement this upper bound with a matching lower bound for bilinear sketches SAT and an arbitrary recovery procedure f(S, T. SAT), where we show that both S and T need to have (2k/=²2) small dimension, matching our upper bound.
For the residual vector norm estimation problem, we in fact design the first sparse recovery al- gorithms, i.e., compressed sensing algorithms, for p > 2, designing a sketching matrix with n² m1-2/pk2/2 poly n) small dimension for recovering the vector è itself. By running a standard sketching algorithm for p-norm estimation in parallel, we can thus estimate || -llp to evaluate the residual cost. We show that least for the sparse recovery problem there is a nearly matching lower bound on the sketching dimension of 2/22/pk2/p, While we do not resolve the sketching dimension of residual norm estimation, lower bound of n 1-2/p follows from previous work Basr-Y et al., 2004) and so a polynomial dependence on n is required.
Finally, we empirically evaluate our residual norm estimation algorithm for low-rank approximation on real data sets, showing that while we achieve similar error for the same sketching dimension, our sketch is 4 to 7 times faster evaluate.
2

---

Published as a conference paper at ICLR 2024
2 PRELIMINARIES
Notation. For an n x matrix A, let A& denote the best rank-k approximation of A and 01 (4) (2(A) 2 ... 2 (A) denote its singular values where min d). We then have ||A A Σi=k+1 of. Given a vector 2 E I", let |ズ|| = ( (2.12)1/ 1/2 denote the p-norm of the vector Let 24 R" denote the best k-sparse vector approximation to such that keep the top coordinates of x in absolute value and make the remaining coordinates O. Let -- next formally define the problems and models consider.
Tk- We
Low-Rank Residual Error Estimation. Given a matrix A E RTxd, our goal is to estimate the rank-k residual error ||A - AR|[ within (1 s) multiplicative factor, where Aş. is the best rank-k approximation to A.
Norm Estimation. In the data stream model, assume there is underlying frequency vector I E 2", initialized to 0", which evolves throughout the course of a stream. The stream consists of updates of the form (i, w). meaning 2; <- I2 + w. At the end of the stream, are asked to approximate f(x) for function f 2n + IR. In our problem, f(x) is the residual 4p Our goal is to estimate this value within
Residual Vector
norm ||
x& lp..
+ E) factor.
èp Sparse Recovery. Rather than estimating the value of || z llp. here our goal is to output s-spas vector & E R" such that || E|Ip (1 + =)] xx
ep Norm Estimation. In the P norm estimation problem, the goal is to approximate |>||p within (1 + s) factor. This problem is well-understood and has space complexity Onn222/p poly(s)), see, e.g., (Andoni et al., 2011; Ganguly Woodruff, 2018). The algorithms for this problem will be used in our algorithm
subroutine.
Next, we review the Count-Sketch algorithm for frequency estimation.
Count-Sketch. We have k distinct hash functions h; [n]] - [B] and an array C of size k B. Additionally, we have & sign functions di [rx] + {-1, 1}. The algorithm maintains C such that C[e, bj -Enhee)= Ty-- The frequency estimation & of r; is defined to be the median of {ge(i) CTC, (e())es
Finally, we mention some classical results regarding singular values. Lemma 2.1 (Extreme singular values of Gaussian random matrices (Vershynin, 2018, Theorem 4.6.1)). Let G be an m x n (m 2 n. Gaussian random matrix of i...d. N(0, 1) entries. holds with probability at least 1 exp(-ct2 that vmm Cyn - S F (G) S (max(C) S ym Cvn+t where C, > 0 are absolute constants.
Lemma 2.2 (Weyl's inequality (Horn & Johnson, 2012, (7.3.13)) Let A, B be matrices with m S n. holds that 0+t5-2 (A B) S a(() + a, for all 1 +. m.
LOW-RANK RESIDUAL ERROR ESTIMATION
In this section, we consider the low-rank error estimation problem where our goal is to estimate the rank-k residual error A A& FF, where Aş is the best rank-k approximation of A.
Lower Bound. We show that for any random S R T Raxt, suppose that with high constant probability we can recover || A+lle within factor of a (1) We must then have that (kk/E2) and -2(k/=²).. Formally, we have the following theorem.
Theorem 3.1. Suppose that for random S Raxn, T E IRaxt, there exists an algorithm A satisfying that A(S, ATT) (1 + e) e) A - AullF F for an arbitrary A E Raxx with high constant probability. Then it must hold that t ((k/=?).
To achieve this, first show 22(k2 2(k) sketching dimension lower bound for general sketching algorithm where the sketch has the form vec(A) where E T=xx² Then we will show that this implies an S2 (EA) lower bound for bilinear sketches. Consider the following two matrix distributions
G eVeB
and
G C+cyEB + co wv
(I)
where
3

---

Published as a conference paper at ICLR 2024
1. G Rk/e'xk is random Gaussian matrix i..d. (0, 1) entries.
2. a is sampled from the distribution of the k-th singular values of a random Gaussian matrix
И E R u, v are uniformly random unit vectors and c is sufficiently large constant. 3. B == Σ anniy where Oi, ui, 02 are sampled from the distribution of the i-th singular values and singular vectors of E xk/ conditioned on its k-th singular value and singular vectors being a, u,
We will first show that any linear sketching algorithm with dimension smaller than O(k2/e2) cannot distinguish the two distributions with high constant probability. To do so, notice that by Yao's 's minimax principle, we can fix the rows of our sketching matrix, and show that the resulting distributions of the sketch have small total variation distance. By standard properties of the variation distance, this implies that no estimation procedure A can be used to distinguish the two distributions with sufficiently large probability. Let L1 and L2 be the corresponding distribution of the linear sketch on D1 and D2 in (1), respectively. Formally, we have
Lemma 3.2. Suppose that the sketching dimension of L1 and L2 is smaller than e, //2//²² for some constant C₁_ Then we have that (Tv S 1/8.
Proof. We first consider the following two distributions.
G and G+ w=
where G E R/ x is a Gaussian random matrix and w E R E R&* are random Gaussian vectors, and 3 is sufficiently large constant. From Theorem of (Li Woodruff, 2016), we have that if the sketching dimension is smaller than cyk²/E², then
drv (Iv)))), / wz )) < 1/10
k
where S(M) is the sketch on M. Let S good C R k/c x be the subset of matrix B where
Pr(a = @(vT/=)) B] 0.99.
We claim that Pr(B E Sgood] 2 0.99. Otherwise, Pr(a & @(VE/e)) 2 Pr(a & @(Vk/e) B & S ggood] Pr[ & S goood] 2 0.01 0.01, contradicting the fact following from Lemma 2.1 that Pr/a & O( O(VT/e)] exp(- exp(=S(k//=2).
Now, fix B E Sgond Recall that a is dependent with B while u, e is independent with B, and combined with the concentration property of the lg norm of Gaussian vector, we get that with probability at least 0.98, we have that / I ||l||2 |al|| ((avE), which implies
drv (TV(S(G + cVEBB, c/EEB + cavE we woT) T)) S 1/9
for such fixed B. Since Pr[B E S Sgood] 2 0.99, from the definition total variation distance we have that drv (C1, C2) < 1/9 + 0.01 < 1/8.
We next show that if we have an algorithm AA that computes a approxxattonni to the rank- (k= residual error, we then can distinguish the two distributions D) and D: in (1) with high probability,
Theorem 3.3. Suppose that for random matrix S E IR= there exists an algorithm A satisfying that A(S, S- vee)(A) (1= Axlle for arbitrary A E Raxn with high constant probability. Then mush hold that s = 12kk2222 2
Proof. By Yao's minimax principle, we may assume that A is drawn from the distributions in (1) and S is deterministic sketching matrix. Note that for both matrix families, the drawn matrix A is rank-k with high probability, and hence the rank 1) residual error of A is equal to its smallest singular value. We shall examine the smallest singular value for the two distributions. If A ~ Di, from Lemma 2.1 and Weyl's inequality (Lemma 2.2), we have that with high probability
Vi
T mmiu (G + //EE)= < o mmax (G) + mmin (c/E)) = Tmax (G) < + +CVE
4

---

Published as a conference paper at ICLR 2024
since B is rank k - 1. On the other hand, when A ~ D2, from the definition of B, a, u, that B + ouv' is also Gaussian matrix and thus + ovE( (B + ouv' is a Gaussian random matrix with entries ( + cf.). Again, from Lemma 2.1, we have with high probability that
Vk min (G eVEB cave. uo uv)) Vi+ -
-
v C2vk,
provided that //22> C2 C2+CVi+ This is satisfied by choosing to be large enough. It follows immediately that A can distinguish the two distributions Dj and D2 and the theorem then follows from Lemma 3.2.
Proof of Theorem 3.1. Suppose that M is drawn from the distribution in (1). By Yao's minimax principle, we can assume that S and T are deterministic sketching matrices. Let A E R be one of the following two matrices with the same probability
M
[M
Or
We first consider the case when A = [M 0). then SAT SMTT, where T" is the first k rows of T. Let T" be a submatrix of T' consisting of a maximal linearly independent subset columns of TV. Then T" has t' S ls columns. Furthermore, since the columns of T' linear combinations of the columns of T we can recover SMT from SMT". Hence, AASS, T, SAT) induces an algorithm T", SMT") of the same output, which estimates ||A A& || M&ll F up (1 +) factor. Next, note that the ji entry of SMT" is equal to (S,T") j vec(M)) Therefore, from Theorem 3.3, we have that t' S2(k2 /E?). Since t' < k, it follows immediately that s ((k/=²).
A similar argument for A = 0
T yields that = ((k/=²)
Upper Bound. We shall give O(k²/Et) upper bound for bilinear sketches. We first recall the definition of Projection- Cost Preserving sketches (PCPs).
Definition 3.4 ((Cohen al., 2015)). Given matrix A E Rnxd, 0, 2 0 and an integer k [d], a sketch S E Rx is an (e, c. k) -columm projection-cost preserving sketch of if for all rank-k P)ll?-
projection matrices P, (1 A(T P)l ||SA(T P)Il + (1+
Lemma 3.5 ((Cohen et al., 2015; Musco & Musco, 2020)). Let S E R be drawn from any of the S an (s, 0, projoectioon-cstt-reeeeriii
following matrix families. Then with probability sketch of A.
1. S is a dense Lolnson--Lndennsnn each element is chosen independently and uniformly +//1/m.
(JL) matrix, with m O( + log(1/))//²) and
2. S is a COUNTSKETCH with c O, m O(22 (E=2)), where each column has single + in random position.
3. S is an ONSAP sparse subspace embedding matrix (Nelson Nguyen, 2013), with c and
= O(k )e??, where each column has ((log(1/e) random #1/
We remark that it easy to see from the definition that if S1 and S2 are both (s, 0, PPP sketches of A, then S2 is (O(s), O, PPP sketch of A.
Our algorithm as follows. Suppose that S and T are matrices such that S and T both satisfy the condition in Definition 3.5. We then compute the rank-k error || AT - [SAT]] and use it as our final estimate. To show the correctness our algorithm, we first prove the following lemma.
Lemma 3.6. Suppose that S is an (E, k) projection-cost preserving sketch of SA. Then have
|| A& < || [5 + + + 1s
Proof. Suppose that P is the minimizer of ||A[[ - P) over all rank-k projections P, and P* is the minimizer of ||A(T - 13. Since S is an (e, c, k) projection-con preserving sketch of A, we have that
|A P0 ||
|A(1 -
/) c |SA[I
||SA[T
-P)]I
5

---

Published as a conference paper at ICLR 2024
Algorithm 1: aapprroxiiitt for -- -
Set 6 = ((= (/g=-2//o-1)/////1 12/pp) and n))
Initialize g. b buckets 21.1,-... log to 0:
Initialize pairwise independent hash functions h; [n] [b]:
Initialize 4-wise hash functions 8y [n) - (-1.1);
Initialize (1 + e)-lp estimation algorithm A with Onn2-2/p 2/p/ poly(e)) space [e.g., (Andoni et al., 2011)]; foreach (i, update comes do
for j 1-1 to do
(),())s - 2hy(0.s + uu sy());
end
10 Perform the update (i) in A:
11 end
12 for f- to l do
13 i median, {s)(t) 20,00,
14 end
is Choose the top coordinates of é to form set J
foreach j E / do
17 Perform the update (j. -ā)) in A.
end
19 return Output of A:
Next, from the definitions of P and P', we have that ||SA [SA] = -ISA[I P) and ||A All 1 |IA(I ll) The desired result follows.
Theorem 3.7. There exist random matrices S E ( and T E RdxxOk/=P)) such that with high constant probubility
|| Ax < |SAT - [SAT) & (1 + +)]lAA - AsI
Moreover, the sketch SAT can be computed in nnz(A) + poly(k/2 (k/=) time.
SiS2, where S1 E (0(0/5))x009)))) is JL matrix and S2 RO(2/e (x))xn is the COUNT-SKETCH matrix in Lemma 3.5. Then T = T,TT, is the same construc- tion with S but replacing with d. Because S₂ and T2 are both COUNT-SKETCH matrices, can compute S2 2 in nnz( A) time. Then note that S2 AT2 are matrices with size O /e2) x we can compute SAT AT27, in mnz(A) + (kl/(k/e) time.
Proof. We construct
We next consider the accuracy. From Lemma 3.5 we have that with high constant probability S,T both rank-k PCPs with error Hence we first have
A A& | < ||SA - A] S (1+ Au
Applying Lemma 3.6 to T and A S yields that
|SA - [SA] 1 SAT - [SAT] < (1+))
Combining the two equations above leads
|| A 1I: <
SAT { < (1+ A
and the claimed result then follows immediately by rescaling e.
4 F, RESIDUAL ERROR ESTIMATION
We next consider the Fp residual error estimation task where our goal is to estimate the k-residual error || up to (1 + factor.
The algorithm is shown in Algorithm 1. At high level. we use the classical COUNTSKETCH to estimate the frequency of each coordinate of æ. Then we select the top & coordinates that have the

---

Published as a conference paper at ICLR 2024
largest estimated values. In parallel we run an Fo estimation algorithm A and then subtract these coordinates with the estimated value. We then use the output of A to be our final estimation of ||æ= Suppose that I is the set of coordinates that are the genuine k largest coordinates, and J is the set of candidates we choose. In the remainder of this section, we shall show that || 1 æ lp is within a (1 + E) factor of || واارد = |æ Hence, if we run an Fp frequency estimation algorithm in parallel (see, e.g., (Ganguly & Woodruff, 2018)) and after subtracting the estimated frequency 2 on each of the coordinates in J, we will obtain the k residual error up to (1 =E=)) factor.
For the purpose of exposition, we first assume b (/--21///p !-2p) and will show that it gives O(1
Then, after normalization, get the desired bound. We first bound the error of COUNTSKETCH for each coordinate. The following lemma is a standard fact of COUNTSKETCH. The corollary below easily follows from Hölder's inequality.
Lemma 4.1 ((Minton & Price, 2014)). Suppose that & 2 clog n. for a constant Then with probability at least 9/10, we have that ( - mal S /x===ll/// holds for all i simultaneously
Corollary 4.2. If we set the number of buckets b ((--2 222///// then with probability at least 9/10, we have that [f. x.| S =||x==1lp/ (cck/ (m), where 0₁ is universal constant.
For an index set T C [m]] we define ST =
|.e/ From the definition of the set I and J, we
have that Sy S S₁. For the other direction, we have
Lemma 4.3. It holds that S 2 S (sp2-/pp) -|
Proof. It follows from Lemma 4.2 and the definitions of I and J that if some i E I is replaced by some j E J, we must have (i) |zt, xzyl
علاعععا and (ii) | 2 |æy|P 2 | 2s "1ktT
| k1/1/P
PP
We claim that |2; ||=->>;
I for all i I J. If not, suppose that [a;]] 2-/2 ||ا for some i E / \ J. we would obtain an estimate è, with | > (2 - -/((ch//p) (|=p | by Corollary 4.2. Since き J, the estimates of 2y for every j E J must be at least (21/2 ee/(ckk/())) ||= which further implies that there exists some j á T such that |xr 2 (21/r - 2e/e(2//////)))))) | lp This contradicts the fact that || 111,, 2 |zz]1 Hence must hold that |2:| |2||==>|] for all i J.
We next decompose such that 2 S k10E))) < 2
(InJ) UT ....UUTTU UTm+1 where m (log(kk/e) is
| x I
|
T2 = T J:
2
< |r: p
<
2 f
f= 0, m
and
10 | x11 10:1
T =
iE I J: |ms <
k
For Tn Tm41 we have that
10s - 10s|| =1p
Σ VETm+1
|. S. k.
Next consider Tr. Note that
Σ TE is displaced by
lry1" S -
and it must hold that [Ty] = (2 Suppose that i E Tç is displaced by j E J. It then follows from the above discussion that
|2/|| - 23 || - -xxllp" 19
2pp || - 2x11p
|.,|" - |z 1
< |zg 10
S 11111-111
c1kl/P
||
12 1|--
x xxlle
|| 1|0-
2pe
2pe
2 1) l
cjkl/p
0i
(2 2/ R
7

---

Published as a conference paper at ICLR 2024
|0y|0 1 0(29) 2p =
Taking the sum we get that Σier, |r.1 -
ET
displaced by
c1 -
<20/"110- all.. ki7p
O
Summing over yields that S - S. S 0(s1-1/P) u which what we
need.
Suppose that we have S₁ Sy S (e)) ||== Il (we normalize e here). Then this means that || - = | = || I.| : - || zr|ø S =|| Then, from the discussion above
we also have that for each j E J. 1 zyI S e
- which means that || - Eull
e0/(o-11|2 || F 0(er/(r (--1/))))))))) | [p)- Therefore, ||1 2ulرة - || =
|| - =>>l I k-
O (e11=->l?) whence we see that any (1 + E) approxxmmaiin of || L5 I| is an (1 + O(
approximation | We can now conclude with the following theorem.
Theorem 4.4. There is an algorithm that uses space Ö(s 0(=--pp)))) 2p/(e-1)g2/ppd 22/p) 2/pp) and outputs (1 + apprroxxinntio of the k-residual error ||== with high constant probability.
L, Sparse Recovery. Recall that in our algorithm, the vector i, is k-sparse and satisfies that 1 - الرة S (1 (1+))]lz=s133 which means that Algorithm actually solves the lp sparse recovery problem. We have the following theorem.
Theorem 4.5. There is an algorithm that uses space 0(e-20/(0-1)) 11 2 2-2/ and solves the (1+e)-lp sparse recovery problem with high constant probability.
Below we show an 2(k22/p1122/2 lower bound for the lp sparse recovery problem with a constant approximation factor. To achieve this, we consider the Gap-infinity problem in (Bar- Yossef et al., 2004).
Definition 4.6 (Gap-infinity problem, (Bar-Yossef Yossef al., 2004)). There are two parties, Alice and Bob, holding vectors a, b E 2" respectively, and their goal is to decide if bil S or l|a- blloc 2 s.
Theorem 4.7 ((Bar Yossef et al., 2004)). Any protocol that solves the Gap-infinity problem with probability at least 9/1 /10 must have (2n/ s²) bits of communication.
The lower bound also holds if we assume there is exactly 1 or O coordinates i satisfying la; - b,l 2 each case occurring with constant probability. The work of Bossef et al., 2004) provides an information cost lower bound for this problem, which, together with the direct sum theorem ((Chakrabarti et al., 2001; Bar- Yossef et al., 2004)), leads to the following corollary.
Corollary 4.8. Suppose that there are independent instances of the Gap-infiitty problem. If Alice and Bob can solve constant fraction of the instances with probability at least 9/10, then they must have (In// 2) buts of communication.
Now are ready to prove bit lower bound for the fp-sparse recovery problem.
Theorem 4.9. Suppose that is sufficiently small constant. Any algorithm that solves the (1 + c) lp sparse recovery problem with high constant probability requires 22(k2/pp!-2ip bits of space.
Proof. We reduce the multi instance Gap-infinity problem to the Ep sparse recovery problem. Suppose that there are lo instances of the Gap-infinity problem (a², 5²) with length n/k and (n/k)L/p, Let z a² that & is a k-sparse vector which satisfies || alp < (1 + c)Il x* where e is sufficiently small constant. We shall show how we can solve, using &, a constant fraction of copies of the Gap-infinity problem on (a',b'). As mentioned above, can assume for each instance (a', b¹) that there is exactly 1 or no coordinates j satisfying (a'), (b'), 2 8, each case occurring with constant probability. Under this assumption, with high constant probability, there Okk) instances for which ||a* - bl = and | 1 = (n). Note that for a coordinate I;, if [x] - 2t. 2 8/2, it will contribute 9(n/k) to ||= I|. Thus, for a (1 approxxmattnnn this event can only happen at most (k) times, which means that from the solution â, we can solve a constant fraction of the instances (at, b²). The theorem then follows from Corollary 4.8.
(i E [n/k]) and x E nd be the resulting vector after concatenating all = Suppose
8

---

Published as a conference paper at ICLR 2024
Table Performance of our algorithm and (Andoni & Nguyen, 2013) on Moviel 100K data and KOS data, respectively.
A 10
20
k 5
A: 10
A: 20
=(Our,, m 50)
0.146
0.295
0.545
c(Ours, m 50)
0.135
0.287
0.543
c(Ours, m 100)
0.074
0.149
c(Ours, m 100)
0.068
0.140
0.279
cIAN13, 50)
0.135
0.287
0.541
cAAN13,
0.141
0.288
0.540
5(AN13, m = 100)
0.070
0.149
0.288
EIANI3, m 100)
0.067
0.138
0.286
Runtime
Runtime
0.105s
0.102s
0.105s
0.1176
0.114s
0.120s
(Ours, 7/ = 50)
(Ours, m2 = 50)
Runtime (Ours, 100)
0.106s
0.105s
0.109s
Runtime (Ours, 100)
0.126s
0.130s
0.123s
Runtime
Runtimee
0.377
0.381s
0.388s
0.39%
0.414s
0.397s
(AN13, 50)
(ANI3, 50)
Runtime
Runtime
0.735x
0.735s
0.728s
0.747s
0.744s
(ANI3, m 100)
(AN13, m 100)
Streaming
Streaming (m = 50)
0.14
0.149s
0.151s
0
0.657s
0.660s
(m 50)
Randomized SVD
0.056s
0.061s
0.075s
Randomized SVD
0.199
0.218%
0.230s
22.070s
We have shown a lower bound in terms of total bits of space. We next show that such a lower bound can be converted to a sketching dimension lower bound, for which we need the following lemma.
Lemma 4.10 (Price & Woodruff, 2011, Lemma 5.2)). A lower bound (2(b) bits for the sparse recovery bit scheme implies lower bound of 22b/ log n) for regular sparse recovery with failure probability 8 - 1/n.
Our theorem follows immediately.
Theorem 4.11. Suppose that is sufficiently small constant. Any algorithm that solves the (1 + c) Ep sparse recovery problem with high constant probability requires 22 2/kk2 (2/pp) 2/pp) measurements.
EXPERIMENTS
In this section, consider experiments for the low-rank residual error estimation problem real-world datasets. All of our experiments were done in Python and conducted on a device with a 3.30GHz CPU and 16GB RAM. We will use the following dataset.
KOS ?ata.? 2 A word frequency dataset. The matrix represents word frequencies in blogs and has dimensions 3430 x 6906 with 353160 non-zero entries. MovieLens 100K. (Harper & Konstan, 2016) A movie ratings dataset, which consists of preference matrix with 100,000 ratings from 611 users across 9,724 movies.
As discussed in the previous section, our algorithm follows the same framework as that in (Andoni & Nguyen, 2013): compute the sketch SAAT' and then compute the rank-k residual error SAT: ||SAT - [SAT]] However, the work of Andoni & Nguyen (2013) only gives an O(k? /5") upper bound for this bilinear sketch, while we have shown any sketch matrices with the rank-k projection-cost preserving property suffice, which allows for an O(2² /ea) upper bound and the use of extremely sparse sketching matrices with this size.
The result is shown in Table 1. We define the enror (Output of the Algorithm)/IIA- -AulE 1. and take an average over 10 independent trials. Since the regime interest is k & n,, d, we vary among (5, 10, 20} and set the sketching size be 50, 100. For the work of Andoni & Nguyen (2013), we set the matrices S, T to be random Gaussian matrices and for ours we set the S.T T to be the OSNAP matrices (Nelson & Nguyen, 2013; Cohen, 2016) with 2. The result shows that while the error of the two ways is almost the same, the runtime ours is about 4- to 7-fold faster than the algorithm in (Andoni & Nguyen, 2013). This is because, in algorithm, the sketching matrix is extremely sparse, where each column has only O(1) non-zero entries.
The theory in (Price Woodruff, 2011) is for p S 2, however, the argument still goes through constant > 2 unchanged.
"The Bag of Words Data Set from the UCT Machine Leaming Repository.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENT
Y. Li is supported in part by the Singapore Ministry of Education (AcRF) Tier 2 grant MOE- T2EP20122-000) and Tier 1 grant RG75/21. Lin and Woodruff would like thank support from the National Institute of Health (NIH) grant 5R01 HG 10798-2. D.W. also did part of this work while visiting the Simons Institute for the Theory of Computing.
REFERENCES
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments, Comput. Syst. Sci., 58(1):137-147, 1999. 2
Alexandr Andoni and Huy L. Nguyen. Eigenvalues of matrix in the streaming model. In Sanjeev Khanna (ed.), Proceedings of the Twenty- Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp. 1729-1737. SIAM, 2013. 1, 2,
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In Rafail Ostrovsky (ed.), IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pp. 363-372. IEEE Computer Society, 2011. doi: 10. 101109/FCCS20111 1....2 URL https: / /ttp///.iii//////////o. org/ / 10. 1119/F0090S. 2011. 82. 3,6
Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. Lower bounds for sparse recovery. In Moses Charikar (ed.). Proceedings of the Twenty-Fire Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp. 1190-1197. SIAM, 2010. doi: 10. 0211137/19788 0781611973075999 URL https: /toi. arg/10... 1137/1. 9781611973075. 95. 2
Ziv Bar-Yosser Yossef, T. S. Jayram, Ravi Kumnr, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Comput. Syst. Sci., 68(4):702-732, 2004. 2,
Radu Berinde, Piotr Indyk, Graham Cormode, and Martin J. Strauss. Space-optimal heavy hitters with strong error bounds. ACM Trans. Database Syst., 35(4):26:1-26:22) 2010. doi: 10.1145/ 1862919.1862923, URL https: http://o...ooo org 10. 1 15 /t////1629999.. 19w.9999....99......
Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao. Informational complexity and the direct sum problem for simultaneous message complexity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pp.
270-278. IEEE Computer Society, 2001.
Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Michael Mitzenmacher (ed.), Proceedings of the 41 Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009, pp. 205-214. ACM, 2009.
Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Dan Bonch, Tim Roughgarden, and Joan Feigenbaum (eds.), Symposium on Theory of Computing Conference, STOC' 13, Palo Alto, CA, USA, June 144, 2013, pp. 81-90. ACM, 2013. doi: 10. 10.1145/2488608 2488620. URL ttttps:///oi... http://doo..ggg/1///// 10. 11 /11115/244822 248880888888882 2288620.
2
Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Robert Krauthgamer (ed.). Proceedings of the Twenty-Sevent Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 278 278-287. SIAM, 2016. 2,
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation. In Rocco A. Servedio and Ronitt Rubinfeld (eds.), Proceedings of the Forty-Seventh Anmual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 17, 2015, pp. 163-172, ACM, 2015. 5
10

---

Published as a conference paper at ICLR 2024
Sumit Ganguly and David P. Woodruff. High probability frequency moment sketches. In loannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella ), 45th International Colloquium Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of L.Plcs, pp- 58:1 18:1-58: Schloss Dagstuhl Leibnniz-Zeenrrum für
Informatik, 2018. 3,7
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4):19:1-19:19, 2016. URL https:///oi...... http:///t...rr...../// 011.:/...00001111111222111111111
Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In 49th Annual IEEE Symposium Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pp. IEEE Computer Society,
2008. 2
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2 edition, 2012. doi: 10.1017/CB09781 139020411.
Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In László Babai (ed.), Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 373-380, ACM, 2004. 2
Piotr Indyk, Eric Price, and David P. Woodruff. On the power of adaptivity in sparse recovery. In Rafail Ostrovsky (ed.), IEEE 52nd Annual Symposium Foundations of Computer Science, FOCS 2011, 1 Palm Springs, CA, USA, October 22-25, 20/1, pp. 285-294. IEEE Computer Society, 2011.
doi: F.L109/OCC..00
URL https: / /oii wrg/r0ggg//.oooo 10. 1109/119// FCCS. 2011. 83.. 2
Yi Li and David P. Woodruff. Tight bounds for sketching the operator norm, schatten norms, and subspace embeddings. Klaus Jansen, Claire Mathieu, José D. Rolim, and Chris Umans (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Puris, France, volume 60 of L.Plcs, pp. 39:1- 39:11, 2016. 4
Gregory T. Minton and Eric Price. Improved concentration bounds for count-sketch. In Chandra Chekuri (ed.), Proceedings of the Twenty-Fifih Annual ACM-SIAM Symposium on Discrete Al- gorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 669-686. SIAM, 2014.
Cameron Musco and Christopher Musco. Projection-cos--prseering sketches: Proof strategies and constructions. CoRR, abs/2004.08433 088444 2020. URL UtLhhtttss///rrvvv..rr///a 2204. 08434. 5
Jelani Nelson and Huy L. Nguyen. OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings. CoRR, abs/1211. 2012.
Jelani Nelson and Huy L. Nguyen. OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 117-126. IEEE Computer Society, 2013. 5,
Eric Price and David P. Woodruff. (1+eps) sparse recovery. CoRR, abs/1 1 110.4414, 2011. 2,
Roman Vershynin. #iigh-Dimensiona Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 10.1017/978 108231596..
David P. Woodruff. Sketching as tool for numerical linear algebra. Found. Trends Theor. Comput. Sei., 10(1-2):1-177, 2014a.
David P. Woodruff. Low rank approximation lower bounds in row-update streams. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Annual Conference Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 1781-1789, 2014b.
11


Reviews:
[{"review_id": "tWX7SYStXn", "reviewer": "Reviewer_FqHJ", "summary": "This paper studies the (approximate) estimation of residual error of rank-k approximation of matrix and k-sparse recovery of vector using linear sketches. For the matrix case (Frobenius norm), the main result is a bilinear sketch of size $O(k^2/\\epsilon^4)$ by combining the count sketch and JL sketch; this improves upon the previous best result $O(k^2/\\epsilon^6)$ [Andoni-Nguyen, SODA'13]. The authors also provide a matching lower bound. For the $k$-sparse recovery under $\\ell_p$ norm for $p>2$, the author show an upper bound of $\\tilde{O}(k^{2/p}n^{1-2/p}$. This is done by two sketches, where one is used to find heavy hitters, and another to do a $F_p$ estimation.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I think this paper is technically solid and solves an interesting open problem. The high-level explanation provided in the paper are helpful to the readers.", "weaknesses": "1. For the matrix case, the improvement compared to Andoni and Nguyen seem a bit incremental.\n2. While I think it makes sense to estimate the residual error of matrix approximations, I think there is little use to estimate the residual error of sparse recovery under $\\ell_p$ norm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9JzUFCdTii", "reviewer": "Reviewer_QAtz", "summary": "This paper studies the problem of estimating the residual error using linear sketching. Specifically it focusses on the following two problems:\n\n1) For any matrix A, the task is to estimate $||A-A_k||_F$ within a $(1+\\epsilon)$-factor where $A_k$ is the best rank-k approximation to $A \\in \\mathbb{R}^{n \\times d}$. For this problem, it is shown a bilinear sketch of the form $SAT$ where the sketching matrices $S \\in \\mathbb{R}^{O(k/\\epsilon^2) \\times n}$ and $T \\in \\mathbb{R}^{d \\times O(k/\\epsilon^2)}$ can be sparse countsketch matrices with a single $\\pm 1$ in their columns. This gives a sketch of size $O(k^2/\\epsilon^4)$. A lower bound is given which shows S and T must have $O(k/\\epsilon^2)$ rows and columns respectively for any algorithm which takes as input $S,T,SAT$ and outputs a $(1+\\epsilon)$ residual ran-k approximation. This shows the upper bound is tight for bilinear sketches.\n\n2) The next problem is estimating $\\| x-x_k\\|_p$ upto $(1 \\pm \\epsilon)$ residual error for any vector $x \\in \\mathbb{R}^{n}$ which is updated in the streaming model, for any $l_p$ norm with $p>2$ and where $x_k$ is the the vector containing the top-k elements of $x$. The algorithm uses countsketch to find the indices of top-k elements of $x$ approximately and parallely uses a known $F_p$ frequency estimation procedure for these coordinates and subtracts the approximate value of these coordinates to get the residual error. This yields an upper bound of $\\tilde{O}(\\epsilon^{-2p/(1-p)}k^{2/p} n^{1-2/p} )$ and also gives a $k$-sparse approximation for $x$. A lower bound of $\\Omega(k^{2/p} n^{1-2/p})$ is also shown for the $k$-sparse recovery problem.\n\nSome experiments are performed with the sparse sketching matrices.", "questions": "1) Can anything be said regarding how good $SAT$ is as compared to $A_k$, the best rank-k approximation to A?\n\n2) I'm confused about the the proof of Lemma 4.3. It seems we should have $(I \\cap J) \\cup T_1 \\cup \\ldots T_{m+1} \\subseteq I$ instead of exactly being equal to $I$ as it could happen that $i \\in I \\backslash J$ and  $x_i > || x_{-k}||_p $  in which case $i$ wouldn't belong to any of \n\nthe sets $ T_1, \\ldots T_{m+1}$? It seems instead of decomposing I, decomposing J as $ J= (I \\cap J) \\cup T_1 \\cup \\ldots T_{m+1}$ where each $T_i$ constains elements of $J$ not in $I$ in the given interval and then doing the analysis should given the same result?\n\nRemark: I have not checked whether Lemma 5.2 of Price and Woodruff, 2011 indeed generalizes to p>2. This is used in Lemma 4.10.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  For the residual matrix norm estimation problem, the paper presents the bilinear sketches which are optimal in size. Moreover, since the sketching matrices can be sparse, they can be computed are pretty fast. Previous results for this problem used dense sketching matrices and had a larger upper bound of $O(k^2/\\epsilon^6)$ on the size of the sketch. The proof for the sketching algorithm is pretty straightforward from results on projection cost preserving sketches. The lower bound proof follow via minimum singular value separation results for random Gaussian matrices.\n\n2. For the residual vector norm recovery problem, the algorithm also outputs a $k-sparse$ approximation in $l_p$ norm which is optimal upto polylog $n$ factors (though the dependence on $\\epsilon$ is unclear). The lower bound proof follows from reducing the gap infinity problem to the $l_p$ sparse recovery problem.\n\n3. Though some of the results are pretty straightforward from prior results (for example, the bilinear sketch upper bound follows directly from the PCP sketch properties), they are an interesting addition to the sketching literature.\n\n4. The paper is mostly well written and easy to follow apart from some typos etc. (see weakness and questions)", "weaknesses": "1) It is unclear how good the upper for the residual norm estimation problem as compared to the optimal. The given lower bound applies to the sparse recovery problem. But this is a harder problem than the norm residual error estimation problem. Some discussion on the actual lower bound for the norm estimation problem might make things more clear for the reader. Also, though the upper bound for the sparse recovery problem is optimal in terms of n and k, it is unclear on what the correct dependence on $\\epsilon$ is.\n\n3) There are some typos etc. in the paper which should be corrected:\n      1) In definition 3.4, $S$ should be $s \\times n$\n      2) The proof of theorem 3.7 should refer to lemma 3.5 instead of 3.4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UJUvvqjb4D", "reviewer": "Reviewer_Mz93", "summary": "This paper researches the $\\textit{residual error estimation}$ problem. To be specific, for a matrix $A$, one estimates $|| A - A_k ||_F$ and judges if it is worthwhile to compute a low-rank approximation $\\widehat{A}$ such that $|| A - \\widehat{A} ||_F \\le (1 + \\varepsilon) || A - A_k ||_F$, where $A_k$ is the best rank-$k$ approximation to $A$; for a vector $x$, one estimates $|| x - x_k ||_p$ and determines whether to compute a $k$-sparse vector $\\widehat{x}$ such that $|| x - \\widehat{x} ||_p \\le (1+\\varepsilon) || x - x_k ||_p$, where $x_k$ is the best $k$-sparse approximation to $x$.  \nGiven a matrix $A$, for the estimator $|| SAT - [SAT]_k ||_F$ of the residual error $|| A - A_k ||_F$, this paper obtains the lower bound and upper bound of the dimensionality $s, t = \\Theta(k / \\varepsilon^2)$, which improves the upper bound $O(k / \\varepsilon^3)$ in [Andoni and Nguyen'13].  \nGiven a vector $x$, for the estimator of $|| x - x_k ||_p$ with $p > 2$, this paper gives the upper bound $\\widetilde{O}(\\varepsilon^{-2p/(p-1)} k^{2/p} n^{1-2/p})$ for space. This result can be extended to the $\\ell_p$ sparse recovery problem, in which the upper bound almost matches the obtained lower bound $\\Omega(k^{2/p} n^{1-2/p})$ when taking $\\varepsilon$ as a constant.", "questions": "See Weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) For low-rank residual error estimation, this paper gives the lower bound $\\Omega( k / \\varepsilon^2 )$ for the dimensionality of the sketching matrices $S$ and $T$, and the upper bound $O(k / \\varepsilon^2)$, which matches the lower bound and improves the upper bound $O(k / \\varepsilon^3)$ in [Andoni and Nguyen'13].     \n(2) For residual error estimation of vector $\\ell_p$ norm with $p > 2$, this paper gives an upper bound $\\widetilde{O}(\\varepsilon^{-2p/(p-1)} k^{2/p} n^{1-2/p})$ for the dimensinality of the sketching matrix. Also, this upper bound can be extended to $\\ell_p$ sparse recovery problem and almost matches the obtained lower bound $\\Omega(k^{2/p} n^{1-2/p})$ when $\\varepsilon$ is a constant.   \n(3) The experimental results indicate that the proposed algorithm has a comparable error $\\varepsilon$ but at least ten times faster than the existing method [Andoni and Nguyen'13].    \n(4) This paper is well-written and easy to understand.", "weaknesses": "In the experiments, this paper only proves the efficiency of the proposed algorithm for low-rank approximation. Can this paper supplement experiments for the residual error estimation of vector norms?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1is8YNEcP2", "reviewer": "Reviewer_k2z9", "summary": "This paper considers the problem of estimating the Frobenius norm residual error of the best rank-$k$ low-rank matrix approximation and the $\\ell_p$-norm residual error of the best $k$-sparse vector approximation. The main result, for the matrix case, is that best rank-$k$ approximation error can be approximated to relative error $\\varepsilon$ using a bilinear compression $SAT \\in \\mathbb{R}^{O(k/\\varepsilon^2) \\times O(k/\\varepsilon^2)}$ of $A$ by two projection-cost-preserving sketches $S$ and $T$. The new result improves the dependence on $\\varepsilon$ from (Andoni and Nguyen, 2013); a new lower bound establishes the optimality of the current method.", "questions": "### Is Lemma 3.2 correct?\n\nThe proof of Lemma 3.2 is not convincing to me in several ways. First, why does $d_{TV}(S(G), S(G+\\beta \\sqrt{\\varepsilon/k} \\cdot wz^\\top) \\le 1/10$ and $\\beta \\sqrt{\\varepsilon/k} \\cdot \\|w\\|\\|z\\|$ imply $d_{TV}(S(G), S(G + c\\alpha\\sqrt{\\varepsilon} \\cdot uv^\\top)) \\le 1/9$. I believe the ultimate result is probably true, but I don't following the line of reasoning.\n\nI'm not sure data processing and linearity of the sketch is enough to conclude that $d_{TV}(\\mathcal{L}_1,\\mathcal{L}_2)$. The perturbation $c\\sqrt{\\varepsilon}B$ is applied to both $G$ and $G + c\\alpha \\sqrt{\\varepsilon} uv^\\top$ and it is _dependent_ with the latter of these. I'm not sure exactly what the author's argument is. It appears that the authors are making a claim of the form:\n\n> If $d_{\\rm TV}(X,Y) \\le \\varepsilon$, then $d_{\\rm TV}(X+Z,Y+Z)\\le \\varepsilon$.\n\nThis claim is certainly not true. Let $X$ be a random variable which is never $0$ and take $X = -Y = Z$. Then $d_{\\rm TV}(X,Y) = 0$ but $d_{\\rm TV}(X+Z,Y+Z) = d_{\\rm TV}(2X,0) = 1$. \n\nI'm not sure how exactly the authors purport to conclude the proof of lemma 3.2. The authors should revise this proof to make unassailable the correctness of this result.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is a nice work of theoretical computer science. The writing is good and reasonably clear. The fact that the projection-cost-preserving sketch technology allows for an improvement of the Andoni–Nguyen result is very interesting and, to the best of my knowledge, novel. The lower bound is nice as well, and it establishes the optimality of the proposed approach (though I have my concerns about the correctness of Lemma 3.2).", "weaknesses": "As a work of _theoretical computer science_, this paper is perfectly adequate. As a work of _machine learning_, it has a few deficiencies.\n\n### Use Case\n\nWhen is the proposed method useful? The story the authors tell feels a bit farfetched to me:\n\n- Using a generalized Nyström approximation and OSNAP sketches, a rank-$k$ approximation can be computed in a single pass over the matrix. For a dense matrix stored on disk, the time cost is roughly $O(mn \\log k + (m+n) k^2)$; the cost of the proposed residual estimate is roughly $O(mn)$. The difference between these costs is not very significant, particularly if $k \\ll m,n$. \n- The authors suggest data streams as a potential application. Indeed, the proposed approach does give a way of estimating the residual error from a stream in low space. After which, the authors say one can use the residual estimate to decide whether or not low-rank approximation is worth it. But this raises two objections: 1) If one is going to compute a low-rank approximation anyways, then one will have to eat the space cost of storing such an approximation eventually. The proposed low-space diagnostic doesn't seem useful if, conditional on a positive outcome, actually computing the approximation needs more space. 2) Often in the streaming setting, we assume we get only a single pass over the data. The authors approach requires two passes: one to compute the diagnostic and a second to compute a low-rank approximation.\n\nIt may be possible that there is some use case where the proposed approach is natural, but it seems to me that the proposed method probably has fairly limited usefulness in practice.\n\n### CountSketch\n\nI find the author's use of CountSketch to be questionable, particularly in the numerical experiments. In my experience, an OSNAP (even with just 2 entries of sparsity per column) is dramatically more safe and effective than CountSketch in practice.\n\nTo demonstrate this, I ran my own experiment. Let $A = \\operatorname{diag}( i^{-6} : i=1,2,\\ldots,10^4)$ and, following Table 1, consider $m = 50$ and $k = 20$. With CountSketch, the estimate $\\| SAT - (SAT)_k \\|_F$ is a factor of **58** smaller than the true residual error $\\| A - A_k \\|_F$. By contrast, OSNAP with _just 2 nonzeros per column_ only underestimates the residual error by a factor of 2! For the proposed use case of screening whether or not significant compression is possible by low-rank approximation, an estimate within a factor of two is probably useful; one that is wrong by more than an order of magnitude is not.\n\nThis is a paper about theoretical computer science: Rigorous analysis of computational methods so that they work in practice even on worst-case inputs. The use of a plain CountSketch in the numerical experiments, now demonstrated to be able to severely underestimate the residual error in practice, should be removed in favor of the OSNAP or, perhaps, the composite CountSketch–Gaussian sketch.\n\nAs a side note, the introduction claims that it will prove that the method works if $S$ and $T$ are chosen to be OSNAP's. But this is omitted from the main text. This should be included, because OSNAP's are often the most effective sketching matrices in practice.\n\n### Numerical Evaluation\n\nThe runtime of a full, dense SVD is not the appropriate comparison in Table 1. Rather, the appropriate comparison is a _randomized low-rank approximation_ such as the randomized SVD or generalized Nyström (with OSNAP's, if the latter).\n\n### Accuracy\n\nAs I mention above and as the authors tacitly admit with their numerical experiments, an error estimate which is within a factor of two is often sufficient, particularly if the proposed use case is determined whether or not to run a low-rank approximation algorithm. Viewed in this light, the improvement of the sketch dimension from $O(k/\\varepsilon^3)$ to $O(k/\\varepsilon^2)$ in the present work is not that meaningful in practice.\n\n### Sparse Approximation\n\nThe residual error for $k$-sparse approximation of vectors in $\\ell_p$ norms for $p > 2$ is very much a question of interest to theoretical computer science. I fail to see any interest for practical problems in machine learning.\n\n### Conclusion\n\nUltimately, I feel like this paper would be more at home at a dedicated TCS publication venue. I'm not sure when I would actually run the author's proposed method in practice, and the improvement from $O(k/\\varepsilon^3)$ to $O(k/\\varepsilon^2)$ has limited practical implications as well. I have significant concerns with the use of plain CountSketch in the numerical experiments. If the numerical experiments were fixed to avoid the use of plain CountSketch, I would be inclined to give a soft recommendation for acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)