Fast subsampled-updating stabilized fast transversal filter (FSU SFTF) RLSalgorithm for adaptive filtering

We present a new, doubly fast algorithm for recursive least-squares (RLS) a daptive filtering that uses displacement structure and subsampled-updating. The fast subsampled-updating stabilized fast transversal filter (FSU SFTF) algorithm is mathematically equivalent to the classical fast transversal f ilter (FTF) algorithm. The FTF algorithm exploits the shift invariance that is present in the RLS adaptation of an FIR filter. The FTF algorithm is in essence the application of a rotation matrix to a set of filters and in th at respect resembles the Levinson algorithm. In the subsampled-updating app roach, we accumulate the rotation matrices over some time interval before a pplying them to the filters, it turns out that the successive rotation matr ices themselves can be obtained from a Schur-type algorithm that, once prop erly initialized, does not require inner products. The various convolutions that appear in the algorithm are done using the fast Fourier transform (FF T). The resulting algorithm is doubly fast since it exploits FTF and FFT's, The roundoff error propagation in the FSU SFTF algorithm is identical to t hat in the SFTF algorithm: a numerically stabilized version of the classica l FTF algorithm. The roundoff error generation, on the other hand, seems so mewhat smaller. For relatively long filters, the computational complexity o f the new algorithm is smaller than that of the well-known LMS algorithm, r endering it especially suitable for applications such as acoustic echo canc ellation.