FSU RLS : a fast recursive least squares algorithm based on displacement structure and the FFT

We present two new fast algorithms for Recursive Least-Squares (RLS) adaptive filtering. These algorithms are especially suited for adapting very long filters such as in the acoustic echo cancellation problem. For the FSU RLS, the starting point is to introduce subsampled updating (SU) in the RLS algorithm. In the SU RLS algorithm, the Kalman gain and the likelihood variable are matrices. Due to the shift invariance of the adaptive FIR filtering problem, these matrices exhibit a low displacement rank. This leads to a representation of these quantities in terms of sums of products of triangular Toeplitz matrices. Finally, the product of these Toeplitz matrices with a vector can be computed efficiently by using the Fast Fourier Transform (FFT). The second algorithm which is the FSU FTF apply the same idea to the FTF algorithm. It uses a Schur procedure to compute the rotation matrix that allows to adapt the filter and use also the FFT. Its computational complexity is of the same order as the FSU RLS.