Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

Thanks for the positive feedback, and for catching the typo in Lemma 8 – we will correct it!

• 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:
  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.
  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]). 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.

Thanks for the question! We will incorporate this discussion into the paper.

We thank the reviewer for their appreciation of our work and the insightful question!

• 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.

Thanks for the question!

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.

Crucially, 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.

Regarding 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.

In 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!

We thank the reviewer for their positive comments and insightful questions!

• 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.

• 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.

• 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.

Thanks again for your questions!