Filtering, State Estimation, and Other Forms of Signal Processing

29 Jul 2008 12:21

---

Filtering. Is the Kalman filter like the EM algorithm, in any meaningful sense? (Yes; where'd that paper by Gharamani showing this go?) What is the Wonham filter, exactly? What are the estimation properties of the parameters in these filters? How bad is it to use the standard linear filters (Wiener, Kalman) on nonlinear systems? What do the existing nonlinear filters look like? (Hidden Markov models are one class of nonlinear filter; they have various drawbacks, mostly about needing to choose the architecture a priori, and it being hard to tell if you're using the wrong architecture, or the process is just intrinsically ugly.)

Nonlinear filtering.

Independent component analysis.

See also: Control Theory; Information Geometry; Monte Carlo and Stochastic Simulation; Time Series

Recommended, big picture:
• Nasir Uddin Ahmed, Introduction to Linear and Nonlinear Filtering for Engineers and Scientists [Clear introductory treatment with not-too-rigorous use of advanced probability theory, which is necessary to really explain what is going on and why it works for nonlinear and/or continuous-time signals.]
• R. W. R. Darling, Nonlinear Filtering --- Online Survey
• Neil Gershenfeld, The Nature of Mathematical Modeling, Part III
• Holger Kantz and Thomas Schreiber, Nonlinear Time Series Analysis
• Robert Shumway and David Stoffer, Time Series Analysis and Its Applications
• Norbert Wiener
  • Extrapolation, Interpolation and Smoothing of Stationary Time Series
  • Cybernetics

