Faster Linear Algebra for Distance Matrices
Authors: Piotr Indyk
Sandeep Silwal
Venue: NeurIPS 2022 Accept (2022)
Keywords: distance matrices
numerical linear algebra
low-rank approximation
sublinear algorithms

Abstract: The distance matrix of a dataset $X$ of $n$ points with respect to a distance function $f$ represents all pairwise distances between points in $X$ induced by $f$. Due to their wide applicability, distance matrices and related families of matrices have been the focus of many recent algorithmic works. We continue this line of research and take a broad view of algorithm design for distance matrices with the goal of designing fast algorithms, which are specifically tailored for distance matrices, for fundamental linear algebraic primitives. Our results include efficient algorithms for computing matrix-vector products for a wide class of distance matrices, such as the $\ell_1$ metric for which we get a linear runtime, as well as an $\Omega(n^2)$ lower bound for any algorithm which computes a matrix-vector product for the $\ell_{\infty}$ case, showing a separation between the $\ell_1$ and the $\ell_{\infty}$ metrics. Our upper bound results in conjunction with recent works on the matrix-vector query model have many further downstream applications, including the fastest algorithm for computing a relative error low-rank approximation for the distance matrix induced by $\ell_1$ and $\ell_2^2$ functions and the fastest algorithm for computing an additive error low-rank approximation for the $\ell_2$ metric, in addition to applications for fast matrix multiplication among others. We also give algorithms for constructing distance matrices and show that one can construct an approximate $\ell_2$ distance matrix in time faster than the bound implied by the Johnson-Lindenstrauss lemma.

