Random Khatri-Rao-Product Codes for Numerically-Stable Distributed Matrix Multiplication Academic Article

abstract

• We propose a class of codes called random Khatri-Rao-Product (RKRP) codes for distributed matrix multiplication in the presence of stragglers. The main advantage of the proposed codes is that decoding of RKRP codes is highly numerically stable in comparison to decoding of Polynomial codes and decoding of the recently proposed OrthoPoly codes. We show that RKRP codes are maximum distance separable with probability 1. The communication cost and encoding complexity for RKRP codes are identical to that of OrthoPoly codes and Polynomial codes and the average decoding complexity of RKRP codes is lower than that of OrthoPoly codes. Numerical results show that the average relative $L_2$-norm of the reconstruction error for RKRP codes is substantially better than that of OrthoPoly codes.

authors

• Narayanan, Krishna

published proceedings

• 2019 57TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON)

author list (cited authors)

• Subramaniam, A. M., Heidarzadeh, A., & Narayanan, K. R.

citation count

• 25

complete list of authors

• Subramaniam, Adarsh M||Heidarzadeh, Anoosheh||Narayanan, Krishna R

publication date

• January 2019

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• n2474-0195ISSN  Journal

keywords

• Cs.it
• Math.it

Digital Object Identifier (DOI)

• 10.1109/allerton.2019.8919859

start page

• 253

end page

• 259

volume

• 00

URL

• http://dx.doi.org/10.1109/allerton.2019.8919859