Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A general orthogonalization technique with applications to time series analysis and signal processing

Author: George Cybenko
Journal: Math. Comp. 40 (1983), 323-336
MSC: Primary 65F25; Secondary 62M20
MathSciNet review: 679449
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • David A. Belsley, Edwin Kuh, and Roy E. Welsch, Regression diagnostics: identifying influential data and sources of collinearity, John Wiley & Sons, New York-Chichester-Brisbane, 1980. Wiley Series in Probability and Mathematical Statistics. 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • L. R. Rabiner & R. Schafer, Digital Processing of Speech Signals, Prentice-Hall, Englewood Cliffs, N.J., 1978.
  • G. W. Stewart, Introduction to matrix computations, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR 0458818
  • J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F25, 62M20

Retrieve articles in all journals with MSC: 65F25, 62M20

Additional Information

Keywords: Orthogonalization, least-squares problems, linear prediction
Article copyright: © Copyright 1983 American Mathematical Society