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

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?)

  • [1] D. A. Belsley, E. Kuh & R. E. Welsch, Regression Diagnostics, Wiley, New York, 1980. MR 576408 (81i:62112)
  • [2] Å. Björck, "Solving linear least squares problems by Gram-Schmidt orthogonalization," BIT, v. 7, 1967, pp. 1-21. MR 0214275 (35:5126)
  • [3] G. E. Box & G. M Jenkins, Time Series Forcasting and Control, Holden-Day, San Francisco, 1970.
  • [4] J. P. Burg, Maximal Entropy Spectral Analysis, Ph.D. dissertation, Stanford University, 1975.
  • [5] G. Cybenko, "The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations," SIAM J. Sci. Statist. Comput., v. 1, 1980, pp. 303-320. MR 596026 (82i:65019)
  • [6] G. Cybenko, Rounding-Errors and Nonoptimality of Lattice Methods for Linear Prediction, Proc. 14th Annual Princeton Conference on Information Systems and Sciences, March 1980.
  • [7] P. Delsarte, Y. Genin & Y. Kemp, "A method of matrix inverse triangular decomposition based on contiguous principal submatrices," Linear Algebra Appl. (To appear.) MR 570391 (82f:65028)
  • [8] R. De Meersman, "A method for least squares solutions of systems with a cyclic coefficient matrix," J. Comput. Math., v. 1, 1975, pp. 51-54. MR 0386248 (52:7106)
  • [9] G. M. Furnival & R. W. Wilson, Jr., "Regression by leaps and bounds," Technometrics, v. 16, 1974, pp. 499-511.
  • [10] G. H. Golub, "Numerical methods for solving least squares problems," Numer. Math., v. 7, 1965, pp. 206-216. MR 0181094 (31:5323)
  • [11] U. Grenander & G. Szego, Toeplitz Forms and their Applications, Univ. of California Press, Berkeley, 1958, p. 38. MR 0094840 (20:1349)
  • [12] F. Itakura & S. Saito, Digital Filtering Techniques for Speech Analysis and Synthesis, Proc. 7th Internat. Congr. Acoust., Budapest, 1971, pp. 261-264.
  • [13] T. Kailath, "A view of three decades of linear filtering theory," IEEE Trans. Information Theory, v. 2, 1974, pp. 146-181. MR 0465437 (57:5337)
  • [14] 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.
  • [15] J. Makhoul, personal communication, 1979.
  • [16] M. H. Quenouille, "The joint distribution of serial correlation coefficients," Ann. Math. Statist., v. 20, 1949, pp. 561-571. MR 0036491 (12:118a)
  • [17] L. R. Rabiner & R. Schafer, Digital Processing of Speech Signals, Prentice-Hall, Englewood Cliffs, N.J., 1978.
  • [18] G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973. MR 0458818 (56:17018)
  • [19] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford Univ. Press, London and New York, 1965. MR 0184422 (32:1894)

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

American Mathematical Society