Volume 4, pp. 14-36, 1996.

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

Michael K. Ng and Robert J. Plemmons

Abstract

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-by-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)=en, where en is the last unit vector. We apply the FFT–based preconditioned conjugate gradient (PCG) method with the Toeplitz matrix T(t1) as preconditioner to solve such systems at the step t. As both matrix vector products T(t)v and T(t1)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(t1)1T(t) is near to 1. The method converges very quickly, and the filter coefficients can be updated in O(nlogn) operations per adaptive filter input. Preliminary numerical results are reported in order to illustrate the effectiveness of the method.

Full Text (PDF) [486 KB], BibTeX

Key words

LMS-Newton adaptive filter algorithm, finite impulse response filter, Toeplitz matrix, circulant matrix, preconditioned conjugate gradient method, fast Fourier transform.

AMS subject classifications

65F10.

Links to the cited ETNA articles

[16] Vol. 2 (1994), pp. 154-170 Michael K. Ng: Fast iterative methods for solving Toeplitz-plus-Hankel least squares problems