The Living Thing / Notebooks :

State space reconstruction

Disclaimer: I know basically nothing about this.

But I think it’s something like: Looking at the data from a, possibly stochastic, dynamical system. and hoping to infer cool things about the kinds of hidden states it has, in some general sense, such as some measure of statistical of computational complexity, or how complicated or “large” the underlying state space, in some convenient representation, is.

TBH I don’t understand this framing, but possibly because I don’t come from a dynamical systems group; I just dabble in special cases thereof. Surely you either do physics, and work out the dynamics of your system from experiment, or you do statistics and select an appropriate model to minimise some estimated predictive loss trading off data set, model complexity and algorithmic complexity. I need to read more to understand the rationale here, clearly.

Anyway, tools here seem to include inventing large spaces of hidden states (Takens embedding); does this get us some nice algebraic properties? Also, how does delay embedding relate? Is that the same? (Further bonus question - did SiJR04 rediscover delay embedding, or have they extended it?) Sample complexity results here seem to be scanty, possibly because they usually want their chaos to be deterministic and admitting noise would be fiddly.

OTOH, from a statistical perspective there are lots of useful techniques to infer special classes of dynamical systems state-space, even with nonlinear dynamics. e.g. in plain old model-based count time series such as branching processes, and grammatical inference of formal syntax, and nonlinear system identification.

I would be interested to see a compelling new insight from the dynamical system perspective on these problems. New estimators; models outside the ken of Kalman filters?

Stuff that I might actually use

Hirata’s reconstruction looks like good clean decorative fun - you can represent graphs by an equivalent dynamical system.


Badii, R., & Politi, A. (1999) Complexity: Hierarchical Structures and Scaling in Physics. . Cambridge University Press
Crutchfield, J. P.(1994) Critical Computation, Phase Transitions, and Hierarchical Learning. In Towards the Harnessing of Chaos, Amsterdam. Elsevier Science Publishers B. V.
Crutchfield, J. P., & Young, K. (1989) Inferring statistical complexity. Physical Review Letters, 63(2), 105–108. DOI.
Donner, R. V., Zou, Y., Donges, J. F., Marwan, N., & Kurths, J. (2010) Recurrence networks—a novel paradigm for nonlinear time series analysis. New Journal of Physics, 12(3), 033025. DOI.
Glazier, J. A., & Libchaber, A. (1988) Quasi-periodicity and dynamical systems: An experimentalist’s view. IEEE Transactions on Circuits and Systems, 35(7), 790–809. DOI.
Grassberger, P., Schreiber, T., & Schaffrath, C. (1991) Nonlinear time sequence analysis. International Journal of Bifurcation and Chaos, 1(3), 521–547. DOI.
Herzel, H. (1988) Complexity of symbol sequences. Syst. Anal. Model. Simul., 5(5), 435–444.
Hirata, Y., & Aihara, K. (2010) Identifying hidden common causes from bivariate time series: A method using recurrence plots. Physical Review E, 81(1), 016203. DOI.
Hirata, Y., Horai, S., & Aihara, K. (2008) Reproduction of distance matrices and original time series from recurrence plots and their applications. The European Physical Journal Special Topics, 164(1), 13–22. DOI.
Hirata, Y., Judd, K., & Kilminster, D. (2004) Estimating a generating partition from observed time series: Symbolic shadowing. Physical Review E, 70(1), 016215. DOI.
Hirata, Y., Suzuki, H., & Aihara, K. (2006) Reconstructing state spaces from multivariate data using variable delays. Physical Review E, 74(2), 026202. DOI.
Iwayama, K., Hirata, Y., Takahashi, K., Watanabe, K., Aihara, K., & Suzuki, H. (2012) Characterizing global evolutions of complex systems via intermediate network representations. Scientific Reports, 2. DOI.
Kantz, H., & Schreiber, T. (2004) Nonlinear time series analysis. (2nd ed.). Cambridge, UK ; New York: Cambridge University Press
Nichkawde, C. (2013) Optimal state-space reconstruction using derivatives on projected manifold. Physical Review E, 87(2), 022905. DOI.
Pitt, L. (1989) Inductive inference, DFAs, and computational complexity. In K. Jantke (Ed.), Analogical and Inductive Inference (Vol. 397, pp. 18–44). Springer Berlin / Heidelberg
Rudary, M., Singh, S., & Wingate, D. (2005) Predictive Linear-Gaussian Models of Stochastic Dynamical Systems. In arXiv:1207.1416 [cs].
Schreiber, T., & Schmitz, A. (2000) Surrogate time series. Physica D: Nonlinear Phenomena, 142(3-4), 346–382. DOI.
Shalizi, C. R., & Crutchfield, J. P.(2000) Computational Mechanics: Pattern and Prediction, Structure and Simplicity.
Shalizi, C. R., & Crutchfield, J. P.(2002) Information Bottlenecks, Causal States, And Statistical Relevance Bases: How To Represent Relevant Information In Memoryless Transduction. Advances in Complex Systems (ACS), 5(01), 91–95.
Shalizi, C. R., & Shalizi, K. L.(2004) Blind construction of optimal nonlinear recursive predictors for discrete sequences. (pp. 504–511). Presented at the Proceedings of the 20th conference on Uncertainty in artificial intelligence
Shalizi, C. R., Shalizi, K. L., & Crutchfield, J. P.(2002) An Algorithm for Pattern Discovery in Time Series. arXiv:cs/0210025.
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
Stark, J., Broomhead, D. S., Davies, M. E., & Huke, J. (2003) Delay Embeddings for Forced Systems II Stochastic Forcing. Journal of Nonlinear Science, 13(6), 519–577. DOI.
Theiler, J. (1990) Estimating fractal dimension. J. Opt. Soc. Am. A, 7(6), 1055–1073.
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.