RECORD
Querying a Matrix through Matrix-Vector Products
Computational Complexity · Submitted 13 Jun 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Surprisingly, this fundamental model does not appear to have been studied on its own, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We consider algorithms with access to an unknown matrix $M\in\mathbb{F}^{n \times d}$ via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \mathbf{v}^q$, and observes $M\mathbf{v}^1,\ldots, M\mathbf{v}^q$. Here the $\mathbf{v}^i$ can be randomized as well as chosen adaptively as a function of $ M\mathbf{v}^1,\ldots,M\mathbf{v}^{i-1}$. Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number $q$ of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix $M$; to compute the AND/OR/Parity of each column or row of $M$, to decide whether there are identical columns or rows in $M$ or whether $M$ is symmetric, diagonal, or unitary; or to compute whether a graph defined by $M$ is connected or triangle-free. We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. Surprisingly, this fundamental model does not appear to have been studied on its own, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider algorithms with access to an unknown matrix $M\in\mathbb{F}^{n \times d}$ via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \mathbf{v}^q$, and observes $M\mathbf{v}^1,\ldots, M\mathbf{v}^q$. | method 0.53 | 0.20 | 0.03 | asserted 0.96 |
| s1 | Here the $\mathbf{v}^i$ can be randomized as well as chosen adaptively as a function of $ M\mathbf{v}^1,\ldots,M\mathbf{v}^{i-1}$. | method 0.77 | 0.15 | 0.02 | asserted 0.70 |
| s2 | Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number $q$ of queries needed to solve various fundamental problems. | contribution 0.72 | 0.47 | 0.06 | asserted 0.91 |
| s3 | We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. | contribution 0.98 | 0.85 | 0.04 | asserted 0.98 |
| s4 | For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix $M$; to compute the AND/OR/Parity of each column or row of $M$, to decide whether there are identical columns or rows in $M$ or whether $M$ is symmetric, diagonal, or unitary; or to compute whether a graph defined by $M$ is connected or triangle-free. | contribution 0.98 | 0.79 | 0.09 | asserted 0.86 |
| s5 | We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. | result 0.96 | 0.95 | 0.12 | asserted 1.00 |
| s6 | We also show separations depending on the underlying field the matrix-vector product occurs in. | result 0.93 | 0.94 | 0.07 | asserted 1.00 |
| s7 | For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. | result 0.96 | 0.95 | 0.06 | asserted 1.00 |
| s8 | Surprisingly, this fundamental model does not appear to have been studied on its own, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas. | gap 0.82 | 0.21 | 0.11 | hedged possibility 0.61 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We consider algorithms with access to an unknown matrix $M\in\mathbb{F}^{n \times d}$ via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \mathbf{v}^q$, and observes $M\mathbf{v}^1,\ldots, M\mathbf{v}^q$. Here the $\mathbf{v}^i$ can be randomized as well as chosen adaptively as a function of $ M\mathbf{v}^1,\ldots,M\mathbf{v}^{i-1}$. Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number $q$ of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix $M$; to compute the AND/OR/Parity of each column or row of $M$, to decide whether there are identical columns or rows in $M$ or whether $M$ is symmetric, diagonal, or unitary; or to compute whether a graph defined by $M$ is connected or triangle-free. We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. Surprisingly, this fundamental model does not appear to have been studied on its own, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
Human review
References
How the literature uses it
5 arXiv papers cite this in 18 sentences
Papers citing it · 10 sentences without a confident label
Uses its method or tool 1 paper
-
To make the proof self-contained, we describe the algorithm of Sun, Woodruff, Yang, and Zhang [ref] .
Quantum query complexity with matrix-vector products · Left and right matrix-vector queries · 0.96
Compares with it 1 paper
-
Compared to the classical bounds using either the $$ oracle [ref] or the $$ oracle [ref] , our quantum algorithms achieve exponential quantum speedups.
Quantum query complexity with matrix-vector products · Introduction · 1.00
Cites it as background 3 papers
-
Specifically, Sun, Woodruff, Yang, and Zhang [ref] studied the complexities of various linear algebra, statistics, and graph problems using matrix-vector products, and Braverman, Hazan, Simchowitz, and Woodworth [ref] proved tight bounds on maximum eigenvalue computation and linear regression in this model.
Quantum query complexity with matrix-vector products · Introduction · 0.94
-
Recently, in the matrix-vector product model, Sun et. al. considered testing various graph and matrix properties [ref] , and Han et. al. considered approximating spectral sums and testing positive semi-definiteness [ref] .
Testing Positive Semi-Definiteness via Random Submatrices · Related work · 0.95
-
These models were recently formalized in the theoretical computer science community in [ref] , though similar models have been studied in numerous fields, such as the number of measurements in compressed sensing, or the sketching dimension of a streaming algorithm.
Testing Positive Semidefiniteness Using Linear Measurements · Introduction · 0.94
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.