ECCC-Report TR14-117https://eccc.weizmann.ac.il/report/2014/117Comments and Revisions published for TR14-117en-usMon, 23 Feb 2015 14:04:03 +0200
Comment 1
| Fast Approximate Matrix Multiplication in ECCC TR14-117 Fails to Converge |
Kevin Kowalski,
Dieter van Melkebeek
https://eccc.weizmann.ac.il/report/2014/117#comment1ECCC TR14-117 presents an efficient iterative algorithm that purportedly computes an approximation to the product of two $n \times n$ matrices. On this comment we show that, in fact, the algorithm converges to a different matrix than the product matrix.Mon, 23 Feb 2015 14:04:03 +0200https://eccc.weizmann.ac.il/report/2014/117#comment1
Paper TR14-117
| Fast Approximate Matrix Multiplication by Solving Linear Systems |
Shiva Manne,
Manjish Pal
https://eccc.weizmann.ac.il/report/2014/117In this paper, we present novel deterministic algorithms for multiplying two $n \times n$ matrices approximately. Given two matrices $A,B$ we return a matrix $C'$ which is an \emph{approximation} to $C = AB$. We consider the notion of approximate matrix multiplication in which the objective is to make the Frobenius norm of the error matrix $C-C'$ arbitrarily small. Our main contribution is to first reduce the matrix multiplication problem to solving a set of linear equations and then use standard techniques to find an approximate solution to that system in $\tilde{O}(n^2)$ time. To the best of our knowledge this the first examination into designing quadratic time deterministic algorithms for approximate matrix multiplication which guarantee arbitrarily low \emph{absolute error} w.r.t. Frobenius norm.Sun, 07 Sep 2014 08:25:58 +0300https://eccc.weizmann.ac.il/report/2014/117