State space reconstruction

October 14, 2014 — August 30, 2022

count data
dynamical systems
stringology
time series

Disclaimer: I know next to 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 or 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 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? Sample complexity results 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. It is especially interesting in grammatical inference of formal syntax where there are many lovely and faintly depressing computational complexity results.

2 Stuff that I might actually use

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

3 Incoming

4 References

Badii, and Politi. 1999. Complexity: Hierarchical Structures and Scaling in Physics. Cambridge Nonlinear Science Series.
Brunton, Proctor, and Kutz. 2016. “Discovering Governing Equations from Data by Sparse Identification of Nonlinear Dynamical Systems.” Proceedings of the National Academy of Sciences.
Charles, Balavoine, and Rozell. 2016. “Dynamic Filtering of Time-Varying Sparse Signals via L1 Minimization.” IEEE Transactions on Signal Processing.
Chen, Huang, Raghupathi, et al. 2022. “Automated Discovery of Fundamental Variables Hidden in Experimental Data.” Nature Computational Science.
Crutchfield, and Young. 1989. “Inferring Statistical Complexity.” Physical Review Letters.
Dupont, Denis, and Esposito. 2005. “Links Between Probabilistic Automata and Hidden Markov Models: Probability Distributions, Learning Models and Induction Algorithms.” Pattern Recognition.
Foote. 1999. “Visualizing Music and Audio Using Self-Similarity.” In Proceedings of the Seventh ACM International Conference on Multimedia (Part 1). MULTIMEDIA ’99.
Grassberger, Schreiber, and Schaffrath. 1991. “Nonlinear Time Sequence Analysis.” International Journal of Bifurcation and Chaos.
Hamilton, Berry, and Sauer. 2016. “Kalman-Takens Filtering in the Presence of Dynamical Noise.” arXiv:1611.05414 [Physics, Stat].
Hirata, Horai, and Aihara. 2008. “Reproduction of Distance Matrices and Original Time Series from Recurrence Plots and Their Applications.” The European Physical Journal Special Topics.
Hirata, Suzuki, and Aihara. 2006. “Reconstructing State Spaces from Multivariate Data Using Variable Delays.” Physical Review E.
Kantz, and Schreiber. 2004. Nonlinear Time Series Analysis.
Levin. 2017. “The Inner Structure of Time-Dependent Signals.” arXiv:1703.08596 [Cs, Math, Stat].
Marwan. 2008. “A Historical Review of Recurrence Plots.” The European Physical Journal Special Topics.
Peña, and Kalnay. 2004. “Separating fast and slow modes in coupled chaotic systems.” Nonlinear Processes in Geophysics.
Pol, and Diaconescu. 2023. “A Data-Driven Approach for Modeling Unknown Multi-Scale Systems.” In 2023 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion (ACSOS-C).
Shalizi, and Crutchfield. 2000. “Computational Mechanics: Pattern and Prediction, Structure and Simplicity.”
Shalizi, and Crutchfield. 2002. “Information Bottlenecks, Causal States, and Statistical Relevance Bases: How to Represent Relevant Information in Memoryless Transduction.” Advances in Complex Systems.
Shalizi, and Shalizi. 2004. “Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences.” In.
Sugihara, May, Ye, et al. 2012. “Detecting Causality in Complex Ecosystems.” Science.
Tan, Algar, Corrêa, et al. 2023. “Network Representations of Attractors for Change Point Detection.” Communications Physics.
Tan, Corrêa, Stemler, et al. 2021. “Grading Your Models: Assessing Dynamics Learning of Models Using Persistent Homology.” Chaos: An Interdisciplinary Journal of Nonlinear Science.
———, et al. 2024. “A Backpropagation Algorithm for Inferring Disentagled Nodal Dynamics and Connectivity Structure of Dynamical Networks.” IEEE Transactions on Network Science and Engineering.