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

Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

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 the master node needs 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. The proposed scheme provides an upper-bound on the recovery threshold as a function of the required accuracy of computation and the probability that the required accuracy can be violated. In addition, it provides an upper-bound on the recovery threshold for the case that the result of the multiplication is sparse, and the exact result is required.

Original languageEnglish (US)
Article number9383252
Pages (from-to)4185-4196
Number of pages12
JournalIEEE Transactions on Information Theory
Volume67
Issue number6
DOIs
StatePublished - Jun 2021
Externally publishedYes

Bibliographical note

Funding Information:
Manuscript received June 28, 2019; revised October 27, 2020; accepted February 7, 2021. Date of publication March 23, 2021; date of current version May 20, 2021. This work was supported by the Iran National Science Foundation (INSF) under Contract 98019168. This article was presented in part at the 2019 IEEE International Symposium on Information Theory (ISIT). (Corresponding author: Mohammad Ali Maddah-Ali.) The authors are with the Department of Electrical Engineering, Sharif University of Technology, Tehran 11365-11155, Iran (e-mail: tayyebeh.jahaninezhad@ee.sharif.edu; maddah_ali@sharif.edu). Communicated by E. Abbe, Associate Editor for Machine Learning.

Publisher Copyright:
© 1963-2012 IEEE.

Keywords

  • approximated matrix multiplication
  • coded computing
  • count-sketch
  • distributed computation
  • Matrix multiplication
  • straggler resistant computing

Fingerprint

Dive into the research topics of 'CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication'. Together they form a unique fingerprint.

Cite this