Notebooks

## State-Space Reconstruction

16 Jul 2016 12:48

An aspect of time series analysis: given that the time series came from a dynamical system, figure out the state space of that system from observation alone.

Here's the basic set-up. Suppose we have a deterministic dynamical system with state $z(t)$ on a smooth manifold of dimension $m$, evolving according to a nice system of differential equations, $\dot{z}(t) = f(z(t))$. What we observe is not the state $z(t)$ but rather a smooth, instantaneous function of the state, $x(t) = g(z(t))$. Now, it should be obvious that in this set-up $z$ is only going to be identified up to a smooth change of coordinates --- basically because we can use any coordinate system we like on the hidden manifold, without changing anything at all. What is surprising is that the system can, in fact, be identified up to a smooth, invertible change of coordinates (i.e., a diffeomorphism).

Fix a finite length of time $\tau$ and a whole number $k$, and set $s(t) = \left(x(t), x(t-\tau), x(t-2\tau), \ldots x(t-(k-1)\tau)\right)$

For generic choices of $f, g$ and $\tau$, if $k \geq 2m+1$ , then $z(t) = \phi(s(t))$. This $\phi$ is smooth and invertible (a diffeomorphism), and commutes with time-evolution, $\frac{d}{dt}\phi(s(t)) = f(\phi(s(t)))$. Indeed, regressing $\dot{s}(t)$ on $s(t)$ will give $\phi^{-1} \circ f$.

The first publication this subject was that by Packard et al. The first proof that this can work was that of Takens, which remains the standard reference. A footnote in Packard et al. leads me to believe that the idea may actually have originated with David Ruelle.

I am especially interested in ways of making this idea work for stochastic systems.

Recommended (big picture):
• Holger Kantz and Thomas Schreiber, Nonlinear Time Series Analysis [An excellent presentation of the nonlinear dynamical systems approach, which comes out of physics]
• Norman H. Packard, James P. Crutchfield, J. Doyne Farmer and Robert S. Shaw, "Geomtry from a Time Series," Physical Review Letters 45 (1980): 712--716
• David Ruelle, Chaotic Evolution and Strange Attractors: The Statistical Analysis of Deterministic Nonlinear Systems [From notes prepared by Stefano Isola]
• Floris Takens, "Detecting Strange Attractors in Fluid Turbulence", pp. 366--381 in D. A. Rand and L. S. Young (eds.), Symposium on Dynamical Systems and Turbulence (Springer Lecture Notes in Mathematics vol. 898; 1981)
Recommended (close-ups):
• Markus Abel, Karsten Ahnert, Jürgen Kurths and Simon Mandelj, "Additive nonparametric reconstruction of dynamical systems from time series", Physical Review E 71 (2005): 015203 [Thanks to Prof. Kürths for a reprint]
• James P. Crutchfield and Karl Young, "Inferring Statistical Complexity", Physical Review Letters 63 (1989): 105--108 [PDF reprint via Jim]
• Kevin Judd, "Chaotic-time-series reconstruction by the Bayesian paradigm: Right results by wrong methods," Physical Review E 67 (2003): 026212 [Word.]
• G. Langer and U. Parlitz, "Modeling parameter dependence from time series", Physical Review E 70 (2004): 056217
• J. Stark, D. S. Broomhead, M. E. Davies and J. Huke, "Takens embedding theorems for forced and stochastic systems", Nonlinear Analysis 30 (1997): 5303--5314 [Unfortunately, the stochastic case is handled by treating it as forcing by a shift map on sequence space, which is an infinite-dimensional space... Thanks to Martin Nilsson Jacobi for telling me about this.]
• J. Timmer, H. Rust, W. Horbelt and H. U. Voss, "Parametric, nonparametric and parametric modelling of a chaotic circuit time series," nlin.cd/0009040
Modesty forbids me:
• CRS and Kristina Lisa Klinkner, "Blind Construction of Optimal Nonlinear Predictors for Discrete Sequences", cs.LG/0406011 = pp. 504--511 of Uncertainty in Artificial Intelligence: Proceedings of the Twentieth Conference (UAI 2004)
• Frank Boettcher, Joachim Peinke, David Kleinhans, Rudolf Friedrich, Pedro G. Lind, and Maria Haase, "On the proper reconstruction of complex dynamical systems spoilt by strong measurement noise", nlin.CD/0607002
• Abraham Boyarsky and Pawel Gora, "Chaotic maps derived from trajectory data", Chaos 12 (2002): 42--48
• Toby S. Cubitt, Jens Eisert, Michael M. Wolf, "Extracting dynamical equations from experimental data is NP-hard", Physical Review Letters 108 (2012): 120503, arxiv:1005.0005
• Cees Diks, Nonlinear Time Series Analysis: Methods and Applications
• Sara P. Garcia and Jonas S. Almedia, "Multivariate phase space reconstruction by nearest neighbor embedding with different time delays", nlin.CD/0609029 = Physical Review E 72 (2006): 027205
• Gershenfeld and Weigend (eds.), Time Series Prediction: Forecasting the Future and Understanding the Past
• Joachim Holzfuss, "Prediction of long-term dynamics from transients", Physical Review E 71 (2005): 016214 [State-space reconstruction by experimentation, rather than just observation. Sounds very cool.]
• S. Ishii and M.-A. Sato, "Reconstruction of chaotic dynamics by on-line EM algorithm," Neural Networks 14 (2001): 1239--1256
• Kevin Judd and Tomomichi Nakamura, "Degeneracy of time series models: The best model is not always the correct model", Chaos 16 (2006): 033105
• Claudia Lainscsek and Terrence J. Sejnowski, "Delay Differential Analysis of Time Series", Neural Computation 27 (2015): 594--614
• A. P. Nawroth and J. Peinke, "Multiscale reconstruction of time series", physics/0608069
• Andrew B. Nobel and Terrence M. Adams, "Estimating a function from ergodic samples with additive noise", IEEE Transactions on Information Theory 47 (2001): 2895--2902
• Louis M. Pecora, Linda Moniz, Jonathan Nichols, Thomas L. Carroll, "A Unified Approach to Attractor Reconstruction", arxiv:0602048
• James C. Robinson, "A topological delay embedding theorem for infinite-dimensional dynamical systems", Nonlinearity 18 (2005): 2135--2143 ["A time delay reconstruction theorem inspired by that of Takens ... is shown to hold for finite-dimensional subsets of infinite-dimensional spaces, thereby generalizing previous results which were valid only for subsets of finite-dimensional spaces."]
• Michael Small
• Applied Nonlinear Time Series Analysis: Applications in Physics, Physiology and Finance
• "Optimal time delay embedding for nonlinear time series modeling", nlin.CD/0312011
• Michael Small and C. K. Tse, "Optimal embedding parameters: A modeling paradigm", physics/0308114
• Ronen Talmon and Ronald R. Coifman, "Empirical intrinsic geometry for nonlinear modeling and time series filtering", Proceedings of the National Academy of Sciences (USA) 110 (2013): 12535--12540