Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Query Efficient Structured Matrix Learning
We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix $A$ given access to matrix-vector product (matvec) queries of the form $x \rightarrow Ax$ and $x \rightarr…
Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
Motivated by the problem of fast processing of attention matrices, we study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices $K\in \mathbb{R}^{n\times n}$. $K$'s columns are in…
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of …
Recommendation SystemsMulti-task nonparallel support vector machine for classification
Direct multi-task twin support vector machine (DMTSVM) explores the shared information between multiple correlated tasks, then it produces better generalization performance. However, it contains matrix inversion operatio…
ClassificationComputational EfficiencySINR Maximizing Distributionally Robust Adaptive Beamforming
This paper addresses the robust adaptive beamforming (RAB) problem via the worst-case signal-to-interference-plus-noise ratio (SINR) maximization over distributional uncertainty sets for the random interference-plus-nois…