Recommended, closeups:
• Jaakko Astola and Pauli Kuosmanen, Fundamental of Nonlinear Digital Filtering
• Jochen Bröcker and Ulrich Parlitz, "Analyzing communication schemes using methods from nonlinear filtering," Chaos 13 (2003): 195--208
• A. E. Brockwell, A. L. Rojas and R. E. Kass, "Recursive Bayesian Decoding of Motor Cortical Signals by Particle Filtering", Journal of Neurophysiology 91 (2004): 1899--1907 [Very nice, especially since they've combining data from multiple experiments. It is a little disappointing that they set up a state-space model, but then only use the state to enforce a kind of weak continuity constraint on the decoding, rather than trying to capture the actual computations going on. But I should talk to them about that... Appendix A gives a very clear and compact explanation of particle filtering.]
• R. W. R. Darling, "Geometrically Intrinsic Nonlinear Recursive Filters," parts I and II, UCB technical reports 494 and 512
• P. Del Moral and L. Miclo, "Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering", in J. Azema, M. Emery, M. Ledoux and M. Yor (eds)., Semainaire de Probabilites XXXIV (Springer-Verlag, 2000), pp. 1--145 [Postscript preprint. Looks like a trial run for Del Moral's book.]
• Uri T. Eden, Loren M. Frank, Riccardo Barbieri, Victor Solo and Emery N. Brown, "Dynamic Analysis of Neural Encoding by Point Process Adaptive Filtering", Neural Computation 16 (2005): 971-988 [Interesting development of filtering methods for point processes, beyond the neural application]
• Robert J. Elliott, Lakhdar Aggoun and John B. Moore, Hidden Markov Models: Estimation and Control
• Gregory L. Eyink, "A Variational Formulation of Optimal Nonlinear Estimation," physics/0011049 [Nice connections between optimal estimation (assuming a known form for the underlying stochastic process), nonequilibrium statistical mechanics, and large deviations theory, leading to tractable-looking numerical schemes.]
• Edward Ionides, "Inference and Filtering for Partially Observed Diffusion Processes" [PDF preprint]
• Jayesh H. Kotecha and Petar M. Djuric, "Gaussian Particle Filtering", IEEE Transactions on Signal Processing 51 (2003): 2592--2601
• M. L. Kleptsyna, A. Le Breton and M.-C. Roubaud, "Parameter Estimation and Optimal Filtering for Fractional Type Stochastic Systems", Statistical Inference for Stochastic Processes 3 (2000): 173--182
• V. V. Prelov and E. C. van der Meulen, "On error-free filtering of finite-state singular processes under dependent distortions", Problems of Information Trasmission 49 (2007): 271--279 ["We consider the problem of finding some sufficient conditions under which causal error-free filtering for a singular stationary stochastic process X = {X_n} with a finite number of states from noisy observations is possible. For a rather general model of observations where the observable stationary process is absolutely regular with respect to the estimated process X, it is proved (using an information-theoretic approach) that under a natural additional condition, causal error-free (with probability one) filtering is possible."]

To read:
• Lakhdar Aggoun and Robert Elliott, Measure Theory and Filtering: Introduction with Applications
• Luis Antonio Aguirre, Bruno Ot´vio S. Teixeira, and Leonardo António B. Tórres, "Using data-driven discrete-time models and the unscented Kalman filter to estimate unobserved variables of nonlinear systems", Physical Review E 72 (2005): 026226
• Francis Alexander, Gregy Eyink and Juan Restrepo, "Accelerated Monte-Carlo for Optimal Estimation of Time Series" = Journal of Statistical Physics 119 (2005): 1331--1345 [PDF]
• Luis B. Almeida, "MISEP - Linear and Nonlinear ICA Based on Mutual Information," Journal of Machine Learning Research submitted [online]
• Shun-ichi Amari, "Estimating Functions of Independent Component Analysis for Temporally Correlated Signals," Neural Computation 12 (2000): 2083--2107
• V.P.Belavkin, "Quantum Diffusion, Measurement and Filtering", quant-ph/0510028 [Published in Probability Theory and Its Applications in 1993-1994]
• Luise Blank, "State estimation without regularizing the initial data", Inverse Problems 20 (2004): 1357--1370
• Holger Boche and Volker Pohl, "Spectral Factorization, Whitening- and Estimation Filter -- Stability, Smoothness Properties and FIR Approximation Behavior", cs.IT/0508018 ["A Wiener filter can be interpreted as a cascade of a whitening- and an estimation filter"]
• T. Bohlin, "Information pattern for linear discrete-time models with stochastic coefficients," IEEE Transactions on Automatic Control 15 (1970): 104--106 [On recursively-computable sufficient statistics]
• R. Boscolo, H. Pan and V. P. Roychowdhury, "Independent Component Analysis Based on Nonparametric Density Estimation", IEEE Transactions on Neural Networks 15 (2004): 55--65
• Luc Bouten and Ramon van Handel, "Quantum filtering: a reference probability approach", math-ph/0508006 ["These notes are intended as an introduction to noncommutative (quantum) filtering theory."]
• D. Brigo, B. Hanzon and F. LeGland, "A differential geometric approach to nonlinear filtering: the projection filter," IEEE Transactions on Automatic Control 43 (1998): 247--252
• Richard S. Bucy, Lectures on Discrete Time Filtering W. Bulatek, M. Lemanczyk and E. Lesigne, "On the Filtering Problem for Stationary Random^2$-Fields", IEEE Transactions on Information Theory 51 (2005): 3586--3593
• Emmanuel Candes and Terence Tao, "Near Optimal Signal Recovery from Random Prjoections and Universal Encoding Strategies", math.CA/0410542
• Pavel Chigansky
  • "On exponential stability of the nonlinear filter for slowly switching Markov chains", math.PR/0411596
  • "An ergodic theorem for filtering with applications to stability", math.PR/0404515
• Pavel Chigansky and Robert Liptser
  • "Stability of nonlinear filters in nonmixing case", math.PR/0304056 = Annals of Applied Probability 14 (2004): 2038--2056
  • "What is always stable in nonlinear filtering?", math.Pr/0504094
• Seungjin Choi, Andrzej Cichocki, Hyung-Min Park, and Soo-Young Lee, "Blind Source Separation and Independent Component Analysis: A Review", Neural Information Processing Letters and Reviews 6 (2005): 1--57
• Alexandre J. Chorin and Paul Krause, "Dimensional reduction for a Bayesian filter", Proceedings of the National Academy of Sciences 101 (2004): 15013--15017 [If I understand their abstract correctly, they're basically saying that you only have to worry about uncertainties along the expanding directions of the dynamics --- uncertainty along the contracting directions is going to go away anyway! Probably it's not that simple...]
• Irene Crimaldi and Luca Pratelli, "Two inequalities for conditional expectations and convergence results for filters", Statistics and Probability Letters 74 (2005): 151--162
• M. H. A. Davis and I. Marcus, "An Introduction to nonlinear filtering," pp. 53--75 in M. Hazewinkel and J. C. Willems (eds.), Stochastic Systems: The Mathematics of Filtering and Identification and Applications
• M. H. A. Davis and P. Varaiya, "Information states for linear stochastic systems," J. Math. Anal. Appl. 37 (1972): 384--402
• Pierre Del Moral
  • "Measure-Valued Processes and Interacting Particle Systems. Application to Nonlinear Filtering Problems", The Annals of Applied Probability 8 (1998): 438--495 [JSTOR]
  • Feynman-Kac Formulae: Genealogical and Interacting Particle Systems [This looks really, really cool]
• Deutsch, Estimation Theory
• G. B. DiMasi and L. Stettner, "Ergodicity of hidden Markov models", Mathematics of Control, Signals, and Systems 17 (2005): 269--296 [Includes consideration of the ergodicity of filters for the HMM]
• C. T. J. Dodson and H. Wang, "Iterative Approximation of Statistical Distributions and Relation to Information Geometry", Statistical Inference for Stochastic Processes 4 (2001): 307--318 ["optimal control of stochastic processes through sensor estimation of probability density functions is given a geometric setting via information theory and the information metric."]
• F. Douarche, L. Buisson, S. Ciliberto and A. Petrosyan, "A Simple Denoising Technique", physics/0406055
• Randal Douc, Olivier Cappé and Eric Moulines, "Comparison of Resampling Schemes for Particle Filtering", cs.CE/0507025
• Randal Douc, Gersende Fort, Eric Moulines and Pierre Priouret, "Forgetting of the initial distribution for Hidden Markov Models", math.ST/0703836
• Randal Douc and France E. Moulines, "Limit theorems for weighted samples with applications to Sequential Monte Carlo Methods", math.ST/0507042 [With application to state-space filtering]
• Gregory L. Eyink and Juan M. Restrepo, "Most Probable Histories for Nonlinear Dynamics: Tracking Climate Transitions", Journal of Statistical Physics 101 (2000): 459--472 [PDF]
• Gregory L. Eyink, Juan M. Restrepo and Francis J. Alexander, "A Statistical-Mechanical Approach to Data Assimilation"
  1. "Analysis Approximations" [PDF]
  2. "Evolution Approximations" [PDF]
  3. "Numerical Algorithms" [PDF]
• R. M. Fernandez-Alcala, J. Navarro-Moreno, and J. C. Ruiz-Molina, "A Unified Approach to Linear Estimation Problems for Nonstationary Processes", IEEE Transactions on Information Theory 51 (2005): 3594--3601
• B. Fristedt, N. Jain and N. Krylov, Filtering and Prediction: A Primer [Blurb]
• Cyril Furtlehner, Jean-Marc Lasgouttes, Arnaud De La Fortelle, "Belief Propagation and Bethe approximation for Traffic Prediction", physics/0703159
• Ramazan Gencay, Faruk Selcuk and Brandon Whitcher, An Introduction to Wavlets and Other Filtering Methods in Finance and Economics
• J. Gough, V. P. Belavkin, and O. G. Smolyanov, "Hamilton-Jacobi-Bellman equations for Quantum Filtering and Control", quant-ph/0502155
• Arnaud Guillin, Randal Douc and Jamal Najim, "Moderate Deviations for Particle Filtering", math.PR/0401058 = Annals of Applied Probability 15 (2005): 587--614
• R. M. Grey and L. D. Davisson, Introduction to Statistical Signal Processing [On-line]
• Dong Guo, Xiaodong Wang and Rong Chen, "New sequential Monte Carlo methods for nonlinear dynamic systems", Statistics and Computing 15 (2005): 135--147
• A. Hannachi, "Probabilitic-based Approach to Optimal Filtering", Physical Review E 61 (2000): 3610--3619
• Jan Hannig and Thomas C. M. Lee, "On Poisson signal estimation under Kullback-Leibler discrepancy and squared risk", Journal of Statistical Planning and Inference 136 (2006): 882--908
• Simon Haykin, José C. Príncipe, Terrence J. Sejnowski and John McWhirter, New Directions in Statistical Signal Processing: From Systems to Brains [Blurb]
• M. Hazewinkel and S. I. Marcus, "On Lie algebras and finite-dimensional filtering" Stochastics 7 (1982): 29--62
• M. Hazewinkel and J. C. Willems (eds.), Stochastic Systems: The Mathematics of Filtering and Identification and Applications
• Aapo Hyvärinen, Juha Karhunen and Erkki Oja, Independent Component Analysis
• V. Ibarra-Junquera, L. A. Torres, H. C. Rosu and J. Collado-Vides, "Monitoring the genetic regulation process with a nonlinear software sensor", q-bio.QM/0409036
• A. Inoue, Y. Nakano and V. Anh, "Linear filtering of systems with memory", math.PR/0407454
• Michael T. Johnson and Richard J. Povinelli, "Generalized phase space projection for nonlinear noise reduction", Physica D 201 (2005): 306--317
• Kevin Judd, "Failure of maximum likelihood methods for chaotic dynamical systems", Physical Review E 75 (2007): 036210 [He means failure for state estimation, not parameter estimation. I wonder if this isn't linked to the old Fox & Keizer papers about amplifying fluctuations in macroscopic chaos?]
• Kevin Judd and Leonard A. Smith
  • "Indistinguishable States I. Perfect Model Scenario", Physica D 151 (2001): 125--141
  • "Indistinguishable States II. The Imperfect Model Scenario", Physica D 196 (2004): 224--242
• Kay, Fundamentals of Statistical Signal Processing [2 vols.]
• R. Khasminskii, "Nonlinear Filtering of Smooth Signals", Stochastics and Dynamics 5 (2005): 27--35
• Sangil Kim, Greg Eyink, Frank Alexander, Juan Restrepo and Greg Johnson, "Ensemble Filtering for Nonlinear Dynamics", Monthly Weather Reveiw 131: 2586--2594 [PDF]
• Arthur J. Krener, "The Convergence of the Extended Kalman Filter," math.OC/0212255, also A. Rantzer and C. I. Byrnes (eds.), Directions in Mathematical Systems Theory and Optimiazation (Berlin: Springer-Verlag, 2002): 173--182
• Venkatarama Krishnan, Nonlinear Filtering and Smoothing: An Introduction to Martingales, Stochastic Integrals and Estimation
• H. J. Kushner
  • "On the differential equations satisfied by conditional probability densities of Markov processes, with applications," J. SIAM Control A2 (1962): 106--119
  • "Approximation to Optimal Nonlinear Filters," IEEE Trans. Auto. Contr. 12 (1967): 546--556
  • Probability Methods for Approximations in Stochastic Control and for Elliptic Equations
• Francois LeGland and Nadia Oudjane
  • "Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters", Annals of Applied Probability 14 (2004): 144--187
  • "A roubstification approach to stability and to uniform particle approximation of nonlinear filters: the example of pseudo-mixing signals", Stochastic Processes and Their Applications 106 (2003): 279--316
• B. C. Levy and R. Nikoukhah, "Robust Least-Squares Estimation with a Relative Entropy Contraint", IEEE Transactions on Information Theory 50 (2004): 89--104
• John M. Lewis, S. Lakshmivarahan and Sudarshan Dhall, Dynamic Data Assimilation: A Least Squares Approach [Blurb]
• Robert S. Liptser and Albert N. Shiryaev, Statistics of Random Processes [2 vols., get 2nd edition]
• Xiaodong Luo, Jie Zhang and Michael Small, "Optimal phase space projection for noise reduction", nlin.CD/0506011
• Andrew J. Majda and Marcus J. Grote, "Explicit off-line criteria for stable accurate time filtering of strongly unstable spatially extended systems", Proceedings of the National Academy of Sciences (USA) 104 (2007): 1124--1129
• W. P. Malcolm, R. J. Elliott and M. R. James, "Risk-Sensitive Filtering and Smoothing for Continuous-Time Markov Processes", IEEE Transactions on Information Theory 51 (2005): 1731--1738
• James Manyika and Hugh Durrant-White, Data Fusion and Sensor Management: A Decentralized Information-Theoretic Approach
• Eddy Mayer-Wolf and Moshe Zakai, "Some relations between mutual information and estimation error on Wiener space", math.PR/0610024
• McDonough and Whalen, Detection of Signals in Noise
• Leonard A. McGee and and Stanley F. Schmidt, "Discovery of the Kalman filter as a practical tool for aerospace and industry", NASA Technical Memorandum 86847 (1 November 1985) [Abstract, with link to scanned full text]
• Sanjoy K. Mitter and Nigel J. Newton, "Information and Entropy Flow in the Kalman-Bucy Filter", Journal of Statistical Physics 118 (2005): 145--176 [This looks rather strange, from the abstract, but potentially interesting...]
• Jun Morimoto and Kenji Doya, "Reinforcement Learning State Estimator", Neural Computation 19 (2007): 730--756
• Jose M. F. Moura and Sanjoy K. Mitter, "Identification and Filtering: Optimal Recursive Maximum Likelihood Approach" [1986 technical report from MIT, found looking for something else, original URL now lost --- presumably since published. Memo to self: (1) definitely read this; (2) look up publication.]
• D. Napoletani, C. A. Berenstein, T. Sauer, D. C. Struppa and D. Walnut, "Delay-Coordinates Embeddings as a Data Mining Tool for Denoising Speech Signals", physics/0504155
• V. Olshevsky and L. Sakhnovich, "Matched Filtering for Generalized Stationary Processes", IEEE Transactions on Information Theory 51 (2005): 3308--3313
• Jimmy Olsson, Olivier Cappe, Dandal Douc and Eric Moulines, "Sequential Monte Carlo smoothing with application to parameter estimation in non-linear state space models", math.ST/0609514
• Edward Ott, Brian R. Hunt, Istvan Szunyogh, Matteo Corazza, Eugenia Kalnay, D. J. Patil, and James A. Yorke, "Exploiting Local Low Dimensionality of the Atmospheric Dynamics for Efficient Ensemble Kalman Filtering," physics/0203058
• E. Ott, B. R. Hunt, I. Szunyogh, A. V. Zimin, E. J. Kostelich, M. Corazza, E. Kalnay, D.J. Patil and J.A. Yorke, "Estimating the state of large spatio-temporally chaotic systems", Physics Letters A 330 (2004): 365--370
• Francescco Paparella, "Filling gaps in chaotic time series", Physics Letters A 346 (2005): 47--53
• Anastasia Papavasiliou, "Particle Filters for Multiscale Diffusions", arxiv:0710.5098
• W. J. Runggaldier and F. Spizzichino, "Sufficient conditions for finite dimensionality of filters in discrete time: A Laplace transform-based approach," Bernoulli 7 (2001): 211--221
• Simo S\"arkk\"a and Tommi Sottinen, "Application of Girsanov Theorem to Particle Filtering of Discretely Observed Continuous-Time Non-Linear Systems", arxiv:0705.1598
• G. Sawitzki, "Finite-dimensional filters in discrete time," Stochastics 5 (1981): 107--114
• M. M. Seron, J. H. Braslavsky and G. C. Goodwin, Fundamental Limitations in Filtering and Control [Website, with full-text PDF and errata]
• Steven T. Smith, "Covariance, Subspace, and Intrinsic Cramer-Rao Bounds", IEEE Transactions on Signal Processing forthcoming [Preprint kindly provided by Dr. Smith]
• Victor Solo and Xuan Kong, Adaptive Signal Processing Algorithms: Stability and Performance
• D. Sornette and K. Ide, "The Kalman-Levy filter," cond-mat/0004369
• R. L. Stratonovich
  • "Conditional Markov Processes," Theoretical Probability and Its Applications 5 (1960): 156--178
  • Conditional Markov Processes and Their Application to the Theory of Optimal Control
• Youngchul Sung, Lang Tong and H. Vincent Poor, "Neyman-Pearson Detection of Gauss-Markov Signals in Noise: Closed-Form Error Exponent and Properties", cs.IT/0506028
• Vladislav B. Tadic and Arnaud Doucet, "Exponential forgetting and geometric ergodicity for optimal filtering in general state-space models", Stochastic Processes and their Applications 115 (2005): 1408--1436
• Hisashi Tanizaki, Nonlinear Filters
• Anatoli Torokhti and Phil Howlett, "Method of recurrent best estimators of second degree for optimal filtering of random signals," Signal Processing 83 (2003): 1013--1024
• Ferdinand van der Heijden, Robert Duin, Dick de Ridder and David M. J. Tax, Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB [MATLAB doesn't do it for me, but this looks like it might be a good survey]
• T. Weissman, "How to Filter an `Individual Sequence with Feedback'", IEEE Transactions on Information Theory 54 (2008): 3831--3841
• J. C. Willems, "Some remarks on the concept of information state," pp. 285--295 in O. L. R. Jacobs (ed.), Analysis and Optimization of Stochastic Systems
• Carl Wunsch, Discrete Inverse and State Estimation Problems: With Geophysical Fluid Applications [Blurb]
• Jie Xiong, An Introduction to Stochastic Filtering Theory [blurb]
• G. G. Yin and V. Kirshnamurthy, "LMS Algorithms for Tracking Slow Markov Chains With Applications to Hidden Markov Estimation and Adaptive Multiuser Detection", IEEE Transactions on Information Theory 51 (2005): 2475--2490
• Abdelhak M. Zoubir and D. Robert Iskander, Bootstrap Techniques for Signal Processing