# Efficient (sublinear) approximation algorithms for matrix-vector multiplication?

Given a matrix $A \in \mathbb{R}^{n \times p}$ and a vector $x \in \mathbb{R}^p$, I am interested in computing the value of the mean matrix-vector product:

$$v = \frac{1}{n} Ax$$

If I did this using standard matrix-vector multiplication, then it would take $O(np)$ operations. I am wondering if there exists an approximate approach that can do better (that is sublinear in $n$ or $p$).

• In what sense is this a mean? Did you mean $v=\frac1p Ax$? Mar 15, 2015 at 2:37

One approach is to treat each component of the result as a separate approximation problem. In this case, we can assume that $A$ is a row vector, so really the problem is to approximate a dot product $\sum_{i=1}^p a_ix_i$, or equivalently, to approximate the mean of the terms, $\frac1p\sum_{i=1}^p a_ix_i$.
This can be done by selecting a random sample of the indices $1,\dots,p$, and taking the mean of $a_ix_i$ over the sample, and constructing the $z$ confidence interval, a standard statistical procedure. In order to apply a Central Limit Theorem type of result to show that this gives asymptotically correct confidence intervals, we would need some mild assumptions on the entries of $A$ and $x$ to ensure that, roughly speaking, the mean cannot be dominated by outliers in a small proportion of entries. If you had upper and lower bounds on the entries of $A$ and $x$, for instance, then you could use Hoeffding's inequality to bound the probability of the estimate exceeding a given margin of error.
If a separate confidence interval for each component is not a desirable form for the output, then the approach could probably be adapted to instead give a margin of error for the norm of the error vector (e.g., with respect to the $\ell^1$, $\ell^2$, or $\ell^\infty$ norms).