Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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.
  • 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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F25, 62M20
  • Retrieve articles in all journals with MSC: 65F25, 62M20
Additional Information
  • © Copyright 1983 American Mathematical Society
  • Journal: Math. Comp. 40 (1983), 323-336
  • MSC: Primary 65F25; Secondary 62M20
  • DOI:
  • MathSciNet review: 679449