Output-Sparse Matrix Multiplication Using Compressed Sensing

Huck Bennett, Karthik Gajulapalli, Alexander Golovnev +1

We give two algorithms for output-sparse matrix multiplication (OSMM), the problem of multiplying two $n\times n$ matrices $A,B$ when their product $AB$ is promised to have at mo…