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 $\min \| d - (X_1+X_2) w \|_2$ by the fast Fourier transform (FFT) based preconditioned conjugate gradient method, for $(M+2n-1)$-by-$n$ real Toeplitz-plus-Hankel data matrices $X_1+X_2$ 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 $X_1+X_2$ is of order $O(n^{\alpha})$, $\alpha >0$, then the method converges in at most $O((2\alpha+1) \log n +1 )$ steps. Since the cost of forming the normal equations and the FFT–based preconditioner is $O(M \log n)$ operations and each iteration requires $O(n \log n)$ operations, the total complexity of our algorithm is of order $O(M \log n + (2\alpha+1) n \log^2 n + n \log n)$ 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