×

LMS-Newton adaptive filtering using FFT-based conjugate gradient iterations. (English) Zbl 0864.65041

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)].

MSC:

65K10 Numerical optimization and variational techniques
60G35 Signal detection and filtering (aspects of stochastic processes)
65F10 Iterative numerical methods for linear systems
93E11 Filtering in stochastic control theory
93E24 Least squares and related methods for stochastic control systems

Citations:

Zbl 0860.65030
PDFBibTeX XMLCite
Full Text: EuDML EMIS