0.3 Approximation with other norms and error measures  (Page 3/3)

and finding $\mathbf{x}$ to minimizing this p-norm while satisfying $\mathbf{Ax}=\mathbf{b}$ .

It has been shown this is equivalent to solving a least weighted norm problem for specific weights.

The development follows the same arguments as in the previous section but using the formula [link] , [link] derived in [link]

with the weights, $w\left(n\right)$ , being the diagonal of the matrix, $\mathbf{W}$ , in the iterative algorithm to give the minimum weighted solution norm in the same way as [link] gives the minimum weighted equation error.

A Matlab program that implements these ideas applied to our pseudoinverse problem with more unknowns than equations (case 3a) is:

This approach is useful in sparse signal processing and for frame representation.

The chebyshev, minimax, or $L_{\infty }$ Appriximation

The Chebyshev optimization problem minimizes the maximum error:

This is particularly important in filter design. The Remez exchange algorithm applied to filter design as the Parks-McClellan algorithm is very efficient [link] . An interesting result is the limit of an ${\left|\right|\mathbf{x}\left|\right|}_p$ optimization as $p\to \infty$ is the Chebyshev optimal solution. So, the Chebyshev optimal, the minimax optimal, and the $L_{\infty }$ optimal are all the same [link] , [link] .

A particularly powerful theorem which characterizes a solution to $\mathbf{Ax}=\mathbf{b}$ is given by Cheney [link] in Chapter 2 of his book:

• A Characterization Theorem: For an $M$ by $N$ real matrix, $\mathbf{A}$ with $M>N$ , every minimax solution $\mathbf{x}$ is a minimax solution of an appropriate $N+1$ subsystem of the $M$ equations. This optimal minimax solution will have at least $N+1$ equal magnitude errors and they will be larger than any of the errors of the other equations.

This is a powerful statement saying an optimal minimax solution will have out of $M$ , at least $N+1$ maximum magnitude errors and they are the minimum size possible. What this theorem doesn't state is which of the $M$ equations are the $N+1$ appropriate ones. Cheney develops an algorithm based on this theorem which finds these equations and exactly calculates this optimal solution in a finite numberof steps. He shows how this can be combined with the minimum ${\left|\right|\mathbf{e}\left|\right|}_p$ using a large $p$ , to make an efficient solver for a minimax or Chebyshev solution.

This theorem is similar to the Alternation Theorem [link] but more general and, therefore, somewhat more difficult to implement.

The $L_1$ Approximation and sparsity

The sparsity optimization is to minimize the number of non-zero terms in a vector. A “pseudonorm", ${\left|\right|\mathbf{x}\left|\right|}_0$ , is sometimes used to denote a measure of sparsity. This is not convex, so is not really a norm but the convex (in the limit) norm ${\left|\right|\mathbf{x}\left|\right|}_1$ is close enough to the ${\left|\right|\mathbf{x}\left|\right|}_0$ to give the same sparsity of solution [link] . Finding a sparse solution is not easy but interative reweighted least squares (IRLS) [link] , [link] , weighted norms [link] , [link] , and a somewhat recent result is called Basis Pursuit [link] , [link] are possibilities.

This approximation is often used with an underdetermined set of equations (Case 3a) to obtain a sparse solution $\mathbf{x}$ .

Using the IRLS algorithm to minimize the $l_p$ equation error often gives a sparse error if one exists. Using the algorithm in the illustrated Matlab program with $p=1.1$ on the problem in Cheney [link] gives a zero error in equation 4 while using no larger $p$ gives any zeros.