Fast Algorithms for Iterative Design of Linear Filters and Adaptive Polynomial Filtering

This thesis proposes algorithms to be utilized for iterative design of linear filters and for adaptive polynomial filtering. The goal is to improve existing algorithms in terms of filtering performance, time and complexity requirements. First, a family of fast algorithms suitable for adaptive polynomial filtering, namely LS-LMS algorithm and its square root variants, is introduced and its connection with the family of RLS algorithms is analyzed. The algorithms are derived by combining the triangularization and backsolving steps of QR-RLS algorithm. In the derivation we allow a modification of the cost function in order to decrease the complexity of the algorithm from O(M^2) to O(M), where M is the number of filter parameters. Second, adaptive filtering algorithms are proposed for the problem of acoustic echo control in the case of strong acoustic distortion in the loudspeaker that decreases the echo attenuation obtained using adaptive linear filtering algorithms in echo cancelers. Several existing algorithms were tested using both linear and homogeneous Volterra filters, but their performance was not found satisfactory either in terms of performance or complexity. A polynomial preprocessor followed by a linear filter was found to perform well when the preprocessor was adapted by the robust, but computationally demanding, QR-RLS algorithm and the linear part was adapted by the normalized LMS algorithm. Third, the problem of optimum energy compaction for FIR and IIR filters is addressed. The analytical method for optimum compaction FIR filter design is analyzed and shown to provide a very fast algorithm under certain conditions. For the design of optimum compaction IIR filters two new methods are proposed. The first design method operates with the numerator and the denominator in the causal part of the associated product filter, which are in turn optimized via iterative relaxations. The second method is similar, except that the angles of the poles are set to fixed values, situated at the transitions in the frequency representation of the corresponding ideal brickwall filter. Thus, the second method is faster than the first, and, moreover, it was observed that when the ideal brickwall filter does not have too many transitions, the second method provides filters with better performance. Both methods make use of semidefinite programming optimization using an appropriate parameterization of positive real polynomials. The last part of the thesis provides contributions to the frequency selective IIR filter design. The frequency response of the filter is fitted to an ideal frequency response by optimizing either a weighted sum of magnitude squares (least squares) criterion or a minimax (Chebyshev) criterion. For the least squares criterion a new convex stability domain is used and experimental evidence is given that the best designs are usually obtained with a multistage algorithm where three methods, Steiglitz-McBride, Gauss-Newton and classical descent, are used consecutively in that order. The result of multistage least squares IIR design is used to initialize the optimization procedure based on a Chebyshev criterion, for which a simplified iterative procedure is proposed. In the simplified procedure only the numerator is updated after initialization. The simplified procedure is compared experimentally with the complete procedure and the results show only very small differences in the criterion.