ϵ-Approximate Coded Matrix Multiplication Is Nearly Twice as Efficient as Exact Multiplication
Haewon Jeong, Ateet Devulapalli, Viveck R. Cadambe, Flávio P. Calmon · IEEE Journal on Selected Areas in Information Theory · 2021
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$\epsilon $relative error from any$m$of the$P$nodes for any$\epsilon > 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 ($\epsilon =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^{2}q$, when the input matrices A, B are split respectively in to a$p \times q$and$q \times p$grids of equal-sized submatrices.