Faster Linear Algebra for Distance Matrices
Piotr Indyk MIT indyk@mit. edu
Sandeep Silwal
MIT silwal Gmi ..t.eudu
Abstract
The distance matrix of dataset X of n points with respect a distance function f represents all pairwise distances between points in X induced by f. Due to their wide applicability, distance matrices and related families of matrices have been the focus of many recent algorithmic works. We continue this line of research and take broad view of algorithm design for distance matrices with the goal of designing fast algorithms, which are specifically tailored for distance matrices, for fundamental linear algebraic primitives. Our results include efficient algorithms for computing matrix- vector products for wide class of distance matrices, such as the l metric for which we get a linear runtime, as well as an 32(n²) lower bound for any algorithm which computes matrix-vector product for the Loo case, showing a separation between the & and the lo metrics. Our upper bound results, in conjunction with recent works on the matrix-vector query model, have many further downstream applications, including the fastest algorithm for computing relative error low-rank approximation for the distance matrix induced by 4 and 2 functions and the fastest algorithm for computing an additive error low- rank approximation for the f2 metric, in addition to applications for fast matrix multiplication among others. We also give algorithms for constructing distance matrices and show that one construct approximate l distance matrix in time faster than the bound implied by the Johnson-Lindensee
lemma.
Introduction
Given of n points X (......,.. Jn the distance matrix of X with respect to distance function is defined as the n X n matrix A satisfying At,j f(x,, Distances matrices are ubiquitous objects arising in various applications ranging from learning image manifolds (TSLO) [S06),
signal processing (SY07] biological analysis [HS93), and non-linear dimensionality reduction [Kru64] Kru78 (SL (CO8), to name a few Unfortunately, explicitly computing and storing A
requires at least (2n²) time and space. Such complexities are prohibitive for scaling to large datasets.
silver lining is that in many settings, the matrix A is explicitly required. Indeed in many applications, it suffices to compute some underlying function or property of A, such as the eigenvalues and eigenvectors of A a low-rank approximation of A. Thus an algorithm designer can hope to use the special geometric structure encoded by A to design faster algorithms tailored for such tasks.
Therefore, it is not surprising that many recent works explicitly take advantage of the underlying geometric structure of distance matrices, and other related families of matrices, to design fast algorithms (see Section 1.2 for thorough discussion of prior works). In this work, continue this line of research and take broad view of algorithm design for distance matrices. Our main motivating question is the following:
We refer reader survey (DPRV15) for a more thorough discussion of applications distance matrices.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Can we design algorithms for fundamental linear algebraic primitives which are specifically tailored for distance matrices and related families of matrices?
We make progress towards the motivating question by studying three of the most fundamental primitives in algorithmic linear algebra. Specifically:
1. We study upper and lower bounds for computing matrix-vector products for a wide array of distance matrices,
2. We give algorithms for multiplying distance matrices faster than general matrices, and,
3. We give fast algorithms for constructing distance matrices.
1.1 Our Results
We now describe our contributions in more detail.
1. We study upper and lower bounds for constructing matrix-vector queries for a wide array of distance matrices.
matrix- veetor query algorithm accepts a vector as input and outputs the vector Az. There is substantial motivation for studying such queries. Indeed, there is now a rich literature for fundamental linear algebra algorithms which are in the "matrix free" or "implicit" model. These algorithms only assume access to the underlying matrix via matrix-vector queries. Some well known algorithms in this model include the power method for computing eigenvalues and the conjugate gradient descent method for solving a system of linear equations. For many fundamental functions of A, nearly optimal bounds terms of the number of queries have been achieved [MMI5] BHSW20 BCW B22. Furthermore, having access to matrix-vector queries also allows the simulation of any randomized sketching algorithm, well studied algorithmic paradigm its own right [4oo14]. This is because randomized sketching algorithms operate the matrix IIA or AlI where II is suitably chosen random matrix, such as a Gaussian matrix. Typically, II is chosen so that the sketches IIA or All have significantly smaller row column dimension compared to A. If A is symmetric, we can easily acquire both types of matrix sketches via a small number of matrix -vector queries.
Therefore, creating efficient versions of matrix-vector queries for distance matrices automatically lends itself to many further downstream applications. We remark that our algorithms can access to the set of input points but do not explicitly create the distance matrix. A canonical example of our upper bound results is the construction of matrix-vector queries for the function [(x,, y) = | vilk-
Theorem 1.1. Let p 2 be an integer. Suppose we are given dataset of n points X Ix, C Rd. X implicitly defines the matrix A., = ||=; æ, [pp Given a query E R", we can compute Az exactly in time O(dd). If is odd, we also require O(ndlog n) preprocessing time.
We give similar guarantees for a wide array of functions f and we refer the reader to Table ! which summarizes our matrix-vecto query upper bound results. Note that some of the functions f we study in Table I do not necessarily induce a metric the strict mathematical sense (for example the still refer to
function f far y) || yll2 does not satisfy the triangle inequality). Nevertheless, such functions under the broad umbrella term of "distance functions" " for ease of notation. We always
explicitly state the function f we referring to.
Crucially, most of our bounds have a linear dependency on n which allows for scalable computation as the size of the dataset X grows. Our upper bounds are optimal in many cases, see Theorem A.13
Combining our upper bound results with optimized matrix-free methods, immediate corollaries of our results include faster algorithms for eigenvalue and singular value computations and low-rank approximations. Low-rank approximation of special interest as it has been widely studied for distance matrices; for low-rank approximation, our bounds outperform prior results for specific distance functions. For example, for the e and E case (and in general PSD matrices), (BCW20) showed that rank-k approximation can be found in time (nddk/E + - -E"" -/""") I)). This bound has extra poly(1/e) overhead compared to our bound stated in Table 2 The work of [TV has worse poly(k, 1/e) overhead for an additive error approximation for the &g case. See Section 1.2 for further discussion of prior works. The downstream applications of matrix-vector queries are summarized in Table 2

---

Function
fæz y)
Preprocessing
Query Time
Reference
eb for even e for p odd Mixed &o Mahalanobis 2istance
|| ylp
((ndp)
Thms.
A.1
A.3
|| =lB
O(ndlog n) OOndlog n) O(ndP)
O (ndp)
Thms.
2.2
A.4
max 1s |oa أy!
(n?²)
Thm.
A.5
x² My
(nd)
Thm.
A.6
Polynomial Kernll
(z,, y)
O (nd")
Thm.
A.7
Total Variation Distance
(V y)
Oggdlogn)
(nd)
Thm.
A.8
KL Divergence
DKL(2 Il
(ndd
Thm.
A.2
Symmetric Divergence
DKL (2 (1 + (y
(ndd
Thm.
A.9
Cross Entropy
(xr, v)
(
Thm.
A.9
Hellinger Distance
E Vz(O)()
(nd)
Thm.
A.10
Table I: A summary of our results for exact matrix-vector queries.
We also study fundamental limits for any upper bound algorithms. In particular, we show that no algorithm can compute matrix-vector query general inputs for the foc metric in subquadratic time, assuming a standard complexity-theoe assumption called the Strong Exponential Time Hypothesis (SETH) [POT [PZ]T]
Theorem 1.2. For any 0 and d = w(og n),, any algorithm for exactly computing for any input 2, where A is the fox distance matrix, requires Q(n²~a) time (assuming SETH).
This shows separation between the functions listed in Table and the too metric. Surprisingly, can create queries for the approximate matrix-vector query in substantially faster time.
Theorem 1.3. Suppose X S (0,,,...,01))" ((1))d We can compute By in time O dOlvalog(d/e)) where | - ol E.
To put the above result into context, the lower bound of Theorem 1.2 holds for points sets in {0, 1, 2, in d z log dimensions. In contrast, if we relax to approximation guarantee, we can obtain subquadratic-time algorithm for d up to O(log" (n)) log log(n)).
Finally, provide general understanding of the limits of upper bound techniques. In Theorem B.I. we show that essentially the only f for which our upper bound techniques apply have a "linear structure" after suitable transformation. We refer Appendix Section B for details.
2. We give algorithms for multiplying distance matrices faster than general matrices.
Fast matrix-vector queries also automatically imply fast matrix multiplication, which can be reduced series of matrix-vector queries. For concreteness, if f is the eg function which induces A, and B is any n matrix, we can compute AB in time O(n² O(n²dp). dp). This substantially faster than the general matrix multiplication bound of n ~ n 2.37 We also give an improvement of this result for case where we are multiplying two distance matrices arising from ey See Table 2 for summary.
3. We give fast algorithms for constructing distance matrices.
Finally, we give fast algorithms for constructing approximate distance matrices. To establish some context, recall the classical Johnson-LLndenstren projection of dataset X C Rd of size onto dimension of size Ollog n) approximately preserves all pairwise distances UL$4 A common applications of this lemma is to instantiate the &g distance matrix. A naive algorithm which computes the distance matrix after performing the JL projection requires approximately On 2 log n) time. Surprisingly, we show that the JL lemma is not tight with respect creating an approximate & distance matrix; show that in an asymptotically better runtime.
(JI.) lemma which (roughly) states that a random
initialize the lz distance
Theorem 1.4 (Informal; See Theorem D.5
can calculate a n n matrix such that each (i. entry Bij of B satisfies (1 E) [2 2zllı I Bij I (1 + E)( - 2zllz llz in time
O 2nn lo-2 l)).)).

---

Problem
f(2,0) v)
Runtime
Prior Work
(1 +) Relative rank k low-rank approximation
ndk g//3
nkw-1 17/3
0 ndk nk 2
e,, 1
Theorem
C.4
BBC20
Additive error e|l A| rank k
ndk 21/3
1 e 13/3
Ö poly(k, 1/e))
low-rank approximation
Theorem C.6
[VWW
(1 +) Relative error rank k
Tk 21/3
12 1175
n'dk nb mb--1
Any in Table
2173
g(w-1773
low-rank approximation
Theorem C.7
[BC222]
(1 = Approximation to top singular values
+
4.a
n dd 2//2
133/2
Any in Table I
g272
2772
Theorem C.8
MMC
Multiply distance matrix with any B E R Multiply two distance
O(Tn)
Any in Table
((n))
Lemma C.9
O(n2d
O(n²)
matrices and
Lemma C.11
Table 2: Applications of our matrix- vector query results. T denotes the matrix-vector query time, given in Table w 2.37 is the matrix multiplication constant [WW1I]
Our result can be viewed the natural runtime bound which would follow if the JL lemma implied an embedding dimension bound of (ppoly(oog log n)). While this is impossible, as it would imply exponential improvement carefully reusing distance calculations via tools from metric compression [[W17]] Our results also extend to the & distance matrix; see Theorem for for details.
the JL bound which is tight [LNI7], we achieve speedup by
Notation. Our dataset will be the n points X = {=1..... Ind C Rd. For points in X, we denote 2. (i) to be the jth coordinate of point 2; for clarity. For all other vectors e. v; denotes the ith coordinate. We are interested in matrices of the form Ai, f(x, 2ÿ) for f Ik RR + which measures the similarity between any pair of points. f might not necessarily be distance function but we use the terminology "distance function" for function f as needed. w z 2.37 denotes the matrix multiplication constant, i.e., the exponent of n in the time required compute the product of two n n matrix (W2II.
of notation. We will always explicitly state the
1.2 Related Works
Matrix- Matrix-Vector Vector Products Queries. Our work can be understood as being part of a long line of classical works on the matrix free or implicit model as well as the active recent line of works on the matrix-vector query model. Many widely used linear algebraic algorithms such as the power method,
the Lanczos algorithm [an50), conjugate gradient descent [S+94), and Wiedemann's 's coordinate recurrence algorithm [We366] to name few, all fall into this paradigm. Recent works such as
[MI5 BHSW20 [CW22] have succeeded in precisely nailing down the query complexity of these classical algorithms in addition to various other algorithmic tasks such low-rank approximation BCW22] trace estimation MMMW21, and other ainear-ageebracc functions (SWYZ21b) RWZ20]
There also a rich literature query based algorithms in other contexts with the goal of minimizing the number of queries used. Examples include graph queries [Goli, distribution queries [Can20), and constraint based queries [ES20) in property testing, inner product queries in compressed sensing
2K12 and quantum queries [LSZ21
Most prior works on query based models assume black-box access to matrix-vector queries. While this is a natural model which allows for the design non-trivial algorithms and lower bounds, not always clear how such queries can be initialized. In contrast, the focus of our work is not on obtaining query complexity bounds, but rather complementing prior works by creating an efficient matrix-vector query for natural class of matrices.

---

Subquadratic Algorithms for Distance Matrices. Most work on subquadratic algorithms for distance matrices have focused on the problem of computing a low-rank approximation. [BW18 [VWW19 both obtain an additive error low-rank approximation applicable for all distance matrices. These works only assume access to the entries of the distance matrix whereas we assume we also have access to the underlying dataset. [BCW20] study the problem of computing the low-rank approximation of PSD matrices with also sample access to the entries of the matrix. Their results extend to low-rank approximation for the & and t distance matrices in addition to other more specialized metries such as spherical metrics. Table 2 lists the runtime comparisons between their results and ours.
Practically, the algorithm of [TW the easiest to implement and has outstanding empirical performance. We note that we can easily simulate their algorithm with no overall asymptotic runtime overhead using O(log n) vector queries. Indeed, their algorithm proceeds by sampling rows of the matrix according to their f value and then post-processing these rows. The sampling probabilities only need to be accurate up to a factor of two. We can acquire these sampling probabilities by performing (log n) matrix-vector queries which sketches the rows onto dimension Oloo n)) and preserves all row-norms up to a factor of two with high probability due to the Johnson-Linded Linddensinnsssssss lemma UL84. This procedure only incurs an additional runtime of (T log n) where T is the time required to perform a matrix-vector query.
The paper [LLP)4 shows that the exact TA distance matrix can be created in time ((n(w+3)22) 2.269 in the case of d = n, which is asymptotically faster than the naive bound of (n = O In contrast, we focus on creating an (entry-wise) approximate distance matrices for all values of d.
We also compare to the paper of ACSS20 In summary, their main upper bounds are approximation algorithms while mainly focus exact algorithms. Concretely, they study matrix vector products for matrices of the form Asj = f(|[=; - xy (2) for some function f :R - R. They present results on approximating the matrix vector product of A where the approximation error is additive. They also consider a wide range of f. including polynomials and other kernels, but the input to is always the f2 distance squared. In contrast, we also present exact algorithms, i.e., with no approximation errors. For example one of our main upper bounds is an exact algorithm when Ar, = ||:; xyyl (see Table 1 for the full list). Since it is possible to approximately embed the ε distance into e2. their methods could be used to derive approximate algorithms for 4, but not the exact ones. Furthermore, we also study a wide variety of other distance functions such as lo and E (and others listed in Table 1) which are not studied in Alman et al. In terms of technique, the main upper bound technique of Alman et al. is to expand f(|12; - x; 2)11) and approximate the resulting quantity via a polynomial. This is related our upper bound results for Eg for even p where also use polynomials. However, our results are exact, while theirs are approximate. Our & upper bound technique is orthogonal to the polynomial approximation techniques used in Alman et al. We also employ polynomial techniques to give upper bounds for the approximate foo distance function which is not studied in Alman et al. Lastly, Alman et al. also focus on the Laplacian matrix of the weighted graph represented by the distance matrix, such as spectral sparsification and Laplacian system solving, In contrast, we study different problems including low-rank approximations, eigenvalue estimation, and the task of initializing an approximate distance matrix. We do not consider the distance matrix as a graph or consider the associated Laplacian matrix.
It is also easy to verify the "folklore" fact that for a gram matrix AAT we can compute AAA u in time ((nd) if A E Raxd by computing ATo first and then A(AT Our upper bound for the lz function can be reduced to this folklore fact by noting that ||x- - y11 = ||= + +1yl] 2xx y). Thus the & matrix can be decomposed into two rank one components due to the terms ||0|i and |1 3 and a gram matrix due to the term (I, v). This decomposition of the E matrix is well-known (see Section 2 in (DPRV15). Hence, a matrix-vector query for the & matrix easily reduces the gram matrix case. Nevertheless, we explicitly state the & upper bound for completeness since we also consider all Eg. functions for any integer p >!
Polynomial Kernels. There have also been works on faster algorithms for approximating a kernel
matrix K defined as the n n matrix with entries K2,- = k(x,, 22) for a kernel function k. Specifically for the polynomial kernel k(x,, x = (I,, x,,) recent works such as [ANWI4] AKK + 20 WZ20 SWYZ21a have shown how to find a sketch K' of K which approximately satisfies || R
| 2||2 for all z. In contrast, we can exactly simulate the matrix-vector product Kz. Our runtime but exponential dependence on p while the
is O (nd") which has a lincar dependence
5

---

aforementioned works have at least quadratic dependence on n but polynomial dependence on p. Thus our results are mostly applicable the setting where our dataset large. i.c. n > d and is small constant. For example, p 2 is common choice in practice [CHC 101. Algorithms with polynomial dependence in d and p but quadratic dependence in n are suited for smaller datasets which have very large d and large Note that a large might arise if approximates non non-polynomial kernel using a polynomial kernel via a taylor expansion. We refer to the references within [ANW14] A WZ20, aWY222 for additional related work. There is also work on kernel density estimation (KDE) data structures which upon query y, allow for estimation of the sum Σzex k(z, y) in time sublinear in X after some preprocessing on the dataset X. For widely used kernels such as the Gaussian and Laplacian kernels, KDE data structures were used in [BIMW2I] to create matrix-vector query algorithm for kernel matrices in time subquadratic X for input vectors which
are entry wise non-negative. We refer the reader to CS17 BCIST8 SRB 19 BIWT9 CKNS20) and references within for prior works on KDE data structures.
Faster Mltrix-Vectton Product Queries for &
We derive faster matrix-vector queries for distance matrices for wide array of distance metrics. First we consider the case of the { metric such that A,, = f(z,, where f(x, y) = || - =/11 =
Σ
1 24 Vel.
Algorithm Preprocessing
Input: Dataset C Rdd
2: procedure PREPROCESSING
3: for [d] do
4: Ti f array of the ith coordinates of all æ E X.
5: end for
6: end procedure
Algorithm 2 matrix-vector Query for
Input: Dataset C Rdd
2: Output: Ay
3: procedure QUERY((Ti)iElA) 3)
4: V1,...,, 9Uh < coordinates of y.
5: Associate every x; E X with the scalar y/
6: for i E [d] do
7:
Compute two arrays B,, C as follows.
8:
B, contains the partial sums of (i) computed in the order induced by T
9:
C, contains the partial sums of y! computed the order induced by T
10:
end for
11:
2 +- 0"
12:
for
[m] do for i [d] do
13:
14:
q position of (i) in the order of T;
15:
S < B lg]
16:
S2 B [4
17:
S3 + C.[g]
S C.[m] C.lg)
19:
z(k)+ = (i) (S4 - S2) + S2 Si
end for end for
21:
end procedure
We first analyze the correctness of Algorithm 2 Theorem 2.1. Let As, ||ا, zy 1.. Algorithm computes Ay exactly.

---

Proof. Consider any coordinate &t E [nx]. We show that (Ay)x is computed exactly, We have
d
d
(Ay) Σ u5ll -xy111
Σ
-z)))
Σ
My
(f) -x)
jm1
j=l
Let x5 denote the order of [n]] induced by T;. We have
d 1
ΣΣ ==
(1)m
Σ
Σ
E
8y - 24 0,((x(()=2,(00)) xx,(0)
(
jist (
We now consider the inner sum. It rearranges to the following:
(1)(1)
Σ
V0 E
yi
E
E yイ
(K) (1)
(
(+)
(1)2+)))
(1) (Ss S1) + S2 S1.
where S2, and S4 defined in lines 15 18 of Algorithm 2 and the last equality follows from the definition of the arrays B, and C. Summing over all E [d] gives us the desired result.
The following theorem readily follows.
Theorem 2.2. Suppose we given dataset (Iı,...,Za) 2n which implicitly defines the distance matrix A.j || - 27 Given a query Rd, we can compute Ay exactly in ((nd) query time. We also require a one time O(dllgg n) preprocessing time which can be reused for all queries.
3 Lower and Upper bounds for loo
In this section give proof of Theorem Specifically, give reduction from so-called Orthogonal Vector Problem (OVP) [1105 to the problem of computing matrix-vector product Az, where Aij -1|x; =yحl for given set of points X {z1, InJ. The orthogonal vector problem is defined as follows: given two sets of vectors A = {al ..... a²) and B (b) [b',...,b"] }"}. A, B C {0, 1] A = [B| n, determine whether there exist x E A and E B such that the dot product x y = ビド= Tyリý (taken over reals) is equal to 0. is known that if OVP can be solved in strongly subquadratic time O for any constant a > and d wlog n), then SETH is false. Thus, an efficient reduction from OVP to the matrix-vector product problem yields Theorem 12
Lemma 3.1. If the metrix-vector product problem for too distance matrices induced by vectors of dimension can be solved in time T(n, d), then OVP (with the same parameters) can be solved in time ( d)).
Proof. Define two functions, f.g (0. - [0, 1]. such that f(0) 9(0) = 1/2, f(2, = 0. g(1) We extend both functions vectors by applying and coordinate wise and sets by = {f(a²), )..., f(a"))()))))))" the function is extended in the same way for B.
letting "
Observe that, for any pair of non zero vectors a, b 10, we have [lf(a) - gbb]l if and only a 0, and [[( o(b)]l oc 1/2 otherwise.
Consider two of binary vectors and B. Without loss of generality we can assume that the vectors are non-zero, since otherwise the problem is trivial. Define three distance matrices: matrix MA defined by the set f(A), matrix MB defined by the set g (B) and MAB defined by the set (B) Furthermore, let M be the disoss-dsstacee matrix, such that such that M., = [I - g(b)) lo Observe that the matrix MAB contains blocks MA and Mg on its diagonal, and blocks M and MT off-diagonal. Thus, MAR = MA appropriate dimension. Since M 1 = (MAR
Mn 2M 1, where 1 denotes an all-ones vector the MA
M 1)/2, we can calculate M 1 in time O d)). Since all entries of M are either or 1/2, we have that M n² if and only there is an entry Mi,j 1/2. However, this only occurs if a² b² = 0.

---

3.1 Approximate &oc Matrix-Verrs Vector Queries
In light of the lower bounds given above. we consider initializing approximate matrix- veecorr queries for the foo function. Note that the lower bound holds for points in {0, 1, 2,2 and thus it is natural to consider approximate upper bounds for the case of limited alphabet.
Binary Case. We first consider the case that all points x E X are from (0, We first claim the existence of polynomial T with the following properties. Indeed, the standard Chebyshev polynomials satisfy the following lemma, see e.g., see Chapter 2 in [SV+14].
Lemma 3.2. There exists a polynomial T R + IR of degree O O(Vdlog(L/e)) such that T(0) = 0 and (T)) 1| S e for all E 1].
Now note that || yاا can only take on two values, 0 1. Furthermore, || ylloo 0 if and
only if || - 2 = 0 and || yoloo = 1 if and only if || y1l3 2 1. Therefore, | yl1 = 0 if
and only if f ul = 0 and | - yl1x 1 if and only if [[ yll//d) 1 S s. Thus,
we have that
[ T[1 x 2213/d01 || - =, - T(I - x x,11B/d1 S -
is a polynomial with (((2d))) monomials in the variables zz z=1),.... x(d). Consider the matrix B satisfying B,, = - Using the same ideas as our upper bound results for f(x. y) = (z, y)", it is straightforward to calculate the matrix vector product By (see Section A.2). To summarize, for each & E [mx]. we write the kth coordinate of By as polynomial in the d coordinates of zy. This polynomial has (((2))) monomials and can be constructed in (n(2d))) time. Once constructed, we can evaluate the polynomial at $1,..., In to obtain all the coordinates of By. Each evaluation requires ((2d)) resulting in overall time bound of (n))))))
for all entries A of A. Note that -
Theorem 3.3. Let A = || - 23yloo. We can compute By in time ((((2))(log((1e) where ||A1- Bl S E.
Entries in (0..... M). We now consider the case that all points x E X are from (0...., Mj4. Our argument will be a generalization of the previous section. At a high level, our goal is to detect which of the M + possible values in {0,... .,, MM } is equal to the fo norm. To do so, we appeal to the prior section and design estimators which approximate the indicator function "||x - y ooo 2 i". By summing up these indicators, we can approximate | ylloo.
Our estimators will again be designed using the Chebyshev polynomials. To motivate them, suppose that we want to detect if || yll 30 2 or if || - y yloce < i. In the first case, some entry in - will have absolute value value at least where as in the other case, all entries of x - y will be bounded by i 1 in absolute value. Thus if we can boost this 'signal", we can apply a polynomial which performs thresholding to distinguish the two cases. This motivates considering the functions of ||x - vll for a larger power k. In particular, in the case that ||x ylloc 2 i, we have || yllk 2 g and otherwise, || - f < dik-1. By setting & log(d). the first value is much larger than the latter, which we can detect using the 'threshold' polynomials of the previous section.
We now formalize intuition. is known that appropriately scaled Chebyshev polynomials satisfy the following guarantees, see e.g., see Chapter 2 in (SV+ 14).
Lemma 3.4. There exists a polynomial T TR. - R of degree ((Vooo((/E)) such that (T(x)) S e/t for all x E [0, 1/(10)) and (T(x)) - 1| S e/t² for all x E 1].
Given F. P.y.C E Rdd our estimator will first try to detect if || - y/ 2 Let Ti be a polynomial (MM*) for & O(M log(Md)) and assuming k is even. Let T2 be polynomial from Lemma 3.4 with = O(v log(M/a) Our estimator will be
from Lemma 3.4 with t
1 Σ
(x(i) - -(())* ik M*
T/
T
j=1
If coordinate is such that [a:(j) - v(o) 2 i, then
(x())= v(
j M M
8

---

and so Ti will evaluate to a value very close to 1. Otherwise, we know that
(x(}) v())a
(i-1)e
1
(1-
8 M
M
M
M poly(M, d)
by our choice of k, which means that T1 will evaluate to value close to O. Formally,
1
Σ j=1
d
Ti
(x(s)
v(1) ik M
will at least 1/d if there is a E [d] with [x(])
u(i)l 2 and otherwise, will be at most 1/(10d).
By our choice of T2, the overall estimate output at least 1 in the first case and value at most in the second case.
The polynomial which the concatenation of T3 and Ti has O ( (T)( d
(dM))O)MV(Ho((M)) monomials, if consider the expression as polynomial in the variables =(1)..... x(d). Our final estimator will be the sum across all i 2 1. Following our upper bound techniques for matrix-vector products for polynomial, e.g. in Section A.2 and as outlined in the prior section, we get the following overall query time:
Theorem 3.5. Suppose we are given X f=1..... nnd S {O...., . M which implicitly defines the matrix A = |2, Tyyloo. For any query we can compute By in time n (dM) (olgg(M//=)) where ||A B| S.
4 Empirical Evaluation
We perform an empirical evaluation of our matrix-vector query for the & distance function. We chose to implement our & upper bound since it's a clean algorithm which possesses many of the same underlying algorithmic ideas as some of our other upper bound results. We envision that similar empirical results hold for most of our upper bounds Table Furthermore, matrix-vector queries are the dominating subroutine in many key practical linear algebra algorithms such as the power method for eigenvalue estimation iterative methods for linear regression: fast matrix- vector query runtime automatically translates to faster algorithms for downstream applications.
Dataset
(n, d)
Algo.
Preprocessing Time
Avg. Query Time
Naive
453.7
43.3
Gaussian Mixture
(5 10 50)
Ours
0.55 s
0.09 s
Naive
2672.5
38.6 s
MNIST
(5 10a, 784)
Ours
5.5
1.9
Naive
~ 2.6 days (estimated)
Glove
(1.2 10, 50)
Ours
16.8
3.4
Table 3: Dataset description and empirical results. (n, d) denotes the number of points and dimension
of the dataset, respectively. Query times are averaged over 10 trials with Gaussian vectors as queries.
Experimental Design. We chose two real and one synthetic dataset for our experiments. We have two "small" datasets and one "large" dataset. The two small datasets have 5 10 points whereas the large dataset has approximately 10th points. The first dataset is points drawn from a mixture of three spherical Gaussians in 50 The second dataset is the standard MNIST dataset [LeC98] and finally, our large dataset is Glove word embeddings
Fl in TR (PSM14).
The two small datasets are small enough that one can feasibly initialize the full in memory in reasonable time. A 5 10 x 5- 10 matrix with each entry stored using 32 bits requires 10 gigabytes of space. This is simply impossible for the Glove dataset as approximately 5.8 terabytes of space is required to initialize the distance matrix (in contrast, the dataset itself only requires < 0.3 gigabytes to store).
distance matrix
Can be accessed here: http: bttp:///itte http://gsttub.comm/rrtt http://w....o......e//eeo.eeeeee benchaarns/nnccsss/s//

---

The naive algorithm for the small datasets is the following: we initialize the full distance matrix (which will count towards preprocessing). and then we use the full distance matrix to perform matrix-vector query. Note that having the full matrix to perform matrix-vector product only helps the naive algorithm since it can now take advantage of optimized linear algebra subroutines for matrix multiplication and does not need to explicitly calculate the matrix entries. Since we cannot initialize the full distance matrix for the large dataset, the naive algorithm in this case will compute the matrix-vector product in a standalone fashion by generating the entries of the distance matrix on the fly. We compare the naive algorithm to our Algorithms | and 2
Our experiments are done in a 2021 MI Macbook Pro with 32 gigabytes of RAM. We implement all algorithms in Python 3.9 using Numpy with Numba acceleration to speed up all algorithms whenever possible.
Results. Results are shown in Table 3 We show preprocessing and query time for both the naive and our algorithm in seconds. The query time is averaged over 10 trials using Gaussian vectors as queries. For the Glove dataset, was infeasible to calculate even a single matrix-vector product, even using fast Numba accelerated code. We thus estimated the full query time by calculating the time on a subset of 10* points of the Glove dataset and extrapolating to the full dataset by multiplying the query time by (n/(5- 10²))² where is the total number of points. We see that in all cases, algorithm outperforms the naive algorithm in both preprocessing time and query time and the gains become increasingly substantial the dataset size increases, as predicted by our theoretical results.
Acknowledgements. This research was supported by the NSF TRIPODS program (award DMS- 2022448), Simons Investigator Award, MIT-IBM Watson AI Lab, GIST- MIT Research Collaboration grant, and NSF Graduate Research Fellowship under Grant No. 1745302.
References
[ACSS20] Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 541-552. IEEE, 2020.
[AGI1] Uri M Ascher and Chen Greif. A first course on numerical methods. SIAM, 2011.
[AKK 20] Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Vel- ingker, David P Woodruff, and Amir Zandich. Oblivious sketching of high-degree polynomial kernels. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 141-160. SIAM, 2020.
[ANW14] Haim Avron, Huy Nguyen, and David Woodruff. Subspace embeddings for the polynomial kernel. Advances in neural information processing systems, 27, 2014.
[AW21] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 202/ ACM-SIAM Symposium Discrete Algorithms (SODA), pages 522-539. SIAM, 2021.
[BCIS18] Arturs Backurs. Moses Charikar, Piotr Indyk, and Paris Siminelakis. Efficient density evaluation for smooth kernels. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 615 02666.6622 2018
[BCW20] Ainesh Bakshi, Nadiia Chepurko, and David P Woodruff. Robust and sample optimal algorithms for psd low rank approximation. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 506-516. IEEE, 2020.
[BCW22] Ainesh Bakshi, Kenneth L Clarkson, and David P Woodruff. Low-rank approximation with 1/33/3 matrix-vector products. arXiv preprint arXiv:2202.05 2022.
2022.
[BHSW20] Mark Braverman, Elad Hazan, Max Simehowitz, and Blake Woodworth. The gradient complexity of linear regression. In Conference on Learning Theory, pages 627-647. PMLR, 2020.
10

---

[BIWW2]] Arturs Backurs, Piotr Indyk. Cameron Musco, and Tal Wagner. Faster kernel matrix algebra via density estimation. Proceedings of the 38th International Conference Machine Learning, pages 500-510, 2021.
[BIW19] Arturs Backurs, Piotr Indyk, and Tal Wagner. Space and time efficient kernel density estimation in high dimensions. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems, NeurIPS, pages 15773-15782, 2019.
[BW18] Ainesh Bakshi and David Woodruff. Sublinear time low-rank approximation of distance matrices. Advances in Newral Information Processing Systems, 31, 2018.
[Can20] Clément L Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing, pages 1-100, 2020.
[CC08] Michael AA Cox and Trevor F Cox. Multidimensional scaling. In Handbook of data visualization, pages 315-344 347.. Springer, 2008.
[CHC* 10] Sin-Wen&ee Chang, Cho-Jui Hsieh, Kai- Wei Chang, Michael Ringgaard, and Chih-Jen Lin. Training and testing low-degree polynomial data mappings via linear svm. Journal of Machine Learning Research, 11(4), 2010.
[CHL21] Andrew M Childs, Shih-Han Hung. and Tongyang Li. Quantum query complexity with matrix-vector products. arXiv preprint arXiv:2102. 11.e..11349 1149, 2021.
[CKNS20] Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estimation through density constrained near neighbor search. 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 172-183, 2020.
[CS17] Moses Charikar and Paris Siminelakis. Hashinng-aasdd-sstimttos for kernel den- sity in high dimensions. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1032-1043, 2017.
[DPV115] Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, and Martin Vetterli. Euclidean distance matrices: essential theory, algorithms, and applications. IEEE Signal Processing Magazine, 32(6))12-30, 2015.
[EK12] Yonina C Eldar and Gitta Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012.
[ES20] Rogers Epstein and Sandeep Silwal. Property testing of Ip-type problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstubl-LeibbizzZZenee für Informatik, 2020.
[Gol17] Oded Goldreich. Introduction property testing. Cambridge University Press, 2017.
[HS93] Liisa Holm and Chris Sander. Protein structure comparison by alignment of distance matrices. Journal of molecular biology, 233(1):123-135) 1993.
[ILPP44] Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, and Ely Porat. Closest pair problems in very high dimensions. In International Colloquium on Automata, Languages, and Programming, pages 782-792. Springer, 2004.
[IPO1] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):677335, 2001.
[IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001.
[IWW77] Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Practical data-dependent metric compression with provable guarantees. Advances Neural Information Processing Systems, 30, 2017.

---

[IVWW19] Pitor Indyk. Ali Vakilian, Tal Wagner, and David P Woodruff. Sample-optimal low- rank approximation of distance matrices. In Conference on Learning Theory, pages 1723-1751. PMLR, 2019.
[JL84] W. Johnson and J. Lindenstrauss. Extensions of lipschitz maps into hilbert space. Contemporary Mathematics, 26: 189-206, 01 1984.
[Kru64] Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to nonmetric hypothesis. Psychometrika, 29(1):1-27, 1964.
[Kru78] Joseph B Kruskal. Multidimeensoonal scaling. Number 11. Sage, 1978.
[Kuc09] Marek Kuezma. An introduction to the theory of functional equations and inequalities: Cauchy's 's equation and Jensen's 's inequality. Springer Science & Business Media, 2009,
[Lan50] Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. 1950.
[LeC98] Yann LeCun. The mnist database of handwritten digits. com/exdb/mnist/, 1998.
http://yann. lecun.
[LN17] Kasper Green Larsen and Jelani Nelson. Optimality of the Haanson-lindenstrnn lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638, IEEE, 2017.
[LS7211] Troy Lee, Miklos Santha, and Shengyu Zhang. Quantum algorithms for graph problems with cut queries. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 939 -0889995.770 SIAM, 2021.
[MM15] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems, 28, 2015.
[MMMW1]] Raphael A Meyer, Cameron Musco, Christopher Musco, and David P Woodruff. Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity Algo- rithms (SOSA), pages 142-155. SIAM, 2021.
[PSM14] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532-1543, 2014.
[RWZ20] Cyrus Rashtchian, David P Woodruff, and Hanlin Zhu. Vector-matrix-ees vector queries for solving linear algebra, statistics, and graph problems. arXiv preprint arXiv:2006. 14015, 2020.
[S+94] Jonathan Richard Shewchuk et al. An introduction to the conjugate gradient method without the agonizing pain, 1994.
[SRB + 19] Paris Siminelakis, Kexin Rong. Peter Bailis, Moses Charikar, and Philip Alexander Levis. Rehashing kernel evaluation in high dimensions. In Proceedings of the 36th International Conference on Machine Learning, ICMI, pages 5789-5798, 2019.
ISV+ 14] Sushant Sachdeva, Nisheeth K Vishnoi, al. Faster algorithms via approximation theory. Foundations and Trends in Theoretical Computer Science, 922:1225-210, 2014.
[SWYZ21a] Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polyno- mial kernels of polynomial degree. In International Conference on Machine Learning, pages 9812-9823. PMLR, 2021.
[SWYZ2Ib] Xiaoming Sun, David P Woodruff, Guang Yang, and Jialin Zhang. Querying matrix through matrix-vector products. ACM Transactions on Algorithmss (TALG), 17(4):1-19, 2021.
12

---

[SY07] Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for sensor network localization. Mathematical Programming, 109(2):677-384, 2007.
[TSL00] Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric
framework for nonlinear dimensionality reduction. science, 290655000:2319-2222 2000.
[Wie86] Douglas Wiedemann. Solving sparse linear equations over finite fields. IEEE transac- tions on information theory, 32(1):54-6) 62, 1986.
[Wi105] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implica- tions. Theoretical Computer Science, 348(2-3):357-3653 2005.
[Woo14] David P Woodruff. Sketching as tool for numerical linear algebra. arXiv preprint 1414,347 2014.
[WS06] Kilian Q Weinberger and Lawrence Saul. Unsupervised learning of image manifolds by semidefinite programming. International journal of computer vision, 70(1):77-90, 2006.
[WZ20] David Woodruff and Amir Zandich. Near input sparsity time kernel embeddings via adaptive sampling. In International Conference on Machine Learning, pages 10324-10333. PMLR, 2020.
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] We include formal upper and lower bounds which natural state the applicability and limitations of our theorems.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethies review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are included in the main body or in the Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code is included in the supplementary.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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)? [Yes]
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? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "YHoMuECc83", "reviewer": "Reviewer_Ap29", "summary": "The authors propose fast algorithms for exact matrix-vector computations when the matrices are pairwise distance matrices (not strictly metrics). This leads to fast algorithms for matrix multiplication when one factor is a distance matrix.\n\nThey also give hopeless lower bounds for the $\\ell_\\infty$ distance, but fast approximate algorithms.\n\nA third contribution is relegated to the appendix.\n\nThey present a small set of experiments to showcase the practical advantages of one of their algorithms.\n", "questions": "I'm a bit surprised that no one had come up with the algorithm for $\\ell_1$ before. Could you perhaps comment on that?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written and easy to follow. All the arguments in the main body seem sound to me.\n\nOne possible objection is the substance of the algorithms for $\\ell_p$ distances, in particular $\\ell_1$, which could almost be considered low-hanging fruit. The case of $\\ell_\\infty$ is much more inspired, and the reduction of OVP, while not very difficult, is non-trivial.\n\nMinor: In the discussion of the binary case in section 3.1, t seems to come out of nowhere.\n\nSome typos I ran into:\n  - Theorem 1.1. z should be in R^n.\n  - l. 162: \"The sampling probabilities only needs\"\n  - l. 166: \"T is the time requires to perform a matrix-vector query.\"\n  - l. 271: \"This motives\"\n", "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": "Jj3ahYA3nqW", "reviewer": "Reviewer_hXqz", "summary": "This submission discusses 3 main results which the authors explicitly state on page 2 and again on pages 2 and 3.  Viz, for a distance matrix A of n points in d-dim Euclidean distance\n\no Computation of A.z in O(ndp)+ O(nd log(n)) steps for l_p norm 1<=p<inf\no Computation of A.B in O(n^2dp) steps for l_p norm 1<=p<=inf\no Computation of distance matrix A itself for n points in R^d in time O(n^2 log(n))", "questions": "\nI found Section B in the supplement to be fundamental to the rationale for writing this paper and its separation from the main text is incomprehensible except for the NeurIPS page limit, excluding supplementary material.", "limitations": "NA.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThis submission is effectively a long journal paper on numerical linear algebra divided in an ad hoc way to fit into the NeurIPS template.  The three results presented are significant and the proof methodology is intricate.  Efficacy of the results are well demonstrated by the experiments.\n\nOn the negative side, this paper has less relevance to ML and much more relevance to numerical linear algebra: its only claim for relevance to ML is that distance matrices arise in ML often as do need for the stated 3 results.  In this reviewer's opinion, this submission should be written in a linear way *not* separating material in the supplements from the main text (to meet NeurIPS page limit as in current form) thus presenting the material in a logical way in 30 or so pages and be submitted it to a numerical algebra publication (such as SIAM Journal in Numerical Algebra) where seasoned numerical analysts who only do matrix algebra will be able to provide much more valuable feedback to the authors.", "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": "7Fxcm4sAGB0", "reviewer": "Reviewer_37Ae", "summary": "The matrix-vector multiplication problem is fundamental and super important in ML applications. Faster algorithms for it are highly desirable.\n\nThis paper presents major speedups for the problem under the assumption that the matrix is not worst-case but is actually a \"distance matrix\" meaning that there is a set of n points x_1,...,x_n that implicitly define the matrix: the i,j entry is the distance between x_i and x_j.\n\nThis setting seems well-motivated and natural.\n\nThe complexity of this problem varies with the specific distance metric that is used, and with the dimension of the data-points x_1,..,x_n. \n\nFor \\ell_1 distance over d dimensional points, the paper presents and algorithm computing the matrix-vector product in O(nd) time rather than the naive O(n^2) worst case bound. Technically, this algorithm is pretty simple and is at the level of an exercise. \n\nThere are other efficient algorithms for other norms that are not presented in the body of the paper.\n\nFor \\ell_infinity over d=O(log n) dimensions, the paper shows a conditional lower bound stating that n^2 time is required, and then they present some interesting approximation algorithms. Both upper and lower bounds in this context are non-trivial but they use rather standard techniques in the context of nearest neighbor algorithms for such metrics.", "questions": "Are you aware of this paper? Isn't there some overlap in results/techniques:\n\n\"Algorithms and Hardness for Linear Algebra on Geometric Graphs\"\nJosh Alman; Timothy Chu; Aaron Schild; Zhao Song\n", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results of this paper are super important and interesting, to a point that I would be surprised if they are actually new. But since I can't point to a previous reference that proves these results, I recommend accepting the paper.\n\nThe main weakness is that the techniques are not so groundbreaking; still, they are nontrivial observations that yield great results.", "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