论文标题
向量 - 矩阵向量查询，用于求解线性代数，统计和图形问题
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
论文作者
论文摘要
我们考虑通过矢量 - 马trix-vector查询学习矩阵的总体问题。这些查询提供了$ \ boldsymbol {u}^{\ mathrm {\ mathrm {t}} \ boldsymbol {m} \ boldsymbol {m} \ boldsymbol {v} $在固定字段$ \ mathbb {f}上，用于指定的Vectors $ \ boldsymbol \ Mathbb {f}^n $。为了激励这些查询，我们观察到它们概括了许多先前研究的模型，例如独立的设置查询，剪切查询和标准图查询。他们还专门研究了最近研究的矩阵矢量查询模型。我们的工作是探索性和广泛的，我们为各种问题，跨越线性代数，统计和图形提供了新的上和下限。我们的许多结果几乎很紧，我们使用线性代数，随机算法和通信复杂性的多种技术。
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}\boldsymbol{v}$ over a fixed field $\mathbb{F}$ for a specified pair of vectors $\boldsymbol{u},\boldsymbol{v} \in \mathbb{F}^n$. To motivate these queries, we observe that they generalize many previously studied models, such as independent set queries, cut queries, and standard graph queries. They also specialize the recently studied matrix-vector query model. Our work is exploratory and broad, and we provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs. Many of our results are nearly tight, and we use diverse techniques from linear algebra, randomized algorithms, and communication complexity.
