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 matrix of full rank . The method is based on the use of projections to solve increasingly larger subproblems recursively and has an 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.

**[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)**

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