article

Free access

On the Linear Convergence of a Covariance Factorization Algorithm

Author:

Marcello PaganoAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 2

Pages 310 - 316

https://doi.org/10.1145/321941.321950

Published: 01 April 1976 Publication History

PDF eReader

Abstract

An algorithm for factoring a covariance function into its Hurwitz factors, which is based on the Cholesky factors of a certain matrix, was proposed by F.L. Bauer and others. This algorithm bears a close connection to the theory of orthogonal polynomials, and a closer one to the theory of prediction of stationary time series. In this paper these relations are pointed out and then used to advantage to prove the linear convergence of this algorithm.

References

[1]

BAUER, F.L. Ein Direktes Iterationsverfahren zur Hurwitzzerlegung eines Polynoms. Archly. el. Ubertr. 9 (1955), 285--290.

Google Scholar

[2]

BAUER, F.L. Beitr~ige zur Entwicklung numerischer Verfahren ftir programmgestuerte Rechenandagen, II. Sztzungsberichte der Mathem, Naturtmss. Klasse der Bayer. Akademie der W~ssenschaften, 1956, pp. 163-203.

Google Scholar

[3]

DEVINATZ, A. Asymptotic estimates for the finite predictor Math. Scan& 16 (1964), 111-120.

Google Scholar

[4]

FmCHER, D, GOLUB, G, HALD, O., LEIvA, C., AND WIDLUND, O. On Fourier-Toeplitz methods for separable elliptic problems. Rep. STAN-CS-73-375, Comput. Sci. Dep., Stanford U., Stanford, Calif., 1973.

Google Scholar

[5]

GERONIMUS, L.YA. Orthogonal Polynomzal~. Transl. and pub. by Consultants Bureau, New York.

Google Scholar

[6]

GRENANDER, U, AND ROSE~BLA~r, M. An extension of a theorem of G. Szego and its application to the study of stochastic processes. Trans. Amer. Math. Soc. 76 (1954), 112-126.

Google Scholar

[7]

GRENANVER, U., AND SZEGd, G. Toepl~tz Forms and Their Applications. U of California Press, Berkeley and Los Angeles, CMif, 1958.

Google Scholar

[8]

LEVXNSON, N. The Wiener RMS (root mean square) error criterion in filter design and prediction. J. Math Phys. 25 (1947), 261-278.

Google Scholar

[9]

PAGANO, M. An algorithm for fitting autoregressive schemes. J. Roy Statist. Soc., Ser. C (Apphed Statzst~cs), $1 (1972), 274-281.

Google Scholar

[10]

RISSANEN, J Algorithms for triangular decomposition of block Hankel and Toeplitz matrices with application to factoring positive matrix polynomials. Math. Comput. 27 (1973), 147-154

Google Scholar

[11]

RISSANEN, J, AND BARBOSA, L. Properties of infinite covariance matrices and stability of optimum predictors. Inform. Sc~s. 1 (1969), 221-236.

Google Scholar

[12]

WmTTZ, E, P. Prediction and Regulation. The English Universities Press Ltd, London, 1963.

Google Scholar

[13]

W, LSON, G. Factorization of the covariance generating function of a pure moving average process. SIAM J. Numer. Anal. 6 (1969), 1-7.

Google Scholar

[14]

WoLv, H. A large-sample test for moving averages. J. Roy. Statist. Soc., Set. B, 11 (1949), 297-305.

Google Scholar

Cited By

View all

van Schuppen Jvan Schuppen J(2021)Stochastic Realization of Gaussian SystemsControl and System Theory of Discrete-Time Stochastic Systems10.1007/978-3-030-66952-2_6(183-230)Online publication date: 3-Aug-2021
https://doi.org/10.1007/978-3-030-66952-2_6
McElroy T(2017)Recursive Computation for Block‐Nested Covariance MatricesJournal of Time Series Analysis10.1111/jtsa.1226739:3(299-312)Online publication date: 17-Oct-2017
https://doi.org/10.1111/jtsa.12267
Newton HPagano M(1983)The Finite Memory Prediction of Covariance Stationary Time SeriesSIAM Journal on Scientific and Statistical Computing10.1137/09040274:2(330-339)Online publication date: 1-Jun-1983
https://dl.acm.org/doi/10.1137/0904027
Show More Cited By

Index Terms

On the Linear Convergence of a Covariance Factorization Algorithm
1. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Ordinary differential equations
  2. Probability and statistics

Recommendations

Convergence of two-stage iterative methods using incomplete factorization

We first study the convergence of two-stage iterative methods using the incomplete factorization for solving a linear system whose coefficient matrix is an H-matrix, and then we study the convergence of two-stage iterative methods using the incomplete ...
Linear convergence of the generalized Douglas---Rachford algorithm for feasibility problems

In this paper, we study the generalized Douglas---Rachford algorithm and its cyclic variants which include many projection-type methods such as the classical Douglas---Rachford algorithm and the alternating projection algorithm. Specifically, we ...
A Toeplitz algorithm for polynomial J-spectral factorization

A block Toeplitz algorithm is proposed to perform the J-spectral factorization of a para-Hermitian polynomial matrix. The input matrix can be singular or indefinite, and it can have zeros along the imaginary axis. The key assumption is that the finite ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 23, Issue 2

April 1976

176 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321941

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1976

Published in JACM Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
386
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)5

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

van Schuppen Jvan Schuppen J(2021)Stochastic Realization of Gaussian SystemsControl and System Theory of Discrete-Time Stochastic Systems10.1007/978-3-030-66952-2_6(183-230)Online publication date: 3-Aug-2021
https://doi.org/10.1007/978-3-030-66952-2_6
McElroy T(2017)Recursive Computation for Block‐Nested Covariance MatricesJournal of Time Series Analysis10.1111/jtsa.1226739:3(299-312)Online publication date: 17-Oct-2017
https://doi.org/10.1111/jtsa.12267
Newton HPagano M(1983)The Finite Memory Prediction of Covariance Stationary Time SeriesSIAM Journal on Scientific and Statistical Computing10.1137/09040274:2(330-339)Online publication date: 1-Jun-1983
https://dl.acm.org/doi/10.1137/0904027
Newton H(1981)On Some Numerical Properties of Arma Parameter Estimation ProceduresComputer Science and Statistics: Proceedings of the 13th Symposium on the Interface10.1007/978-1-4613-9464-8_25(172-177)Online publication date: 1981
https://doi.org/10.1007/978-1-4613-9464-8_25

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Convergence of two-stage iterative methods using incomplete factorization

Linear convergence of the generalized Douglas---Rachford algorithm for feasibility problems

A Toeplitz algorithm for polynomial J-spectral factorization

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations