Matrix multiplication is a fundamental building block for large scale computer computations. There has been significant recent interest in using coding to speed up distributed computation.
Matrix multiplication is a fundamental building block for large scale
computations arising in various applications, including machine learning. There
has been significant recent interest in using coding to speed up distributed
matrix multiplication, that are robust to stragglers (i.e., machines that may
perform slower computations). In many scenarios, instead of exact computation,
approximate matrix multiplication, i.e., allowing for a tolerable error is also
sufficient. Such approximate schemes make use of randomization techniques to
speed up the computation process. In this paper, we initiate the study of
approximate coded matrix multiplication, and investigate the joint synergies
offered by randomization and coding. Specifically, we propose two coded
randomized sampling schemes that use (a) codes to achieve a desired recovery
threshold and (b) random sampling to obtain approximation of the matrix
multiplication. Tradeoffs between the recovery threshold and approximation
error obtained through random sampling are investigated for a class of coded
matrix multiplication schemes.