## 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.

See also: Manifold Learning

- 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)

- To read:
- 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