Approximate Solutions of Linear Systems at a Universal Rate

Understand

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 $\|Ay - b\|$ is small.
• We prove that for all $0< \varepsilon <1 $ there is a composition of $k$ orthogonal projections onto the $n$ hyperplanes generated by the rows of $A$, where $$k \leq 2 \log\left(\frac{1}{\varepsilon} \right) \frac{ n}{ \varepsilon^{2}}$$ which maps the origin to a vector $y\in \mathbb{R}^n$ satisfying $\| A y - Ax\| \leq \varepsilon \cdot \|A\| \cdot \| x\|$.
• We note that this upper bound on $k$ is independent of the matrix $A$.