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

We present a new fast algorithm for Recursive Least-Squares (RLS) adaptive filtering that uses displacement structure and subsampled updating. The FSU FTF algorithm is based on the Fast Transversal Filter (FTF) algorithm, which exploits the shift invariance that is present in the RLS adaptation of a FIR filter. The FTF algorithm is in essence the application of a rotation matrix to a set of filters 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 filters. 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 filters, 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 coustic echo cancellation.