Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu

We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $\boldsymbol{u}^{\mathrm{T}}\boldsymbol{M}\bolds…