Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

Raphael A. Meyer, William Swartworth, David P. Woodruff

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} = \ma…