FAST RECURSIVE LEAST-SQUARES ADAPTIVE FILTERING BY FAST FOURIER TRANSFORM-BASED CONJUGATE-GRADIENT ITERATIONS

Recursive least squares (RLS) estimations are used extensively in many signal processing and control applications. In this paper we consider RLS with sliding data windows involving multiple (rank k) updating an d downdating computations. The least squares estimator can be found by solving a near-Toeplitz matrix system at each step. Our approach is t o employ the preconditioned conjugate gradient method with circulant p reconditioners to solve such systems. Here rye iterate in the time dom ain (using Toeplitz matrix-vector multiplications) and precondition in the Fourier domain, so that the fast Fourier transform (FFT) is used throughout the computations. The circulant preconditioners are derived from the spectral properties of the given input stochastic process. W hen the input stochastic process is stationary, we prove that with pro bability 1, the spectrum of the preconditioned system is clustered aro und 1 and the method converges superlinearly provided that a sufficien t number of data samples are taken, i.e., the length of the sliding wi ndow is sufficiently long. In the case of point-processing (k = 1), ou r method requires O(n log n) operations per adaptive filter input wher e n is the number of least squares estimators. In the case of block-pr ocessing (k greater than or equal to n), our method requires only O(lo g n) operations per adaptive filter input. A simple method is given fo r tracking the spectral condition number of the data matrix at each st ep, and numerical experiments are reported in order to illustrate the effectiveness of our FFT-based method for fast RLS filtering.