2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | G.4.3 | ||
| Paper Title | Fast Compressive Large-Scale Matrix-Matrix Multiplication Using Product Codes | ||
| Authors | Orhan Ocal, Kannan Ramchandran, University of California at Berkeley, United States | ||
| Session | G.4: Group Testing and Sparse Codes | ||
| Presentation | Lecture | ||
| Track | Graphs, Games, Sparsity, and Signal Processing | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Matrix-matrix multiplication and its derivatives are fundamental linear-algebraic primitives at the core of many modern optimization and machine learning algorithms. We design a new and novel framework for speeding up large-scale matrix-matrix multiplication when the output matrix is known to be sparse, as is true in many applications of interest. Our solution is based on a novel use of product codes which have been studied in the communications literature. In particular, when multiplying two matrices of sizes n×d and d×n where the output matrix is (exactly) K-sparse with support uniformly distributed, our algorithm requires max(O(dK),O(dn)) computations. We also extend our framework to handle the approximately-sparse setting where the output matrix has K-entries that are significantly larger than the rest. In this case, the computational complexity is max(O(dK log^2(n)),O(dn log^2(n))). We corroborate our findings with numerical simulations that validate our claims. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
