TY - JOUR

T1 - RECENT PROGRESS IN COMPUTABILITY FOR PREDICTION AND WIENER FILTER THEORY

AU - Boche, Holger

AU - Pohl, Volker

AU - Poor, H. Vincent

N1 - Publisher Copyright:
© 2022 A. Razmadze Mathematical Institute of Iv. Javakhishvili Tbilisi State University. All rights reserved.

PY - 2022/12

Y1 - 2022/12

N2 - This paper reviews some fundamental results in prediction theory, spectral factorization and Wiener filtering with a particular focus on questions of computability. Since the mathematical theory of prediction and estimation of stationary time series was established by Kolmogorov, Paley, Szegö, Wiener, and many others, it seems to be an open question whether it is possible to effectively compute optimal filter coefficients and important performance measures on digital computers, i.e. on Turing machines. In this paper, we show that the optimum mean squared error (MSE) for predicting a stationary time series from its past observations is generally not Turing computable. However, under an additional condition on the stochastic process, namely, for strictly positive spectral densities, Turing computability of the corresponding optimal MSE can be guaranteed. Nevertheless, even if the MSE is Turing computable, there always exist spectral densities that are polynomial-time computable on a Turing machine, but such that the corresponding optimal MSE is not polynomial-time computable. This observation proves a complexity blowup for the computation of the MSE on digital computers. Finally, we show that the spectral factorization and the calculation of the optimal prediction filter are generally not Turing computable even under additional strong assumptions on the smoothness of the spectral density.

AB - This paper reviews some fundamental results in prediction theory, spectral factorization and Wiener filtering with a particular focus on questions of computability. Since the mathematical theory of prediction and estimation of stationary time series was established by Kolmogorov, Paley, Szegö, Wiener, and many others, it seems to be an open question whether it is possible to effectively compute optimal filter coefficients and important performance measures on digital computers, i.e. on Turing machines. In this paper, we show that the optimum mean squared error (MSE) for predicting a stationary time series from its past observations is generally not Turing computable. However, under an additional condition on the stochastic process, namely, for strictly positive spectral densities, Turing computability of the corresponding optimal MSE can be guaranteed. Nevertheless, even if the MSE is Turing computable, there always exist spectral densities that are polynomial-time computable on a Turing machine, but such that the corresponding optimal MSE is not polynomial-time computable. This observation proves a complexity blowup for the computation of the MSE on digital computers. Finally, we show that the spectral factorization and the calculation of the optimal prediction filter are generally not Turing computable even under additional strong assumptions on the smoothness of the spectral density.

KW - Complexity blowup

KW - Computability

KW - Estimation

KW - Prediction Spectral factorization

KW - Turing machine

KW - Wiener Filter

UR - http://www.scopus.com/inward/record.url?scp=85149825359&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85149825359

SN - 2346-8092

VL - 176

SP - 323

EP - 344

JO - Transactions of A. Razmadze Mathematical Institute

JF - Transactions of A. Razmadze Mathematical Institute

IS - 3

ER -