Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Authors: Raphael A Meyer
William Joseph Swartworth
David Woodruff
Venue: ICML 2025 poster (2025)
Keywords: Tensors
Kronecker measurements
Sketching
Matrix-Vector
Lower Bound
Query Complexity
Primary area: theory->everything_else
TL;DR: First exponential lower bounds on the number of Kronecker matrix-vector products to solve Linear Algebra Problems

Abstract: We study the computational model where we can access a matrix $\mathbf{A}$ only by computing matrix-vector products $\mathbf{A}\mathrm{x}$ for vectors of the form $\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q$.
    We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of $\mathbf{A}$.
    Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries.
    We further prove that algorithms whose queries come from a small alphabet (e.g., $\mathrm{x}_i \in \\{\pm1\\}^n$) cannot test if $\mathbf{A}$ is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1.
    In steep contrast to the non-Kronecker case, this shows that sketching $\mathbf{A}$ with different distributions of the same subguassian norm can yield exponentially different query complexities.
    Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.

Understanding the Kronecker Matrix- Vector Complexity of Linear Algebra
Raphael A. Meyer
William Swartworth David P. Woodruff
Abstract
These applications overcome the curse of dimensionality by representing underlying high dimensional linear op- erator as network of a series of low dimensional tensors. Abstractly, in these applications we are given an order 2q tensor A E [IR")&4 that represents a linear operator from (IR") 0o to (R"))9 and we often want to approximately compute some properties of this linear operator, such as its trace or spectral norm.
We study the computational model where can access matrix A only by computing matrix- vector products Ax for vectors of the form x = X1 8xy. We prove exponential lower bounds on the number of queries needed to estimate var- ious properties, including the trace and the top eigenvalue of A. Our proofs hold for all adap- tive algorithms, modulo mild conditioning as- sumption on the algorithm's 's queries. We further prove that algorithms whose queries come from a small alphabet (e.g., X; E {+1)") cannot test if A identically zero with polynomial com- plexity, despite the fact that a single query using Gaussian vectors solves the problem with proba- bility 1. In steep contrast to the non- -oo-KKrneeker case, this shows that sketching A with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that ran- dom vectors with Kronecker structure have expo- nentially smaller inner products than their non- Kronecker counterparts.
By appropriately reordering the entries of A, can explic- itly write down a matrix A E R** x that describes this linear operator. Our goal then becomes to estimate the trace, spectral sum, operator norm, or some other property of A. However, since we may not know the structure the un- derlying compact representation, we would like to estimate properties of A without explicitly forming A, as doing so would break our compact representation of A. Instead we take advantage of our compact representation to efficiently and implicitly access A through linear measurements, such as the Kronecker matrix vector product:
Definition 1. Let A E R Then Kronecker Matrix- Vector Product Oracle is an oracle that, given X1:..., Xy R", returns Ax E RRn where x = 0/11,; Here, @ de- notes the Kronecker product.
For many different compact representations of A, it is pos- sible to compute some compact representation of the Kro- necker metrix-vector product Ax efficiently (Lee & Ci- chocki, 2014; Feldman et al., 2022). This is done in many algorithms and can go by different names, such as Khatri- Rao sketching or rank-one measurements, However, these algorithms tend to make strong assumptions about the struc- ture of A in order to achieve polynomial runtime (Al Daas et al., 2023; Li et al., 2017) obtain a worst-case runtime that is exponential in q (Meyer & Avron, 2023; Avron et al., 2014; Song et al., 2019b). has been unclear whether this exponential cost is unavoidable and what structure in A leads to this expensive runtime. In this paper, we address this question by demonstrating explicit constructions of A that elicit these lower bounds.
1. Introduction
Tensors have emerged as a canonical way to represent multi- modal or very high-dimensional datasets in areas ranging from quantum information science (Biamonte, 2019) to medical imaging (Selvan & Dam, 2020; Sedighin, 2024). Such applications often result in compact representations of tensors. For instance, applications in quantum information theory use the so-called PEPS network or other compact tensor networks, while applications in partial differential equations often use tucker or tensor train decompositions.
'Computing + Mathematical Sciences Department, Cal- ifornia Institute of Technology. 'Department of Com- puter Science, Carnegie Mellon University. Correspondence to: Raphael Meyer <ram900 caltech.ed...................... William Swart- worth <wswartwo@ andrew cdu.., David Woodruff <dwoodruf@ es. cmu.
Algorithms for fast tensor computations are well studied. There is a large number of randomized algorithms that pro- vide strong approximation guarantees to a tensor and are very efficient. Although not all in the Kronecker matrix- vector model, many such applications involve making linear
Proceedings of the 4dnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
measurements with rank-one tensor, for which our tech- niques may apply. Further, there is body of work lower bounds for tensor algorithms. This work often focuses complexity classes, for instance showing that computing the spectral norm of A is NP-Hard. However, it is not clear how this relates to the number of Kronecker vatrix-vector products takes to estimate a property of A, which is the focus of our paper. Relatively little research focuses on query complexity lower bounds for tensor computations.
performance. In contrast, we demonstrate that having sub- gaussiamity does not suffice to understand the complexity of Kronecker matrix-vector algorithms. Analogously, we show that there can also be gap between using complex-valued and real-valued queries, which again does not typically mat- ter in the non-Kronecker case. As a byproduct of our analy- sis, we prove that an algorithm of (Meyer & Avron, 2023) has a near-optimal sample complexity for trace estimation.
Broadly, our analysis reveals new insights on the fundamen- tal complexity of linear algebra in the Kronecker matrix- vector model. We show that basic linear algebra tasks must incur an exponential sample complexity in the worst case. So, if we wish to have faster algorithms then we need to assume that A has some structure that avoids the worst- case structure imposed by these lower bounds. Further, we show that when designing randomized algorithms for the Kronecker matrix-vector model, it is important to examine our base random variables more closely that we may in the non- KonnKronecker case, as the choice of two similar variables like Rademachers and Gaussians may incur an additional exponential cost.
In this paper, we leverage a novel observation about the vectors in
orthogonality of random Kronecker-structune order to prove exponential lower bounds on the number of Kronecker matrix-vector products needed to approximately compute properties of A. We show that any algorithm which can estimate the trace or spectral norm of A to even low accuracy must use number of Kronecker matrix- vector products that is exponential in g. modulo mild assumption on the conditioning of the algorithm:
Theorem 2 (Informal version of Theorem 6). Any "well- conditioned" algorithm must compute t 2 Ca Kronecker matrix-vector products with A to return an estimate 2 E
(1+ (A) with probability at least 3-
The rest of the paper is structured as follows: we first dis- cuss related work. In Section 2 we introduce notation. In Section 3 we explain our theorem statements in more detail. In Section 4 we prove our lower bounds on trace estima- tion and spectral norm approximation against all Kronecker matrix-vector algorithms. In Section 5 we prove our lower bounds against small alphabet algorithms for the zero testing problem.
Theorem 3 (Informal version of Theorem 7). Any "well- conditioned" algorithm must compute t 2 C Kronecker veclor-matrix-vecte products with A to return an estimate 2 E (1 + 3) tr( with probability at least 3.
This explains why methods such as Kronecker JL. and Kro- necker Hutchinson require exponential sketching dimension as observed by several prior works (Meyer Avron, 2023; Ahle & Knudsen, 2019). Phrased another way, this analy- sis explains why the Kronecker matrix- complexity of linear algebra problems is exponentially higher than the classical (non-Kronecker) matrix- complexity.
1.1. Related Work
Tensors have long history of study in the sketching liter- ature, particularly for the problem of & norm estimation (Ahle et al., 2020; Ahle & Knudsen, 2019; Pham & Pagh, 2013). Previously (Ahle & Knudsen, 2019) observed that Kronecker-structure Eg embedding cannot work with fewer than exponential measurements in the number of modes. This is why (Ahle& & Knudsen, 2019) require a more compli- cated sketch to construct their embeddings for high-mode tensors. However it does not appear to be known whether a Kronecker-structured sketch could work for f2 estimation, using a subexponential number of measurements, if one drops the requirement that the sketch be an embedding. Our work partially resolves this by showing that any such sketch- ing matrix must be extremely poorly conditioned. There is also a large body of work on sketching Tucker, tensor train, tree networks, and general tensor networks, see, e.g., (Song et al., 2019 9a; Mahankali et al., 2024) and the references therein.
Our core orthogonality observation also implies another gap between Kronecker and non-Kronecker matrix- com- plexities. We show that for the zero testing problem, there an exponential gap between sketching with the Kronecker product of Gaussian vectors versus Rademacher vectors. It suffices to using single query with the Kronecker of Gaus- sian vectors to test if A is zero, but it takes ((29) queries with Rademacher vectors.
Theorem 4 (Special case of Theorem 18). For any Kro- necker matrix-vector algorithm whose query vectors v- = SL V; are built from the Rademacher alphabet v; E [11)", In, it is necessary and sufficient to use ((29) to test if A if O.
The difference between using "small alphabets" (e.g., Rademacher vectors) and "large alphabets" (e.g., Gaus- sian vectors) almost never asymptotically matters in the non- Kronecrek case, where we expect that all algorithms that use subgaussian variables achieve the same asymptotic
2

---

Here, Cr and Co are constants greater than which are specified in Lemma 8. Notice that the first result is against mafrix-vector methods where the second is against vector-matrix-ver compute Ax, while methods where Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
2. Preliminaries
Theorem 7. Any k-conditioeed Kronecker vector-matrix- vector algorithm that can estimate the trace of any PSD matrix A to relative error (1 = =) with probability at least 3 must use at least t = (2minn(C *Wove) matrix-vector products.
We use capital bold letters (A... to denote matrices, lowercase bold letters to denote vectors (a.b,c...., and low- ercase non-bold letters to denote scalars (a.b.c....) IR is the set of reals, C is the set of complex numbers, and N is the set of natural numbers. We will let A denote an algorithm. x denotes the transpose and x" denotes the conjugate trans- pose. We use bracket notation [a]; to denote the tth entry of a and [A]e, to denote the (i entry of A. ||all2 denotes the 1.2 norm of vector. 6 denotes the Kronecker product. (r(A) the trace of a matrix. We let [r]] [1....,n} be the set of integers from 1 to For probability distri- butions IP and Q on space (12 F), Drv (IP, Q is the total
Kronecker
we can compute x Ax. The proofs for these results both fol- low from strong orthogonality between random Kronecker structured vectors. Formally, we rely on the following ob- servation:
variation distance between PP and Q, and DKL (PI Q) is the
Kullback-Liebler divergence. We will let L C C denote an alphabet.
Lemma 8. Ler = t1 8 ....... @ ug where is uniformly random unit vector in IR.". Then, for any v = V1 S...V where each va is an arbitrary unit vector in RR, we have that
3. Technical Overview
Pr v
C S C
In this section, we state core technical results more precisely and discuss their context while delaying their proof details to later in the paper. We start with the discussion of lower bounds against not ill-conditioned algorithms for trace estimation and spectral norm computation. Then, we go into the discussion of zero testing and the insufficiency of subgaussianity to understand Kronecker matrix-vector complexity.
For some universal constants Cr, Co= > 1.
We prove Lemma 8 in Appendix A. What makes Lemma 8 unique is the rate of C, inside the probability. This is because for uniformly random unit vector a E R=" and arbitrary unit vector b E R",, we instead expect that (a. b)² z ny. So, in contrast, Lemma 8 shows an exponentially smaller inner product between random Kronecker-structuree vectors. We will momentarily explain how Lemma translates into the lower bounds of Theo- rems 6 and 7, but first we take moment to discuss the strength of the conditioning assumption.
3.1. Lower Bounds on Trace and Spectral Norm Estimation
In this section we formally state Theorem 2 and Theorem 3, our lower bounds against approximating the trace and the spectral norm of a matrix. Both lower bounds hold against algorithms that are not ill-conditioned. So, we first take a moment to formalize this conditioning:
To understand the weight of this conditioning assumption, we take a moment to examine some of the most common Kronecker matrix-vector, algorithms: Khatri-Ras Sketches. A Khatri- Rao Sketch a non-adaptive Kronecker matrix- vector product and typically takes each query vector to be the Kronecker product of q iid copies of some subgaussian vector. That is, v()) 33 v where v(() D for some isotropic distribution D. For instance, Kronecker JL and Kronecker Hutchinson use Khatri- -aatri-RaoBoa Sketching (Jin et al., 2021; Sun et al., 2021; Feldman et al., 2022; Bujanovic & Kressner, 2021; Meyer & Avron, 2023; Lam et al., 2024). In these cases, we should expect V = [y(1) ... v() to be ex- tremely well conditioned. This is because the inner products between the query vectors tensorizes as in Lemma 8:
Definition& 5. Fix matrix-vector algorithm Algo. For any input matrix A, let vi),,.., (()) be the matrix-vector queries computed by Algo, and let V == [y(1] v(0) E Ra xt be the matrix formed by concatenating these vectors. If we know that for all inputs A we have that the condi- tion number of V is at most Ki then we say that Algo is ccconditioned.
We prove lower bounds against Kronecker matrix-vector algorithms that are λ conodiiioee We will momentarily discuss how mild this conditioning assumption is. First, we state our formal results:
(v
Any c-conditioned Kronecker matrix-vector algorithm that can estimate the spectral norm of any symmetric matrix A to multiplicative less than error c2l2 with probability least must use least I. M(min (Cg/2 C2/2 --)) }) Kronecker matrix-vector products.
Theorem 6.
If the sketching vectors come from a continuous random distribution, then Lemma tells us that these vectors have exponentially small inner product. If the sketching vectors
3

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
instead come from discrete random distribution, then The- orem 18 in Section 5 shows that the inner product will be exactly zero with very high probability. Either way, the matrix V has nearly orthogonal columns with very high probability, in turn implying that the condition number of V is at most (11) with very high probability. So, any Khatri- Rao sketching method must incur the exponential lower bounds in Theorems& 6 and 7. More broadly, we are not aware of any Kronecker matrix-vecte algorithm that whose condition number is exponential in q, which is the degree of ill-conditioning required to avoid incurring the exponential lower bound.
of this results in Theorem 18 of Section 5, where we only allow the entries of vectors belong to a fixed alphabet L C RR For large enough n, we show that (1 o )) queries are necessary and sufficient solve the zero-testing problem. In other words, we must pay cost that is ex- ponential in q unless |C| = S2(g). Broadly this tell us the following:
Knowing that random vector is subgaussian does not suffice to tightly bound the query complexity of the Kronecker matrix-vector algorithm using that variable.
We also note that any algorithm that can estimate the trace of a PSD matrix to relative error (1) can be used to solve Problem 9. In particular, it is worth comparing Theorem 10 to Table 1 from (Meyer & Avron, 2023). (Meyer & Avron, 2023) show an algorithm that uses the Kronecker product of Rademacher vectors estimate the trace of PSD matrix to constant factor error using 0(29) queries when = 2. They also show that the same algorithm run with uniformly random unit vectors instead of Rademacher vectors achieves the same result in just O(155)) queries.
3.2. Zero Testing
Consider the following very simple problem:
Problem 9. Let A E Rn xn" be matrix. Using only matrox-vector products with A, decide if = 0 if + O. Be correct with probability at least 3.
When we are allowed to use classical mron-Kronecker) matrix-vector products, then we can solve Problem with a single Gaussian query with probability 1. The same holds in the Kronecker matrix-vector case: if we let g1 @ ...... @ 84 where g; (O, I) then Av + 0 with prob- ability one if A + 0. This is direct consequence of the kernel of any nonzero matrix being a set of measure zero.
We can therefore conclude from Theorem 10 that the op- timal query complexity of any algorithm that solves trace estimation while using the {+1} alphabet is therefore ((29) when = 2. Since we know that O(159)) is possible with continuous variables, we prove for the first time that the task of trace extimation cannot be solved with optimal query complexity using Rademacher vectors.
This low query complexity remains true in the classical (non- Kronecker) case if we restrict ourselves to use Rademacher vectors. More formally, if we only allow ourselves to com- pute Ax for vectors E [=1]"" then using ((1) matrix- vector products suffices to solve Problem 9. This follows from many possible results, including applying Hutchin- son's 's estimator to AT to estimate |A] Il to constant factor accuracy with (1) queries (Meyer& & Avron, 2023).
Again, this reinforces how the choice of base subgaussian distribution can exponentially change our final sample com- plexity. The core of the proofs here also rely on orthogonal- ity. We show that with overwhelming probability, random Kronecker-structue
vectors built from a small alphabet are almost surely perfectly orthogonal:
This story ubiquitous in matrix matrix-vector complexity - chang- ing the base distribution we sample with from any subgaus- sian distribution any other subgaussian distribution (e.g- from Gaussian to Rademacher) does not change this asymp- totic complexity of solving linear algebra problems (Saibaba & Mikedlar, 2025; Meyer et al., 2021).
Lemma 11. There exists a distribution over random vectors u E RT such that every fixed vector v = V X .... & Va with v, E 1=1 has (u, v) with probability at least 24
Again, we prove this result in broader generality in Section 5, with respect to an arbitrary alphabet.
We now show that this story fails to hold true in the Kro- necker matrix-vector setting:
We also take a moment to reflect further on another observa- tion from (Meyer & Avron, 2023): the complex Kronecker metrix-vector oracle is different from the real Kronecker matrix-vector oracle. That is. if we allow v = =8L_v; where V; E C", this model is more expressive than the real-valued Kronecker matrix-vector model. In particular, it takes up to 2 real-valued Kronecker matrix- vector products to simulate computing a single complex Kronecker matrix- vector product. We also analyze the complex case for the zero zero-testing problem. and show that zero testing with the { (=1, +1) alphabet requires 2211259) queries, establishing
Theorem 10. Consider any Kronecker matrix-vector algo- rithm that only computes product using query vectors of the form v1 8- & Vg where v, E {=1}". Then, this algorithm needs (299) queries to solve Problem 9.
Not only does building queries with the Kronecker product of Rademacher entries not suffice, but no algorithm that uses {+1} entries can efficiently test if a matrix is zero This steeply violates the story we would expect to hold from the classical -ronekron) case. We prove a generalization
4

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
that this is easier than the zero testing in the real {+1] alpha- bet. However, this difference in base of exponent between 24 and 1.25% may also be attributed to the difference in the size of the alphabet, and so it remains unclear how to make an apples-to-apples comparison of the real and complex models and show that the complex model is fundamentally more query efficient.
can be used to construct linear measurement algorithm. That is, suppose that some vector-matrix-vector algorithm can estimate the trace of any PSD matrix A E R xn" with probability 2 using queries. We can then fix the input matrix A = aaT, where a is the vector as in Theorem 13. Then, a vector-matrix-vector product with A is v = (v, a)², which is the square a linear measurement with a. Further, Ar) = tr(aaT) = ||all So, we must have that the number of vector-matrix -vector queries made by A cannot violate the linear measurement lower bound in Theorem 13.
3
4. Proving Theorem 6 and Theorem 7
In this section, we outline the proof techniques for Theo- rem 6 and Theorem 7. Both lower bounds rely on Lemma 8 as a starting point, as we can plant a very large random Kronecker-structuree vector on some Gaussian data. Since the inner product between our queries v E R8 and the planted vector u R= is tiny, our queries cannot reli- ably identify the planted structure u. More specifically, the noise from the Gaussian data hides the impact of the inner product between v and on our queries. In the following subsections, we formalize this idea.
So, our goal is now to prove Theorem 13. The crux of the proof is to use Lemma 8 to show that no Kronecker matrix- vector method can distinguish between linear measurements between two vectors:
Problem 14. Fix n, N and À 6VE. Letg R" be (O, I) vector, and let u = un @ ... @ ug where each E R" is distributed uniformly on the set of vectors with |u:
2 = n. Further, let
More broadly, our proofs hold against adaptive algorithms. That is, the algorithm is allowed to use previous responses from the oracle decide what query compute next. We handle adaptivity by generalizing the proof techniques in (Simchowitz et al., 2017), who propose an information- theoretic structure to lower bound the number of matrix- vector products needed to solve certain linear algebra prob- lems. In Appendix D, we generalize their techniques in order to give lower bounds against arbitrary constrained matrix-vector models. For instance, while we constrain ourselves to use Kronecker-structuredd matrix-vector prod- ucts, we could instead analyze sparse query vectors instead though this model. We leave the broader implications of this generalized lower bound as future work.
ag == and
a1 := g Au.
Suppose that nature samples i E =(0,1) uniformly at ran- dom. An algorithm then computes linear measurements with :- a; and has to guess if ag a= a..
In Appendix B we formally prove the exponential lower bound against Problem 14 as stated in Theorem 13. We do take moment to sketch the proof here though.
Consider non-adaptive Kronecker-structuree linear mea- surement algorithm for Problem 14. If a method is non- adaptive, then we can think of it as a method that picks a matrix V with Cronecker-structuree columns and computes VTa = [(v(1) .a) ... (v(t), a)). So, to prove our lower bound against non-adaptive algorithms, we need show that for all V with Kronecker struutuued columns and con- dition number at most K. it is not possible to distinguish Wg := VTay from W1 := VTa1.
4.1. Proof Sketch of Trace Estimation Lower Bound
We now outline the proof of Theorem 7. We start by invok- ing a related but different query complexity problem in a related but different computational model.
We start by examining these two distributions. Because g is Gaussian, we know that wo ~ (O, VTV). Similarly, for fixed value of u, we know that W1 ~ (VVVT VTV). These two distributions differ only in their means and share the same covariance matrix. In particular, bound the KL Divergence between wo and W for fixed value of u:
Fix a vector E R== The Kronecker- Structured Linear Measurement Oracle for is the oracle that, given any vectors Vi...., Vy E R", returns the inner product (a, X1 8 ..... S xxx ER.
Definition 12.
casily
input
output
(X
.xk)
ORACLE
(a. X1
xx2)
Theorem 13. Any c-coniitioned Strrucuurr Linear Measurement algorithm that can estimate the squared L2 norm ||al[2 relative error (1 E) with proba- bility?, 3
2² (wL(Wollw//u) = u V'V(VIV) 2
(1)
C9/2 2 must use least Mminn(C x² x=ve)) queries.
This follows from the KL divergence between M(,, Σ) and A/ Σ) being exactly 1 "u. We can then use union bound with Lemma 8 to say that ||Tuu| Σ Ein(vi (V()),)) u)2 s 1C,9 with probability least 1C
First note that Theorem 13 suffices to prove Theorem 7. This because any vector-mane matrix-vector trace estimation method
5

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
So, can bound
log(A) classical (non- Kronecker) matrix-vector products. We take D = n We abstract out their analysis in Appendix D, allowing us to pick a different distribution over unit vectors u and restrict- ing the set of matrix-vector query vectors to be Kronecker- structured. Fundamentally, by taking to instead be the Kronecker product of iid unit vectors in R", we can against take advantage of Lemma 8 much like in trace estimation lower bound of Section 4.1. Intuitively, we again have that the inner products between our query vectors and the planted random vector are exponentially small, and therefore at ev- ery time step [t] of the algorithm, it is exceedingly unlikely that the matrix-vector algorithm suddenly goes from having small inner product with to having a large inner product with u.
requires computing at least D2( logt (
X² DKL(wollwii)) = u (TV(VVV)--vV
x
- |
2 (VTVV)-lll
2
12 < 9t)
where the last line uses that we can take the columns of V to be unit vectors without loss of generality, so that
1
T max V) min (V)² S K
I( Miin (min(V) (V)²
By Pinsker's Inequality and the Neyman- Pearson Lemma (Csiszár & Körner, 2011; Neyman & Pearson, 1933), we know that wo and w, cannot be distinguished with prob- 2 so long as their KL divergence is at most O(1),
Formally, we prove the following distinguishing lower bound:
ability 3
Theorem 15. Consider the problem using Kronecker matrix vector products to test if A = Ao or A = A as shown above, where u ui & ... @ un for iid uniformly ran- dom unit vectors u, E R". Then, any x-conditioned Kronecker matrix-vector algorithm needs at least t = M(min CCg/2 })=)) queries to correctly identify A with probability 3.
which happens when f O C² x the requirement that our union bound earlier hold with high probability, also require that O(C)). This yields our overall lower bound, showing that wo and W1 cannot be distinguished when both O(C)) and 0 C7 completing the lower bound.
0
O
C2 f Mixed with
We note the above lower bound holds only against non- adaptive algorithms. In Appendix B, we adapt a proof strat- egy from (Simchowitz et al., 2017) to show that adaptiv- ity cannot help much. That proof much more involved, and the fundamental intuitions unique our method are well captured by the analysis above. In brief, the proof against adaptive methods shows that at every point of time i E (4), the algorithm does not suddenly learn new informa- tion about the direction of u, owing to Lemma 8. This anal- ysis gives us the benefit of proving a lower bound against adaptive methods, but comes with the downside of having
We prove Theorem 15 in Appendix C. The key payoff from this testing lower bound comes from comparing the spectral norms of Ao and A1. The spectral norm of Ao is at most O(1) while the spectral norm of A is 2(A) for large X. In particular, if we take X C²/² then we get the following lower bound:
Corollary 16. There exists a number C >> 1 such that any k-conditioned Kronecker matrix-vector algorithu that can determine if || S 3 or || 2 C with probability at least 2/2 must use at least M(Cg 2 - queries.
C2/2 slightly worse rates, giving = [m "E in the adaptive case as opposed to L = 2min (CB xeee in the non-adaptive one.
This means that even computing an overwhelmingly coarse approximation to the spectral norm of a matrix must incur an exponential query complexity. This corollary directly implies Theorem 6.
4.2. Proof Sketch of Spectral Norm Estimation Lower Bound
5. Zero Testing
In this section, we outline the proof of Theorem 6. We follow the proof strategy in (Simchowitz et al., 2017) again here. In (Simchowitz et al., 2017), the authors show lower bounds against distinguishing between two matrices from matrix-vector products. Specifically,, they let G E D be matrix with iid (0 1) entries and let E R be a random unit vector in DRP. They show that distinguishing between
In this section, we consider the zero-testing problem with Kronecker measurements. That is, we suppose that we have a nonzero tensor A E (RR))8, How many Kronecker structured measurements of the form vi @ .... @ Ug do we need to show that A is nonzero?
As it turns out, the most difficult case for zero-testing is when A itself has Kronecker structure. When we can write A = aj @ .... @ a,. then each measurement of A gives a result of the form (v.(vaa,) which is 0 as long as at least one of the terms in the product 0. This suggests
G G+C GT
G + GT
Ao
and
A
+
Auu
V2D
22D
6

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
that we should first study the zero-testing problem in the non-Kronecker setting.
2. For an arbitrary finite alphabet C. P(C,n) S a-1c)
[2] n-1
Here, we make the additional assumption that the entries of each a, come from a fixed "alphabet" that we call L C C. This assumption may seem strange at first, but one motiva- tion is that in the non- Kronecceek setting, trace estimators such as Hutchinson typically only require that one sketch using Rademacher random vectors. If one attempts use Kronecker product of Rademacher vectors, then trace esti- mation turns out to require number of measurements that is exponential in q. The zero-testing problem gives a sim- pler setting in which to observe this exponential dependence. Indeed the reason is quite similar to our norm- norm-estimation results- Kronecker products of Rademacher can be orthog- onal a fixed tensor with high probability, just as how Kronecker products of Gaussians typically very nearly orthogonal to one another.
3. For an arbitrary finite alphabet L. Q((,,)) n) 2 [2]
4.
- 1),2) -c
Qc(1-1,,,,
3/4
Proof.
1. Choose 'D to be uniform over ((1, 1). (1))
Then any vector u in {-1,1}² has dot product 0 with one element of (1,,),, (1, (1,- So if v is uni- form from {(1, (1, (1)), then with probability 1/2, vuu= 0.
Choose D to be the uniform distribution over vectors of support size 2 whose first nonzero value is 1 and whose second nonzero value is -1. Let be drawn from 'D and let i, be the coordinates of its support. Now suppose that u has entries in L. Then v = 0 precisely when [u]: = [u]j.
To set up some notation, suppose we have a tensor A E (R")09, For v E R" say that the measurement of A along mode i by v is the tensor in (I")8q-1 that results from taking the inner product of against each of the mode fibers. We use the notation A X, v. This is the Modal Product as defined in (Golub & Van Loan, 2013).
For each k E L. let nıg denote the number of entries of u that take value k. The probability that [u]: = [uly is then
+ n1... ))
11 2
112
+
+
2
2
The following definitions will be useful for writing our upper and lower bounds with respect to given alphabets.
We can bound this sum as
Definition 17. For a given alphabet L. and field F, either R or C, let
[4|
T1
(m
ni)
2
2
P=(C,n) min max Pr [v + 0),
i=1
WEE" V-D
121
2 1 2
where DD ranges over all probability distributions on the nonzero vectors in F", When is not specified, we assume that IF = TR.
n)
2
[
n).
In the last line we used the bound M n3 2
Similarly, we define
[2] [II n, 2
which is a special case of Cauchy- Schwarz. It follows that
Qr(E,n)= = max min Pr [vTu + 0], De vEE" u>De
n [C| n 1
where Dr ranges over distributions on L
Pr[ju]: = (ul,) N
C
Intuitively, P captures highest success probability that we can achieve for zero-testing on the hardest input distribution. So upper-bounding P can be used to give a zero-testing lower bound.
Choose Dr to to have i.i.d. entries over and let u be drawn from Dr Let i be the first nonzero coordinate of Conditioned on all coordinates of u except i, the value of T is uniform over a set of size C]. Therfore V is 0 with probability at most 1 [2]-
Similarly a lower bound on Q shows that there is distribu- tion over measurements that has good success probability of giving nonzero measurement on all inputs. So lower bound on Q can be used to give an upper bound for the zero-testing problem.
4. To bound Pc, choose the distribution D to be uniform Now observe that any two-dimensional vector with entries in 1+1, + is orthogonal to one of these four vectors. So Pe < -
over {(1, (1, -1) (1, [i)).
Theorem 18. We have the following.
Similarly, for Qe we choose our measure- ment distribution Dr to be uniform over
1. P((-1,1),2)
7

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
(1,,)) (1,-)) (1, These vectors are pairwise linearly independent, so any fixed u is orthogonal to at most one of them. Thus Qc 2 3/4.
Proef. Let X1.....; the definition of Pr(C, n). Set x1 .... Xg- Take matrix A to be xxT.
Xy.....x be drawn from the distribution D in
Suppose that we make t measurements of the form Av where v(() for i E [t] has Kronecker structure and uses the alphabet C. The result the measurement is nonzero precisely when xTv(1) * The probability that this is nonzero is exactly (P),,, By union bound, the probability that at least one of the matrix-vector products is nonzero is at most ((P+(C, n))9. On the other hand, constant factor trace estimator must distinguish A from the 0 matrix with probability 2 so we need E (C, m)) 2 3" from which the claim follows.
The following gives a general lower bound for the zero- testing problem via Kronecker measurements. The idea effectively to boost the analogous lower bound for non- Kronecker-structue structurdd measurements. We also give corre- sponding upper bound that works by reducing to the analo- gous upper bound for non- -truutur- measure- ments inductively along each mode.
3.
Theorem 19. (i) Zero-testing of an arbitrary vector v E (R=))0 with 352 success probability, using Kronecker structured measurements in (Cm)09 requires at least ())(P((C,n)-9)) measurements.
Combining the previous results give the following bounds for zero-testing.
Corollary 21. Zero testing for a tensor in (R")00 with success probability zh
(ii) Suppose that & S F. There is zero-tester using Sronecker-structuree measurements over the alpha- bet Σ, that succeeds with probability and uses (Q)(L.n) measurements..
1. requires at least (2(29) measurements over the alpha- bet {-1,1} when n = 2.
Proof. For the lower bound, let D be the distribution that achieves the minimum in the definition of p(C, n). Let
2. Requires at least 12((1 - 1 ) an arbitrary alphabet C.
[2] n-
Vi,..., Vy be drawn independently from D. Let X1, X be arbitrary fixed vectors in L". Then we have
For zero testing for a tensor in (C")04, is necessary and sufficient to use ((443)9) measurements for the alphabet (,1,1,,, when
(x1 6 ... & x,)T(v C ... s vg) (xIvi).... (...(xxxxx (xTy))-
Note that x! v; # 0 with probability at most p(C,n) Each of the terms x] v. independent, and so the probability that the product is nonzero is at most n)),
Proof. Combine Theorem 18 with Theorem 19.
Suppose that an algorithm makes m <ronecker-structuree measurements. Then by union bound, the probability that at least one of the measurements is nonzero is at most mp(C,n)) The claim follows.
We obtain a similar corollary for trace estimation.
Corollary 22. Constant- trace estimation of real PSD matrix requires (2(24) measurements when n = and when using Rademacher Kronecker-strucee vector queries, i.e. with vectors in ({-1,1)3)84,
matrix-
For the upper bound, choose our measurement vectors to be of the form u @ ... u, where the u,'s 's are i.i.d. from the distribution Dz. Then for a nonzero tensor A have
Constant-factor trace estimation of a complex PSD matrix requires (((4/3)9) measurements when 2 and when using complex Rademacher Kronecker-structured matrix- vector queries, i.e. with vectors in ({-1, 1, - -
(A, uj ② & u,,) A X in X2 u2... Xg ug.
Since Air is nonzero, A has some nonzero fiber along mode 1. and therefore A u1 is nonzero with probability least Q7 n.. Continuing inductively, the measurement above is nonzero with probability at least Qr(Cnn) Given m measurements of this form, the probability that all them are 0 is at most
Proof. Combine Corollary 21 with Lemma 20.
6. Conclusion
We addressed several fundamental linear algebraic problems in the Kronecker matrix- vector query model. A number of interesting questions remain. Some of Our lower bounds have a dependence on the condition number of the mea- surement matrix. Is this dependence necessary? This is open even in the case of non-adaptive measurements. Rigor- ously, we know that proving the following corollary would
(1 - (1)) S cxp(-mQe(C.n))))
which is at most 1/4 for m > 2Qr(f.n)-9.
Lemma 20. An algorithm that performs constant-factor trace estimation requires at least 2 n) Kronecker- structured vector-matrix-vecte queries.
8

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
suffice remove the conditioning assumption in both the non-adaptive and adaptive cases:
Al Daas, H., Ballard, G., Cazeaux, P., Hallman, E., Mikedlar, A., Pasha, M., Reid, T. W., and Saibaba, A. K. Random- ized algorithms for rounding in the tensor-train format. SIAM Journal on Scientific Computing, 45(1):A74-A95, 2023.
Conjecture 23. Let u = in @ @ Ug where each u; is a uniformly random unit vector in IR.. Let [v(1). v(*] where each vi) is an arbitrary Kronecker- structured vector. Let P be the orthogonal pro- jection onto the range V.... Then, so long as S poly (n. q),
random))
Avron, H., Nguyen, H., and Woodruff, D. Subspace em- beddings for the polynomial kernel. Advances in neural information processing systems, 27, 2014.
we have that
9
Pull
with probability at least C2
n2
Biamonte, J. Lectures on quantum tensor networks. arXiv preprint arXiv: 10049, 2019.
for some C1, C2 > 1.
The above conjecture a direct generalization of Lemma To this, note that taking = 1 in Conjecture 23 exactly recovers Lemma 8.
Bujanovic, Z. and Kressner, D. Norm and trace estimation with random rank-one vectors, SIAM Journal on Matrix Analysis and Applications, 42((1)200-22) 223, 2021.
In the case that Conjecture 23 does not hold, this suggests that a ill-conditioned might be efficient in the Kronecker matrix-vector model. Namely, does there exist Khatri-Ro sketching matrix that allows for &g norm estimation (and is extremely poorly conditioned)? would also be interesting to obtain tight bounds for trace estimation in the Kronecker matrix-vector model. Lower bounds for Hutchinson-style estimators are known, but could there be better estimators, perhaps analogous to the Hutch++ (Meyer et al., 2021) al- gorithm?
Csiszár, I. and Körner, J. Information theory: coding theo- rems for discrete memoryless systems. Cambridge Uni- versity Press, 2011.
Feldman, N., Kshetrimayum, A., Eisert, J., and Goldstein, M. Entanglement estimation in tensor network states via sampling. PRX Quantum, 3(3)003031,, 2022.
Golub, G. H. and Van Loan, C. F. Malrix computations. JHU press, 2013.
Acknowledgments
Jin, R., Kolda, T. G., and Ward, R. Faster johnson- lindenstrauss transforms via kronecker products. Infor- mation and Inference: A Journal of the IMA, 10(4):1533- 1562, 2021.
Raphael Meyer was partially supported by Caltech Cen- ter for Sensing to Intelligence grant to Joel A. Tropp and ONR Award N-00014-24-1-2221 to Joel A. Tropp. William Swartworth and David Woodruff received support from a Simons Investigator Award and Office of Naval Research award number N0001421 12647. We thank Ethan Epperly for detailed comments improving the presentation of the paper.
Lam, H. Y., Ceruti, G., and Kressner, D. Random- ized low-rank runge-kutta methods. arXiv preprint arX0v:2409.06384, 2024.
Lee, N. and Cichocki, A. Fundamental tensor operations for large-scale data analysis in tensor train formats, arXiv preprint arXiv: 1005.7786 2014.
Impact Statement
Li, X., Haupt, J., and Woodruff, D. Near optimal sketch- ing of low-rank tensor regression. Advances in Neural Information Processing Systems, 30, 2017.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Mahankali, A. V., Woodruff, D. P., and Zhang, Z. Near- linear time and fixed- parameeer tractable algorithms for tensor decompositions. In Guruswami, V. (ed.), 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA. USA, volume 287 of LIPlcs, pp. 79:1-79:23. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2024.
References
Ahle, T. D. and Knudsen, J. B. Almost optimal tensor sketch. arXiv preprint arXiv: 1900:01811, 2019.
Ahle, T. D., Kapralov, M., Knudsen, J. B., Pagh, R., Vel- ingker, A., Woodruff, D. P., and Zandich, A. Oblivious sketching of dighee polynomial kernels. In Proceed- ings of the Fourteenth Anmual ACM-SIAM Symposium on Discrete Algorithms, pp. 141-161 SIAM, 2020.
Meyer, R. A. and Avron, H. Hutchinson's estimator is bad at kromecker-tracee trace--titatttiiiioon arXiv preprint Ntt::3309004552. 2023.

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Meyer, R. A., Musco, C., Musco, C., and Woodruff, D. P. Hutch++: Optimal stochastic trace estimation. In Sympo- sium Simplicity in Algorithms (SOSA), pp. 142-155. SIAM, 2021.
Zhang, H. and Chen, S. X. Concentration inequalities for statistical inference. arXiv preprint (tt:::2/11.0225555 2020.
Neyman, and Pearson, E. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophi- cal Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Char- 1933.
acter, 231 (694-706))
Pham, N. and Pagh, Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 239-247, 2013.
Saibaba, A. K. and Mikedlar, A. Randomized low-rank approximations beyond gaussian random matrices. SIAM Journal on Mathematics of Data Science, 7(1):336-162
2025.
Sedighin, Tensor methods biomedical image analysis. Journal of Medical Signals Sensors, 14(6):16, 2024.
Selvan, R. and Dam, E. B. Tensor networks for medical im- age classification. In Medical imaging with deep learning, pp. 721-732. PMLR, 2020.
Simchowitz, M., Alaoui, A. E., and Recht, B. On the gap between strict-saddles and true convexity: An omega (log d) lower bound for eigenvector approximation. arXiv preprint arXiv:1704.0453 2017.
Simchowitz, M., El Alaoui, A., and Recht, B. Tight query complexity lower bounds for pea via finite sample de- formed wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1249-1259, 2018.
Song. Z., Woodruff, D. P., and Zhong, P. Relative error tensor low rank approximation. Chan, T. M. (cd.), Pro- ceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego. Cali- fornia, USA, January 6-9, 2019, pp- 2772-2789. SIAM, 2019a.
Song. Z., Woodruff, D. P., and Zhong, Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Al- gorithmss, pp. 2772-2789 SIAM, 2019b.
Sun, Y., Guo, Y., Tropp. A., and Udell, M. Tensor random projection for low memory dimension reduction. arXiv preprint arXiv:2105.00100 2021.
Vershynin, R. High-dimenssonal probability: An introduc- tion with applications in data science, volume 47, Cam- bridge university press, 2018.
10

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
A. Near-Total Orthogonality with Real Vectors
In this section, we prove Lemma and related concentrations and lemmas that characterize the near-total orthogonality of the Kronecker product of random unit vectors with respect to otehr Kronecker-strucce struuuurrd vectors. We conclude with short lemma showing how conditioning relates projections of sronecker-structuree vectors.
Lemma 24, Let X be disitributed as the first entry of a uniformly random vector in /nS". Let log Then Y subexponential with subexponential norm || S 0().
Proof. Recall that the B() m=1) distribution has pdf given by
[(n/2) ((1/2)[((m - 1)/2)
1/2 x) 21mm-3)/2 = f(x)
on the interval [0, 1), and that |X| is distributed as the square root of a B(1/2, = random variable.
By the change of variables formula, the pdf vn
L [ is given by
T(n/2) f(x²) x=== = r(1/2)(((n - 1)/2)
(1 (n)nx)))1)))
dx
which is is uniformly bounded by Cvn on [0, 1/2] for an absolute constant C. We then have that for 2 log that,
2
Pr(Y S -) Pr([X Se Pr(
X
<
)) S Vn
sup fx(x) S 2Ce =E(u,1/2]
Vn
Also X is subgaussian with constant subgaussian norm indedendent of n (see for example Theorem 3.4.6 (Vershynin, 2018).) Thus X also subexponential with constant subexponential norm. So for positive t, X satisfies a right tail bound of the form
Pr(X X 1) exp(-cl)-
Since Y X, we obtain the same right tail bound for Y, and our claim follows.
Lemma 8 Restated. Let u Un @ & ug where u, is a uniformly random unit vector in R... Then, for any kronecker-
strucutred wnit vector v V ② Vi we have that S C.9 has
S(7) = Pr (u, v)2
v)2
S SC
72
for some universal constants C,2 Cp
Proof. We start by letting X == v X, == (u, v, and Y; == In(X,), so that Y = In(X) = E Y, a sum of iid terms. We will argue the concentration of via the concentration of Y. By Lemma 24, we know that log / has sub-exponential norm K, where Z the first entry of random on the unit sphere of radius vn. Since the mean log Z most 1.32 + 1 S 1.4 for n 2 13, we know that log |Z| lLlog [2]] has sub-exponential norm at most K 1.4. Then, by Bernstein's 's Inequality (as written in Proposition 4.2 of (Zhang & Chen, 2020)).
log 7 2 y Eloo [Z|] + 2/ < min 5T xxxra
Pr
Since Y; 2og |2,| log(n), we can equivalently take μ = E[Y;) and write
Pr Y, Z qu + +| =/ Se - min! o5 ाKं④)

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Recalling that X = =e and that μ S O,
Pr X 2 cl-91e|] c
min bq(K+1 2[
22
Next we need compute μ = E| Ellog X;). Letting &b denote the digamma function, we can write ([log(X;))
(ba) (a 3) ()))) (b ) and therefore that
2 1.27 + In(n) S |M| & 1.271 + (m(n)
Then, know that X 2 et-olee glpl implies that X 2 et (--((.127++mm)))
96 1e2-1.2771
So, have
e d-11271g
mint sg(K+1.0)2 22
Pr
X
<
719
Taking = 16(K + 1.4)
1+
1,271
1)q then gives us
8.K+14y2
oq
Pr
X
Se 69
719
where a = 1.271 - 16(K + 1.4)²
(
1+
2721
1) E (0,0000).. From Lemma 24, we know that K = O(1), which
8(K +1.4
completes the proof.
We will also need the following result the MGF of the inner product of Kronecker-structure vectors. Lemma 25. Let
Uj 2 u, where u, a uniformly random unit vector in IR". Then, for any kronecker-strucuured unit vector Vi Vi and 7 E (0, 1),
Ele (u.01)
s1+ [
2n n2
S e
2m
Proof. We approach this bound via linearization. Since <u, 0)1 S 1) < 1, we know that en < 27/ 0)1 So, bound
Eied (u.0))
S 1 2ny El| i,, 0) + 2n (u, 11)
Since (un, 01) is a distributed as a Beta(
n-1 2
random variable, and since (u1 01) 2 0, we know that [u[ 00)1] =
27
KK 01)] 1. So, n
(l. <1+
nd 27 < 2m
where the last inequality uses that + x S e for x < 1.
Lastly, we show the following lemma that relates conditioning to the constants Co and C₁ from Lemma 8.
Lemma 26. Let (1) (+) E 18= be unit vectors. Suppose that = [v v(0] E IR has condition number
less than K. Let = (x(1) ... x(1] E gnnxt be an orthogonal matrix that spans V. Then, for any unit vector u, we have
((x(0 ( u2 < x² |
Proof. There exists some invertible map R such that V XR (for instance, if we built X as the Q factor of the QR of V).
Letting V = UUZT be the SVD of V, notice that
R X = -X-U)EZ
12

---

Understanding the Kronecker Matrix- Vector Complexity of Linear Algebra
is also an SVD and therefore that R has the same singular values as V. Since x(0) standard basis vector, bound
Xe; VR ee where e; is the ith
(u x = (u.VR- e,)
| R- 1 11e:112 (amin (V))
VT
where that R and V share singular values in the last equality. Next, since V has unit vector columns, we know that mmax V) 2 1. So, [Fmin
[ (V)) x2 Therefore, we have
[Fmin (V))²
(u, x0x 1
completing the lemma.
B. L2 Estimation via Linear Measurements
Problem 27. Fix a vector a E R² Then, the Kronecker-structured linear measurement oracle for a is the oracle that, when given any Kronecker structured vector v E R=n,, returns (a, v). the L.2 Estimation via Kronecker Measurements problem, we have to use a few oracle queries as possible to return a number 2 E such that (1 - =) ||a|| S S (1 + e) ||al| with probability 3.
using k cocodiiionee Theorem 28. Any (possibly adaptive) algorithm A that solves Problem 27 with probability z/e (Ca/2 ( queries.
Kronecker-structuree queries must use at least ( = (
Our proof methodology mirrors that of Section in (Simchowitz et al., 2017), but applied to this linear measurements framework instead of the matrix-vector framework studied in their paper (and partially explained in Appendix D). The
crux of this section is to show that Lemma 8 implies the lower bound in Theorem 28. We prove this lower bound by appealing to the following testing problem:
Problem 29. Fix n, 9 E N and X 1. Let E Rn be a (N I) vector, and let u Ug My where each u, R"
vector uniformly distributed on the set of vectors with |u;ll 2 = n. Further, let
ag =
and
a1 = -++ Au.
Suppose that nature samples E {0, 1} a == a; and then guesses ifi = uniformly at random. Then, an algorithm A computes t linear measurements with
The result Theorem 28 follows from combining two results: showing that any L2 estimating algorithm can distinguish ag from a1, and that distinguishing a from a requires exponential query complexity. We start with the former result.
Lemma 30. Let A be any linear measurement algorithm that can solve Problem 27 with probability 3h2 for some s E (0, 0.25).
Then A can solve Problem 29 when X = -6ve and n = ( ) with probubility least 3
Proof. Throughout this proof, we let C > 0 be large enough constant that both the concentrations required simulta- neously hold with probability TO We will concretely assume that
40 8C }. Note that li is chi-squared C )n² C (1 + A )n². We also know that ||b|| = n
we/2 I min
1
X A
random variable with parameter n². So, ||aم|| = ||gl|2 E (1 no/7
exactly. Further, since g is Gaussian, we know that (g. h) (O, |b| [ NO0 v). and therefore that (g h) Cn.//2 This lets expand
(g. h) |a 1/ || 2 x2 |||| -
2 (1 )) 2
2AC n
n472
2 (1 & )n + x2 2²,1
(1 1 )
So, we have that
|a 1 S (1
X )n
and
|a ||113 2 (1+ + }²) )n
13

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
In particular, since À G,E, have that
(1 + =) a 12 s (1+ 36E n' < =) + 362 n S [1 -E)
E) ||a112
holds for all & E (0, 0.25). In particular, this means that any algorithm A that can estimate (1+ss) ||a||2 from / measurements can distinguish ag from a with high probability, completing the proof
Next, we show the crux of the lower bound - that Problem 29 has exponential sample complexity lower bound. We show this by applying Imported Lemma 43 to our setting. In order to instantiate this theorem though, we have to introduce some further notation.
Setting 31. Fix an algorithm A that solves Problem 29. Let Setv(",,... ,..., vlt) be the (possibly adaptive) query vectors computed by A. Let wi,-.., We be the responses from the oracle. That is, wi (v(*), a). Let 2, (v(1), wa,.... v(9,, ws) be the transcript of all information sent between A and the oracle in the first i queries. By Yao minimax principle, assume without loss of generality that A is deterministic. Therefore, v80 is deterministic function of Z;-1.
We let Q denote the distribution of Z, when a= ag- We let Iu, denote the distribution of Z, when a = a conditioned on specific value of u. We let denote the marginal distribution of Pu over all u, or equivalently that the distribution of Z, when a Lastly, we A be the event that {Vj [1], (v) u)² S Tr} for some numbers S T S... S Tr. that will be clear from context.
Following this notation, to show that no algorithm can distinguish a from a1, it suffices to show that there is low total variation between P and Q. We will do this by applying Imported Lemma 43. In particular, specialized to our context, the lemma says the following:
Corollary 32. Consider Setting 31, Fix any numbers 0 S TI S ... S Tb. we are given that
Pr[i e [t] : (v(), u)² Tal Sz
(2)
and that
27
EuldP in (Z, Adull
51+z
(3)
2
dl2 (2x)
then the total variation distance between IP and Q is at most /32. In particular, if we take 27 then A canmot distinguish between an and a with probability at least J.
This corollary follows directly from plugging in Setting 31 into Imported Lemma 43. order prove Theorem 28, we just need prove that both Equations (2) and (3) hold with 27 This will be the focus of the rest of the subsection.
First, we will need the following claim about divergences:
Lemma 33. Let P. denote the distribution (a, E), Fs the distribution ((b, E), and Q the distribution (o, E). Then,
(z.(z) 27
E
aaaaaaa
2~Q
(2)
and
dP (2)dP))P (z))
2>Q
Proof. We prove only the second claim as the first claim follows from taking = a. We directly expand the expectation using the corresponding PDFs, nothing that the terms outside the expectation all exactly cancel since our distributions all
14

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
share the same covariance matrix.
dPP (z)
E
e (2-a)) (2- a (2-a)- (x-
(x-b)+=²
z~
(d)(
E
2n
H(a
c -
z
e -1(a a
(a+b)) (x+)))))))
(Gaussian MGF)
= e -t
a a b (a+b)
-- "abb 2 aabbT 'btza" lb)
aa'
We will also need the following information-theorrtie claim from (Simchowitz al., 2017):
Imported Theorem 34 (Proposition 5.1 (Simchowitz al., 2017)). Let prior distribution over parameters 0 E O. Let (Poteee be a family of distributions on space (X, parameterized by 0. Let {Ao)oge be a set of events defined on F. Let be an action space (i.e. an arbitrary set). Let C x θ + {0, 3 be binary loss function. Let A denote determinstic algorithm that observes data and picks action; that is A is any map from X to V. Let Vo be the probability an algorithm can achieve loss O without observing data:
Vo sup Pr [C(, 0) 0],
NEVOuP
and let Vy be the probability that A achieves loss after observing a sample from Py while event Ag happens:
VV E Pr [C(A(x), 0) = 0, Aa]. o-Paol
Then, for any probability distribution Q also on (X
V. S Vo+ + Vo(1 Vo) E E
[PPalai
[Aao]
anp and
This result will suffice to bound Equation (2): Lemma 35. Consider Setting 31, where
= C. Then, we have that
Pr E [t] (v(0, u) 2 2 m s 2
C3/2 T
so long as f. = (min(((m'))))
Proof. We start by expanding the target probability into a probabilistic claim for each query made by the algorithm:
Pr e [t] (v) u)2 2 nd S
(r 1 u)2 2 W (vC), u)2 S Ty]
Now, we bound each summand on the right by using Imported Theorem 34. We take 0 := u, so that P is the distribution of u. Then, Io becomes Fu from Setting 31, and Q is exactly Q as in Setting 31. We take the truncation event Ag = A
The set of actions V is conditioned on the prior query vectors yl)) ......... ((-1)) v(-,))()1)) already made by the algorithm:
3d == (v()) ( x0 )))
|
1, cond([ v10) s x}
15

---

Understanding the Kronecker Matrix-Vectoor Complexity of Linear Algebra
Lastly, we take [(v(0), u) [[v()) ug Therefore, Imported Theorem 34 takes
Vo- = sup Pr((v, u/2 2 7 S %
where the last inequality uses Lemma 8, recalling that Ti C. So, Imported Theorem 34 tells us that
V. = E Pr [<(A()), 0) = 0, Ao] u 2
Pr((v(() u)² 2 Ti
Vj E li - 1](v() u/² S Ti)
S C 9
C C E u
1 [45-11
So, next we bound this expectation. First, we take moment to examine this ratio of probabilities. We would like to apply Lemma 33 to bound the inner-most expectation. However, the indicator variable inside the expectation prevents us from doing so. Instead, we apply Lemma 49 to this situation (taking P. = Ps = P. This lemma tells us that
( (1p((2] 2; 2/-1) dQ(2, 2z-1) 1
E
(P.l2..) [Q(2,)
1 LAu '1
S Z. (v(),
sup
II E ==1
2
Now, we analyze this conditional expectation on the right. First, recall that we assumed without loss of generality that A is determinstic algorithm. Therefore, the jth query vector vO) is deterministic in 2j-1. So, the random variable 2; Zj-1 is equivalent to just looking at Wj = (v(), a). Formally using the Data Processing Incquality (Lemma E.1 from (Simchowitz et al., 1)), this means that suffices to bound
2
dP we 23-1) dQ wy 2j-1)
|
Next, we take a moment to analyze the impact of conditioning here. Unfortunately, it is annoying to analyze the expression above due to the way that wy (v(5), a) may depend on the previous observations in 2,-1. Instead, we appeal to the Data Processing Inequality again orthonormalize. In particular, for the set of queries V, V == [v(1) vo)] in 2,, let
X, (x()) x(i) be the result of running Gram-Schmidt Vj- That is, X, is orthogonal matrix that spans V-- We can write our new adjusted transcript as
ž, = (x(1), (xx1), a..... x(0, (x()) a))
Since this process is invertible, it does not change the statistical distance, and therefore it suffices to bound
(
(dF(((x0), a) - (Q((x))) a) 1) |
E
Next, we observe that the set of all observations under the adjusted transcript w = [(x()) a) ... (x(1), a)] = XJa is
distributed as multivariate Gaussian. Under Q, w NO,, xJX,) WO, I). Similarly, under P,,, NN(XX uu, I).
Notice that under both distributions, we have that all entries of w are independent. Therefore, we know that (x(), a) is independent of all other (x(1m), a) given X,. So, we can use Lemma 33 to say that
dPPn((x0) dQ (x(i), a) 2
2
|
e (x0)))
E
We want to upper bound this expectation in terms of original transcript 2, though. Here, our conditioning assumption. By Lemma 26, we know that (x()), u)2 2 < x² [IV]ull This means bound
dIP ((x() , a) 2
E
$ Se
dQ (x(i) a) 12
16

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Further, using our conditioning assumption, know that Backing up, we then need to bound
2/-1) 2
2
dP (2)
E 2,-
[Aa 1
2
sup 2, : (v (O JEA
II
dQ(2)
3)-1)
12
j=1
E5
Vj-1lVVjul?
sup
2, : (v()), (v)))
V7uul
sup
2: (vl))... (.))AA-
I e A
A322
Then, we can complete our overall lemma by taking
Pr e [8] (v u)² Ril
Pr((v() uu)² 24 Vj j - 11 (v6) u)² u Tyl
(
( 2 |ل|2:|
C + Cp E E'
4 "1
u E,~
0/5h + Co 9/2 0/ 22322800113)
20 x 222707911
s 21 9/2 x 12
1
s 27
where we take = (minn(C ca/2 x
C2/2 O
}) on the last line.
x (e)e
Lemma 36. Consider Setting 31, where T1 = ... = C- Then, we have that
27
EuldPul uit 1onnnA A1A) dQ((,)
E
< 1+
ze0
so long as t = Ommin Cgl2 ea/2
NeVE }).
Proof. Equation (6.31) of (Simchowitz et al., 2017) shows that we can rewrite
En Eu[dd [dd (Z. dQQ(2,)
dP n. A ddPP (Ze n A
=
E
E Z
(dQ(2,))2
where u' is an iid copy of u. Then, by Lemma 49 we know that
dP (Z, n (dl)) (Z, 0 (())
dP u (Z, Z dd
(Z, (Z-1)
E
sup
2
2.QQ
(dQ(2,))
2, E AA
(dQ(Z,
1)-1))2
17

---

Understanding the Kronecker Matrix- Vector Complexity of Linear Algebra
As in Lemma 35, we change our basis from V to Xz. Under Q, we have w (O, Under Pva. we have w ((XX,,,)) I). So, by Lemma 33, know that
dP (2,
2 ur 2(-1) 2 = (x)
E
(dQ(2, 1z-1))²
And, again following Lemma 26, we bound ((x(0) u}} S VJullz so the above exponential is most ex Ju]ull Therefore,
dP u Z n Ai)ddPur (2 (Z
dP (
3 1 (2, 24-1)
E 2
sup
(dQ(2, 2;-1))² 2
(dQ(2)))
ZEEALAA
/=1
Ei- VVJul
sup
ZEEiinA
sup ZEAAinA
< A² 22200
< 1 + 27
where we take = Ommin(C C2/2
}} O
C²/2 }) on the last line, completing the proof.
C. Formal Adaptive Matrix-Vector Lower Bound
Written in the notation and form of Appendix D, write Theorem 15 equivalently the following:
Theorem 15 Restated. Consider Setting 39 where V is the set of conditioned Kronecker-structure query vectors:
V = ((v(2) ,....,...... ((v((),....v(()) v(0) V vj (1) S"" cond((v()) v(01) s xx}
Then, t= (mmin((( ( / 1) matrix-vector products are needed to correctly guess if A = Ao or A in Setting 39 with probability least z. where Co and C, are the constants Lemma 8.
Proof. We proceed by using Theorem 40 in conjunction with Lemma 8 and Lemma 25. In particular, we Lemma 8 tells us that ((() S Co" for any < C, Therefore, we can take T = = C, so that E Tj = iCy. By assuming
307 that f S X=gz, we know that 12x2 Σラー Se
23.2
20, < 4. Then,
1 s c59+8) 1=1
f(7) + e
Σi=l
ffT,)
+8
C.
i=1
$ (1 + Ct) 9/2
27
where the last line holds so long as 1. < O(C 4/2). Similarly, we can use Lemma 25 to bound E. En,,r (e s 2 for
24
18

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
any 7) (0, 1). Therefore,
u,u/>p led (od'n" (Eizi rJ) n (Ei m0
22,
[u,u'))
Sel, e govof
e 0z
u,u'~p
2 22,2,
22,
3 e 290
2 2
S e R
< 1 + 8 1222t
n
$ 1 + 27
where that 1/
x²+²t < in the first inequality, that < x C7
in the second inequality, that ex S 1 + 2x for 27-8x in the last inequality. By Theorem 40, we find that having
4C*
S in the third inequality, and we take S C²
< O(min[Cg
x }) does not suffice to correctly guess if A Ao A A1 in Setting 39 with probability at least
D. Connecting to the Simchowitz et. al Lower Bounds
In (Simchowitz et al., 2017), the authors prove a lower bound against the number of matrix-vector products needed to detect there a rank-one matrix planted on random Wigner matrix. Their techniques and proofs are all written to consider the generic matrix-vector model, where proof techniques can be significantly generalized to allow matrix-vector products with a limited matrix-vector model. To start, we define generic notion of limited matrix-vector model.
compute Av for any vector E RDD However, with minor alteration, their
Definition 37. Fix a set V E (SDY. A matrix-vector algorithu A is V limited if it always computed exactly matrix vector products and if. for all input matrices A E DxD the algorithm only computes (possibly adaptive) query vectors (1) ...., y(() such that the sequence (y(1), (()) E Vt.
The proof methods of (Simchowitz et al., 2017) rely assuming that the matrix-vector queries computed are orthonormal. We do not want to assume that the queries admissible in V are orthonormal, so we instead will make an assumption on V that measure how far y from having orthonormal queries:
Definition 38. For each (v(1), ..... ) E Vt, let V = [v0 (()) E Dxt, If. for all
v(0) E y we know
that the condition number of V is at most K, then we say that Ve is k conditioned.
We can now setup the instance of the lower bound problem considered in (Simchowitz et al., 2017).
Setting 39. Fix D E N and X 1. Fix V limited matrix-vector algorithm A. Let P be isotropic prior distribution over planted vectors E SD-1, so that E E[u] = O and E. E[uu"] II Let W = + GT) where G E DxD is matrix with
tid (0, 1) entries. Let Ao == VD computes t matrix vector products with A = A; and returns guess of the value of
W and A JD
W + AuuT. Nature picks i E {0,1] uniformly at random. A then
In this setting, will show that (Simchowitz al., 2017) proves the following lower bounding mechanism:
Theorem 40. Consider Setting 39. Fix any 0 < 5i S ... S Ti and &. > Let f(r) be the probability that the best possible blind guess for D has squared inner product least b:
f(T): = (y(t) v()
sup
sup Pr Pr((v u)2 81.
sE[d
Suppose that for some E (0,
f(n) 2
c 3
2e T3
(f(T)) S²
19

---

Understanding the Kronecker Matrix- Complexity of Linear Algebra
and that
IE [e (u Eim at 29g EE 1 1
un u.u'
1. then any such algorithm Then, can distinguish from A with probability at most 1 + 1y32. In particular, if S 27' A cannot correctly guess if 0 i
2 1 with probability at least g.
In Appendix C, we show how to use Theorem 40 to lower bound Kronecker matrix- vector complexity. In this section, we instead will show how Theorem 40 follow from (Simchowitz et al., 2017). To start, will use the notion of Truncated Probability Distributions from (Simchowitz et al., 2017).
Definition 41. Let P be a probability measure. Let A be an event. Then, the truncated probability measure Tf with respect to A is defined by saying for all events B, P[B:A] = P[BnA]
This is not a probability distribution as its integral is less than 1 for any nontrivial event A. For discussion as to why the truneated probability distribution helpful in proving information-theeee 2018). We will also need the idea of the marginal of truncated distributions.
lower bounds, see (Simchowitz al., 2017;
Definition 42. Let be distribution over a space + Let (Fe) be a family of probability measures on space FF. For each 0, let Ag be event on F. For any event B FF we can then define the marginal truncated distribution P[; A] as
P[B; A]
E Ao]
9-P
Notice that the total measure of PP is P A PP : P]
= Eg Po[x: Aol = Prowe[Ao]- Without truncation, we write
We will concretely take Q and P to be distributions over transcripts of matrix-vector products between A and A. That is, we Av(!) be the transcript of t matrix -vetoor products. Then, we take Q to be the distribution
let 2, (v(),, Av(1).. ..... (-()) of 2, given 0, so that A VD W. We then will take P our prior distribution, so that 0 be the distribution of Z, given both = 1 and fixed value of so that A -WW W + AuuT for fixed u. For any fixed VD
Then, we let P.
we will take our truncation event to be A. 1/ := 0 S .... < Ti as given in Theorem 40. In words, this truncation set Vr is the set of all queries that fail to find nontrivial information about the vector u. Lastly, this means that P is the marginal distribution of all the truncated distributions. That is, is the distribution of Z, given i = but not given any particular value of u, and Pl. A] is P truncated to the cases where our algorithm has not computed any matrix-vector products that achieve nontrivial inner product with u.
v()) E V (v(*), u)² < B Vi [4]] using the constants
Our main goal is bound the total variation distance between Q and P. (Simchowitz al., 2017) bound this distance by truncating P and bounding both the probability of the truncated event not happening and the distance between Q and the truncated PP[:: AJ. This is formalized by Proposition 6.1 from (Simchowitz et al., 2017), whose proof has fixable error. We provide and prove the fixed version below:
Imported Lemma 43 (Proposition 6.1 of (Simchowitz et al., 2017)). Let P, (Po JoEe and As define marginal truncated distribution Pl-, A] on F). Let Q be a probability distribution on (X,F). Then, letting p == P ; A] = Pre- [Ag), we have
1
dP|r; A] dQ(xx)
1 1-P
Drv (PV(P.Q)
E anB
+1 2p
2
2
27
In particular, if we have ExnQ
< 11+2 z and 1- p < z for some E (0, 1), then we can bound Drv P) S
dQ(z)
v32..
Proof. This proof is close copy of the result in (Simchowitz et al., 2017), but avoids errors in algebra. For ease of notation,
let PA := A). Note that P PA A 2 0, which implies that
/ IdP dIP dlAl
dP
dIP A
1-p
20

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
so by the triangle inequality,
1 / [d[(x) - dP(z)) Drv (2, - 2
1 $ / [dQ(x) -dPa(x) 1
[dP(z) - dP (z))
|dQ(s)- dP (z)
1-p
Next, since Q is a probability measure,
/ [dQ(z) dP dP
(x) Q 22
11 S
E
dB dQ(a))
1
2
+ - 2P2(X))
E
dF dQ(z)
2
2p.
2Q
Combining what we've shown, we conclude the first result, that
2
dP (x) dQ(x)
1-P 2
Drv (Q,P)
+ 2p
Now, we move onto the second result. Directly substituting our values for z and 1 2, we get
(rv(Q,P) -
I + 2
2p +
p
2
2
1
1-p
V + 2(1 p)
2
V2 2z 2
<
2
2
$
333 + 2 V
2
$ v32
df (Q,)2))
We next import the results that (Simchowitz al., 2017) used to bound E Ez,nQ
and 1 1-p p- Pr[Vi]
Pr[iic E [f] (v()) u $1. Starting with 1 p. we import Theorem 5.3:
Imported Theorem 44 (Theorem 5.3 from (Simchowitz et al., 2017)). Consider Setting 39, Fix S TI S... S Tt. Let
[(T) be the probability that the best possible blind guess for u using a vector in Det achieves squared inner product at least b:
[(T) == sup
sup Pr[(v u3 $1
(ve))... xe((
Then, Pr(Bie [t] (y(0), u)²
A1 is at most
dIP (AP.(AV))
2 v012) dQ(Av (()) v()))
E f(T) Σ upp
S(T.)
sup
Il E j=1
(4 (())
This theorem exactly matches Theorem 5.3 from (Simchowitz et al., 2017) if we make two changes. First, we do not yet apply the inequality (5.25) for reasons we will discuss momentarily. Second, we change their set V into our set Vr in Lemma 5.2 so that we only consider queries that belong to V as opposed to arbitrary query vectors in S?, The proof of Lemma 5.2 does not change from this redefinition of Vr Next, we must bound this big expectation that appears on the
21

---

Understanding the Kronecker Matrix- Vector Complexity of Linear Algebra
right hand side above. In inequality (5.25), (Simchowitz al., 2017) bounds this expectation under the assumption that
v(1) v(O) are orthonormal. We cannot make this assumption, as orthonormal basis for vectors in Ve might not belong
to Vr So, we rephrase Lemma C.3 from (Simchowitz et al., 2017), making this orthonormality reduction explicit:
Imported Lemma 45 (Lemma C.3 from (Simchowitz al., 2017)). Consider Imported Theorem 44, Let x(1) orthonormal vectors such that span (x() .....
11111 x()) be
x span(v (v (.0)) for all E [t]. Then,
dP (Av v(t)) (00) | ,..,, 5(0)
)²
E
dQ(AvO) ((0))
Applying this result to Imported Theorem 44, that we need to upper bound the expression
Diu
sup (gO) GOyEER
Unfortunately, it is not immediately obvious how to relate (u, ( to v()),... ((0) 7I..... In the non-Kronecker case, when Ve covers all vectors in SP. we can take x ( without loss of generality. However, if V covers Kronecker- structured query vectors, then we do not know what the worst-case relationship between these terms is. So, make an
assumption on v to proceed. In particular, we assume that V is well conditioned.
Lemma 46. Consider Imported Theorem 44. Under the assumption that V is r-conditioned, know that
Pr[Bi e [t] (v(), u)² flS)
+2 D 55 f(A))
Proof. From the definition of the conditioning of VA, we know that for all (v()...., v()) E V that V = ((()) {(t)] has condition number at most k. Therefore, by Lemma 26, we know that (u, (0) s 2 Σ j=1 (n, vl0l,. By definition of Vs further know that (u, v00)2 S Z. So, get that
20y VS(T) s Σ (s(Tt)
sup (v()).., (
Overall, going back to Imported Theorem 44, we find that
Pr[ e [1] (V(),))² Bls + Σ 23,² Ei 3 V
completing the proof.
This suffices bound the term 1 1-2 p in Imported Lemma 43. However, we still have do bound the expected squared likelihood ratio term. Lemma C.3 from (Simchowitz et al., 2017) is analogous to Imported Lemma 45 but instead applies to this context:
Imported Lemma 47 (Lemma C.3 from (Simehowitz et al., 2017)). Consider Imported Theorem 44. Let IP be the distribution of Z, conditioned on i 1 but not conditioned on a specific value of u ~ P. Let (!) ...... x(() be orthonormal vectors such that span (
x00 spun (1) (())).))(()))) for all E (4). Then,
dQ())) )
dP|2; Vil
E zi4Q
an) DA3 او (z (8(0 (100,,) ((aa)) - (x00)) (x(0) (0))))))))))))) - (200) an) (l)0
E Ap
sup (0))..,,()))e//ee..
22

---

Understanding the Kronecker Matrix- Vector Complexity of Linear Algebra
Again, Lemma C.4 is not phrased exactly this way in (Simchowitz al., 2017). This result follows from the proof of Lemma C.4 without substituting the final inequality on page 30. In order resolve the impact of orthonormality this proof, again appeal to conditioning;
Lemma 48. Consider Imported Lemma 47. Under the assumption that V is --conditioned, we know that
dP|Z; Vill dQ(2,)
(a Eis ret 2 (Ei= 1z)²
E 2nd
<
u,u
Proof. As in the proof of Lemma 46, we know that (xx(), u)| S terms in Imported Lemma 47,
Ti vD
and (x ()) u''l S v vi
So, directly bounding the VD"
u) ( uu)
(u, u²)
(x) u/ (x() uu')
Σ
(x0) u) (x(() u')
j=1
2
15:T
i-1
$
D
(u,
+
Σ
2D
D
i=1
j=1
R²T
R²T
D
[(,
f=1
= =
+
D
1=1
Which completes the proof by substituting this back into Imported Lemma 47:
dP|2,; Vil
(uall at 2422 (Elsr 7:)²
E
E
202
dQ((z))
n.u'-P
We can now prove the overall lower bound Theorem 40.
Proof of Theorem 40. We apply Imported Lemma 43 to the distribution P truncated to V We get that
p = P(V = Pr
Mi E [4] : (v(0),)2² øl
2.-F
so that
1 1-p= p=
Pr
Bi [t] v,(0,uj² > Bl.
z,
By Lemma 46, we therefore know that
2 Of 75 Vf(T)
1 --p 1-p3
which we told is at most We similarly know by Lemma 48 that
27
di dT Ze: Vil
c Pn
Ei +t 220 (20) n7)
E z,-Q
<
E un
dQ( Zz.)
we are told most + z. So, by Imported Lemma 43, we complete the proof.
23

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
D.I. Unrolling Lemma
Partially unrelated to the above, will also need mildly generalize technical result from (Simchowitz et al., 2017) that helps handle adaptivity when resolving the adaptive lower bound against L2 estimation. The following is very similar to Lemma C.2 from (Simchowitz et al., 2017):
Lemma 49 (Unrolling Lemma). Let Fa. Pb. and C be distributions over random variable Z, = (Z1.-.. zt) for some arbitrary sample space E f. Let 2, = (Z1,'.. .... 22) for all E [t]. Let [et) be a sequence of events such that A is deterministic in 2, and such that A' S A 1--1_ Let (i( be the expected likelihood ratio between our three distributions at timestep i given Z;-
dP ( 2 1 2,-1) 2
9: (2(2,-1)
(dQ(22) 1s 2(-1))²
Then,
dP (2) (dQ(2,))2
11 11a--1]
II (2
sup
Z.EA--1
1=1
Proof. We start by defining the tail set (2;) the set of all ",-1," & such that (21,"" 2z, 2,,1111"" ,,) E A'. We will also define
Gi(Z,) = sup II 9j (Z,))) (,, j=it2
Notice that Go (Zo) E IT 9i and take G.- (Z == 1. Further, notice that for any Z where the event A'-1 holds,
G--1(2--199(2111))
sup
(2-12)4-1)9(22-111))) (2-
Then, for any i E [t]. we use tower rule to expand
dF (2,) d (Z,)
E
LiAi ()--)
(d((())))
dIPa (Z,))dPP(Z))
E
E
1s1i (21--1(2(-1) Z
(dQ( 22
dlP (Z, Zi-1 1 14-1) dl (2 )dl (Zi-1)
E
E
11- Gi Gi- (Zi-1) Z
(2;
1)-1))2
(dQ 1))2
dP
dlPa(2 2z-1)dPPA( 22-1)
E
(A--1/G:-1(2/ E
2
(dD(2,-1)))
(d0(2, 21-1))2
dP
(2,
11
|11-1 1/ 11--)----2---00
(dQ(2,-1))2
(Z,-1)
1 G-2-(1)))))
(dD(22-1))2
dPa IdPPP
< E
|Ai- 21-2(2,
(d)(
So, by induction, we find that
dF a (Z.)
dlP, (Z, ddP
dP )dlP
E
1 = EE
(JQ 222 1 G1
< S
1 Go(Zo)
(Q((2))
(dQ ((1(2)) 21)
We take A to be the whole space, so [[4o] = 1. Also, Go = supZ,EA Ii gi (Z,-1). ). So, we find
dPP (Z, ddP. (Zt))
E
114-11 <
sup
II (Z(-))
E
sup
(2)))
Z,EA" t=2
(dQ(2)))²
2,EA' t=1
24

---

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
completing the proof.
25


Reviews:
[{"review_id": "sitB1wwQ0t", "reviewer": "Reviewer_VCfy", "summary": "The authors study a computational model where a matrix A can only be accessed through matrix-vector products Ax where x has the specific form of the Kronecker product of q vectors. The paper establishes several key results:\n- The authors prove exponential lower bounds (in terms of q) on the number of queries needed to estimate properties such as the trace and top eigenvalue of a matrix, when restricted to using Kronecker matrix-vector products. These bounds apply to all adaptive algorithms under a mild conditioning assumption.\n- They demonstrate a fundamental gap between different types of random vectors.\n- The core technical insight driving these results is that random vectors with Kronecker structure have exponentially smaller inner products compared to their non-Kronecker counterparts, fundamentally limiting information extraction per query.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and insightful questions!\n\n* **On subclasses with non-exponential complexity:** That's an excellent question exploring the boundary of our worst-case results. Information-theoretically, if a matrix class $\\mathcal{A}$ has $D$ degrees of freedom (e.g., $D = O(kqn^2)$ if $A$ is a sum of $k$ Kronecker-structured symmetric matrices), then $\\approx D$ KMVP queries should suffice to identify $A \\in \\mathcal{A}$. However, our work focuses on the *computational* query complexity within the restricted Kronecker matrix-vector product (KMVP) model, where queries are of the form $A(\\otimes x_i)$. Our results show that *without* assuming specific structure that is *exploitable* via KMVP queries (or alternative queries enabled by the structure, like Tensor Train-vector products for TT-matrices), the complexity is exponential, specifically $\\exp(q)$. Therefore, efficient algorithms *necessitate* leveraging such structural assumptions, confirming that MPO/TT or similar structured classes are indeed the candidates where sub-exponential complexity might be achievable, precisely *because* they allow breaking away from the limitations of the generic KMVP oracle.\n\n* **On approximate tensor representations:** We interpreted this as \"given access to an arbitrary tensor $T$, can we show exponential lower bounds against the number of KMVPs needed to recover an approximate compact tensor representation of $T$?” Based on Lemma 45 (appendix), which shows $\\exp(q)$ queries are needed to find a Kronecker vector $v$ non-trivially correlated with a planted rank-one Kronecker vector $u$ in noise ($A = W + \\lambda uu'$), our answer is partially yes. This suggests that even finding low-rank tensor *structure* within noise is hard in the KMVP model. While we haven't rigorously proven \"$\\exp(q)$ queries are needed to produce a near-optimal TT approximation to $A$,\" Lemma 45 strongly indicates the difficulty of recovering even approximate structure efficiently via KMVPs alone.\n\n* **On the accuracy-complexity trade-off:** Our results suggest this trade-off is poor in the KMVP model. For zero-testing from a small alphabet (Section 5), algorithms with polynomial query complexity incur infinite relative error with high probability. For the not-ill-conditioned lower bounds (Section 4), Theorem 6 (spectral norm, $\\lambda_1(A)$) already demonstrates exponential multiplicative error even with exponentially many queries. Theorem 7 (trace estimation, $\\mathrm{tr}(A)$) likely implies a similar outcome via Lemma 37. Thus, for these fundamental problems, simply relaxing the accuracy requirement to constant multiplicative error does not appear to break the $\\exp(q)$ barrier within the KMVP model, according to our analysis.\n\nThanks again for your questions!", "claims_and_evidence": "The claims made in the paper are supported by rigorous mathematical proofs. The authors provide formal theorems, lemmas, and detailed proofs for their main results. The conditioning assumption they make for their lower bounds (requiring that the matrix of query vectors is not ill-conditioned) is reasonable and well-justified, as they explain why most practical algorithms naturally satisfy this condition. The paper effectively connects theoretical results to practical implications, explaining previously observed phenomena in prior work through a coherent mathematical framework, which adds credibility to their claims.", "methods_and_evaluation_criteria": "The methods used are appropriate. The authors:\n- Define the relevant computational model precisely (Kronecker Matrix-Vector Oracle).\n- Establish formal proof frameworks for lower bounds.\n- Use appropriate information-theoretic techniques adapted from prior work.\n- Derive matching upper and lower bounds for certain problems.", "theoretical_claims": "The theoretical analysis appears sound:\n- Lemma 8, which establishes the near-orthogonality of random Kronecker-structured vectors, forms a critical foundation for the other results. The proof appears sound.\n- The proofs of Theorems 6 and 7 (lower bounds for spectral norm and trace estimation) build on established information-theoretic techniques but extend them to the Kronecker setting.\n- The zero-testing complexity results (Theorem 18) correctly establish both upper and lower bounds for different alphabet sizes.", "experimental_designs_or_analyses": "This is a theoretical paper without experimental components.", "relation_to_broader_scientific_literature": "The paper effectively connects to several areas of scientific literature, such as lower bounds for matrix-vector algorithms, tensor sketching, Kronecker variants of randomized linear algebra methods, etc.", "essential_references_not_discussed": "To the best of my understanding, the authors have covered the main results in the literature.", "other_strengths_and_weaknesses": "Strengths and weaknesses have been highlighted in other questions.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. The results establish exponential lower bounds for the worst case. Are there natural subclasses of matrices or tensors for which the Kronecker matrix-vector complexity is not exponential?\n2. How do your results extend to approximate tensor representations? Do the same exponential lower bounds apply when we only seek approximate solutions?\n3. How does the trade-off between query complexity and accuracy behave? Specifically, if we relax the accuracy requirements (e.g., allow larger approximation errors), can we achieve sub-exponential query complexity?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wjfpnWgH6i", "reviewer": "Reviewer_xSH8", "summary": "Given a matrix $A$, this paper considers estimating the top eigenvalue and the trace of $A$ by matrix-vector multiplications in which the vector is the Kronecker product of $q$ vectors. The main results of the paper are that constant factor estimation of these values require exponential in $q$ such matrix-vector multiplications.\n\nAnother result states that testing whether $A=0$ requires exponential in $q$ Kronecker matrix-vector multiplications if the $q$ vectors come from the Radamacher distribution. This is in contrast with the Gaussian case.\n\nAll of the results of the paper rely on the fact that a random Kronecker product vector is almost orthogonal to an arbitrary Kronecker product vector with high probability. In fact, the “level of orthogonality” is smaller than what one expects for general vectors by a factor exponential in $q$. This is not very hard to see from the algebraic structure of the Kronecker product.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for raising this critical point about the relationship between our general matrix lower bounds and specific tensor decomposition applications. We understand the concern that our worst-case instances might not be compactly representable. However, our work's primary focus is on understanding the fundamental limitations imposed by the **Kronecker matrix-vector product (KMVP) query model itself**. We view this model, where interaction is limited to queries of the form $A(\\otimes x_i)$, as a natural, restricted way to interact with large linear operators (which may or may not arise from tensors), and we aim to characterize its inherent power.\n\nCrucially, as the reviewer notes, some tensors *are* compactly representable. Our results in Section 5 for Zero-Testing provide a concrete example where the lower bound instance *is* a sparse rank-one tensor, exactly representable in standard formats (CP, Tucker, TT, etc.). For this directly relevant case, we prove an exponential ($\\exp(q)$) separation between small-alphabet sketches (like Rademacher, used in practice) and large-alphabet sketches (Gaussian), showing the former fail dramatically even for this simple task. This yields the direct, practical implication that small-alphabet sketches should be avoided in tensor algorithms relying on KMVP-like queries.\n\nRegarding the bounds in Section 4 for potentially non-compact matrices: these results are vital because they establish the **baseline difficulty** of solving fundamental problems when restricted *solely* to KMVP queries. The exponential ($\\exp(q)$) complexity proves that **any algorithm achieving sub-exponential performance in this model *must* implicitly or explicitly leverage structural properties of the matrix beyond what is accessible through generic KMVP queries.** If an algorithm treats the matrix purely as a black-box accessible only via KMVPs, it *will* fail on our hard instances. Therefore, our work rigorously demonstrates *why* successful tensor algorithms often cannot afford to be structure-oblivious; they must exploit the specific tensor representation (like TT/Tucker) either through specialized queries or direct manipulation of factors. This directly addresses the dichotomy noted in our introduction [Lines 36-41]: our lower bounds explain the inefficiency of structure-oblivious methods operating within the KMVP framework and quantify the inherent cost associated with this restricted oracle access.\n\nIn summary, our results provide fundamental insights into the KMVP query model. The zero-testing bounds offer direct practical guidance, while the general lower bounds rigorously justify the necessity of structure-aware algorithm design for tensors when seeking efficient solutions. We hope this clarifies the significance of our findings, and we will refine the paper's exposition to better emphasize these connections. Thank you again for the feedback!", "claims_and_evidence": "Some claims regarding the importance of this result for tensor decompositions are not justified in my opinion.", "methods_and_evaluation_criteria": "The paper is theoretical and this is not applicable.", "theoretical_claims": "I have not checked the proofs carefully, but the results sound natural and correct to me.", "experimental_designs_or_analyses": "The paper is theoretical and this is not applicable.", "relation_to_broader_scientific_literature": "It is not clear what the exact implications of these results are to the broader literature.\n\nPrior works have established exponential bounds for embeddings which I believe are important for the sampling literature, but the current results do not seem to give any implications for that either.", "essential_references_not_discussed": "I don't know any important references that have not been discussed.", "other_strengths_and_weaknesses": "The results of the paper are not very surprising in my opinion and they are not aligned with the motivations about tensor decomposition with which the paper starts. More specifically, the paper argues that their results have strong implications for tensor decomposition since in many cases, one does not want to unravel the decomposition’s structure to test properties related to it, and therefore, it is more suitable to consider the matrix-vector multiplication model. However, the results of the paper are for general matrices and not the structured matrices arising from tensor decompositions. I don’t find the results very appealing if they are not generalizable to such structured matrices, and I don’t see how they could be generalized to such matrices.", "other_comments_or_suggestions": "I don't have any other comments or suggestions.", "questions_for_authors": "My main question is whether these results are generalizable to the structured matrices that appear in tensor decompositions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aG2sBr5mdL", "reviewer": "Reviewer_KWPu", "summary": "This paper studied the Kronecker matrix product oracle complexity lower bounds for estimating the trace and spectrum of a matrix $A$. The authors showed that for a matrix $A\\in R^{n^q\\times n^q}$ and vector $x = \\otimes x_i$, $x_i\\in R^d$ and $i\\in [q]$, to estimate $tr(A)$ or $\\lambda_1(A)$, it requires at least $C^q$ products between $A$ and R$x$. The result relies on a novel probability bound on the inner product of 2 uniform kronecker-product-vectors. The result also implied that if $x_i\\in\\{1,-1\\}^n$, it takes $2^q$ queries to kronecker matrix products to $A$ to test whether $A = 0$ or not, while if $x_i$ are gaussian vectors it only requires 1 query.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and the insightful question!\n\n* **On the effect of sparsity:** If $A$ is sparse, we do not particularly expect this to drastically reduce the *oracle* query complexity. Suppose we aim to show that $s$-sparsity reduces complexity. We can take our dense lower bound instance $A \\in \\mathbb{R}^{n^q \\times n^q}$ and embed it into a larger zero-padded matrix $B \\in \\mathbb{R}^{m^q \\times m^q}$ (where $m \\approx n/s^{1/q}$) such that $B$ is $s$-sparse but information-theoretically equivalent to $A$ regarding KMVP queries involving the non-zero block. Our $\\exp(q)$ lower bounds would still hold for recovering information about the original $A$ via queries to $B$. This indicates that the hardness demonstrated by our lower bounds stems from the limitations of the KMVP queries interacting with worst-case matrix constructions, rather than simply the density of the matrix. It might be possible to get sparsity-dependent bounds with careful parameterization, but simple sparsity alone doesn't bypass the worst-case lower bound in this model.\n\nThanks for the question!", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proofs in the main body.", "experimental_designs_or_analyses": "Theory paper. N/A", "relation_to_broader_scientific_literature": "The work nices extends the thread of research of the computation complexity of tensor calculations.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I think this paper is clearly written with many useful intuitions and explanations. I am not very familiar with the literature on the oracle complexity of tensor calculations using kronecker products. However, I think this paper has a significant contribution in the computational (oracle) complexity for tensor calculations. The paper provided a very interesting separation in the oracle complexity between the methods using non-kronecker products and knronecker products, as well as an separation in the performance of knronecker product based algorithm between large alphabets and small alphabets. The techniques in this paper might also be of independent interest for other fields.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I am wondering how would the sparsity of A contributes to the oracle complexity of kronecker products?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GnRlRPHFiF", "reviewer": "Reviewer_q7YV", "summary": "- The paper addresses several fundamental linear algebraic problems in the Kronecker matrix-vector query model\n\n- Its main contribution is a proof that it requires at least an exponential number of Kronecker matrix-vector products to get a decent estimate of key properties of the matrix\n\n- It also proves that Kronecker matrix-vector algorithms with small-alphabet queries require polynomial complexity for zero testing, whereas it takes O(1) in the non-Kronecker case\n\n- The analysis reveals new insights on the fundamental complexity of linear algebra in the Kronecker matrix-vector model.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive feedback, and for catching the typo in Lemma 8 – we will correct it!\n\n* **On the practical impact:** Our exponential ($\\exp(q)$) lower bounds for the generic KMVP model serve as a crucial baseline, demonstrating that applications requiring efficiency *cannot* treat the tensor as an arbitrary black-box accessed only via KMVPs ($A(\\otimes x_i)$ queries). They *must* exploit known structural properties. This implies two paths forward:\n    1.  **Avoid problematic queries:** Our results on small-alphabet algorithms (Section 5) directly advise against using such sketches (e.g., Rademacher vectors with entries in $\\{\\pm 1\\}$) in downstream applications, as used in practice [Feldman et al., Rakhshan Rabusseau], favoring continuous distributions like Gaussian instead for tasks like zero-testing.\n    2.  **Leverage structure:** Efficient algorithms must use more structural information. Our bounds quantify the \"cost of ignorance\" when restricted to KMVPs. This justifies why successful tensor methods often use algorithms tailored to specific representations (like [Ahle et al.], exploiting data storage) or leverage query types beyond standard KMVPs that are enabled by that structure (e.g., MPO-vector products for TT-matrices [Rakhshan Rabusseau]).\n    For low-order tensors (e.g., $q=3$ or $q=4$ in medical imaging), an $\\exp(q)$ dependence might be tolerable, but our results highlight the scaling limitations for higher-order tensors common in other fields like quantum information science.\n\nThanks for the question! We will incorporate this discussion into the paper.", "claims_and_evidence": "All claims made in the submission are well supported by clear and convincing evidence as far as I am aware of.", "methods_and_evaluation_criteria": "Proper mathematical tools are used for proving the theoretical claims in the paper.", "theoretical_claims": "I have to admit that I did not check the correctness of the proofs due to the time limit.", "experimental_designs_or_analyses": "There is no experimental design or analysis in the paper, as it is a pure theoretical work.", "relation_to_broader_scientific_literature": "- The theoretical result reveals new insights on the fundamental complexity of linear algebra in the Kronecker matrix-vector model.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "- The paper is very well organized and written.\n\n- It is undiscussed how the theoretical merit may affect practical applications that involve Kronecker matrix-vector models", "other_comments_or_suggestions": "- I think there is a typo in Lemma 8 - ... universal constants $C_\\tau, C_\\delta > 1$ ... should it be $C_\\tau, C_0$ instead?", "questions_for_authors": "How could your result on the exponential complexity of Kronecker matrix-vector models affect its \n applications, such as quantum information science or medical imaging?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall, three of the reviewers found the paper interesting and well-written. However, one of the reviewers raised concerns about the motivation of the Kronecker matrix-vector product model, and thereby, about the significance of the results. These concerns remain after the author response, and should be carefully addressed in the paper.
Decision: Accept (poster)