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

The idea of using an IRLS algorithm to achieve a Chebyshev or $L_{\infty }$ approximation seems to have been first developed by Lawson [link] and extended to $L_p$ by Rice and Usow [link] , [link] . The basic IRLS method for $L_p$ was given by Karlovitz [link] and extended by Chalmers, et. al. [link] , Bani and Chalmers [link] , and Watson [link] . Independently, Fletcher, Grant and Hebden [link] developed a similar form of IRLS but based on Newton's method and Kahng [link] did likewise as an extension of Lawson's algorithm. Others analyzed and extended this work [link] , [link] , [link] , [link] . Special analysis has been made for $1\le p<2$ by [link] , [link] , [link] , [link] , [link] , [link] , [link] and for $p=\infty$ by [link] , [link] , [link] , [link] , [link] , [link] . Relations to the Remez exchange algorithm [link] , [link] were suggested by [link] , to homotopy [link] by [link] , and to Karmarkar's linear programming algorithm [link] by [link] , [link] . Applications of Lawson's algorithm to complex Chebyshev approximation in FIR filter design have been made in [link] , [link] , [link] , [link] and to 2-D filter design in [link] . Reference [link] indicates further results may be forthcoming. Application to array design can be found in [link] and to statistics in [link] .

This paper unifies and extends the IRLS techniques and applies them to the design of FIR digital filters. It develops a framework that relates allof the above referenced work and shows them to be variations of a basic IRLS method modified so as to control convergence. In particular, wegeneralize the work of Rice and Usow on Lawson's algorithm and explain why its asymptotic convergence is slow.

The main contribution here is a new robust IRLS method [link] , [link] that combines an improved convergence acceleration scheme and a Newton based method. This gives a very efficient and versatilefilter design algorithm that performs significantly better than the Rice-Usow-Lawson algorithm or any of the other IRLS schemes. Both theinitial and asymptotic convergence behavior of the new algorithm is examined and the reason for occasional slow convergence of this and allother IRLS methods is discovered.

We then show that the new IRLS method allows the use of $p$ as a function of frequency to achieve different error criteria in the pass and stopbandsof a filter. Therefore, this algorithm can be applied to solve the constrained $L_p$ approximation problem. Initial results of applications to the complex and two-dimensional filter design problem are presented.

Although the traditional IRLS methods were sometimes slower than competing approaches, the results of this paper and the availability of fast moderndesktop computers make them practical now and allow exploitation of their greater flexibility and generality.

Minimum squared error approximations

Various approximation methods can be developed by considering different definitions of norm or error measure. Commonly used definitions are $L_1$ , $L_2$ , and Chebyshev or $L_{\infty }$ . Using the $L_2$ norm, gives the scalar error to minimize

or in matrix notation using [link] , the error or residual vector is defined by

giving the scalar error of [link] as

This can be minimized by solution of the normal equations [link] , [link] , [link]

The weighted squared error defined by

or, in matrix notation using [link] and [link] causes [link] to become