Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss
Authors: Aleksandros Sobczyk
Mathieu Luisier
Venue: NeurIPS 2022 Accept (2022)
Keywords: Johnson-Lindenstrauss
Hutch++
Euclidean distances
Statistical leverage scores
Random projection
Approximate isometry
Dimensionality reduction

Abstract: A classical result of Johnson and Lindenstrauss states that a set of $n$ high dimensional data points can be projected down to $O(\log n/\epsilon^2)$ dimensions such that the square of their pairwise distances is preserved up to a small distortion $\epsilon\in(0,1)$. It has been proved that the JL lemma is optimal for the general case, therefore, improvements can only be explored for special cases. This work aims to improve the $\epsilon^{-2}$ dependency based on techniques inspired by the Hutch++ Algorithm, which reduces $\epsilon^{-2}$ to $\epsilon^{-1}$ for the related problem of implicit matrix trace estimation. We first present an algorithm to estimate the Euclidean lengths of the rows of a matrix. We prove for it element-wise probabilistic bounds that are at least as good as standard JL approximations in the worst-case, but are asymptotically better for matrices with decaying spectrum. Moreover, for any matrix, regardless of its spectrum, the algorithm achieves $\epsilon$-accuracy for the total, Frobenius norm-wise relative error using only $O(\epsilon^{-1})$ queries. This is a quadratic improvement over the norm-wise error of standard JL approximations. We also show how these results can be extended to estimate (i) the Euclidean distances between data points and (ii) the statistical leverage scores of tall-and-skinny data matrices, which are ubiquitous for many applications, with analogous theoretical improvements. Proof-of-concept numerical experiments are presented to validate the theoretical analysis.

Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss
Aleksandros Sobczyk
Mathieu Luisier
IBM Research and ETH Zürich
ETH Zürich
Zürich, Switzerland obc0zurich hmm. com
Zürich, Switzerland
mluisier@iis ee ethz. ch
Abstract
A classical result of Johnson and Lindenstrauss states that of high dimen- sional data points can be projected down to Ollog n/c²) dimensions such that the square of their pairwise distances preserved up small distortion It has been proved that the JL lemma is optimal for the general case, therefore, improvements can only be explored for special cases. This work aims to improve the c dependency based on techniques inspired by the Hutch++ Algorithm [34], which reduces - co for the related problem of implicit matrix trace estimation. We first present an algorithm to estimate the Euclidean lengths of the rows of a matrix. We prove for element-wise probabilistic bounds that are at least as good standard JL. approximations in the worst-case, but are asymptotically better for matrices with decaying spectrum. Moreover, for any matrix, regardless its spectrum, the algorithm achieves e-accuracy for the total, Frobenius norm- wise relative error using only O(E queries. This is a quadratic improvement over the norm- wise eттоr of standard JL approximations, We also show how these results can be extended to estimate (i) the Euclidean distances between data points and (ii) the statistical leverage scores of tall-and-skinny data matrices, which ubiquitous for many applications, with analogous theoretical improvements. troof-of-concepp numerical experiments are presented validate the theoretical analysis.
(0, 1).
Introduction
The Johnson-LLindensrruuss (JL) lemma [29] is a fundamental concept dimensionality reduction and data science. Given set of n high dimensional data points X = {xI,..., Fn). where each I E _dd, the goal is to find a projection f IR + R* that maps the vectors to a much smaller dimension < such that the geometry of the original is approximately preserved. Specifically, the projection should preserve the pairwise distances up to small distortion E (0, 1). that is
[-=)]|=; 21 < llf( f(x,))1 < (1++))l
for all j.j E [n]. If f satisfies this property, then it is called an c-isometry. Johnson and Lindenstrauss proved that, given c, such an ff can be found in randomized polynomial time and that the projected dimension is no larger than Ollognee)) n2c²). In the last decades the JL lemma has made an impact in many areas, including Graph Algorithms [6, 42), Machine Learning [5, 11, 16, 24], Numerical Linear Algebra [14, 33, 40, 44] and Optimization [20, 22, 38).
In the existing literature, a common approach approximate the metric is to first find map that preserves Euclidean lengths instead of distances. The approximate isometry property is then achieved by applying this map to all the pairwise difference vectors. since the Euclidean distance between æ and y is equal to the length of æ ef. [18, 29]. In this work we follow the same methodology. We first study the problem of approximating the Euclidean lengths of the rows of an
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

