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?
