Abstract
We develop a new algorithm for solving Toeplitz linear least squares problems. The Toeplitz matrix is first embedded into a circulant matrix. The linear least squares problem is then transformed into a discrete least squares approximation problem for polynomial vectors. Our implementation shows that the normwise backward stability is independent of the condition number of the Toeplitz matrix.
The work of the first and the third author is supported by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister’s Office for Science, Technology and Culture. The scientific responsibility rests with the authors.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Bojanczyk, R. Brent, and F. DE Hoog, QR factorization of Toeplitz matrices, Numer. Math., 49 (1986), pp. 81–94.
A. Bultheel and M. Van Barel, Vector orthogonal polynomials and least squares approximation, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 863–885.
J. Chun, T. Kailath, and H. Lev-ari, Fast parallel algorithms for QR and triangular factorization, SIAM J. Sci. Statist. Comput., 8 (1987), pp. 899–913.
G. Cybenko, A general orthogonalization technique with applications to time series analysis and signal processing, Math. Comp., 40 (1983), pp. 323–336.
—, Fast Toeplitz orthogonalization using inner products, SIAM J. Sci. Statist. Comput., 8 (1987), pp. 734–740.
I. Gohberg, T. Kailath, and V. Olshevsky, Fast Gaussian elimination with partial pivoting for matrices with displacement structure, Math. Comp., 64 (1995), pp. 1557–1576.
M. Gu, Stable and efficient algorithms for structured systems of linear equations, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 279–306.
N. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 1996.
S. Qiao, Hybrid algorithm for fast Toeplitz orthogonalization, Numer. Math., 53 (1988), pp. 351–366.
D. Sweet, Numerical Methods for Toeplitz matrices, PhD thesis, University of Adelaide, Adelaide, Australia, 1982.
—, Fast Toeplitz orthogonalization, Numer. Math., 43 (1984), pp. 1–21.
M. Van Barel and A. Bultheel, A parallel algorithm for discrete least squares rational approximation, Numer. Math., 63 (1992), pp. 99–121.
—, Discrete linearized least squares approximation on the unit circle, J. Comput. Appl. Math., 50 (1994), pp. 545–563.
—, Orthonormal polynomial vectors and least squares approximation for a discrete inner product, Electron. Trans. Numer. Anal., 3 (1995), pp. 1–23.
J. Varah, The Prolate matrix, Linear Algebra Appl., 187 (1993), pp. 269–278.
B. Waldén, R. Karlson, and J.-g. Sun, Optimal backward perturbation bounds for the linear least squares problem, Numerical Linear Algebra with Applications, 2 (1995), pp. 271–286.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Van Barel, M., Heinig, G., Kravanja, P. (2001). An Algorithm Based on Orthogonal Polynomial Vectors for Toeplitz Least Squares Problems. In: Vulkov, L., Yalamov, P., Waśniewski, J. (eds) Numerical Analysis and Its Applications. NAA 2000. Lecture Notes in Computer Science, vol 1988. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45262-1_4
Download citation
DOI: https://doi.org/10.1007/3-540-45262-1_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41814-6
Online ISBN: 978-3-540-45262-1
eBook Packages: Springer Book Archive