A general orthogonalization technique with applications to time series analysis and signal processing
HTML articles powered by AMS MathViewer
- by George Cybenko PDF
- Math. Comp. 40 (1983), 323-336 Request permission
Abstract:
A new orthogonalization technique is presented for computing the QR factorization of a general $n \times p$ matrix of full rank $p (n \geqslant p)$. The method is based on the use of projections to solve increasingly larger subproblems recursively and has an $O(n{p^2})$ operation count for general matrices. The technique is readily adaptable to solving linear least-squares problems. If the initial matrix has a circulant structure the algorithm simplifies significantly and gives the so-called lattice algorithm for solving linear prediction problems. From this point of view it is seen that the lattice algorithm is really an efficient way of solving specially structured least-squares problems by orthogonalization as opposed to solving the normal equations by fast Toeplitz algorithms.References
- David A. Belsley, Edwin Kuh, and Roy E. Welsch, Regression diagnostics: identifying influential data and sources of collinearity, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, New York-Chichester-Brisbane, 1980. MR 576408
- Ȧke Björck, Solving linear least squares problems by Gram-Schmidt orthogonalization, Nordisk Tidskr. Informationsbehandling (BIT) 7 (1967), 1–21. MR 214275, DOI 10.1007/bf01934122 G. E. Box & G. M Jenkins, Time Series Forcasting and Control, Holden-Day, San Francisco, 1970. J. P. Burg, Maximal Entropy Spectral Analysis, Ph.D. dissertation, Stanford University, 1975.
- George Cybenko, The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations, SIAM J. Sci. Statist. Comput. 1 (1980), no. 3, 303–319. MR 596026, DOI 10.1137/0901021 G. Cybenko, Rounding-Errors and Nonoptimality of Lattice Methods for Linear Prediction, Proc. 14th Annual Princeton Conference on Information Systems and Sciences, March 1980.
- Ph. Delsarte, Y. Genin, and Y. Kamp, A method of matrix inverse triangular decomposition based on contiguous principal submatrices, Linear Algebra Appl. 31 (1980), 199–212. MR 570391, DOI 10.1016/0024-3795(80)90219-0
- R. De Meersman, A method for least squares solution of systems with a cyclic rectangular coefficient matrix, J. Comput. Appl. Math. 1 (1975), 51–54. MR 386248, DOI 10.1016/0771-050X(75)90008-X G. M. Furnival & R. W. Wilson, Jr., "Regression by leaps and bounds," Technometrics, v. 16, 1974, pp. 499-511.
- G. Golub, Numerical methods for solving linear least squares problems, Numer. Math. 7 (1965), 206–216. MR 181094, DOI 10.1007/BF01436075
- Ulf Grenander and Gabor Szegö, Toeplitz forms and their applications, California Monographs in Mathematical Sciences, University of California Press, Berkeley-Los Angeles, 1958. MR 0094840 F. Itakura & S. Saito, Digital Filtering Techniques for Speech Analysis and Synthesis, Proc. 7th Internat. Congr. Acoust., Budapest, 1971, pp. 261-264.
- Thomas Kailath, A view of three decades of linear filtering theory, IEEE Trans. Inform. Theory IT-20 (1974), 146–181. MR 465437, DOI 10.1109/tit.1974.1055174 J. Makhoul, "A class of all-zero lattice digital filters: properties and applications," IEEE Trans. Acoust. Speech Signal Process., v. 4, 1978, pp. 304-314. J. Makhoul, personal communication, 1979.
- M. H. Quenouille, The joint distribution of serial correlation coefficients, Ann. Math. Statistics 20 (1949), 561–571. MR 36491, DOI 10.1214/aoms/1177729948 L. R. Rabiner & R. Schafer, Digital Processing of Speech Signals, Prentice-Hall, Englewood Cliffs, N.J., 1978.
- G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Additional Information
- © Copyright 1983 American Mathematical Society
- Journal: Math. Comp. 40 (1983), 323-336
- MSC: Primary 65F25; Secondary 62M20
- DOI: https://doi.org/10.1090/S0025-5718-1983-0679449-6
- MathSciNet review: 679449