Iterative matrix inversion with $L^\infty$ norm The usual conjugate gradient type algorithms for iteratively finding the inverse of a matrix applied to a vector, $x = A^{-1} y$, works by minimizing $\|Ax - y\|^2$ where $\| \cdot \|$ is the $L^2$-norm. The stopping criterion is usually $\|Ax - y\| < \varepsilon \|y\|$ with some small $\varepsilon$.
Is there an efficient algorithm if I'm interested in the same problem but using the $L^p$-norm for the stopping criterion? 
I've actually found some papers with $1 \leq p \leq 2$, but I'd need large $p$, more precisely what I'm really interested in is the $L^\infty$-norm. Are there efficient algorithms for $L^\infty$?
 A: One approach is to solve the optimization problem:
\begin{equation*}
\min_x\quad \|Ax-y\|_\infty.
\end{equation*}
This is a nonsmooth optimization problem, but is amenable to a variety of scalable optimization techniques, for instance, Nesterov's smooth minimization of non-smooth functions. Of course, the above problem can also be cast as a linear program, and thus solved more accurately using interior point methods.
However, if you meant that you wish to minimize $\|Ax-y\|_2$, while ensuring that $\|Ax-y\|_\infty \le \delta\|y\|_\infty$, then you have at your hands a second order cone program, for which there are interior point methods, as well as other more scalable methods.
A: Complementing Suvrit's answer, from chapter 6 of Boyd & Vandenberghe:



A: As a shameless plug for my own work: As you want to use the $\infty$-norm as a stopping criterion, you may be interested in homotopy methods. For the sake of completeness, assume that you want to find sparse approximate solutions to $Ax=b$. You set a tolerance $\delta= \|b\|_\infty$ and see that $x_\delta = 0$ is the sparsest $x$ that solves $Ax=b$ up to the tolerance $\delta$ (in the $\infty$-norm). A homotopy method starts from this $x_\delta$ and $\delta$ and reduces the value of $\delta$ while keeping $x_\delta$ a solution of (in this case)
$$
\min_x \|x\|_1\quad\text{s.t.}\quad\|Ax-b\|_\infty\leq\delta.
$$
It can be shown that the path $\delta\mapsto x_\delta$ is piecewise linear and that one can calculate the whole path by solving a number of very small linear programs. On top of that, consecutive linear programs that have to be solved are very similar to that a specialized algorithm that takes this into account can be made faster than commercial LP solvers. We describe the method in the paper "A Primal-Dual Homotopy Algorithm for $\ell^1$-Minimization with $\ell^∞$-Constraints".
I suspect that a similar method could be derived for minimal 2-norm approximate solutions but I am not sure if the method could be made fast.
