Iterative matrix inversion with $L^\infty$ norm

Question

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$?

Answer 1

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.

Answer 2

Complementing Suvrit's answer, from chapter 6 of Boyd & Vandenberghe:

---

---

Answer 3

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.