# Approximate Matrix Multiplication with approximation guarantees that ignore large elements?

Approximate matrix multiplication is a technique to replace a matrix product $$A^t B$$ with a smaller product $$(\Pi A)^t(\Pi B)$$. Intuitively, if $$\Pi$$ is chosen from a suitable distribution that has

• dimensionality reduction properties, i.e. $$\Pi \in\mathbb{R}^{n\times m}$$ with $$n \leq m$$ is compressing, and
• approximately preserves inner products $$\langle \Pi x,\Pi y\rangle \in (1\pm \epsilon)\langle x,y\rangle$$,

then one can hope that each entry of $$(\Pi A)^t(\Pi B)$$, which takes the form $$\langle \Pi A_i, \Pi B_i\rangle$$, is both approximately correct, and computable in time depending on $$n \leq m$$.

While this is an interesting technique (and useful in many areas of computer science), in my (cryptographic) applications I have never been able to use it. In particular, in my setting

• The product $$A^tB = \Delta I + E$$ for "small" $$E$$, i.e. the product $$A^tB$$ is small, except for at most $$O(n)$$ "large" elements ($$\Delta I$$), and
• At least one of the individual $$A, B$$ is pseudorandom, and therefore has $$\lVert A\rVert_F$$ (for example) "large".

Typically (see for example Theorem 3), the approximation guarantees scale multiplicatively with $$\lVert A\rVert_F\lVert B\rVert_F$$, hence are not useful due to the pseudorandomness constraint. I have seen some papers that instead give bounds that depend on $$\lVert A^tB\rVert_F$$, but these are also not useful for me, due to the largeness of $$\Delta I$$.

The paper compressed matrix multiplication by Pagh has the following result, which is almost very useful to me. It is stated in Section 1.2.

Let $$N\leq 2n^2$$ be the number of non-zero entries in $$A$$ and $$B$$. We obtain an approximation $$C$$ in time $$O(N+nb)$$ and space $$O(b\log n)$$ such that

• If $$AB$$ has frobenius norm $$q$$ when removing its $$b$$ largest entries, the error of each entry is bounded whp. by $$q/\sqrt{b}$$.

For my application, I can set $$q = O(n)$$, and get an error bound depending on $$E$$, which has small Frobenius norm, i.e. it is applicable in my setting of both $$\lVert A\rVert_F, \lVert B\rVert_F$$ large, and $$A^t B =\Delta I + E$$ with $$\Delta >0$$ large. Concretely, this is useful to me, but I would be interested in knowing if the result has been improved. Pagh's result has 140 citations though, so it seems best to ask a question rather doing a full literature review on a topic outside of my research area.

I am curious about other approximate matrix multiplication algorithms with a similar guarantee, namely where when $$A^t B = \Delta I + E$$ for $$\Delta$$ large, one may still obtain good approximations. In particular, I would be interested in a data-independent algorithm, i.e. a distribution $$\mathcal{D}$$ such that, for $$\Pi\sim \mathcal{D}$$, $$(\Pi A)^t(\Pi B)\approx A^t B$$, again with error depending on $$\lVert E\rVert_F$$ rather than $$\lVert A\rVert_F, \lVert B\rVert_F$$, or $$\lVert \Delta I + E\rVert_F$$.

Are such algorithms known? Or more generally, are there other algorithms similar to Pugh's that allow one to get error bounds that depending on the output $$AB$$, where one may ignore the "largest" elements of the output?