Efficient Matrix Multiplication: The Sparse Power-of-2 Factorization

Müller R, Gäde B, Bereyhi A (2020)

Publication Type: Conference contribution, Original article

Publication year: 2020

Publisher: Institute of Electrical and Electronics Engineers Inc.

Conference Proceedings Title: 2020 Information Theory and Applications Workshop, ITA 2020

Event location: San Diego, CA, USA US

ISBN: 9781728141909

DOI: 10.1109/ITA50056.2020.9244952

Abstract

We present an algorithm to reduce the computational effort for the multiplication of a given matrix with an unknown column vector. The algorithm decomposes the given matrix into a product of matrices whose entries are either zero or integer powers of two utilizing the principles of sparse recovery. While classical low resolution quantization achieves an accuracy of 6 dB per bit, our method can achieve many times more than that for large matrices. Numerical and analytical evidence suggests that the improvement actually grows unboundedly with matrix size. Due to sparsity, the algorithm even allows for quantization levels below 1 bit per matrix entry while achieving highly accurate approximations for large matrices. Applications include, but are not limited to, neural networks, as well as fully digital beam-forming for massive MIMO and millimeter wave applications.

Authors with CRIS profile

Ralf Müller Professur für Informationsübertragung Bernhard Gäde Lehrstuhl für Digitale Übertragung Ali Bereyhi Lehrstuhl für Digitale Übertragung

How to cite

APA:

Müller, R., Gäde, B., & Bereyhi, A. (2020). Efficient Matrix Multiplication: The Sparse Power-of-2 Factorization. In 2020 Information Theory and Applications Workshop, ITA 2020. San Diego, CA, USA, US: Institute of Electrical and Electronics Engineers Inc..

MLA:

Müller, Ralf, Bernhard Gäde, and Ali Bereyhi. "Efficient Matrix Multiplication: The Sparse Power-of-2 Factorization." Proceedings of the 2020 Information Theory and Applications Workshop, ITA 2020, San Diego, CA, USA Institute of Electrical and Electronics Engineers Inc., 2020.

BibTeX: Download