Approximate Solutions of Linear Systems at a Universal Rate

Abstract

Let $A\in {\mathbb{R}}^{n\times n}$ be invertible, $x\in {\mathbb{R}}^n$ unknown and $b=Ax$ given. We are interested in approximate solutions: vectors $y\in {\mathbb{R}}^n$ such that $\Vert Ay-b\Vert$ is small. We prove that for all $0<\epsilon <1$ there is a composition of $k$ orthogonal projections onto the $n$ hyperplanes generated by the rows of $A$, where $$k\le 2\log \left(\frac{1}{\epsilon }\right)\frac{n}{{\epsilon }^2}$$ which maps the origin to a vector $y\in {\mathbb{R}}^n$ satisfying $\Vert Ay-Ax\Vert \le \epsilon \cdot \Vert A\Vert \cdot \Vert x\Vert$. We note that this upper bound on $k$ is independent of the matrix $A$. This procedure is stable in the sense that $\Vert y\Vert \le 2\Vert x\Vert$. The existence proof is based on a probabilistically refined analysis of the Random Kaczmarz method which seems to achieve this rate when solving for $Ax=b$ with high likelihood.