Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

Raphael A Meyer, William Joseph Swartworth, David Woodruff
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:43909-43933, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-meyer25a, title = {Understanding the {K}ronecker Matrix-Vector Complexity of Linear Algebra}, author = {Meyer, Raphael A and Swartworth, William Joseph and Woodruff, David}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {43909--43933}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/meyer25a/meyer25a.pdf}, url = {https://proceedings.mlr.press/v267/meyer25a.html}, 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.} }
Endnote
%0 Conference Paper %T Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra %A Raphael A Meyer %A William Joseph Swartworth %A David Woodruff %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-meyer25a %I PMLR %P 43909--43933 %U https://proceedings.mlr.press/v267/meyer25a.html %V 267 %X 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.
APA
Meyer, R.A., Swartworth, W.J. & Woodruff, D.. (2025). Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:43909-43933 Available from https://proceedings.mlr.press/v267/meyer25a.html.

Related Material