Approximate Weighted C R Coded Matrix Multiplication
Authors:
- 6 June 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 5095-5099
Abstract
One of the most common operations in signal processing is matrix multiplication. However, it presents a major computational bottleneck when the matrix dimension is high, as can occur for large data size or feature dimension. Two different approaches to overcoming this bottleneck are: 1) low rank approximation of the matrix product; and 2) distributed computation. We propose a scheme that combines these two approaches. To enable distributed low rank approximation, we generalize the approximate matrix CR-multiplication to accommodate weighted block sampling, and we introduce a weighted coded matrix multiplication method. This results in novel approximate weighted CR coded matrix multiplication schemes, which achieve improved performance for distributed matrix multiplication and are robust to stragglers.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- On the Optimal Recovery Threshold of Coded Matrix MultiplicationIEEE Transactions on Information Theory, 2019
- Improving Distributed Gradient Descent Using Reed-Solomon Codes2018
- On the optimal recovery threshold of coded matrix multiplication2017
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- High-dimensional coded matrix multiplication2017
- Sketching as a Tool for Numerical Linear AlgebraFoundations and Trends® in Theoretical Computer Science, 2014
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a MatrixSIAM Journal on Computing, 2006
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix MultiplicationSIAM Journal on Computing, 2006
- Fast Monte-Carlo algorithms for approximate matrix multiplication2001
- Weighted Empirical Adaptive Variance Estimators for Correlated Data RegressionJournal of the Royal Statistical Society Series B: Statistical Methodology, 1999