THE FAST ADAPTIVE ROTORS RLS ALGORITHM

This paper introduces a fast algorithm (requires order iV computations instead of N2) for implementation of the QR-RLS adaptive filter. This fast adaptive rotors (FAR) algorithm can be implemented with a pipelined array of processors called “ROTOR's” and “CISOR's.” The ROTOR's compute 2x2 orthogonal (Givens) rotations, while the CISOR's compute the cosines and sines of the angles used in the ROTOR's. The algorithm requires 4N ROTOR's and 2N CISOR's at each iteration to compute the solution to the RLS problem. The algorithm is also numerically stable. The FAR algorithm is derived using a single generic updating formula for orthogonal matrices, which is introduced and derived within. While the generic updating formula is reminiscent of previous fast transversal filters and fast lattice algorithms, the set of internal propagated adaptive filter quantities is entirely different and constitutes yet another complete characterization of the RLS covariance and the important forward, backward, and pinning estimation problems. © 1990 IEEE