Output-Sparse Matrix Multiplication Using Compressed Sensing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911105377370112 |
|---|---|
| author | Bennett, Huck Gajulapalli, Karthik Golovnev, Alexander Warton, Evelyn |
| author_facet | Bennett, Huck Gajulapalli, Karthik Golovnev, Alexander Warton, Evelyn |
| contents | 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 most $O(n^δ)$ many non-zero entries for a given value $δ\in [0, 2]$. We then show how to speed up these algorithms in the fully sparse setting, where the input matrices $A, B$ are themselves sparse. All of our algorithms work over arbitrary rings.
Our first, deterministic algorithm for OSMM works via a two-pass reduction to compressed sensing. It runs in roughly $n^{ω(δ/2, 1, 1)}$ time, where $ω(\cdot, \cdot, \cdot)$ is the rectangular matrix multiplication exponent. This substantially improves on prior deterministic algorithms for output-sparse matrix multiplication.
Our second, randomized algorithm for OSMM works via a reduction to compressed sensing and a variant of matrix multiplication verification, and runs in roughly $n^{ω(δ- 1, 1, 1)}$ time. This algorithm and its extension to the fully sparse setting have running times that match those of the (randomized) algorithms for OSMM and FSMM, respectively, in recent work of Abboud, Bringmann, Fischer, and Künnemann (SODA, 2024). Our algorithm uses different techniques and is arguably simpler.
Finally, we observe that the running time of our randomized algorithm and the algorithm of Abboud et al. are optimal via a simple reduction from rectangular matrix multiplication. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10250 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Output-Sparse Matrix Multiplication Using Compressed Sensing Bennett, Huck Gajulapalli, Karthik Golovnev, Alexander Warton, Evelyn Data Structures and Algorithms 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 most $O(n^δ)$ many non-zero entries for a given value $δ\in [0, 2]$. We then show how to speed up these algorithms in the fully sparse setting, where the input matrices $A, B$ are themselves sparse. All of our algorithms work over arbitrary rings. Our first, deterministic algorithm for OSMM works via a two-pass reduction to compressed sensing. It runs in roughly $n^{ω(δ/2, 1, 1)}$ time, where $ω(\cdot, \cdot, \cdot)$ is the rectangular matrix multiplication exponent. This substantially improves on prior deterministic algorithms for output-sparse matrix multiplication. Our second, randomized algorithm for OSMM works via a reduction to compressed sensing and a variant of matrix multiplication verification, and runs in roughly $n^{ω(δ- 1, 1, 1)}$ time. This algorithm and its extension to the fully sparse setting have running times that match those of the (randomized) algorithms for OSMM and FSMM, respectively, in recent work of Abboud, Bringmann, Fischer, and Künnemann (SODA, 2024). Our algorithm uses different techniques and is arguably simpler. Finally, we observe that the running time of our randomized algorithm and the algorithm of Abboud et al. are optimal via a simple reduction from rectangular matrix multiplication. |
| title | Output-Sparse Matrix Multiplication Using Compressed Sensing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.10250 |