×

Simplicial multivalued maps and the witness complex for dynamical analysis of time series. (English) Zbl 1320.37034

Summary: Topology-based analysis of time-series data from dynamical systems is powerful: it potentially allows for computer-based proofs of the existence of various classes of regular and chaotic invariant sets for high-dimensional dynamics. Standard methods are based on a cubical discretization of the dynamics and use the time series to construct an outer approximation of the underlying dynamical system. The resulting multivalued map can be used to compute the Conley index of isolated invariant sets of cubes. In this paper we introduce a discretization that uses instead a simplicial complex constructed from a witness-landmark relationship. The goal is to obtain a natural discretization that is more tightly connected with the invariant density of the time series itself. The time-ordering of the data also directly leads to a map on this simplicial complex that we call the witness map. We obtain conditions under which this witness map gives an outer approximation of the dynamics and thus can be used to compute the Conley index of isolated invariant sets. The method is illustrated by a simple example using data from the classical Hénon map.

MSC:

37M10 Time series analysis of dynamical systems
65P20 Numerical chaos
55U10 Simplicial sets and complexes in algebraic topology
37C70 Attractors and repellers of smooth dynamical systems and their topological structure

Software:

CHomP

References:

[1] Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, and P. Pilarczyk, {\it A database schema for the analysis of global dynamics of multiparameter systems}, SIAM J. Appl. Dyn. Syst., 8 (2009), pp. 757-789. · Zbl 1186.37021
[2] A.W. Baker, {\it Lower bounds on entropy via the Conley index with applications to time series}, Topol. App., 120 (2002), pp. 333-354. · Zbl 1004.54025
[3] K. Borsuk, {\it On the imbedding of systems of compacta in simplicial complexes}, Fund. Math., 35 (1948), pp. 217-234; also available online from http://matwbn.icm.edu.pl/ksiazki/fm/fm35/fm35119.pdf. · Zbl 0032.12303
[4] R. Bott and L.W. Tu, {\it Differential Forms in Algebraic Topology}, Grad. Texts in Math. 82, Springer, Berlin, 1982. · Zbl 0496.55001
[5] C. Conley, {\it Isolated Invariant Sets and the Morse Index}, CBMS Reg. Conf. Ser. Math. 38, AMS, Providence, RI, 1978. · Zbl 0397.34056
[6] C.J.A. Delfinado and H. Edelsbrunner, {\it An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere}, Comput. Aided Geom. Design, 12 (1995), pp. 771-784. · Zbl 0873.55007
[7] S. Day, R. Frongillo, and R. Trevin͂o, {\it Algorithms for rigorous entropy bounds and symbolic dynamics}, SIAM J. Appl. Dyn. Syst., 7 (2008), pp. 1477-1506. · Zbl 1171.37011
[8] S. Day, O. Junge, and K. Mischaikow, {\it A rigorous numerical method for the global analysis of infinite-dimensional discrete dynamical systems}, SIAM J. Appl. Dyn. Syst., 3 (2004), pp. 117-160. · Zbl 1059.37068
[9] C.H. Dowker, {\it Homology groups of relations}, Ann. of Math. (2), 56 (1952), pp. 84-95. · Zbl 0046.40402
[10] V. de Silva, {\it A weak characterisation of the Delaunay triangulation}, Geom. Dedicata, 135 (2008), pp. 39-64. · Zbl 1165.52014
[11] V. de Silva and E. Carlsson, {\it Topological estimation using witness complexes}, in Proceedings of the 1st Eurographics Symposium on Point-Based Graphics, M. Alexa and S. Rusinkiewicz, eds., The Eurographics Association, Zürich, Switzerland, 2004, pp. 157-166.
[12] V. de Silva and R. Ghrist, {\it Coverage in sensor networks via persistent homology}, Algebr. Geom. Topol., 7 (2007), pp. 339-358. · Zbl 1134.55003
[13] R.W. Easton, {\it Geometric Methods for Discrete Dynamical Systems}, Oxford University Press, Oxford, UK, 1998.
[14] H. Edelsbrunner, {\it The union of balls and its dual shape}, Discrete Comput. Geom., 13 (1995), pp. 415-440. · Zbl 0826.68053
[15] H. Edelsbrunner and J. Harer, {\it Persistent homology: A survey}, in Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemp. Math. 453, J.E. Goodman, J. Pach, and R. Pollack, eds., AMS, Providence, RI, 2008, pp. 257-282. · Zbl 1145.55007
[16] H. Edelsbrunner and E.P. Mücke, {\it Three-dimensional alpha shapes}, in Proceedings of the 1992 Workshop on Volume Visualization, ACM, New York, 1992, pp. 75-82. · Zbl 0806.68107
[17] J.H. Friedman, J.L. Bentley, and R.A. Finkel, {\it An algorithm for finding best matches in logarithmic expected time}, ACM Trans. Math. Software, 3 (1977), pp. 209-226. · Zbl 0364.68037
[18] J. Franks and D. Richeson, {\it Shift equivalence and the Conley index}, Trans. Amer. Math. Soc., 352 (2000), pp. 3305-3322. · Zbl 0956.37010
[19] R. Ghrist, {\it Barcodes: The persistent topology of data}, Bull. Amer. Math. Soc. (N.S.), 45 (2008), pp. 61-75. · Zbl 1391.55005
[20] A. Hatcher, {\it Algebraic Topology}, Cambridge University Press, Cambridge, UK, 2002. · Zbl 1044.55001
[21] M. Hénon, {\it A two-dimensional mapping with a strange attractor}, Comm. Math. Phys., 50 (1976), pp. 69-77. · Zbl 0576.58018
[22] T. Kaczynski, K. Mischaikow, and M. Mrozek, {\it Computational Homology}, Appl. Math. Sci. 157, Springer-Verlag, New York, 2004. · Zbl 1039.55001
[23] W.D. Kalies, K. Mischaikow, and R. VanderVorst, {\it An algorithmic approach to chain recurrence}, Found. Comput. Math., 5 (2005), pp. 409-449. · Zbl 1099.37010
[24] D.P. Lathrop and E.J. Kostelich, {\it Characterization of an experimental strange attractor by periodic orbits}, Phys. Rev. A, 40 (1989), pp. 4028-4031.
[25] E.N. Lorenz, {\it Deterministic nonperiodic flow}, J. Atmospheric Sci., 20 (1963), pp. 130-141. · Zbl 1417.37129
[26] K. Mischaikow, {\it CHomP: Computational Homology Project}, http://chomp.rutgers.edu (2014).
[27] K. Mischaikow and M. Mrozek, {\it Chaos in the Lorenz equations: A computer-assisted proof}, Bull. Amer. Math. Soc., 32 (1995), pp. 66-72. · Zbl 0820.58042
[28] K. Mischaikow and M. Mrozek, {\it Conley index theory}, in Handbook of Dynamical Systems, Volume 2, North-Holland, Amsterdam, 2002, pp. 393-460. · Zbl 1035.37010
[29] K. Mischaikow, M. Mrozek, J. Reiss, and A. Szymczak, {\it Construction of symbolic dynamics from experimental time series}, Phys. Rev. Lett., 82 (1999), pp. 1144-1147; also available online from http://link.aps.org/doi/10.1103/PhysRevLett.82.1144.
[30] K. Mischaikow, M. Mrozek, A. Szymczak, and J. Reiss, {\it From Time Series to Symbolic Dynamics: An Algebraic Topological Approach}, Technical report, Georgia Institute of Technology, Atlanta, GA, 1997, http://www.math.rutgers.edu/.
[31] M. Mrozek, {\it An algorithmic approach to the Conley index theory}, J. Dynam. Differential Equations, 11 (1999), pp. 711-734. · Zbl 0941.37004
[32] J.R. Munkres, {\it Elements of Algebraic Topology}, Benjamin/Cummings, Menlo Park, CA, 1984. · Zbl 0673.55001
[33] N.H. Packard, J.P. Crutchfield, J.D. Farmer, and R.S. Shaw, {\it Geometry from a time series}, Phys. Rev. Lett., 45 (1980), pp. 712-716.
[34] V. Robins, {\it Towards computing homology from finite approximations}, Topology Proc., 24 (1999), pp. 503-532; also available online from http://at.yorku.ca/b/a/a/k/28.htm. · Zbl 1026.55009
[35] T. Sauer, J.A. Yorke, and M. Casdagli, {\it Embedology}, J. Stat. Phys., 65 (1991), pp. 579-616. · Zbl 0943.37506
[36] F. Takens, {\it Detecting strange attractors in turbulence}, in Dynamical Systems and Turbulence (Warwick, 1980), Lecture Notes in Math. 898, D. Rand and L.-S. Young, eds., Springer, Berlin, Heidelberg, 1981, pp. 366-381. · Zbl 0513.58032
[37] A. Weil, {\it Sur les théorémes de Rham}, Comment. Math. Helv., 26 (1952), pp. 119-145. · Zbl 0047.16702
[38] A.J. Zomorodian, {\it Fast construction of the Vietoris-Rips complex}, Computers & Graphics-UK, 34 (2010), pp. 263-271.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.