The fast subsampled-updating recursive least-squares (FSU RLS) algorithm for adaptive filtering based on displacement structure and the FFT

In this paper, we derive a new fast algorithm for Recursive Least-Squares (RLS) adaptive filtering. This algorithm is especially suited for adapting very long filters such as in the acoustic echo cancellation problem. 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 ltering 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).