Bellman filter: Difference between revisions

 

Line 18: Line 18:

== Model and notation ==

== Model and notation ==

A commonly used specification keeps a linear–Gaussian state transition and allows a general observation density. For <math>t=1,\dots,n</math>:<ref name=”LangeIntro2024″ />

commonly used specification keeps linear–Gaussian state transition a general observation density. For <math>t=1,\dots,n</math>:<ref name=”LangeIntro2024″ />

* ”’Observation equation:”’

* ”’Observation equation:”’

<math>y_t \sim p(y_t\mid x_t)</math>

<math>y_t \sim p(y_t\mid x_t)</math>

Recursive state estimator for state-space models derived via dynamic programming

The Bellman filter is a recursive algorithm for estimating a sequence of unobserved (latent) states in a state-space model from noisy observations. It is typically formulated for models with a linear–Gaussian state transition and a possibly nonlinear and/or non-Gaussian observation density, and it updates the state by solving a per-time-step optimisation problem involving log ⁡ p ( y t ∣ x t ) {\displaystyle \log p(y_{t}\mid x_{t})} . Under linear–Gaussian observation models, it reduces to the standard Kalman filter update.^[1][2][3]

In a discrete-time state-space model, an unobserved state vector evolves over time and generates observations. The linear–Gaussian case admits an optimal recursive solution via the Kalman filter, and standard econometric treatments include the monographs by Harvey and by Durbin & Koopman.^[4][5]

For nonlinear and/or non-Gaussian observation models, exact filtering generally becomes intractable and practical methods rely on approximation (e.g. extended/iterated Kalman filtering) or simulation (e.g. particle filters). The Bellman filter is often presented as a “filtering-by-optimisation” alternative that tracks a posterior mode at each time step.^[1]

Although the approach is more generally applicable, a commonly used specification keeps the classic linear–Gaussian state transition while allowing a general observation density. For t = 1 , … , n {\displaystyle t=1,\dots ,n} :^[1]

y t ∼ p ( y t ∣ x t ) {\displaystyle y_{t}\sim p(y_{t}\mid x_{t})}

• State-transition equation:

x t = c + T x t − 1 + R η t {\displaystyle x_{t}=c+Tx_{t-1}+R\eta _{t}}
where η t ∼ i.i.d.  N ( 0 , Q ) {\displaystyle \eta _{t}\sim {\text{i.i.d. }}{\mathcal {N}}(0,Q)} .

The filter maintains predicted quantities x ^ t ∣ t − 1 {\displaystyle {\hat {x}}_{t\mid t-1}} , P t ∣ t − 1 {\displaystyle P_{t\mid t-1}} and filtered quantities x ^ t ∣ t {\displaystyle {\hat {x}}_{t\mid t}} , P t ∣ t {\displaystyle P_{t\mid t}} .^[1]

For the observation model, Fisher information is defined as:^[1]
I ( x ) := ∫ [ − ∇ 2 log ⁡ p ( y ∣ x ) ] p ( y ∣ x ) d y . {\displaystyle I(x):=\int \left[-\nabla ^{2}\log p(y\mid x)\right]\,p(y\mid x)\,dy.}

x ^ t ∣ t − 1 = c + T x ^ t − 1 ∣ t − 1 , {\displaystyle {\hat {x}}_{t\mid t-1}=c+T{\hat {x}}_{t-1\mid t-1},}

P t ∣ t − 1 = T P t − 1 ∣ t − 1 T ⊤ + R Q R ⊤ . {\displaystyle P_{t\mid t-1}=TP_{t-1\mid t-1}T^{\top }+RQR^{\top }.} ^[1]

x ^ t ∣ t = arg ⁡ max x ∈ R d { log ⁡ p ( y t ∣ x ) − 1 2 ( x − x ^ t ∣ t − 1 ) ⊤ P t ∣ t − 1 − 1 ( x − x ^ t ∣ t − 1 ) } . {\displaystyle {\hat {x}}_{t\mid t}=\arg \max _{x\in \mathbb {R} ^{d}}\left\{\log p(y_{t}\mid x)-{\tfrac {1}{2}}(x-{\hat {x}}_{t\mid t-1})^{\top }P_{t\mid t-1}^{-1}(x-{\hat {x}}_{t\mid t-1})\right\}.} ^[1]

P t ∣ t = ( P t ∣ t − 1 − 1 + I ( x ^ t ∣ t ) ) − 1 . {\displaystyle P_{t\mid t}=\left(P_{t\mid t-1}^{-1}+I({\hat {x}}_{t\mid t})\right)^{-1}.} ^[1]

If
y t = d + Z x t + ε t {\displaystyle y_{t}=d+Zx_{t}+\varepsilon _{t}}
where ε t ∼ i.i.d.  N ( 0 , H ) {\displaystyle \varepsilon _{t}\sim {\text{i.i.d. }}{\mathcal {N}}(0,H)} ,
then the update reduces to the Kalman filter update.^[1][3]

A Gauss–Newton interpretation of iterated Kalman updates appears in Bell and Cathey.^[6]

With a linear–Gaussian state transition, standard Rauch-Tung-Striebel (RTS) fixed-interval smoothing recursions can be used to obtain smoothed estimates x ^ t ∣ n {\displaystyle {\hat {x}}_{t\mid n}} and P t ∣ n {\displaystyle P_{t\mid n}} from the filtered output.^[1][7]

• Durbin, J.; Koopman, S. J. (2012). Time Series Analysis by State Space Methods (2nd ed.). Oxford University Press. ISBN 978-0199641178.
• Harvey, A. C. (1990). Forecasting, Structural Time Series Models and the Kalman Filter. Cambridge University Press. ISBN 978-0521405737.
• Lange, Rutger-Jan (2024). “Short and simple introduction to Bellman filtering and smoothing”. arXiv:2405.12668 [stat.ME].
• Kalman, R. E. (1960). “A New Approach to Linear Filtering and Prediction Problems”. Journal of Basic Engineering. 82 (1): 35–45. doi:10.1115/1.3662552.
• Rauch, H. E.; Tung, F.; Striebel, C. T. (1965). “Maximum likelihood estimates of linear dynamic systems”. AIAA Journal. 3 (8): 1445–1450. doi:10.2514/3.3166.