Fast recursive least squares adaptive filtering by fast Fourier transform-based conjugate gradient iterations

• Published in: SIAM journal on scientific computing 1996-07, Vol.17 (4), p.920-941
• Main Authors: NG, M. K, PLEMMONS, R. J
• Format: Article
• Language: English
• Subjects: Abstract harmonic analysis; Algorithms; Exact sciences and technology; Fourier transforms; Mathematical analysis; Mathematics; Numerical analysis; Numerical analysis. Scientific computation; Numerical linear algebra; Sciences and techniques of general use; Signal processing; Spectrum analysis; Stochastic models
• ISSN: 1064-8275; 1095-7197
• DOI: 10.1137/0917060

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 and downdating computations. The least squares estimator can be found by solving a near-Toeplitz matrix system at each step. Our approach is to employ the preconditioned conjugate gradient method with circulant preconditioners to solve such systems. Here we iterate in the time domain (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. When the input stochastic process is stationary, we prove that with probability 1, the spectrum of the preconditioned system is clustered around 1 and the method converges superlinearly provided that a sufficient number of data samples are taken, i.e., the length of the sliding window is sufficiently long. In the case of point-processing $(k = 1)$, our method requires $O(n\log n)$ operations per adaptive filter input where $n$ is the number of least squares estimators. In the case of block-processing $(k \geqslant n)$, our method requires only $O(\log n)$ operations per adaptive filter input. A simple method is given for tracking the spectral condition number of the data matrix at each step, and numerical experiments are reported in order to illustrate the effectiveness of our FFT based method for fast RLS filtering.