Fast algorithms for optimal FIR filter and smoother of discrete-time state-space models

In this paper, fast algorithms are suggested for the optimal FIR filter and smoother of discrete-time state-space models with system noise. While the computation order of the previous algorithms for the optimal FIR filter and smoother is O(N²) with filter length N, it is shown in this paper that it can be reduced to O(N) by modifying the computation sequences and by using the property of the transition matrix. Once the state-space model is given, the suggested algorithms become more efficient than multichannel Levinson algorithm. In addition, the FIR smoother is extended to a fixed-lag FIR smoother so that it can estimate the state in the filter window.