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

The fast Newton transversal filter (FNTF) algorithm starts from the recursive least-squares algorithm for adapting a finite impulse response filter. The FNTF algorithm approximates the Kalman gain by replacing the sample covariance matrix inverse by a banded matrix of total bandwidth 2M+1 (AR(M) assumption for the input signal). In this algorithm, the approximate Kalman gain can still be computed using an exact recursion that involves the prediction parts of two fast transversal filter (FTF) algorithms of order M. We introduce the subsampled updating (SU) approach in which the FNTF filter weights and the Kalman gain are provided at a subsampled rate, say every L samples. Because of its low computational complexity, the prediction part of the FNTF algorithm is kept as such. A Schur type procedure is used to compute various filter outputs at the intermediate time instants, while some products of vectors with Toeplitz matrices are carried out with the FFT. This leads to the fast subsampled-updating FNTF (FSU FNTF) algorithm, an algorithm that is mathematically equivalent to the FNTF algorithm in the sense that exactly the same filter output is produced. However it shows a significantly smaller computational complexity for large filter lengths at the expense of some relatively small delay. The FSU FNTF algorithm (like the FNTF algorithm) has good convergence and tracking properties. This renders the FSU FNTF algorithm very interesting for applications such as acoustic echo cancellation.