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

S. W. Kahng built upon the findings by Karlovitz by considering the process of finding an adequate $\lambda$ for partial updating. He applied Newton-Raphson's method to this problem and proposed a closed form solution for $\lambda$ , given by

resulting in

The rest of Kahng's algorithm follows Karlovitz's approach. However, since $\lambda$ is fixed, there is no need to perform the linear search at each iteration. Kahng's method has an added benefit: since it uses Newton's method to find $\lambda$ , the algorithm tends to converge much faster than previous approaches. It has indeed been shown to converge quadratically. However, Newton-Raphson-based algorithms are not guaranteed to converge globally unless at some point the existing solution lies close enough to the solution, within their radius of convergence [link] . Fletcher, Grant and Hebden [link] derived the same results independently.

Burrus, Barreto and Selesnick [link] , [link] , [link] modified Kahng's methods in several important ways in order to improve on their initial and final convergence rates and the method's stability (we refer to this method as BBS). The first improvement is analogous to a homotopy [link] . Up to this point all efforts in $l_p$ filter design attempted to solve the actual $l_p$ problem from the first iteration. In general there is no reason to believe that an initial guess derived from an unweighted $l_2$ formulation (that is, the $l_2$ design that one would get by setting $w_0=\widehat{1}$ ) will look in any way similar to the actual $l_p$ solution that one is interested in. However it is known that there exists a continuity of $l_p$ solutions for $1<p<\infty$ . In other words, if $a_2^{\star }$ is the optimal $l_2$ solution, there exists a $p$ for which the optimal $l_p$ solution $a_p^{\star }$ is arbitrarily close to $a_2^{\star }$ ; that is, for a given $\delta >0$

This fact allows anyone to gradually move from an $l_p$ solution to an $l_q$ solution.

To accelerate initial convergence, the BBS method of Burrus et al. initially solves for $l_2$ by setting $p_0=2$ and then sets $p_i=\sigma ·p_{i-1}$ , where $\sigma$ is a convergence parameter defined by $1\le \sigma \le 2$ . Therefore at the $i$ -th iteration

where $p_{des}$ corresponds to the desired $l_p$ solution. The implementation of each iteration follows Karlovitz's method with Kahng's choice of $\lambda$ , using the particular selection of $p$ given by [link] .

To summarize, define the class of IRLS algorithms as follows: after $i$ iterations, given a vector $a_i$ the IRLS iteration requires two steps,

1. Find $w_i=f\left(a_i\right)$
2. Find $a_{i+1}=g(w_i,a_i)$

The following is a summary of the IRLS-based algorithms discussed so far and their corresponding updating functions:

1. Basic IRLS algorithm.
   • $w_i={|D-\mathbf{C}{a}_i|}^{p-2}$
   • ${\mathbf{W}}_i=\text{diag}\left(\sqrt{w_i}\right)$
   • $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$
2. Rice-Usow-Lawson (RUL) method
   • $w_i=w_{i-1}^{\alpha }{|D-\mathbf{C}{a}_i|}^{\frac{\alpha }{2\gamma }}$
   • ${\mathbf{W}}_i=\text{diag}\left(w_i\right)$
   • $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$
   • $\alpha =\frac{\gamma (p-2)}{\gamma (p-2)+1}$
   • $\gamma$ constant
3. Karlovitz' method
   • $w_i={|D-\mathbf{C}{a}_i|}^{p-2}$
   • ${\mathbf{W}}_i=\text{diag}\left(\sqrt{w_i}\right)$
   • $a_{i+1}=\lambda {\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+(1-\lambda )a_i$
   • $\lambda$ constant
4. Kahng's method
   • $w_i={|D-\mathbf{C}{a}_i|}^{p-2}$
   • ${\mathbf{W}}_i=\text{diag}\left(\sqrt{w_i}\right)$
   • $a_{i+1}=\left(\frac{1}{p-1}\right){\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+\left(\frac{p-2}{p-1}\right)a_i$
5. BBS method
   • $p_i=\text{min}(p_{des},\sigma ·p_{i-1})$
   • $w_i={|D-\mathbf{C}{a}_i|}^{p_i-2}$
   • ${\mathbf{W}}_i=\text{diag}\left(\sqrt{w_i}\right)$
   • $a_{i+1}=\left(\frac{1}{p_i-1}\right){\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+\left(\frac{p_i-2}{p_i-1}\right)a_i$
   • $\sigma$ constant

Modified adaptive Irls algorithm

Much of the performance of a method is based upon whether it can actually converge given a certain error measure. In the case of the methods described above, both convergence rate and stability play an important role in their performance. Both Karlovitz and RUL methods are supposed to converge linearly, while Kahng's and the BBS methods converge quadratically, since they both use a Newton-based additive update of the weights.