K. Maouche et Dtm. Slock, Fast subsampled-updating stabilized fast transversal filter (FSU SFTF) RLSalgorithm for adaptive filtering, IEEE SIGNAL, 48(8), 2000, pp. 2248-2257
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.