LMS-Newton adaptive filtering using FFT-based conjugate gradient iterations (Q1920182)

In linear least squares adaptive predictive filtering, a (scalar) output \(o(t)\) is predicted from an \(n\)-vector \(x(t)\) of past signal samples by taking them in a linear combination \(o(t) = w(t)^*x(t)\). The coefficients are collected in the vector \(w(t)\), which is assumed to have length \(n\). The star here means complex conjugate transpose. The prediction error is minimized in least squares sense. In adaptive filtering, the filter \(w\) depends on the time instant \(t\) and is updated as \(t\) passes to \(t+1\). In this updating process one has to solve a system \(T(t)d(t) = x(t)\). Here \(T(t)\) is a positive definite Hermitian Toeplitz matrix that contains the autocorrelation coefficients estimated at time \(t\). To make use of fast Fourier transform (FFT) techniques, \(T(t)\) is embedded in a larger circulant matrix \(C(t)\). (This \(C(t)\) is diagonalized by the discrete Fourier transform matrix.) It is shown how to update the spectrum of \(C(t)\) when new data are entering. Then a preconditioned conjugate gradient method is used to solve the Toeplitz system and hence to update the filter coefficients \(w(t)\). As a preconditioner for \(T(t)\), the authors use \(T(t-1)\), which is available from the previous step. Using stochastic assumptions on the signal, the authors prove that their algorithm converges and they give an estimate for the number of iterations. By the use of FFT techniques, each adaptive time step will require only \(O(n\log n)\) operations. Several numerical experiments show the superiority of the proposed method. Similar results are obtained by the authors in [SIAM J. Sci. Comput. 17, No. 4, 920-941 (1996; Zbl 0860.65030)].