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]**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**

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