Volume 2, pp. 154-170, 1994.
Fast iterative methods for solving Toeplitz-plus-Hankel least squares problems
Michael K. Ng
Abstract
In this paper, we consider the impulse responses of
the linear-phase filter whose
characteristics are determined on the basis of an observed time series,
not on a prior specification. The impulse responses can be found by solving
a least squares problem
by the fast Fourier transform (FFT) based preconditioned conjugate gradient
method, for -by- real
Toeplitz-plus-Hankel data matrices with full column rank.
The FFT–based preconditioners are derived from
the spectral properties of the given input stochastic process,
and their
eigenvalues are constructed by the Blackman-Tukey spectral estimator
with Bartlett window which is commonly used in signal processing.
When the stochastic process is stationary and when
its spectral density function
is positive and differentiable, we prove that with probability 1,
the spectra of the preconditioned normal equations
matrices are clustered around 1,
provided that large data samples are taken.
Hence if the smallest singular value of is of order
, ,
then the method converges in at most steps.
Since the cost of forming the normal equations and the FFT–based
preconditioner
is operations and each iteration requires
operations, the total complexity of our algorithm
is of order operations.
Finally, numerical results are reported to illustrate the
effectiveness of our FFT–based preconditioned iterations.
Full Text (PDF) [232 KB],
BibTeX
Key words
least squares estimations, linear-phase filter, Toeplitz-plus-Hankel matrix, circulant matrix, preconditioned conjugate gradient method, fast Fourier transform.
AMS subject classifications
65F10, 65F15, 43E10.
ETNA articles which cite this article
Vol. 4 (1996), pp. 14-36 Michael K. Ng and Robert J. Plemmons:
LMS-Newton adaptive filtering using FFT-based conjugate gradient iterations
|