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
DOI: https://doi.org/10.1090/S0025-5718-1983-0679449-6
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] 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
  • [2] Ȧke Björck, Solving linear least squares problems by Gram-Schmidt orthogonalization, Nordisk Tidskr. Informations-Behandling 7 (1967), 1–21. MR 0214275
  • [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] 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, https://doi.org/10.1137/0901021
  • [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] 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, https://doi.org/10.1016/0024-3795(80)90219-0
  • [8] 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 0386248, https://doi.org/10.1016/0771-050X(75)90008-X
  • [9] G. M. Furnival & R. W. Wilson, Jr., "Regression by leaps and bounds," Technometrics, v. 16, 1974, pp. 499-511.
  • [10] G. Golub, Numerical methods for solving linear least squares problems, Numer. Math. 7 (1965), 206–216. MR 0181094, https://doi.org/10.1007/BF01436075
  • [11] 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
  • [12] F. Itakura & S. Saito, Digital Filtering Techniques for Speech Analysis and Synthesis, Proc. 7th Internat. Congr. Acoust., Budapest, 1971, pp. 261-264.
  • [13] Thomas Kailath, A view of three decades of linear filtering theory, IEEE Trans. Information Theory IT-20 (1974), 146–181. MR 0465437
  • [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. Statistics 20 (1949), 561–571. MR 0036491
  • [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 [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR 0458818
  • [19] 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

DOI: https://doi.org/10.1090/S0025-5718-1983-0679449-6
Keywords: Orthogonalization, least-squares problems, linear prediction
Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society