The fast subsampled-updating fast newton transversal filter (FSU FNTF) algorithm for adaptive filtering based on a schur procedure and the FFT

The Fast Newton Transversal Filter (FNTF) algorithm starts from the Recursive Least-Squares algorithm for adapting an FIR filter of length N. 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 estimate and 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. A Schur type algorithm is used to compute various lter 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 which has a relatively low computational complexity for large N while presenting good convergence and tracking performances. This renders the FSU FNTF algorithm very interesting for applications such as acoustic echo cancellation.