×

Dynamic mode decomposition in vector-valued reproducing kernel Hilbert spaces for extracting dynamical structure among observables. (English) Zbl 1441.37092

Summary: Understanding nonlinear dynamical systems (NLDSs) is challenging in a variety of engineering and scientific fields. Dynamic mode decomposition (DMD), which is a numerical algorithm for the spectral analysis of Koopman operators, has been attracting attention as a way of obtaining global modal descriptions of NLDSs without requiring explicit prior knowledge. However, since existing DMD algorithms are in principle formulated based on the concatenation of scalar observables, it is not directly applicable to data with dependent structures among observables, which take, for example, the form of a sequence of graphs. In this paper, we formulate Koopman spectral analysis for NLDSs with structures among observables and propose an estimation algorithm for this problem. This method can extract and visualize the underlying low-dimensional global dynamics of NLDSs with structures among observables from data, which can be useful in understanding the underlying dynamics of such NLDSs. To this end, we first formulate the problem of estimating spectra of the Koopman operator defined in vector-valued reproducing kernel Hilbert spaces, and then develop an estimation procedure for this problem by reformulating tensor-based DMD. As a special case of our method, we propose the method named as Graph DMD, which is a numerical algorithm for Koopman spectral analysis of graph dynamical systems, using a sequence of adjacency matrices. We investigate the empirical performance of our method by using synthetic and real-world data.

MSC:

