0.3 Approximation with other norms and error measures

Approximation with other norms and error measures

Most of the discussion about the approximate solutions to $\mathbf{Ax}=\mathbf{b}$ are about the result of minimizing the $l_2$ equation error $\left|\right|Ax-{b\left|\right|}_2$ and/or the $l_2$ norm of the solution ${\left|\right|\mathbf{x}\left|\right|}_2$ because in some cases that can be done by analytic formulas and also because the $l_2$ norm has a energy interpretation. However, both the $l_1$ and the $l_{\infty }$ [link] have well known applications that are important [link] , [link] and the more general $l_p$ error is remarkably flexible [link] , [link] . Donoho has shown [link] that $l_1$ optimization gives essentially the same sparsity as the true sparsity measure in $l_0$ .

In some cases, one uses a different norm for the minimization of the equation error than the one for minimization of the solution norm. And inother cases, one minimizes a weighted error to emphasize some equations relative to others [link] . A modification allows minimizing according to one norm for one set of equations and another for a different set. A more generalerror measure than a norm can be used which used a polynomial error [link] which does not satisfy the scaling requirement of a norm, but is convex. One could even use theso-called $l_p$ norm for $1>p>0$ which is not even convex but is an interesting tool for obtaining sparse solutions.

Note from the figure how the $l_{10}$ norm puts a large penalty on large errors. This gives a Chebyshev-like solution. The $l_{0.2}$ norm puts a large penalty on small errors making them tend to zero. This (and the $l_1$ norm) give a sparse solution.

The $L_p$ Norm approximation

The IRLS (iterative reweighted least squares) algorithm allows an iterative algorithm to be built from the analytical solutions of the weighted least squareswith an iterative reweighting to converge to the optimal $l_p$ approximation [link] .

The overdetermined system with more equations than unknowns

If one poses the $l_p$ approximation problem in solving an overdetermined set of equations (case 2 from Chapter 3), it comes from defining the equation error vector

and minimizing the p-norm

or

neither of which can we minimize easily. However, we do have formulas [link] to find the minimum of the weighted squared error

one of which is derived in [link] , equation [link] and is

where $\mathbf{W}$ is a diagonal matrix of the error weights, $w_n$ . From this, we propose the iterative reweighted least squared (IRLS) error algorithmwhich starts with unity weighting, $\mathbf{W}=\mathbf{I}$ , solves for an initial $\mathbf{x}$ with [link] , calculates a new error from [link] , which is then used to set a new weighting matrix $\mathbf{W}$

to be used in the next iteration of [link] . Using this, we find a new solution $\mathbf{x}$ and repeat until convergence (if it happens!).

This core idea has been repeatedly proposed and developed in different application areas over the past 50 years with a variety of success [link] . Used in this basic form, it reliably converges for $2<p<3$ . In 1990, a modification was made to partially update the solution each iteration with