# Fast Approximate Matrix Multiplication by Solving Linear Systems

Preprint · Shiva Manne, Manjish Pal

- Archive id: arxiv:1408.4230
- Published: 2014-08-19
- arXiv: https://arxiv.org/abs/1408.4230
- Source URL: https://arxiv.org/abs/1408.4230
- PDF: https://arxiv.org/pdf/1408.4230
- Provenance: arxiv

## Abstract

In 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.