CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication

DOI10.1109/TIT.2021.3068165zbMATH Open1476.68246arXiv1812.10460OpenAlexW3137779858WikidataQ114084342 ScholiaQ114084342MaRDI QIDQ5001784

Mohammad Ali Maddah-Ali, Tayyebeh Jahani-Nezhad

Publication date: 23 July 2021

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that we need to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count--sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count--sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count--sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes.

Full work available at URL: https://arxiv.org/abs/1812.10460

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Numerical algorithms for specific classes of architectures (65Y10) Computational aspects of data analysis and big data (68T09) Numerical methods for low-rank matrix approximation; matrix compression (65F55)