The fast subsampled-updating fast Newton transversal filter (FSU FNTF) algorithm for adaptive filtering

The fast Newton transversal filter (FNTF) algorithm starts from the recursi ve least-squares algorithm for adapting a finite impulse response filter. T he FNTF algorithm approximates the Kalman gain by replacing the sample cova riance matrix inverse by a banded matrix of total bandwidth 2M + 1 (AR(M) a ssumption for the input signal). In this algorithm, the approximate Kalman gain can still be computed using an exact recursion that involves the predi ction parts of two fast transversal filter (FTF) algorithms of order M. We introduce the subsampled updating (SU) approach in which the FNTF filter we ights and the Kalman gain are provided at a subsampled rate, say every L sa mples. Because of its low computational complexity, the prediction part of the FNTF algorithm is kept as such, A Schur type procedure is used to compu te various filter outputs at the intermediate time instants, while some pro ducts of vectors with Toeplitz matrices are carried out with the FFT. This leads to the fast subsampled-updating FNTF (FSU FNTF) algorithm, an algorit hm that is mathematically equivalent to the FNTF algorithm in the sense tha t exactly the same filter output is produced. However, it shows a significa ntly smaller computational complexity for large filter lengths at the expan se of some relatively small delay, The FSU FNTF algorithm (like the FNTF al gorithm) has good convergence and tracking properties. This renders the FSU FNTF algorithm very interesting for applications such as acoustic echo can cellation.