Solving Dense Linear Systems Faster Than via Preconditioning

Michał Dereziński, Jiaming Yang

We give a stochastic optimization algorithm that solves a dense $n\times n$ real-valued linear system $Ax=b$, returning $\tilde{x}$ such that $\Vert A\tilde{x}-b\Vert \le \epsilon \Vert b\Vert$ in time: $…