elements from arbitrary matrix A E Rnxd in the so-called matrix-vector query model. In this model, the matrix A might not be explicitly available, but we have access linear operator that computes the product Ax. for an arbitrary vector x. For non-symmetric and rectangular matrices we assume that we can compute both Az and AT x. This model is particularly useful when dealing with matrix functions, L.e. when A f(B) is implicitly defined as function of another matrix B. Two applications arise from network science. For a graph G. let A be its adjacency matrix, B its edge-incidence matrix, W the diagonal matrix containing non-negative edge weights and L B W B its Laplacian. The exponential function of the adjacency matrix, @AA,, provides information about node centrality measures [10, 23), while the diagonal entries of BL B are the so-called "effective resistances" of the edges [33, 36, 42], which can be used to identify important edges. Another example, which is detailed in Section 4, is for computing the leverage scores of matrix, which can be found in the diagonal of the orthogonal projector H = A(A A)T AT. In all of these applications, explicitly evaluating the corresponding matrix functions has typically cubic complexity, which can be prohibitively expensive. However, after some algebra, the quantities of interest can be expressed as the Fuclidean lengths of the rows of matrix function in the matrix-vector query model. One can therefore use techniques related to the JL lemma to derive fast approximations. To this end, we first recall the concept of transforms, as defined in [40].
Definition 1 (Johnson-Linder) Lindenstrauss transform [40]). A random matrix S E gr forms a Johnson- Lindenstrauss transform with parameters e, 8 E (0, 1/2) and positive integer n, or (e, 8, n)-JLT for short, if with probability at least 1 - 6, for any fixed set V C IRd with n elements holds that (1 - -c]]lu| < [|Svi|2 S (1 + +e]lui|| for all u E V.
is known that Gaussian matrices can provide JLTs; e.f. [5, 29].
Lemma 1 (Gaussian random projections [5, 29I). Let G E Rrd with iidd (0,11/V7 and e E (0, For fixed x E IR" it holds that
Pr [|| - || < <||=||²] 2 1 - 2 exp (-m((e))
For a sel X C. Rd of n vectors and for 5 E (0, 1/2), as long as r 4log(2n/6) then G forms an (e, n.LL.
The dimension of G depends on 1/e², which can quickly become very large if a high accuracy is needed. Consequently, if r is very large, then it is also very expensive to compute the product G.A. There is therefore no advantage in taking an approximate solution over computing the true solution. Here, we would like to improve this dependency on To achieve this, we will also use a powerful generalization of JLT, the so-called of Oblivious Subspace Embeddings [40], which extend the JLT definition for an entire subspace, instead of finite set. We use the definitions from [44].
Definition 2 (Oblivious Subspace Embedding [44]). Let 'D be distribution on r x n matrices S, where is a function of n, d and e, ō E (0, 1/2). We call S an (e, 6) Oblivious Subspace Embedding, or (c, 6)-EEE for any fixed n x d matrix A. S ~ D is a (1 + é) 12-Subspace Embedding for A with probability at least - 5, that is, for all x E Rd is holds that
(1 - A2 < ||SAz||2 S (1 (1+ A11
Notation. By default, the Householder notation is used, denoting matrices with capital letters, vectors with small letters, and scalars with Greek letters. [n] is the set (1,2....,,, where n E N. T is the identity matrix of size n X n and e; its i-th column. A. is the element of A in row i and column j. A& denotes the best rank-k approximation of in the 2-norm. || is the Frobenius norm of A, while the 2-norm is assumed for both matrices and vectors when the norm subscript is omitted. A is the transpose of A and At is the pseudoinverse. P[a] E [0, 1] denotes the probability of an event a to occur. A (f, σr) is the normal distribution with mean value μ and standard deviation σ. (A) denotes the i-th largest singular value of A. nnz(A) is the number of nonzeros A. Ō(k) == O log" (k:) for some constant We refer to matrices with i.i.d. elements from ((0 1) as Gaussian matrices. In the complexity analysis, wt denotes the fast matrix multiplication exponent, where 2 < w < 2.37286 [4].
Why Gaussians? In this work we focus on Gaussian random projections. Other constructions satisfying the (e, 8, n).IIIT definition exist in the literature, such as randomized Fourier/Hadamard [2, 3, 43] sparse [1. 15, 17, 30, 32, 35] transforms. When the input matrix is explicitly available,

---

such constructions are faster to apply than Gaussian random projections. However, as already mentioned, this is not the case in the matrix-vector query model. Consider the following simple example. Assume that we are interested to compute the Euclidean row norms of the matrix A where A E [Rax is dense input matrix. As already detailed, these norms can be approximated by the Euclidean row norms of the matrix A 525, where S is an (c, 5, -JLT matrix with r columns. a Gaussian matrix, then can be evaluated in two steps, i.e. by computing = AS and then is a CountSketch [15, 35],
Á AB, with a total complexity of 2 On the other hand, then the matrix B AS can be evaluated in On²)), which is faster than ( However, since B is dense and it has special structure, then the second step A AB still requires 0 operations. The total complexity is therefore still dominated by the O 2 2) term. It is also known that Gaussian matrices require asymptotically less columns than the aforementioned fast transforms to satisfy the (c, 6, n)-JLT definition. This means that Gaussian matrices can in fact be the fastest option, since is minimized. Nevertheless, all results of this work derived as structural results, i.c. they do not necessarily require Gaussian matrices. Any matrix satisfying the properties that detailed in the proofs can be used instead. All aforementioned fast transforms are for example excellent candidates.
Contributions. In Algorithm 1, we present the main algorithm of this work to approximate the Euclidean row norms of matrix A E Ixx which is inspired by the Hutch++ algorithm [34]. Following [34], this algorithm is called "Adaptive." since it needs make two passes over the input matrix A. The main contributions are the following:
1. The proposed algorithms require asymptotically less matrix- queries achieve the same accuracy as standard JL random projections for matrices with decaying spectrum, that is, spectral decay properties are reflected in the approximation bounds. To the best of our knowledge, this is the first work to provably reduce the number of required matrix-vector queries for Euclidean length approximations.
2. For any matrix, regardless of its spectrum, the proposed algorithms require a number of matrix-vector queries that depends on 1/c to achieve e-accuracy for the total, Frobenius norm-wiss error, as opposed to 1/e² for standard JL..
3. For the worst-case inputs, that is, for matrices with flat spectrum, the approximated values are at least as good as standard JL.
4. The techniques can be directly applied to and give similar improvements for the related problems of approximate pairwise Euclidean distances and approximate leverage scores.
Algorithm 1 Adaptive Euclidean Norm Estimation
Input:
Matrix A E nxd n 2 d. positive integer m < d.
Output: 2; = ||e: All3.
# Step 1: Low-rank approximation
1: Construct
random matrices S,G E dxd with i.i.d. elements from (0, 1).
(dm)
2: Compute B= = A A(AS).
O (T (A, m))
3: Compute an orthonormal basis Q E dxxm for range (e.g., via QR).
& O(dm²)
Step 2: Project and compute row norms
4: Compute Ā AQ and C = AG.
D O (A, m)) > Onmm²) > (mm)
5: Compute Á A(I - QQ = - Á(QTO) G).
6: return ã; = |le All2 + ||e, Ál? for all E [n].
In Table 1 we summarize the approximation guarantees of the proposed Algorithms 2, and 3 for the aforementioned problems. We also compare it to the corresponding bounds of existing JL-ba approximations to highlight the achieved improvements. For the precise statements we refer to the corresponding sections.
Regarding the complexity of Algorithm 1, by TMM TMM(A, we denote the complexity of computing the product AB, where B is a dense matrix with columns. For example, if A is just a dense matrix, TMM (A, m) = O(ndm==2), by leveraging fast matrix multiplication [4]. Another example is when A is implicitly available function of given sparse matrix C, e.g. if A 8 then
3

---

Table I: Comparison between the approximation bounds that are achieved in this work versus standard JL random projections for the three different problems considered here. In all cases, the number of matrix-vector queries m that are performed the same.
-² (up to logarithmic factors on n. 6), where E (0. 1/2) is the accuracy and ō E (0, 1/2) the success probability. Here, k is an integer such that m = (kk/6) and A& A Ag. M is matrix such that its rows define pairwise distance vectors between the rows of A. The 0,'s is are the leverage scores of the input matrix.
proportional
Element-wise
Frobenius nosm-wise
This work
JL
This work
JL
ref.
Row norms
<lle_ A
||o A&
<lle A|E elle. MI1
<||A||?
Thms. 1 & 2
Distances <lle7 M| ||e] Mx
e MMMM
<||M
Thm. 5
Leverage scores
c0;
e0,
ed
ed
Thm. 3
TMM = 3 x TMM(C, m) = On)))(C)m) The results are stated for general TMM m), but they will be specialized, where applicable, for the targeted applications.
Related work. A related topic is stochastic matrix trace estimation [7, 27, 28, 34, 37, 39J. Intu- itively, set of data points can be seen as the columns of matrix. In various applications the trace of such a matrix contains useful information like triangle counts in graphs [6]. Hutchinson [27] proposed randomized algorithm rapidly approximate the trace of such matrix, which uses similar ideas to JL: it projects the rows of the matrix onto a fow-dimensional subspace so that the trace can be quickly computed. Avron and Toledo showed that the dimension of that subspace needs be proportional to e in order to guarantee worst-case e-approximation for the trace [7]. This dependence on e matches the requirements for the c-isometry of JL. The c overhead can be prohibitive when is small, i.e. in applications where high accuracy is needed. Recently, in their seminal work, Meyer, Musco, Musco, and Woodruff [34] proved remarkable result: their Hutch++ algorithm is the first to obtain e-accuracy for stochastic trace estimation while requiring only 1/c matrix-vector queries. For the related problem estimating the diagonal elements of matrix, which was also recently studied in depth [9, 26), Baston and Nakatsukasa [9] achieved e-accuracy for the total, norm- norm-wise error of the entire diagonal using (11/c) matrix-vector queries, but not for each individual diagonal element, which should not be possible due to the optimality of the JL lemma [31]. It is worth noting that the squared row norms of matrix A can be found in the diagonal of AA" tthrrefore, our work is closely related. Our results for the total norm-wise error, however (see e.g. Theorem 2), are tighter than simply using [9] on AAT since we are exploiting the special structure of AAT From a Fine-Graii Grained complexity perspective, estimating row norms can be easily reduced diagonal estimation, but the opposite reduction is not straightforward, therefore, one can argue that diagonal estimation is harder, which justifies our tighter bounds.
Outline. The analysis of Algorithm 1 is given in Section 2. In Sections and 4 we show two important applications of the main results, namely for the estimation of the pairwise Euclidean distances between a set of data points and for the estimation of the statistical leverage scores of a tall-and-skinny data matrix. In Section 5 we present indicative experiments to validate the theoretical analysis, before finally giving concluding remarks and future directions in Section 6.
2 Analysis of Algorithm!
In this section we provide the analysis of Algorithm 1. Preliminary results and long proofs which were omitted from the main text and can be found in the Appendix. We state the following general result for the wementtwise bounds of Algorithm 1.
Lemma 2. (Proof in the Appendix) Let A E R If we use Algorithm with m matrix-vector queries to estimate the Euclidean lengths of the rows e, A, i E [n], then as long m 2 1 2 32 log(An/8 4n/5) it holds that
1 5.- le, A11 <
Slog(
TeT - A(I-QQQT )12, for all i E [n].
with probability at least 1 8 for all i [n]] simultaneously.

---

Evidently, this result implies that if we can determine suitable bound for |le A QQT) then we automatically get a proper bound for the element-wise approximations of Algorithm 1. If A has fast decaying spectrum and Q captures the dominant eigenspace of A we can expect that our approximations are very accurate, even for small I. For the general case, however, the following Lemma 3 as well as the optimality of the JL. lemma [31] already hint that this is not possible (see also Appendix II, Limitations low-rank projections).
Lemma 3. Let A E Buxd For
d, it holds that [1e] (A Ax)ll S (A) S I
k
Proof. Clearly, [|,](A- - & |aX1== | (A Ax) 2241 (A). For the second part have that (A) 1/2 & Ei=1of |
2.1 Projecting rows on randomly chosen subspaces
To proceed further with the analysis, we show some Sength-preservve properties the orthogonal projector QQT, which is an orthogonal projector a random subspace as obtained in line 3 of Algorithm 1. Note that Corollary 1 stated for constant factor approximations, Here we provide brief proof sketch. For the main result we refer to Lemma 8 in Appendix III.
Corollary 1 (Projection on rowspace(SA) (SA A)). (Proof in the Appendix) Let 6 E (0, f), Av
A Ag, and S be such that
(i) S D, where D is (1/3,6)-OSS for any fixed k-dimensional subspace;
(ii) S is (1/3, 2n)
If Q is matrix that forms an orthonormal basis for rowspacc(SA") A), then, with probability at least 1 25, for all [n] simultaneously, holds that
le A(I - -QII-QQTTT )1 < ||eT (Aa))l
leeT A llle, A& || S "lle, Alllee Aull-
Proof sketch. To prove the result it suffices to find a projector within rowspace( SAT A) with the desired properties. To do this, consider the matrix II, (&VV SATA, where VR, Mg originate from the SVD of A& = V Clearly, this 11, is rank-k matrix within rowspace(SAA) (SA
After some algebra, the problem reduces to get a bound for the quantities le, AV C s SV.ER k A eeel for all E [n]. where the existence of C-1 is guaranteed due to the (1/3, 8)-OSE property of S. For each this quantity is the absolute value of the inner prod- (S(V,C-1V, V2 A )e;, SV&V A )e:)), which can be written in simplified form as (SIK, Six). Therefore, we use an (1/3,6, 6, 2n) JLT to bound the inner products between the vectors of the set
V = {e, AVE E [m]] Ue, AV. [m]].
finally bound the dlement-wise approximations of Algorithm 1. Theorem 1. (Proof in the Appendix) Let A E Raad and 2 d. If we use Algorithm I with m vetrix-vector queries to estimate the Euclidean lengths of the rows of A, then there exists a global constant C such that, as long
Having all pieces in-place,
(i) m 2 1 2 (log(n//)) such that G satisfies Lemma and S forms an (1/3,6, 2n)-JLT,
(ii) m Z O + logglog/////// (1g((1))), such that S forms an (1/3,8) 8)EEE for a k-dimensional subspace,
then it holds that
i - lee All < CV log le (A
Ax) A||| S CV
log( 2 De
[A Alll TAI,
for all i E [n] with probability at least 1 36.
5

---

Discussion. We can investigate the bounds for special matrix cases. We highlight the approximation power of Algorithm 1 for matrices with decaying spectrum. For matrices with linear decay suffices to take m Z O(c Do(='Vloogje log(n/6) queries to achieve an almost c-accuracy. For matrices with exponential decay we can use as few as m 2 ((log(1/c) matrix-vector queries. For matrices with no decay, e.g., for orthogonal projector matrices, Lemma already guarantees that Algorithm provides at least as accurate element-win wiiee approximations as standard JL projections. We recall once more that the JL lemma is optimal in the general case [31], therefore, improvements can only be derived for special cases, like the ones considered here.
2.2 Frobenius norm bounds
Due to the tightness of Lemma 3, which is crucial for the dlement-wise bounds, is highly unlikely that low-rank projection-basee methods can generally achieve better dlement-wise approximations. However, if carefully examine the total, Frobenius norm-wise error, we can in fact obtain a true e-relative error approximation. This cannot be done by "simply" adding together all element-wise bounds, i.e., we must use a different "collective" approach. This result also makes the element- wise bounds more appealing: even if there remain few outliers that violate the element-wiss e- approximation, the total error is still very small. We note that this a quadratic improvement over the norm-wise eπror of standard JL projections.
Theorem 2. (Proof in the Appendix) In Algorithm 1, for some absolute constants c, C, if c clog(1/6), ) it holds that
X X S CV log( ( ||AlIE
Vlog(t)
where X is the sum of the returned approximations. For I k O
where E (0,1/2).
setting m 2 Ok//6 6 + log( it follows that
X - |AII EElAA
2.3 Complexity
The complexity of Algorithm is as follows. In the first step two matrices S and G must be generated with d m random elements each. Hence, ((d)) calls to a random number generator required. In the second step, the products A (AS) and A (AG) can be both computed in O(TMM(A, m) + [AT m)). Next we need to create an orthonormal basis for A AS which has size d x m. This can be done with a standard Householder QR or another orthogonal factorization in (dm²? [25, Chapter 5]. The complexity of this operation
be improved using fast matrix multiplication primitives [19]. The product AQ costs O (A, m)). We then have to compute Ā(QTOL G), which takes (dm??) or Oddm-11) to first obtain QTG G and then the same cost to get Á(QT G). Finally, for the last step the squared row norms of 2n vectors, the rows of Á, and the rows of Á, are needed. For each row of Å and Á the cost of computing the squared Euclidean norm is Omm) therefore the cost for the last step is O(n)). Summing up, the total cost of Algorithm is (dm² + TMM A, m) + nm).
3 Euclidean distances
In many applications it is desired to find an approximate isometry for set of data points. Let A E nxd be a matrix whose rows define these d-dimensional data points. Assume we are interested to estimate all the (2) distances between the rows of A. Let B be matrix with size (?) x and each row of B equal to the vector (e, - e for some j. E [n]. Each row (e: ee) of B, when multiplied with A, gives the difference vector E, A - e. A. Therefore, to estimate the Euclidean distances between the rows of A, it is sufficient to estimate the Euclidean lengths of the rows of the matrix B.A. Algorithm 2 we describe this procedure for a general "incidence matrix" B, e.g., when one wants to estimate only a subset of the pairwise distances. Since B has in general more rows than A, the matrix multiplications must be computed in the correct order to minimize their complexity.
Note that B is nothing than the edge incidence matrix of complete graph.

---

Algorithm 2 Adaptive Euclidean Distance Estimation
Input: Data matrix A R t 2 d, incidence matrix B R positive integer m d. Output:
Approximate pairwise distances T; z ||e, BA i E [n]. # Step 1: Low-rank approximation
1: Construct two random matrices S, G E Rd with i..d. elements from (1, 1).
D ((m))
2: Compute the product S = A ( (B(())))
D OT(MM (A, m) + TMM (AM(AA (AT 3: Compute an orthonormal basis Q E _d for vange(S) (e.g., via QR).
.m) + nm)
> (dm²²)
# Step 2: Project and compute row norms
4: Compute À = AQ and C = AG.
D O(TMM (A, m))
5: Compute Á = A(1 - QQ")== C-A(Q
A(QTTT)) G).
> (tm²²) D (
6: return ã; = [Iee B) + [I(e, B)ål for all E |n].
Bounds. Approximation bounds can be directly derived from Theorems and 2, replacing A with BA. For completeness, they can be found in Theorem 5 in the Appendix.
Complexity. The complexity of Algorithm 2 is as follows. O(dm) operations are needed to generate G and S. The product $ = A B B AS is evaluated in three steps. We first com- pute AS in (TTMM m)). then ((AS) and B' (BAS) in O(n)), and finally A ATBB" BAS) in O(TMM(A ,m)). The intermediate products can be caleulated batches to save memory. The QR factorization of Š requires O(dm²). The products À AQ and ((TMM A, m)), whereas the product Q G can be performed in O(dm²). Accordingly, the product Á(Q G) needs Otm²²) and C Á(Q T G) O(m)). In the last step each row norm costs O(m) operations, resulting in ((n)). The total complexity of Algorithm 2 is therefore
AG both require
O (TMM (A, m) + (A" m) + nm + dm3 + +dm).
4 Statistical leverage scores
We next consider the problem of approximating the leverage scores of tall-and-skinny matrix. The leverage scores of the rows of can found in the diagonal of the orthogonal projector matrix P = AAT = UU where U is any orthonormal basis for (A)) Specifically, the leverage score 0, of the i-th row of A is equal to all the following quantities
0. = le AA 1 e, AA'e e,U'
& e T.UUTe lle T
0, It is known that the leverage scores of n d matrix A with rank(A) = S d sum to >i= =r. Leverage scores are important in outlier detection, graph sparsification, and numerical linear algebra. We consider the general case where U is not explicitly available, and only have access to A.
To simplify the analysis, we assume that the matrix A has full column rank. The true rank r of A (or the numerical rank, if A is approximately low-rank) as well as a corresponding set of r linearly independent columns of A can be computed in ((nzz( A) + d' (()))), with provable approximation guarantees for the leverage scores of the selected column subset. See sections 4 and 5 of [41] for details and [8. 12, 13] for related algorithms and lower bounds.
To use Algorithm to estimate leverage scores, we first need a linear operator that computes AA's for an arbitrary vector v. Since evaluating (A7 A) in order to compute its pseudoinverse and ultimately the orthogonal projector AAt A(AT A)t AT is expensive, we opt for fast approximate operator. For this we can use standard techniques from the literature. One of the first approximation algorithms for tall-and-skinny leverage scores was proposed in [21]. In [41] it shown that this algorithm is only efficient for dense matrices, or more specifically for matrices with at least w n. nonzeros per row. Given Rdd with n >> d and w (logn) nonzeros per row, the idea consists of approximating the leverage scores of the rows of A with the squared Euclidean row norms of the matrix
A(1I,))111.
Some intermediate steps be slightly improved using fast matrix multiplication.
7

---

Here, II is a subspace embedding for range(A) and HI, is an e-JLT. It can be proved that (II A)1 in fact an approximate "orthogonalizer" for A. a property that we can leverage in our algorithm. Specifically, we apply Algorithm 1 to approximate the Fuclidean row norms of A(T1A) instead of multiplying with 1l.. This procedure is described in Algorithm
Algorithm 3 Adaptive Leverage Scores Estimation
Input: A E gaxd, with n >> and (log n)) nonzeros per row, positive integer m < d.
Output: Approximate leverage scores 0; R ||e A| i E [n].
# Step I: Construct approximate pseudoinverse operator
1: Construct II, an (e1, 0)-OSE for range( A).
2: Compute R from a QR factorization of I1, i.. II =QR and use R-1 substitute for (II,
Step 2: Low-rank approximation
3: Construct two random matrices S, G E Rdxm with i.d. elements from (0, > ((m))
4: Compute the product S = Rt (AT (A)R-
(TMM (A, m)) > Odm²²)
5: Compute an orthonormal basis
d for range($) (e.g., via QR).
Step 3: Project and compute row norms
6: Compute À = A(R QQ) and C GG)
> O (A, m)) b (dm²) D ((m)
7: Compute Á = A(I - QQ = C- A(Q G).
8:
return i) = 0, [I(e; B) + lI(e; B) for all i E [n].
The following theorem gives approximation bounds for the leverage scores returned by Algorithm 3.
Theorem 3. Let A E Baxd, 0; ||e] AAtI2 and 0g the values returned by Algorithm 3. The following hold:
n d
10,-011 (e1 + ve2)0,, and
Σ
0
S (E1 + E2)d.
Proof: Let 0; = [0e]= A(T]AA[TA)) so that
00 0.1 10: 0. + 0: 0,1 10, 0,1 +.1+10 +100 1
From [21, Lemma 9] it follows that 10, - 0,1 - -,00, Subsequently, 0, (1 + 1- -1)0 - 0, From Theorem we recall that for appropriate m, k,
A - 0. s Vc20; I ( (1/9 )o,
Combining all these observations we find that
4 Vo 0, < 2( 0.
0, 0,1 < 8,
8, + 0 0,
61
Rescaling é1 and 62 gives the clement-win bounds. For the Frobenius norm bounds can use similar arguments combination with Theorem
Complexity and choice of c1, 6g- The complexity of Algorithm 3 can be split into two parts: (i) the complexity of obtaining an 61 é1-approximate orthonormal basis for A, and (ii) the complexity of estimating the norms of this basis. The complexity of the former has been heavily studied in the literature and depends on the choice of the subspace embedding. For very tall-and-skinny matrices, an efficient construction is
combination of CountSketch [15, 35), Subsampled Randomized Hadamard Transform (SRHT) [43] and a Gaussian subspace embedding; see e.g. [15]. This provides sketch 1I, A with dimension O(d/e²) x d in 7 (II, A) time. Computing the QR factorization of the sketch requires Oid3 /22) to obtain R. Since R is upper triangular, the computation of
R R-+G and GG) cost ( (A, m)) each. The
R R-'Q both take m() The products A(R-1Q) -Q) and A(R-IG)
last step takes (nm) The total complexity is
(II + d / 2 Tam m) + nm).
8

---

To achieve e-accuracy in the Frobenius norm, it suffices to use m = O(/log(n/0)//e) With E C2 e, the total complexity becomes
( + d²/e² (A, vlog(n/o)/e) + h mogooolllonn////////
If, instead, we use standard JL projections to estimate the row norms of AR the total complexity is A + d² / (A, log(n/6)/ log(n/6))
to achieve the same Frobenius norm-wise accuracy. For any matrix which is "tall-enough" such that the (TTMM(,, A, log(n/6)/ce)) factor dominates the complexity, Algorithm 3 achieves quadratic improvement over standard estimators.
Numerical experiments
Algorithm 1 was implemented in Python using NumPy. We conducted experiments to verify the approximation guarantees and the convergence improvements against standard Gaussian random projections. Following [34], we generated synthetic matrices with decay in the spectrum. Specifically, d matrices A, with = 5000, were created as follows. We drew a random orthogonal d x matrix Q. We then fixed diagonal d x d matrix A which defines the eigenvalues of the matrix. Each element Ac,s, i E [d] is set to i- for a given e 2 O. The larger the e, the faster the spectral decay. We finally constructed the symmetric = QAQ T which were used in the numerical experiments. Following [34], we applied four different decay factors, specifically
{0.5, 1, 1.5,).
The approximation errors of standard JL projections versus Algorithm are compared in Figure 1. We plot the approximation errors of both methods as the number of samples increases. We plot two types of errors, the maximum element- wise and the Frobenius norm-wore wise errors
T |e_ A|
X ||A|I |APE
max (E(d]
and
le: A|
where ē; are the approximated row norms and X is their sum returned by either Algorithm 1 or standard JL projections. The exact same number of matrix vector queries is used in both methods. Standard JL projections involve only one random matrix G, which is multiplies A from the right. G has size d x m, m being the number of samples. Algorithm 1, on the other hand, A multiplied four times with matrix from the right. Therefore, x m/ 4, so that both algorithms are tested with the same number matrix-vector products. each plot we illustrate the mean error over 10 independent runs and the standard deviation. Standard JL approximations perform marginally better than Algorithm I only for the element- wise errors and only for the matrix with very slow decay. In all other cases, Algorithm I performs significantly better.
set G, S, and Q in Algorithm to have size
6 Conclusion
We proposed an adaptive algorithm estimate the Euclidean row norms of matrix A. This algorithm improves standard matrix-vector queries are required to achieve the same Frobenius norm-wise accuracy for all matrices; (ii) Asymptotically less ceatrix-vecto queries are needed to achieve the same dlement-wise accuracy for matrices with decaying spectrum; (iit) At least as accurate dement-wise approximations as standard JL are achieved for worst-case input matrices, that is, for matrices with flat spectrum. We also showed how these results can be applied to other important problems, specifically to estimate Fuclidean distances between data points, which is related to the fundamental concept of approximate isometries that has many applications in data science, as well as for statistical leverage scores estimations, which ubiquitous quantities not only in data science and statistics, but also in numerical linear algebra and spectral graph thcory.
estimators in the following aspects: (i) Quadratically less
As future work, several directions can be envisioned. Most prominently, it would be interesting to determine whether the studied techniques can be used to improve Oblivious Subspace Embeddings [40, 44]. Such improvements would have an immediate impact in many problems in NLA, e.g. least squares regression, low-rank approximations and column subset selection. Two other relevant topics concern (a) the possibility to derive lower bounds similar to [34] for Fuclidean row norms estimation and (b) to make the algorithms non-adaptive, like the non-adaptive versions of Hutch++ [28, 34] which are based results from [14], the Nyström++ of [37].

---

JL (norm-wise)
J. (elemeet-wisee) Alp1 (element-wisgg
JL (norm-wise)
JL le ement-wise)
Alg1 (norm-wise)
Alg1 (norm-wise)
Alg1 (element wise!
109
10
Relative
10a2
Relative
10-1
10-3
10
10-4
106
200
100
200
Matrox-vector multiplication quenes
Matrix-vector multiolication queries
Very slow eigenvalue decay (c = 0.5)
Slow eigenvalue decay (c 1.0)
Inrorm-wisel
(element wise)
JL (norm wisel Alg1 (norm-wise)
ement emeettwisc) Alg1 (element-wisel
Alg1 (normwwise]
+
Alp1 (element-wiss))
10
10-1
10
10-3
Relative
Relative
10-7
10-5
20
10-7-
10-
100
100
200
300
409
500
600
Matrix vector multiplisation queries m
Matrixvectto vector multiplication queries m
Matrix
(c) Moderate eigenvalue decay (c 1.5)
(d) Fast eigenvalue decay 2.0)
Figure 1: Comparison between the element-wise (dashed curves with "x" marker) and norm-wise (solid curves with "star" marker) relative errors of Algorithm (blue) and standard Gaussian random projections (red) versus number of matrix-vector multiplication queries (x-axis) mean relative еrror of the approximation averaged over 10 independent runs is plotted. The upper and lower bounds around each curve represent the standard deviation. As expected, for matrices with a very slow decay standard JL projections perform marginally better with respect to the element-wis errors, but Algorithm I performs significantly better for all other cases.
random matrices with power law spectra. The
Acknowledgements
The authors would like to thank Cameron Musco for helpful comments.
References
[1] Dimitris Achlioptas. Database- frienndlyefredlyyyyeeee random projections: Jaansson-Lnddentraann with binary coins. Journal of computer and System Sciences, 66(4))671-687, 2003.
[2] Nir Ailon and Bernard Chazelle. The fast Johnsonnn transform and approximate nearest neighbors. SIAM J. Comput.. 39(1)3302-322, 2009.
[3] Nir Ailon and Edo Liberty. Fast dimension reduction using rademacher series on dual bch codes. Discrete & Computational Geometry, 42(4):615-630, 2009.
[4] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proc. 202/ ACM-SIAM Symposium on Discrete Algorithms, pages 522-539. SIAM, 2021.
[5] Rosa Arriaga and Santosh Vempala. An algorithmic theory learning: Robust concepts and random projection. Machine learning, 63(2):161-182. 2006.
10

---

[6] Haim Avron. Counting triangles in large graphs using randomized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Applications, volume 10, pages 10-9, 2010.
[7] Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. JACM, 58(2):1-34, 2011.
[8] Maria-Florina Balcan, Yi Li, David P Woodruff, and Hongyang Zhang. Testing matrix rank, optimally. In Proc. 30th ACM-SIAM Symposium Discrete Algorithms, pages 727-746. SIAM, 2019.
[9] Robert A Baston and Yuji Nakatsukasa. Stochastic diagonal estimation: probabilistic bounds and an improved algorithm. arXiv preprint arXiv:2201. 10684, 2022.
[10] Kai Bergermann and Martin Stoll. Fast computation of matrix canction-based centrality mea- sures for layer-coupled multiplex networks. Physical Review E, 105(3):034305, 2022.
[11] Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. Random projections for k-means clustering. Advances Neural Information Processing Systems, 23, 2010.
[12] Nadiaa Chepurko, Kenneth L. Clarkson, Praneeth Kacham, and David P Woodruff. Near-optimal algorithms for linear algebra in the current matrix multiplication time. In Proc. 2022 ACM-SIAM Symposium Discrete Algorithms, pages 3043-3068. SIAM, 2022.
[13] Ho Yee Cheung. Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. JACM, 60(5):1-25, 2013.
[14] Kenneth L Clarkson and David Woodruff. Numerical linear algebra in the streaming model. In Proc. 41st ACM Symposium on Theory of Computing, pages 205-214, 2009.
[15] Kenneth L Clarkson and David Woodruff. Low-rank approximation and regression in input sparsity time. JACM, 63(6): 1-56, 2017.
[16] Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proc. 47th ACM Symposium Theory of Computing, pages 163-172, 2015.
[17] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse Johnson-Lindenstennn Lindenstrauss transform. In Proc. 42nd ACM Symposium Theory of Computing, pages 341-350, 2010.
[18] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithmss, 22(1):60-65, 2003.
[19] James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra stable. Numerische Mathematik, 108(1):59-91 2007.
[20] Michal Derezinski, Jonathan Lacotte, Mert Pilanci, and Michael W Mahoney, Newton-LESS: Sparsification without trade-offs for the sketched Newton update. Advances in Neural Informa- tion Processing Systems, 34, 2021.
[21] Petros Drineas, Malik Magdon-Ismail Michael W Mahoney, and David P Woodruff. Fast approximation of matrix coherence and statistical leverage. JMLR, 13(1):347533066 2012.
[22] Petros Drineas, Michael W Mahoney, Shan Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische mathematik, 117(2):119-449, 2011.
[23] Ernesto Estrada and Naomichi Hatano.
Hatano. Communicability in complex networks. Physical Review
E, 77(3))03611 11, 2008
[24] Alex Gittens and Michael W Mahoney, Revisiting the Nyström method for improved large-scale machine learning. JMLR, 17(1):3777-0411, 2016.
[25] G.H. Golub and C.F. Van Loan. Matrix Computationss Johns Hopkins Studies in the Mathemat- ical Sciences. Johns Hopkins University Press, 2013.

---

[26] Eric Hallman, Ilse CF Ipsen, and Arvind Saibaba. Monte Carlo methods for estimating the diagonal of real symmetric matrix. arXiv preprint Stti:2202.028887,, 2022.
[27] Michael Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in CoutittccsSimmlattin and Computation, 18(3): 1059- 1076, 1989.
[28] Shuli Jiang, Hai Pham, David Woodruff, and Richard Zhang. Optimal sketching for trace estimation. Advances in Neural Information Processing Systems, 34, 2021.
[29] William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math., 26(1):189-20) 1984.
[30] Daniel M. Kane and Jelani Nelson. Sparser Johnsom-Lindeestrrun Transforms. JACM, 61(1):1-
23, January 2014.
[31] Kasper Green Larsen and Jelani Nelson. Optimality of the Johnson--Lindesstrauss lemma. In 58th IEEE Symposium Foundations of Computer Science, pages 633-638, IEEE, 2017.
[32] Ping Li, Trevor J Hastie, and Kenneth W Church. Very sparse random projections. In Proc. 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 287-296, 2006.
[33] Michael W. Mahoney. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning, 3(2):123-224 2011.
[34] Raphael A. Meyer, Cameron Musco, Christopher Musco, and David P. Woodruff. Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity Algorithms, pages 142-155. SIAM, January 2021.
[35] Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th IEEE Symposium on Foundations of Computer Science, pages 117-126. IEEE, 2013.
[36] Mark EJ Newman. A measure of betweenness centrality based random walks. Social networks, 27(1)399-5, 2005.
[37] David Persson, Alice Cortinovis, and Daniel Kressner. Improved variants of the Hutch++ algorithm for trace estimation. SIAM J. Matrix Anal. Appl., 43(3):1162-1188 2022.
[38] Mert Pilanci and Martin Wainwright. Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM J. Optim., 27())205-244, 2017. 2017.
[39] Farbod Khoraaa and Uri Ascher. Improved bounds on sample size for implicit matrix trace estimators. Foundations of Computational Mathematics, 15(5):1187-12122 2015.
[40] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections.
In 47th IEEE Symposium Foundations of Computer Science, pages 143-152. IEEE, 2006.
[41] Aleksandros Sobczyk and Efstratios Gallopoulos. Estimating leverage scores via rank revealing methods and randomization. SIAM J. Matrix Anal. Appl., 42(3): 1999-12199-1288 2021.
[42] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J.
40m 1916)11113-1 2011.
[43] Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02): 11- 2011.
[44] David P. Woodruff. Sketching tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See for example Section II in the Appendix (which also mentioned in the main text), where we describe why our methods cannot achieve true element-wist e-approximations.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is more related to the mathematical foundations of AL.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We always state what the inputs of our algorithms are expected to be, what sizes or properties should the matrices have, etc.
(b) Did you include complete proofs of all theoretical results? [Yes] Short proofs were left in the main text. Longer proofs were placed the Appendix. All new Lemmas, Theorems and Corollaries have been rigorously proved. All imported theoretical results have been clearly cited.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No] No because the code proprietary.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] We do not perform training.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 5
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Our small scale indicative experiments were ran small laptop.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We did not use any external assets.
(b) Did you mention the license of the assets? [N/A] We did not use any external assets.
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We did not any external assets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We did not use any external assets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing or conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We did not crowdsourcing conducted research with human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did not use crowdsourcing or conducted research with human subjects.
13


Reviews:
[{"review_id": "GiPM4mjhY5I", "reviewer": "Reviewer_Lczq", "summary": "The authors provide a dimensionality reduction techniques that is more optimized towards certain data than the traditional JL. Specifically speaking, while JL is known to be optimal when dealing with data with no decay, it is not the optimal method when dealing with datasets that admit exponential or even linear decay. In this paper, the authors provide a technique inspired by the Hutch++ algorithm that deals with such instances of data.", "questions": "The results stated in the paper seem sound and are contributing. However, a valid question that usually pops up among practitioners who aim to use dimensionality reduction to boost the performance of their work, are matrices with linear decay/exponential decay common in the field of data science, i.e., how often we get to actually deal with such data that admits such properties?\n\nIn addition, is it possible to use some variant of your analysis when dealing with lewis weights?\n\nFinally, please make sure that the main manuscript is at most 9 pages, while the current version of the paper can be refered to as the supplementary material.", "limitations": "The authors clearly stated the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n    1) The paper seems sound theoretically, which hinges upon using delicate and interesting lemmata and theorems.\n    2) The experimental section (regardless of using only synthetic data), shows that JL is indeed not optimal for the case where data admits linear/exponential decay.\n\n* Weaknesses:\n    1) The writing of the paper is somewhat hard to follow, especially around the proof sketches.\n    2) The experimental section only accounts for synthetic data. Is it possible to add an experiment that includes real-world data? This will indeed highlight the applicabilities of your approach.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7LjZRQULin3", "reviewer": "Reviewer_Bucs", "summary": "For the Johnson Lindenstrauss transform we can embed $n$ points in $O(\\log(n)\\epsilon^{-2})$ dimensional space such that we have at most $\\epsilon$ distortion. This paper instead look at the problem of having an embedding that only preserves the norm of the data points instead of the metric. The paper does this so that the dimension of the new space only has an $\\epsilon^{-1}$ dependence. The goal is that doing it via such an embedding is faster than just computing the norm of the row. \n\nThe paper then presents two applications including computing the metric. ", "questions": "So for context, the reason we like the JL transform is because we can compute it quickly (i.e. faster than doing regular matrix multiplication) [1]. However, the key idea there is the fact that we can do the transform using a Fourier transform and sparse matrices. \n\nHowever, in this paper, we are using a Gaussian matrix. So the matrix multiplication for $AS$ in Algorithm 1 step 2 is multiplying a $n \\times d$ matrix by a $d \\times m$ matrix where $m \\le d \\le n$. My understanding is that the best rate for this is still $O(m^{\\omega-2}dn)$ where $\\omega \\ge 2$ is the exponent for square matrix multiplication (i.e. multiply two $n\\times n$ matrices in time $O(n^\\omega)$. However, that is old. Looking for more new results I found [3] which shows that for multiplying an $n \\times n^\\alpha$ matrix with a $n^\\alpha \\times n$ matrix can be done in $O(n^{2+\\epsilon})$ for any $\\epsilon > 0$. Hence I am not sure if that matrix multiplication can be done faster than $O(nd)$ which is the time taken to compute the true norms. \n\nEven otherwise with step taking $O(nm^2)$ we need $m \\le \\sqrt{d}$. \n\n\n[1] THE FAST JOHNSON–LINDENSTRAUSS TRANSFORM AND APPROXIMATE NEAREST NEIGHBORS∗\nNIR AILON† AND BERNARD CHAZELLE‡\n[2] Knight, Philip A., Fast rectangular matrix multiplication and QR decomposition, Linear Algebra Appl. 221, 69-81 (1995). ZBL0827.65044.\n[3]  Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor by François Le Gall† Florent Urrutia\n\n", "limitations": "Yes. ", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Post Rebuttal**\n\nI thank the authors for their response. Their response does help clarify my questions about applications and the matrix multiplication. \n\nIn light of this I raise my score. \n\n**Strengths**\n\nI think the problem is very interesting and I like the proof techniques as well. \n\nThe algorithm is theoretically motivated and the results are theoretically proved. \n\nThe improvement over the JL is empirically demonstrated. \n\n**weaknesses**\n\nWhile the paper does present two applications. I am left unclear as to where this problem shows up in practice (even though the problem is interesting). \n\nThe cost of matrix multiplication has not been discussed and this is crucial to the viability of the method.  \n\nI am not sure if this the best fit for a the machine learning community. Maybe the theoretical CS community might appreciate this more (SODA, FOCS, STOC etc). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6zFCPWgEtiA", "reviewer": "Reviewer_GYrC", "summary": "The proposed problem is to estimate the euclidean length of matrix rows, and the authors propose a solution using fewer queries than requires by the JL-transform. This is done in the \"matrix-vector query model\", where access to the target matrix A is indirect, and only via queries of the form Ax for any vector x. The authors suggest an algorithm based on the Hutch++ algorithm, and give some claims of optimality. Results are derived for estimating Frobenius norms, inter-row distances, and statistical leverage scores.", "questions": "What is the main algorithmic contribution above the Hutch++ algorithm? \n\nCan you further elaborate on the import of Lemma 3, and what it means for the optimality of Theorem 2?\n\n--------------------------------\n\nFollowing the author rebuttal, and explanation on contribution above the Hutch++ algorithm, I've raised my score to 5. \n\nConcerning the statement of the JL lemma: Your Definition 1 relates to the norm of the input vectors. JL relates to the distance between the input vectors. This isn't the same, and the latter can be maintained without the former. ", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Rigorous approach to several interesting mathematical problems.\n\nWeaknesses: The authors fail to argue that this paper has sufficient (in fact, any) ties to other machine learning applications. In my opinion the paper is out of scope for this conference, and seems more suited to a cs theory conference. The matrix-vector sample model is also quite limited, and in general I'm also unsure of how much this is a contribution this paper makes over those of the Hutch++ algorithm. The results seem incremental.\n\nMinor concern: The statement of the JL lemms is not precise, as the lemma itself relates to distances and the statement relates to norms. It is true that norms imply distances, but only if the transform is linear, and only if one takes the input set to be all difference vectors, which is a larger set. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6tHpiqYnZHo", "reviewer": "Reviewer_FGjt", "summary": "The authors give an algorithm to approximate the pairwise Euclidean distances of row vectors of any given matrix. This algorithm improves the bounds of typical Johnson-Lindenstrauss estimators in a few specific settings:\n- When achieving the same Frobenius norm-wise accuracy, less matrix-vector queries are required;\n- When achieving the same element-wise accuracy less matrix-vector queries are required;\n- The algorithm given is as least as accurate as the standard Johnson-Lindenstrauss techniques, when given matrices with flat spectrums.", "questions": "Suggestion: improve notation, try to include more details ", "limitations": "No potentially negative societal impact in sight.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and structured. The algorithms are well presented, but the authors tend to omit details. The main results, that is Theorems 1,2,3 and 5, show that the techniques of the authors are improvements of the Johnson-Lindenstrauss techniques for their specific use-case. The presentation of proofs is overall good, with a few minor inconveniences. The proofs, that are omitted from the paper and are part of the Appendix, are at least sketched, so the reader gets an idea of the proof. Also enough text is given to follow the structure of the paper.\n\nBecause of the notation, sometimes the math is hard to read/follow (see the proof sketch of Corollary 1 for example, also Alg1 as placeholder for the output is suboptimal).\n\nThe paper is well written, besides some minor issues with the notation. The result is interesting and a real improvement for the cases presented. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept