Fast Approximate Matrix Multiplication by Solving Linear Systems

In this paper, we present novel deterministic algorithms for multiplying two n × n matrices approximately. Given two matrices A,B we return a matrix C' which is an 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 tildeO(n2) 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 absolute error w.r.t. Frobenius norm.