The Living Thing / Notebooks :

State filtering

Kalman and friends

Kalman-Bucy filter and variants, recursive estimation, predictive state models, Data assimilation. A particular sub-field of signal processing for models with hidden state.

In statistics terms, the state filters are a kind of online-updating hierarchical model for sequential observations of a dynamical system where the random state is unobserved, but you can get an optimal estimate of it based on incoming measurements and known parameters.

A unifying feature of all these is by assuming a sparse influence graph between observations and dynamics, that you can estimate behaviour using efficient message passing.

This is a twin problem to optimal control.


Linear systems

In Kalman filters per se you are usually concerned with multivariate real vector signals representing different axes of some telemetry data problem. In the degenerate case, where there is no observation noise, you can just design a linear filter.

The classic Kalman filter (Kalm60) assumes a linear model with Gaussian noise, although it might work with not-quite Gaussian, not-quite linear models if you prod it. You can extend this flavour to somewhat more general dynamics.

If you are doing telemetry then you probably know a priori that your model is not linear in this case, and extensions are advisable.

(NB I’m conflating linear observation and linear process models here, but this is fine for a link list, I think.)

Non-linear dynamical systems

Cute exercise: you can derive the analytic Kalman filter for any noise and process dynamics of with Bayesian conjugate, and this leads to filters of nonlinear behaviour. Multivariate distributions are a bit of a mess for non-Gaussians, though, and a beta-Kalman filter feels contrived.

Upshot is, the non-linear extensions don’t usually rely on non-Gaussian conjugate distributions and analytic forms, but rather do some Gaussian/linear approximation, or use randomised methods such as particle filters.

For some example of doing this in Stan see Sinhrks’ statn-statespace.

Discrete state Hidden Markov models

TBD. Viterbi algorithm.

Other interesting state filters

TODO: learn if the “Predictive state representation” of WoJS05 and SiJR04 is in fact a state filter? Looks similar to something I’ve derived… Or is this better classified as state space reconstruction?

Note that state filters can also do approximate gaussian process regression, apparently. See Särkka’s work.

State filter inference

How about learning the parameters of the model generating your states? Ways that you can do this in dynamical systems include basic linear system identification, general system identification, . But can you identify the parameters (not just hidden states) with a state filter? Yes, see recursive estimation.


