2.5 Constrained approximation and mixed criteria  (Page 6/10)

which can be minimized by solving

with the normal equations

where $W$ is an $L$ by $L$ diagonal matrix with the weights $w_k$ from [link] along the diagonal. A more general formulation of the approximation simply requires $W^{T}W$ to be positive definite. Some authors define the weighted error in [link] using $w_k$ rather than $w_k^2$ . We use the latter to be consistent with the least squared error algorithms in Matlab [link] .

Solving [link] is a direct method of designing an FIR filter using a weighted least squared error approximation. To minimize the sum of thesquared error and get approximately the same result as minimizing the integral of the squared error, one must choose $L$ to be 3 to 10 or more times the length $L$ of the filter being designed.

Iterative algorithms to minimize theError

There is no simple direct method for finding the optimal approximation for any error power other than two. However, if the weighting coefficients $w_k$ as elements of $W$ in [link] could be set equal to the elements in $|A-A_d|$ , minimizing [link] would minimize the fourth power of $|A-A_d|$ . This cannot be done in one step because we need the solution to find the weights! We can, however, pose an iterative algorithm whichwill first solve the problem in [link] with no weights, then calculate the error vector $ϵ$ from [link] which will then be used to calculate the weights in [link] . At each stage of the iteration, the weights are updated from the previous error and the problem solved again.This process of successive approximations is called the iterative reweighted least squared error algorithm (IRLS).

The basic IRLS equations can also be derived by simply taking the gradient of the $p$ -error with respect to the filter coefficients $h$ or $a$ and setting it equal to zero [link] , [link] . These equations form the basis for the iterative algorithm.

If the algorithm is a contraction mapping [link] , the successive approximations will converge and the limit is the solution of the minimum $L_4$ approximation problem. If a general problem can be posed [link] , [link] , [link] as the solution of an equation in the form

a successive approximation algorithm can be proposed which iteratively calculates $x$ using

starting with some $x_0$ . The function $f(·)$ maps $x_m$ into $x_{m+1}$ and, if

${lim}_{m\to \infty }{x}_m=x_0$ where $x_0=f\left(x_0\right)$ , $x_0$ is the fixed point of the mapping and a solution to [link] . The trick is to find a mapping that solves the desired problem, converges, and converges fast.

By setting the weights in [link] equal to

the fixed point of a convergent algorithm minimizes

It has been shown [link] that weights always exist such that minimizing [link] also minimizes [link] . The problem is to find those weights efficiently.

Basic iterative reweighted least squares

The basic IRLS algorithm is started by initializing the weight matrix defined in [link] and [link] for unit weights with $W_0=I$ . Using these weights to start, the $m^{th}$ iteration solves [link] for the filter coefficients with

This is a formal statement of the operation. In practice one should not invert a matrix, one should use a sophisticated numerical method [link] to solve the overdetermined equations in [link] The error or residual vector [link] for the $m^{th}$ iteration is found by