37M99 Approximation methods and numerical treatment of dynamical systems
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alaa, A. M.; van der Schaar, M., Bayesian inference of individualized treatment effects using multi-task gaussian processes, (Advances in neural information processing systems, Vol. 30 (2017)), 3424-3432
[2] Álvarez, M. A.; Rosasco, L.; Lawrence, N. D., Kernels for vector-valued functions: A review, Foundations and Trends® in Machine Learning, 4, 3, 195-266 (2012) · Zbl 1301.68212
[3] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: Structure and dynamics, Physics Reports, 424, 4-5, 175-308 (2006) · Zbl 1371.82002
[4] Brunton, B. W.; Johnson, L. A.; Ojemann, J. G.; Kutz, J. N., Extracting spatial-temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition, Journal of Neuroscience Methods, 258, 1-15 (2016)
[5] Bullmore, E.; Sporns, O., Complex brain networks: graph theoretical analysis of structural and functional systems, Nature Reviews Neuroscience, 10, 3, 186-198 (2009)
[6] Caponnetto, A.; Micchelli, C. A.; Pontil, M.; Ying, Y., Universal multi-task kernels, Journal of Machine Learning Research (JMLR), 9, Jul, 1615-1646 (2008) · Zbl 1225.68155
[7] Centola, D.; Macy, M., Complex contagions and the weakness of long ties, American Journal of Sociology, 113, 3, 702-734 (2007)
[8] Chung, F. R., Spectral graph theory, Vol. 92 (1997), American Mathematical Soc. · Zbl 0867.05046
[9] Cliff, O. M.; Prokopenko, M.; Fitch, R., An information criterion for inferring coupling of distributed dynamical systems, Frontiers in Robotics and AI, 3, 71 (2016)
[10] Couzin, I. D.; Krause, J.; James, R.; Ruxton, G. D.; Franks, N. R., Collective memory and spatial sorting in animal groups, Journal of Theoretical Biology, 218, 1, 1-11 (2002)
[11] Defferrard, M.; Bresson, X.; Vandergheynst, P., Convolutional neural networks on graphs with fast localized spectral filtering, (Advances in neural information processing systems, Vol. 29 (2016)), 3844-3852
[12] Evgeniou, T.; Micchelli, C. A.; Pontil, M., Learning multiple tasks with kernel methods, Journal of Machine Learning Research (JMLR), 6, Apr, 615-637 (2005) · Zbl 1222.68197
[13] Evgeniou, T.; Pontil, M., Regularized multi – task learning, (ACM SIGKDD international conference on knowledge discovery and data mining (KDD’04) (2004), ACM), 109-117
[14] Fujii, K.; Inaba, Y.; Kawahara, Y., Koopman spectral kernels for comparing complex dynamics: Application to multiagent sport plays, (European conference on machine learning and knowledge discovery in databases (ECML-PKDD’17) (2017), Springer), 127-139
[15] Fujii, K.; Kawahara, Y., Supervised dynamic mode decomposition via multitask learning, Pattern Recognition Letters, 122, 1, 7-13 (2019)
[16] Fujii, K.; Kawasaki, T.; Inaba, Y.; Kawahara, Y., Prediction and classification in equation-free collective motion dynamics, PLoS Computational Biology, 14, 11, Article e1006545 pp. (2018)
[17] Fujii, K.; Takeishi, N.; Kibushi, B.; Kouzaki, M.; Kawahara, Y., Data-driven spectral analysis for coordinative structures in periodic systems with unknown and redundant dynamics, bioRxiv, 511642 (2019)
[18] Fujii, K.; Yokoyama, K.; Koyama, T.; Rikukawa, A.; Yamada, H.; Yamamoto, Y., Resilient help to switch and overlap hierarchical subsystems in a small human group, Scientific Reports, 6 (2016)
[19] Giannakis, D., Ourmazd, A., Slawinska, J., & Zhao, Z. (2017). Spatiotemporal pattern extraction by spectral analysis of vector-valued observables, arXiv preprint arXiv:1711.02798; Giannakis, D., Ourmazd, A., Slawinska, J., & Zhao, Z. (2017). Spatiotemporal pattern extraction by spectral analysis of vector-valued observables, arXiv preprint arXiv:1711.02798
[20] Grasedyck, L.; Kressner, D.; Tobler, C., A literature survey of low-rank tensor approximation techniques, GAMM-Mitteilungen, 36, 1, 53-78 (2013) · Zbl 1279.65045
[21] Heersink, B., Warren, M. A., & Hoffmann, H. (2017). Dynamic mode decomposition for interconnected control systems, arXiv preprint arXiv:1709.02883; Heersink, B., Warren, M. A., & Hoffmann, H. (2017). Dynamic mode decomposition for interconnected control systems, arXiv preprint arXiv:1709.02883
[22] Hojo, M.; Fujii, K.; Inaba, Y.; Motoyasu, Y.; Kawahara, Y., Automatically recognizing strategic cooperative behaviors in various situations of a team sport, PLoS One, 13, 12, Article e0209247 pp. (2018)
[23] Idé, T.; Kashima, H., Eigenspace-based anomaly detection in computer systems, (ACM SIGKDD international conference on knowledge discovery and data mining (KDD’04) (2004), ACM), 440-449
[24] Kawahara, Y., Dynamic mode decomposition with reproducing kernels for koopman spectral analysis, (Advances in neural information processing systems, Vol. 29 (2016)), 911-919
[25] Klus, S.; Gelß, P.; Peitz, S.; Schütte, C., Tensor-based dynamic mode decomposition, Nonlinearity, 31, 7, 3359 (2018) · Zbl 1404.65313
[26] Koopman, B. O., Hamiltonian systems and transformation in hilbert space, Proceedings of the National Academy of Sciences, 17, 5, 315-318 (1931) · Zbl 0002.05701
[27] Kuhlman, C. J.; Kumar, V. A.; Marathe, M. V.; Mortveit, H. S.; Swarup, S.; Tuli, G., A general-purpose graph dynamical system modeling framework, (Winter simulation conference (WSC’11) (2011), IEEE), 296-308
[28] Kutz, J.; Fu, X.; Brunton, S. L., Multiresolution dynamic mode decomposition, SIAM Journal on Applied Dynamical Systems, 15, 2, 713-735 (2016) · Zbl 1338.37121
[29] Liu, W.; Zha, Z.-J.; Wang, Y.; Lu, K.; Tao, D., \(p\)-Laplacian Regularized sparse coding for human activity recognition, IEEE Transactions on Industrial Electronics, 63, 8, 5120-5129 (2016)
[30] Mezić, I., Spectral properties of dynamical systems, model reduction and decompositions, Nonlinear Dynamics, 41, 1, 309-325 (2005) · Zbl 1098.37023
[31] Micchelli, C. A.; Pontil, M., Kernels for multi – task learning, (Advances in neural information processing systems, Vol. 17 (2005)), 921-928
[32] Micchelli, C. A.; Pontil, M., On learning vector-valued functions, Neural Computation, 17, 1, 177-204 (2005) · Zbl 1092.93045
[33] Mortveit, H. S.; Reidys, C. M., Discrete, sequential dynamical systems, Discrete Mathematics, 226, 1-3, 281-295 (2001) · Zbl 1004.05056
[34] Mortveit, H.; Reidys, C., An introduction to sequential dynamical systems (2007), Springer Science & Business Media
[35] Oseledets, I. V., Tensor-train decomposition, SIAM Journal on Scientific Computing, 33, 5, 2295-2317 (2011) · Zbl 1232.15018
[36] Proctor, J. L.; Brunton, S. L.; Kutz, J., Dynamic mode decomposition with control, SIAM Journal on Applied Dynamical Systems, 15, 1, 142-161 (2016) · Zbl 1334.65199
[37] Proctor, J. L.; Eckhoff, P. A., Discovering dynamic patterns from infectious disease data using dynamic mode decomposition, International Health, 7, 2, 139-145 (2015)
[38] Quang, M. H.; Kang, S. H.; Le, T. M., Image and video colorization using vector-valued reproducing kernel Hilbert spaces, Journal of Mathematical Imaging and Vision, 37, 1, 49-65 (2010) · Zbl 1392.94042
[39] Rowley, C. W.; Mezić, I.; Bagheri, S.; Schlatter, P.; Henningson, D. S., Spectral analysis of nonlinear flows, Journal of Fluid Mechanics, 641, 115-127 (2009) · Zbl 1183.76833
[40] Schmid, P. J., Dynamic mode decomposition of numerical and experimental data, Journal of Fluid Mechanics, 656, 5-28 (2010) · Zbl 1197.76091
[41] Schrödl, S. J., Operator-valued reproducing kernels and their application in approximation and statistical learning (2009), Technische Universität München, (Ph.D. thesis) · Zbl 1198.47001
[42] Seo, Y., Defferrard, M., Vandergheynst, P., & Bresson, X. (2017). Structured sequence modeling with graph convolutional recurrent networks, arXiv preprint arXiv:1612.07659; Seo, Y., Defferrard, M., Vandergheynst, P., & Bresson, X. (2017). Structured sequence modeling with graph convolutional recurrent networks, arXiv preprint arXiv:1612.07659
[43] Susuki, Y.; Mezić, I., Nonlinear koopman modes and coherency identification of coupled swing dynamics, IEEE Transactions on Power Systems, 26, 4, 1894-1904 (2011)
[44] Susuki, Y.; Mezić, I., Nonlinear Koopman modes and power system stability assessment without models, IEEE Transactions on Power Systems, 29, 2, 899-907 (2014)
[45] Takeishi, N.; Kawahara, Y.; Tabei, Y.; Yairi, T., Bayesian dynamic mode decomposition, (International joint conference on artificial intelligence (IJCAI’17) (2017)), 2814-2821
[46] Takeishi, N.; Kawahara, Y.; Yairi, T., Learning koopman invariant subspaces for dynamic mode decomposition, (Advances in neural information processing systems, Vol. 30 (2017)), 1130-1140
[47] Takeishi, N.; Kawahara, Y.; Yairi, T., Sparse nonnegative dynamic mode decomposition, (2017 IEEE international conference on image processing (ICIP’17) (2017), IEEE), 2682-2686
[48] Takeishi, N.; Kawahara, Y.; Yairi, T., Subspace dynamic mode decomposition for stochastic Koopman analysis, Physical Review E, 96, 033310 (2017)
[49] Takeuchi, K.; Kawahara, Y.; Iwata, T., Structurally regularized non-negative tensor factorization for spatio-temporal pattern discoveries, (European conference on machine learning and knowledge discovery in databases (ECML-PKDD’17) (2017), Springer), 582-598
[50] Taubin, G., A signal processing approach to fair surface design, (International conference on computer graphics and interactive techniques (SIGGRAPH’95) (1995), ACM), 351-358
[51] Tu, J. H.; Rowley, C. W.; Luchtenburg, D. M.; Brunton, S. L.; Kutz, J. N., On dynamic mode decomposition: Theory and applications, Journal of Computational Dynamics, 1, 2, 391-421 (2014) · Zbl 1346.37064
[52] Vicsek, T.; Czirók, A.; Ben-Jacob, E.; Cohen, I.; Shochet, O., Novel type of phase transition in a system of self-driven particles, Physical Review Letters, 75, 6, 1226-1229 (1995)
[53] Williams, M. O.; Kevrekidis, I. G.; Rowley, C. W., A data-driven approximation of the koopman operator: Extending dynamic mode decomposition, Journal of Nonlinear Science, 25, 6, 1307-1346 (2015) · Zbl 1329.65310
[54] Wu, C. W., Synchronization in networks of nonlinear dynamical systems coupled via a directed graph, Nonlinearity, 18, 3, 1057-1064 (2005) · Zbl 1089.37024
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.