RECENT PROGRESS IN COMPUTABILITY FOR PREDICTION AND WIENER FILTER THEORY

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.