No. 994

Title:

A Recursive Recomputation Approach for Smoothing in Nonlinear State Space Modeling
-- An Attempt for Reducing Space Complexity --

Author(s):

Kazuyuki, Nakamura (Department of Statistical Science, Graduate University of Advanced Studies and Japan Science and Technology);
Takashi, Tsuchiya (The Institute of Statistical Mathematics and Department of Statistical Science, Graudate University of Advanced Studies)

Key words:

Particle filter, smoothing, state space model, hidden Markov model, space complexity

Abstract:

    We develop a new generic implementation scheme for numerical smoothing in nonlinear and Bayesian state space modeling. While recent numerical methods for state space models have the great advantages of allowing flexibility in modeling, exhaustive usage of storage in smoothing is practically a common serious problem, because storage required for smoothing is typically O(MT), where M is the space for storing the filtering distribution at each time point and T is the length of the time series. Our new generic implementation scheme, which we call recursive recomputation scheme, reduces the space complexity from O(MT) to O(M log T), at the cost of a factor of O(log T) in time complexity. This reduction is accomplished by employing carefully designed recursive recomputation. The Japanese stock market price time series data with T = 956 is taken up as an instance to demonstrate advantage of the proposed scheme. The particle filter is implemented with the scheme to smooth the whole interval estimating the change of volatility. The number of particles is 3,000,000, and the whole interval is smoothed with 4.3GB storage, accomplishing saving of storage by a factor of 1/20 where an ordinary implementation would require 86GB.