A Simple Complexity Lower Bound for Solving $Ax=b$

Ohad Shamir

In this note, we provide a short and direct proof that approximately solving $Ax=b$ to relative error $\epsilon$, where $A$ has condition number $\kappa$ and unrestricted dimension,…