0.6 Linear phase l_p filter design  (Page 2/4)

Since $A\left(\omega \right)$ is a real continuous function as defined by [link] , one can write the linear phase $l_p$ design problem as follows

where $a$ relates to $h$ by considering the symmetry properties outlined in [link] . Note that the two objects from the objective function inside the $l_p$ norm are real. By sampling [link] one can write the design problem as follows

or

where $D_k$ is the $k$ -th element of the vector $D$ representing the sampled desired frequency response $D\left({\omega }_k\right)$ , and $C_k$ is the $k$ -th row of the trigonometric kernel matrix as defined by [link] .

One can apply the basic IRLS approach described in [link] to solve [link] by posing this problem as a weighted least squares one:

The main issue becomes iteratively finding suitable weights $w$ for [link] so that the algorithm converges to the optimal solution $a^{\star }$ of the $l_p$ problem [link] . Existence of adequate weights is guaranteed by Theorem [link] as presented in [link] ; finding these optimal weights is indeed the difficult part. Clearly a reasonable choice for $w$ is that which turns [link] into [link] , namely

Therefore the basic IRLS algorithm for problem [link] would be:

1. Initialize the weights $w_0$ (a reasonable choice is to make them all equal to one).
2. At the $i$ -th iteration the solution is given by
   $$a_{i+1}={\left[{\mathbf{C}}^T{\mathbf{W}}_i^T{\mathbf{W}}_i\mathbf{C}\right]}^{-1}{\mathbf{C}}^T{\mathbf{W}}_i^T{\mathbf{W}}_{i}D$$
3. Update the weights with
   $$w_{i+1}={|D-\mathbf{C}{a}_{i+1}|}^{p-2}$$
4. Repeat the last steps until convergence is reached.

It is important to note from Appendix [link] that ${\mathbf{W}}_i=\text{diag}\left(\sqrt{w_i}\right)$ . In practice it has been found that this approach has practical defficiencies, since the inversion required by [link] often leads to an ill-posed problem and, in most cases, convergence is not achieved.

As mentioned before, the basic IRLS method has drawbacks that make it unsuitable for practical implementations. Charles Lawson considered a version of this algorithm applied to the solution of $l_{\infty }$ problems (for details refer to [link] ). His method has linear convergence and is prone to problems with proportionately small residuals that could lead to zero weights and the need for restarting the algorithm. In the context of $l_p$ optimization, Rice and Usow [link] built upon Lawson's method by adapting it to $l_p$ problems. Like Lawson's methods, the algorithm by Rice and Usow updates the weights in a multiplicative manner; their method shares similar drawbacks with Lawson's. Rice and Usow defined

where

and

and follow the basic algorithm.

L. A. Karlovitz realized the computational problems associated with the basic IRLS method and improved on it by partially updating the filter coefficient vector. He defines

and uses $\widehat{a}$ in

where $\lambda \in [0,1]$ is a partial step parameter that must be adjusted at each iteration. Karlovitz's method [link] has been shown to converge globally for even values of $p$ (where $2\le p<\infty$ ). In practice, convergence problems have been found even under such assumptions. Karlovitz proposed the use of line searches to find the optimal value of $\lambda$ at each iteration, which basically creates an independent optimization problem nested inside each iteration of the IRLS algorithm. While computationally this search process for the optimal $\lambda$ makes Karlovitz's method impractical, his work indicates the feasibility of IRLS methods and proves that partial updating indeed overcomes some of the problems in the basic IRLS method. Furthermore, Karlovitz's method is the first one to depart from a multiplicative updating of the weights in favor of an additive updating on the filter coefficients. In this way some of the problems in the Lawson-Rice-Usow approach are overcome, especially the need for restarting the algorithm.