A fast QR/Frequency-domain RLS adaptive filter

There has been considerable recent interest in QR factorization for recursive solution to the least-squares adaptive-filtering problem, mainly because of the good numerical properties of QR factorizations. Early work by Gentleman and Kung (1981) and McWhirter (1983) has produced triangular systolic arrays of N²/2 processors that solve the Recursive Least Squares (RLS) adaptive-filtering problem (where N is the size of the adaptive filter). Here, we introduce a more computationally efficient solution to the QR RLS problem that requires only O(N) computations per time update, when the input has the usual shift-invariant property. Thus, computation and implementation requirements are reduced by an order of magnitude. The new algorithms are based on a structure that is neither a transversal filter nor a lattice, but can be best characterized by a functionally equivalent set of parameters that represent the time-varying "least-squares frequency transforms" of the input sequences. Numerical stability can be insured by implementing computations as 2 × 2 orthogonal (Givens) rotations.