The fast subsampled-updating stabilized fast transversal filter (FSU SFTF) RLS algorithm

We present a new fast algorithm for Recursive Least-Squares (RLS) adaptive filtering that uses displacement structure and subsampled updating. The FSU SFTF algorithm is based on the Stabilized Fast Transversal Filter (SFTF) algorithm, which is a numerically stabilized version of the classical FTF algorithm. The FTF algorithm exploits the shift invariance that is present in the RLS adaptation of a FIR lter. The FTF algorithm is in essence the application of a rotation matrix to a set of lters and in that respect resembles the Levinson algorithm. In the subsampled updating approach, we accumulate the rotation matrices over some time interval before applying them to the lters. It turns out that the successive rotation matrices themselves can be obtained from a Schur type algorithm which, once properly initialized, does not require inner products. The various convolutions that thus appear in the algorithm are done using the Fast Fourier Transform (FFT). For relatively long lters, the computational complexity of the new algorithm is smaller than the one of the well-known LMS algorithm, rendering it especially suitable for applications such as acoustic echo cancellation.