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 $n$th-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) = 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)^{-1} v$ 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)^{-1}T(t)$ is near to 1. The method converges very quickly, and the filter coefficients can be updated in $O( n \log n)$ 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