LMS-Newton adaptive filtering using FFT-based conjugate gradient iterations

In this paper, we propose a new fast Fourier transform (FFT) based LMS-Newton (LMSN) adaptive filter algorithm. At each adaptive time step t, the nth-order filter coefficients are updated by using the inverse of an n-ky-n Hermitian, positive definite, Toeplitz operator T(t). By applying the cyclic displacement formula for the inverse of a Toeplitz operator, T(t)^-1 can be constructed using the solution vector of the Toeplitz system T(t)u(t) = e_n, where e_n is the last unit vector. We apply the FFT-based preconditioned conjugate gradient (PCG) method with the Toeplitz matrix T(t-1) as preconditioner to solve such systems at the step t. As both matrix vector products T(t)v and T(t-1)^-1v can be computed by circular convolutions, FFTs are used throughout the computations. Under certain practical assumptions in signal processing applications, we prove that with probability 1 that the condition number of the preconditioned matrix T(t-1)^-1T(t) is near to 1. The method converges very quickly, and the filter coefficients can be updated in O(n logn) operations per adaptive filter input. Preliminary numerical results are reported in order to illustrate the effectiveness of the method.