Characterization of the Complexity of Computing the Minimum Mean Square Error of Causal Prediction

This paper investigates the complexity of computing the minimum mean square prediction error for wide-sense stationary stochastic processes. It is shown that if the spectral density of the stationary process is a strictly positive, computable continuous function then the minimum mean square error (MMSE) is always a computable number. Nevertheless, we also show that the computation of the MMSE is a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\# P_{1}$ </tex-math></inline-formula> complete problem on the set of strictly positive, polynomial-time computable, continuous spectral densities. This means that if, as widely assumed, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$FP_{1} \neq \# P_{1}$ </tex-math></inline-formula>, then there exist strictly positive, polynomial-time computable continuous spectral densities for which the computation of the MMSE is not polynomial-time computable. These results show in particular that under the widely accepted assumptions of complexity theory, the computation of the MMSE is generally much harder than an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$NP_{1}$ </tex-math></inline-formula> complete problem.