ε-Approximate Coded Matrix Multiplication is Nearly Twice as Efficient as Exact Multiplication

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of P computation nodes where each node stores 1/m of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with ε relative error from any m of the P nodes for any ε > 0. We obtain this result through a careful specialization of MatDot codes --- a class of matrix multiplication codes previously developed in the context of exact recovery ε=0). Since prior results showed that MatDot codes achieve the best exact recovery threshold for a class of linear coding schemes, our result shows that allowing for mild approximations leads to a system that is nearly twice as efficient as exact reconstruction. For Entangled-Poly codes --- which are generalizations of MatDot codes --- we show that approximation reduces the recovery threshold from p^2 q + q -1 to p^2q, when the input matrices A, B are split respectively in to a p *q and q * p grids of equal-sized submatrices.