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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.