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$).
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.
Of course, this approach gives only a probabilistic approximation method; it cannot guarantee accuracy with 100% certainty. But this is not of practical significance, as long as the error probabilities can be made sufficiently low. And in any case, it's not too hard to show that there cannot exist a deterministic approximation algorithm running in sublinear time, so probabilistic approximation is all that we could ask for in this case.
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).
