Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Authors: Raphael A Meyer, William Joseph Swartworth, David Woodruff
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational model where we can access a matrix A only by computing matrixvector products Ax for vectors of the form x = x1 xq. We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of A. Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm s queries. [...] Broadly, our analysis reveals new insights on the fundamental complexity of linear algebra in the Kronecker matrixvector model. We show that basic linear algebra tasks must incur an exponential sample complexity in the worst case. |
| Researcher Affiliation | Academia | 1Computing + Mathematical Sciences Department, California Institute of Technology. 2Department of Computer Science, Carnegie Mellon University. Correspondence to: Raphael Meyer <EMAIL>, William Swartworth <EMAIL>, David P. Woodruff <EMAIL>. |
| Pseudocode | No | The paper does not contain any explicitly labeled pseudocode or algorithm blocks. The term 'algorithm' is used to refer to a general computational method, not a structured procedure presented in code-like format. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described, nor does it provide links to code repositories or supplementary materials for code. |
| Open Datasets | No | This paper is theoretical and focuses on proving lower bounds for computational complexity in the Kronecker matrix-vector model. It does not describe or use any datasets for empirical evaluation. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with datasets, therefore, there is no mention of dataset splits (e.g., training, validation, test splits). |
| Hardware Specification | No | This paper is theoretical and focuses on proving computational complexity lower bounds. It does not describe any experimental setup or specific hardware used for computations. |
| Software Dependencies | No | This paper is theoretical and does not report on any empirical experiments that would require specific software dependencies with version numbers for replication. |
| Experiment Setup | No | This paper is theoretical and focuses on mathematical proofs and lower bounds. It does not describe an experimental setup, hyperparameters, or training configurations. |