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.

Refs

BaPo99
Badii, R., & Politi, A. (1999) Complexity: Hierarchical Structures and Scaling in Physics. . Cambridge University Press
Crut94
Crutchfield, J. P.(1994) Critical Computation, Phase Transitions, and Hierarchical Learning. In Towards the Harnessing of Chaos, Amsterdam. Elsevier Science Publishers B. V.
CrYo89
Crutchfield, J. P., & Young, K. (1989) Inferring statistical complexity. Physical Review Letters, 63(2), 105–108. DOI.
DZDM10
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.
GlLi88
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.
GrSS91
Grassberger, P., Schreiber, T., & Schaffrath, C. (1991) Nonlinear time sequence analysis. International Journal of Bifurcation and Chaos, 1(3), 521–547. DOI.
Herz88
Herzel, H. (1988) Complexity of symbol sequences. Syst. Anal. Model. Simul., 5(5), 435–444.
HiAi10
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.
HiHA08
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.
HiJK04
Hirata, Y., Judd, K., & Kilminster, D. (2004) Estimating a generating partition from observed time series: Symbolic shadowing. Physical Review E, 70(1), 016215. DOI.
HiSA06
Hirata, Y., Suzuki, H., & Aihara, K. (2006) Reconstructing state spaces from multivariate data using variable delays. Physical Review E, 74(2), 026202. DOI.
IHTW12
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.
KaSc04
Kantz, H., & Schreiber, T. (2004) Nonlinear time series analysis. (2nd ed.). Cambridge, UK ; New York: Cambridge University Press
Nich13
Nichkawde, C. (2013) Optimal state-space reconstruction using derivatives on projected manifold. Physical Review E, 87(2), 022905. DOI.
Pitt89
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
RuSW05
Rudary, M., Singh, S., & Wingate, D. (2005) Predictive Linear-Gaussian Models of Stochastic Dynamical Systems. In arXiv:1207.1416 [cs].
ScSc00
Schreiber, T., & Schmitz, A. (2000) Surrogate time series. Physica D: Nonlinear Phenomena, 142(3-4), 346–382. DOI.
ShCr00
Shalizi, C. R., & Crutchfield, J. P.(2000) Computational Mechanics: Pattern and Prediction, Structure and Simplicity.
ShCr02
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.
ShSh04
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
ShSC02
Shalizi, C. R., Shalizi, K. L., & Crutchfield, J. P.(2002) An Algorithm for Pattern Discovery in Time Series. arXiv:cs/0210025.
SiJR04
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
SBDH03
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.
Thei90
Theiler, J. (1990) Estimating fractal dimension. J. Opt. Soc. Am. A, 7(6), 1055–1073.
WoJS05
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.