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 Free Access

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.

- 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** - Ȧke Björck,
*Solving linear least squares problems by Gram-Schmidt orthogonalization*, Nordisk Tidskr. Informationsbehandling (BIT)**7**(1967), 1–21. MR**214275**, DOI https://doi.org/10.1007/bf01934122
G. E. Box & G. M Jenkins, - 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 https://doi.org/10.1137/0901021
G. Cybenko, - 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 https://doi.org/10.1016/0024-3795%2880%2990219-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 https://doi.org/10.1016/0771-050X%2875%2990008-X
G. M. Furnival & R. W. Wilson, Jr., "Regression by leaps and bounds," - G. Golub,
*Numerical methods for solving linear least squares problems*, Numer. Math.**7**(1965), 206–216. MR**181094**, DOI https://doi.org/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, - Thomas Kailath,
*A view of three decades of linear filtering theory*, IEEE Trans. Inform. Theory**IT-20**(1974), 146–181. MR**465437**, DOI https://doi.org/10.1109/tit.1974.1055174
J. Makhoul, "A class of all-zero lattice digital filters: properties and applications," - M. H. Quenouille,
*The joint distribution of serial correlation coefficients*, Ann. Math. Statistics**20**(1949), 561–571. MR**36491**, DOI https://doi.org/10.1214/aoms/1177729948
L. R. Rabiner & R. Schafer, - 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** - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**

*Time Series Forcasting and Control*, Holden-Day, San Francisco, 1970. J. P. Burg,

*Maximal Entropy Spectral Analysis*, Ph.D. dissertation, Stanford University, 1975.

*Rounding-Errors and Nonoptimality of Lattice Methods for Linear Prediction*, Proc. 14th Annual Princeton Conference on Information Systems and Sciences, March 1980.

*Technometrics*, v. 16, 1974, pp. 499-511.

*Digital Filtering Techniques for Speech Analysis and Synthesis*, Proc. 7th Internat. Congr. Acoust., Budapest, 1971, pp. 261-264.

*IEEE Trans. Acoust. Speech Signal Process.*, v. 4, 1978, pp. 304-314. J. Makhoul, personal communication, 1979.

*Digital Processing of Speech Signals*, Prentice-Hall, Englewood Cliffs, N.J., 1978.

Retrieve articles in *Mathematics of Computation*
with MSC:
65F25,
62M20

Retrieve articles in all journals with MSC: 65F25, 62M20

Additional Information

Keywords:
Orthogonalization,
least-squares problems,
linear prediction

Article copyright:
© Copyright 1983
American Mathematical Society