Approximate Weighted CR Coded Matrix Multiplication

MaRDI QIDQ6354092arXivFDO

Authors Neophytos Charalambides, Mert Pilanci, Alfred Hero

Publication date 19 November 2020

Published in arXiv

Mathematics Subject Classification ID

Numerical approximation and computational geometry (primarily algorithms) (65Dxx) Numerical linear algebra (65Fxx)

arXiv classification

cs.ITcs.NAmath.ITmath.NA

Abstract: One of the most common, but at the same time expensive operations in linear algebra, is multiplying two matrices $A$ and $B$. With the rapid development of machine learning and increases in data volume, performing fast matrix intensive multiplications has become a major hurdle. Two different approaches to overcoming this issue are, 1) to approximate the product; and 2) to perform the multiplication distributively. A extit{$CR$-multiplication} is an approximation where columns and rows of $A$ and $B$ are respectively sampled with replacement. In the distributed setting, multiple workers perform matrix multiplication subtasks in parallel. Some of the workers may be stragglers, meaning they do not complete their task in time. We present a novel extit{approximate weighted $CR$ coded matrix multiplication} scheme, that achieves improved performance for distributed matrix multiplication.

Cited in

(1)

• Approximate Matrix Multiplication through Joint Leverage Score Sampling

This page was built for publication: Approximate Weighted $CR$ Coded Matrix Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354092)