Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

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

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
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: https://doi.org/10.1090/S0025-5718-1983-0679449-6
  • MathSciNet review: 679449