TY - JOUR

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

AU - Boche, Holger

AU - Pohl, Volker

AU - Poor, H. Vincent

N1 - Funding Information:
The work of H. Boche was supported in part by the German Federal Ministry of Education and Research (BMBF) within the national initiative on 6G Communication Systems through the research hub 6G – life under Grant 16KISK002, within the national initiative for Post Shannon Communication (NewCom) under Grant 16KIS1003K, and the project Hardware Platforms and Computing Models for Neuromorphic Computing (NeuroCM) under Grant 16ME0442. It has further received funding by the Bavarian Ministry of Economic Affairs, Regional Development and Energy as part of the project 6G Future Lab Bavaria as well as in part by the German Research Foundation (DFG) within Germany’s Excellence Strategy EXC–2092–390781972. V. Pohl acknowledges the support of the DFG under Grant PO 1347/3–2.
Funding Information:
The work of H. V. Poor was supported by the U.S. National Science Foundation under Grants CCF-1908308 and CNS-2128448.
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

UR - http://www.scopus.com/inward/citedby.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 -