Computing Orthogonal Projections Can Be Too Computational Expensive

Orthogonal projections are widely used to determine optimal controllers, filters and approximations. This paper shows that despite their simple theoretical foundation and their regular use in practical applications, the complexity for computing orthogonal projections might be very high. The paper proves that the causal projection on L2 maps computable continuous functions onto not computable functions. Moreover, it is shown that the orthogonal projection associated with the polynomial approximation in L2 shows complexity blowup in the sense that it maps polynomial-time computable continuous functions onto polynomials that are not polynomial-time computable. Finally, it is shown that the coefficients of the Wiener prediction filter for stationary stochastic processes might not be computable in polynomial time, even for smooth and polynomial-time computable spectral densities.