Arulampalam, M. S., Maskell, S., Gordon, N., & Clapp, T. (2002) A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2), 174–188. DOI.
Battey, H., & Sancetta, A. (2013) Conditional estimation for dependent functional data. Journal of Multivariate Analysis, 120, 1–17. DOI.
Brunton, S. L., Proctor, J. L., & Kutz, J. N.(2016) Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proceedings of the National Academy of Sciences, 113(15), 3932–3937. DOI.
Carmi, A. Y.(2013) Compressive system identification: Sequential methods and entropy bounds. Digital Signal Processing, 23(3), 751–770. DOI.
Carmi, A. Y.(2014) Compressive System Identification. In A. Y. Carmi, L. Mihaylova, & S. J. Godsill (Eds.), Compressed Sensing & Sparse Filtering (pp. 281–324). Springer Berlin Heidelberg
Cassidy, B., Rae, C., & Solo, V. (2015) Brain Activity: Connectivity, Sparsity, and Mutual Information. IEEE Transactions on Medical Imaging, 34(4), 846–860. DOI.
Cauchemez, S., & Ferguson, N. M.(2008) Likelihood-based estimation of continuous-time epidemic models from time-series data: application to measles transmission in London. Journal of The Royal Society Interface, 5(25), 885–897. DOI.
Chen, B., & Hong, Y. (2007) Testing for the Markov Property in Time Series.
Clark, J. S., & Bjørnstad, O. N.(2004) Population time series: process variability, observation errors, missing values, lags, and hidden states. Ecology, 85(11), 3140–3150. DOI.
Durbin, J., & Koopman, S. J.(1997) Monte Carlo maximum likelihood estimation for non-Gaussian state space models. Biometrika, 84(3), 669–684. DOI.
Durbin, J., & Koopman, S. J.(2012) Time series analysis by state space methods. (2nd ed.). Oxford: Oxford University Press
Eden, U., Frank, L., Barbieri, R., Solo, V., & Brown, E. (2004) Dynamic Analysis of Neural Encoding by Point Process Adaptive Filtering. Neural Computation, 16(5), 971–998. DOI.
Fraser, A. M.(2008) Hidden Markov models and dynamical systems. . Philadelphia, PA: Society for Industrial and Applied Mathematics
Gourieroux, C., & Jasiak, J. (2015) Filtering, Prediction and Simulation Methods for Noncausal Processes. Journal of Time Series Analysis, n/a-n/a. DOI.
Harvey, A., & Koopman, S. J.(2005) Structural Time Series Models. In Encyclopedia of Biostatistics. John Wiley & Sons, Ltd
Harvey, A., & Luati, A. (2014) Filtering With Heavy Tails. Journal of the American Statistical Association, 109(507), 1112–1122. DOI.
Hefny, A., Downey, C., & Gordon, G. (2015) A New View of Predictive State Methods for Dynamical System Learning. arXiv:1505.05310 [Cs, Stat].
Hong, X., Mitchell, R. J., Chen, S., Harris, C. J., Li, K., & Irwin, G. W.(2008) Model selection approaches for non-linear system identification: a review. International Journal of Systems Science, 39(10), 925–946. DOI.
Ionides, E. L., Bhadra, A., Atchadé, Y., & King, A. (2011) Iterated filtering. The Annals of Statistics, 39(3), 1776–1802. DOI.
Kalman, R. (1959) On the general theory of control systems. IRE Transactions on Automatic Control, 4(3), 110–110. DOI.
Kalman, R. E.(1960) A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engineering, 82(1), 35. DOI.
Kalouptsidis, N., Mileounis, G., Babadi, B., & Tarokh, V. (2011) Adaptive algorithms for sparse system identification. Signal Processing, 91(8), 1910–1919. DOI.
Kitagawa, G. (1987) Non-Gaussian State—Space Modeling of Nonstationary Time Series. Journal of the American Statistical Association, 82(400), 1032–1041. DOI.
Kitagawa, G. (1996) Monte Carlo Filter and Smoother for Non-Gaussian Nonlinear State Space Models. Journal of Computational and Graphical Statistics, 5(1), 1–25. DOI.
Kitagawa, G., & Gersch, W. (1996) Smoothness Priors Analysis of Time Series. . New York, NY: Springer New York : Imprint : Springer
Kobayashi, H., Mark, B. L., & Turin, W. (2011) Probability, Random Processes, and Statistical Analysis: Applications to Communications, Signal Processing, Queueing Theory and Mathematical Finance. . Cambridge University Press
Koopman, S. J., & Durbin, J. (2000) Fast Filtering and Smoothing for Multivariate State Space Models. Journal of Time Series Analysis, 21(3), 281–296. DOI.
Lei, J., Bickel, P., & Snyder, C. (2009) Comparison of Ensemble Kalman Filters under Non-Gaussianity. Monthly Weather Review, 138(4), 1293–1306. DOI.
Olfati-Saber, R. (2005) Distributed Kalman Filter with Embedded Consensus Filters. In 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC ’05 (pp. 8179–8184). DOI.
Robertson, A. N.(2011) A Bayesian approach to drum tracking.
Robertson, A., & Plumbley, M. (2007) B-Keeper: A Beat-tracker for Live Performance. In Proceedings of the 7th International Conference on New Interfaces for Musical Expression (pp. 234–237). New York, NY, USA: ACM DOI.
Robertson, A., Stark, A., & Davies, M. E.(2013) Percussive Beat tracking using real-time median filtering. . Presented at the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases
Robertson, A., Stark, A. M., & Plumbley, M. D.(2011) Real-Time Visual Beat Tracking Using a Comb Filter Matrix.
Rodriguez, A., & Ruiz, E. (2009) Bootstrap prediction intervals in state–space models. Journal of Time Series Analysis, 30(2), 167–178. DOI.
Rudary, M., Singh, S., & Wingate, D. (2005) Predictive Linear-Gaussian Models of Stochastic Dynamical Systems. In arXiv:1207.1416 [cs].
Sarkka, S. (2007) On Unscented Kalman Filtering for State Estimation of Continuous-Time Nonlinear Systems. IEEE Transactions on Automatic Control, 52(9), 1631–1641. DOI.
Singh, S., James, M. R., & Rudary, M. R.(2004) Predictive State Representations: A New Theory for Modeling Dynamical Systems. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (pp. 512–519). Arlington, Virginia, United States: AUAI Press
Sorenson, H. W.(1970) Least-squares estimation: from Gauss to Kalman. IEEE Spectrum, 7(7), 63–68. DOI.
Tavakoli, S., & Panaretos, V. M.(2016) Detecting and Localizing Differences in Functional Time Series Dynamics: A Case Study in Molecular Biophysics. Journal of the American Statistical Association, 1–31. DOI.
Wolfe, B., James, M. R., & Singh, S. (2005) Learning Predictive State Representations in Dynamical Systems Without Reset. In Proceedings of the 22Nd International Conference on Machine Learning (pp. 980–987). New York, NY, USA: ACM DOI.