RECENT PROGRESS IN COMPUTABILITY FOR PREDICTION AND WIENER FILTER THEORY

Holger Boche, Volker Pohl, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)323-344
Number of pages22
JournalTransactions of A. Razmadze Mathematical Institute
Volume176
Issue number3
StatePublished - Dec 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Complexity blowup
  • Computability
  • Estimation
  • Prediction Spectral factorization
  • Turing machine
  • Wiener Filter

Fingerprint

Dive into the research topics of 'RECENT PROGRESS IN COMPUTABILITY FOR PREDICTION AND WIENER FILTER THEORY'. Together they form a unique fingerprint.

Cite this