Deterministic algorithms for skewed matrix products

Abstract

Recently, Pagh presented a randomized approximation algorithm for the multiplication of real-valued matrices building upon work for detecting the most frequent items in data streams. We continue this line of research and present new {\em deterministic} matrix multiplication algorithms. Motivated by applications in data mining, we first consider the case of real-valued, nonnegative $n$-by-$n$ input matrices $A$ and $B$, and show how to obtain a deterministic approximation of the weights of individual entries, as well as the entrywise $p$-norm, of the product $AB$. The algorithm is simple, space efficient and runs in one pass over the input matrices. For a user defined $b\in (0,n^2)$ the algorithm runs in time $O(nb+n\cdot \text{Sort}(n))$ and space $O(n+b)$ and returns an approximation of the entries of $AB$ within an additive factor of $\Vert AB{\Vert }_{E1}/b$, where $\Vert C{\Vert }_{E1}={\sum }_{i,j}|C_{ij}|$ is the entrywise 1-norm of a matrix $C$ and $\text{Sort}(n)$ is the time required to sort $n$ real numbers in linear space. Building upon a result by Berinde et al. we show that for skewed matrix products (a common situation in many real-life applications) the algorithm is more efficient and achieves better approximation guarantees than previously known randomized algorithms. When the input matrices are not restricted to nonnegative entries, we present a new deterministic group testing algorithm detecting nonzero entries in the matrix product with large absolute value. The algorithm is clearly outperformed by randomized matrix multiplication algorithms, but as a byproduct we obtain the first $O(n^{2+\epsilon })$-time deterministic algorithm for matrix products with $O(\sqrt{n})$ nonzero entries.