American Institute of Mathematical Sciences

December  2020, 7(2): 209-241. doi: 10.3934/jcd.2020009

An incremental approach to online dynamic mode decomposition for time-varying systems with applications to EEG data modeling

 Electrical and Computer Engineering Department, Michigan State University, East Lansing, MI 48824, USA

Received  September 2019 Published  July 2020

Fund Project: This work has been supported by NSF Award IIS-1734272

Dynamic Mode Decomposition (DMD) is a data-driven technique to identify a low dimensional linear time invariant dynamics underlying high-dimensional data. For systems in which such underlying low-dimensional dynamics is time-varying, a time-invariant approximation of such dynamics computed through standard DMD techniques may not be appropriate. We focus on DMD techniques for such time-varying systems and develop incremental algorithms for systems without and with exogenous control inputs. We build upon the work in [35] to scenarios in which high dimensional data are governed by low dimensional time-varying dynamics. We consider two classes of algorithms that rely on (ⅰ) a discount factor on previous observations, and (ⅱ) a sliding window of observations. Our algorithms leverage existing techniques for incremental singular value decomposition and allow us to determine an appropriately reduced model at each time and are applicable even if data matrix is singular. We apply the developed algorithms for autonomous systems to Electroencephalographic (EEG) data and demonstrate their effectiveness in terms of reconstruction and prediction. Our algorithms for non-autonomous systems are illustrated using randomly generated linear time-varying systems.

Citation: Mustaffa Alfatlawi, Vaibhav Srivastava. An incremental approach to online dynamic mode decomposition for time-varying systems with applications to EEG data modeling. Journal of Computational Dynamics, 2020, 7 (2) : 209-241. doi: 10.3934/jcd.2020009
References:
 [1] M. Brand, Incremental singular value decomposition of uncertain data with missing values, in European Conference on Computer Vision, Springer, 2002,707–720. [2] M. Brand, Fast low-rank modifications of the thin singular value decomposition, Linear Algebra Appl., 415 (2006), 20-30.  doi: 10.1016/j.laa.2005.07.021. [3] B. W. Brunton, L. A. Johnson, J. G. Ojemann and J. N. Kutz, Extracting spatial–temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition, Journal of Neuroscience Methods, 258 (2016), 1-15. [4] R. Chavarriaga and J. D. R. Millán, Learning from EEG error-related potentials in noninvasive brain-computer interfaces, IEEE Transactions on Neural Systems and Rehabilitation Engineering, 18 (2010), 381-388.  doi: 10.1109/TNSRE.2010.2053387. [5] R. Chavarriaga, A. Sobolewski and J. D. R. Millán, Errare machinale est: The use of error-related potentials in brain-machine interfaces, Frontiers in Neuroscience, 8 (2014), 208. doi: 10.3389/fnins.2014.00208. [6] X. Chen and K. S. Candan, LWI-SVD: Low-rank, windowed, incremental singular value decompositions on time-evolving data sets, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2014,987–996. doi: 10.1145/2623330.2623671. [7] A. C. Costa, T. Ahamed and G. J. Stephens, Adaptive, locally linear models of complex dynamics, Proc. Natl. Acad. Sci. USA, 116 (2019), 1501-1510.  doi: 10.1073/pnas.1813476116. [8] A. Delorme and S. Makeig, EEGLAB: An open source toolbox for analysis of single-trial eeg dynamics including independent component analysis, Journal of Neuroscience Methods, 134 (2004), 9-21.  doi: 10.1016/j.jneumeth.2003.10.009. [9] P. W. Ferrez and J. d. R. Millán, Error-related EEG potentials generated during simulated brain–computer interaction, IEEE Transactions on Biomedical Engineering, 55 (2008), 923-929.  doi: 10.1109/TBME.2007.908083. [10] J. Grosek and J. N. Kutz, Dynamic mode decomposition for real-time background/foreground separation in video, arXiv preprint, arXiv: 1404.7592. [11] M. Gu and S. C. Eisenstat, A Stable and Fast Algorithm for Updating the Singular Value Decomposition, Technical Report YALEU/DCS/RR-966, Department of Computer Science, Yale University, New Haven, CT, 1993. [12] M. Hemati, E. Deem, M. Williams, C. W. Rowley and L. N. Cattafesta, Improving separation control with noise-robust variants of dynamic mode decomposition, in 54th AIAA Aerospace Sciences Meeting, (2016), 1103. doi: 10.2514/6.2016-1103. [13] M. S. Hemati, M. O. Williams and C. W. Rowley, Dynamic mode decomposition for large and streaming datasets, Physics of Fluids, 26 (2014), 111701. doi: 10.1063/1.4901016. [14] T. K. Huckle, Efficient computation of sparse approximate inverses, Numer. Linear Algebra Appl., 5 (1998), 57-71.  doi: 10.1002/(SICI)1099-1506(199801/02)5:1<57::AID-NLA129>3.0.CO;2-C. [15] R. Isermann and M. Münchhof, Identification of Dynamic Systems: An Introduction with Applications, Springer, Heidelberg, 2011. doi: 10.1007/978-3-540-78879-9. [16] S. M. Kay, Fundamentals of Statistical Signal Processing, Prentice Hall PTR, 1993. [17] B. O. Koopman, Hamiltonian systems and transformation in Hilbert space, Proceedings of the National Academy of Sciences, 17 (1931), 315-318.  doi: 10.1073/pnas.17.5.315. [18] M. Korda and I. Mezić, Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control, Automatica J. IFAC, 93 (2018), 149-160.  doi: 10.1016/j.automatica.2018.03.046. [19] J. N. Kutz, S. L. Brunton, B. W. Brunton and J. L. Proctor, Dynamic Mode Decomposition: Data-Driven Modeling of Complex Systems, vol. 149, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2016. doi: 10.1137/1.9781611974508. [20] S. Maćešić, N. Črnjarić-Žic and I. Mezić, Koopman operator family spectrum for nonautonomous systems-part 1, arXiv preprint, arXiv: 1703.07324. [21] D. Matsumoto and T. Indinger, On-the-fly algorithm for dynamic mode decomposition using incremental singular value decomposition and total least squares, arXiv preprint, arXiv: 1703.11004. [22] C. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719512. [23] I. Mezić, Spectral properties of dynamical systems, model reduction and decompositions, Nonlinear Dynam., 41 (2005), 309-325.  doi: 10.1007/s11071-005-2824-x. [24] I. Mezić, Analysis of fluid fows via spectral properties of the Koopman operator, Annual Review of Fluid Mechanics, 45 (2013), 357-378.  doi: 10.1146/annurev-fluid-011212-140652. [25] I. Mezić and A. Banaszuk, Comparison of systems with complex behavior, Phys. D, 197 (2004), 101-133.  doi: 10.1016/j.physd.2004.06.015. [26] G. M. Oxberry, T. Kostova-Vassilevska, W. Arrighi and K. Chand, Limited-memory adaptive snapshot selection for proper orthogonal decomposition, Internat. J. Numer. Methods Engrg., 109 (2017), 198-217.  doi: 10.1002/nme.5283. [27] J. L. Proctor, S. L. Brunton and J. N. Kutz, Dynamic mode decomposition with control, SIAM J. Appl. Dyn. Syst., 15 (2016), 142-161.  doi: 10.1137/15M1013857. [28] J. L. Proctor and P. A. Eckhoff, Discovering dynamic patterns from infectious disease data using dynamic mode decomposition, International Health, 7 (2015), 139-145.  doi: 10.1093/inthealth/ihv009. [29] C. W. Rowley, I. Mezić, S. Bagheri, P. Schlatter and D. S. Henningson, Spectral analysis of nonlinear flows, J. Fluid Mech., 641 (2009), 115-127.  doi: 10.1017/S0022112009992059. [30] P. J. Schmid, Dynamic mode decomposition of numerical and experimental data, J. Fluid Mech., 656 (2010), 5-28.  doi: 10.1017/S0022112010001217. [31] J. Sherman and W. J. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics, 21 (1950), 124-127.  doi: 10.1214/aoms/1177729893. [32] A. Surana, Koopman operator based nonlinear dynamic textures, in 2015 American Control Conference (ACC), IEEE, 2015, 1333–1338. doi: 10.1109/ACC.2015.7170918. [33] J. H. Tu, C. W. Rowley, D. M. Luchtenburg, S. L. Brunton and J. N. Kutz, On dynamic mode decomposition: Theory and applications, J. Comput. Dyn., 1 (2014), 391-421.  doi: 10.3934/jcd.2014.1.391. [34] M. O. Williams, I. G. Kevrekidis and C. W. Rowley, A data–driven approximation of the Koopman operator: Extending dynamic mode decomposition, J. Nonlinear Sci., 25 (2015), 1307-1346.  doi: 10.1007/s00332-015-9258-5. [35] H. Zhang, C. W. Rowley, E. A. Deem and L. N. Cattafesta, Online dynamic mode decomposition for time-varying systems, SIAM J. Appl. Dyn. Syst., 18 (2019), 1586-1609.  doi: 10.1137/18M1192329.

show all references

References:
 [1] M. Brand, Incremental singular value decomposition of uncertain data with missing values, in European Conference on Computer Vision, Springer, 2002,707–720. [2] M. Brand, Fast low-rank modifications of the thin singular value decomposition, Linear Algebra Appl., 415 (2006), 20-30.  doi: 10.1016/j.laa.2005.07.021. [3] B. W. Brunton, L. A. Johnson, J. G. Ojemann and J. N. Kutz, Extracting spatial–temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition, Journal of Neuroscience Methods, 258 (2016), 1-15. [4] R. Chavarriaga and J. D. R. Millán, Learning from EEG error-related potentials in noninvasive brain-computer interfaces, IEEE Transactions on Neural Systems and Rehabilitation Engineering, 18 (2010), 381-388.  doi: 10.1109/TNSRE.2010.2053387. [5] R. Chavarriaga, A. Sobolewski and J. D. R. Millán, Errare machinale est: The use of error-related potentials in brain-machine interfaces, Frontiers in Neuroscience, 8 (2014), 208. doi: 10.3389/fnins.2014.00208. [6] X. Chen and K. S. Candan, LWI-SVD: Low-rank, windowed, incremental singular value decompositions on time-evolving data sets, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2014,987–996. doi: 10.1145/2623330.2623671. [7] A. C. Costa, T. Ahamed and G. J. Stephens, Adaptive, locally linear models of complex dynamics, Proc. Natl. Acad. Sci. USA, 116 (2019), 1501-1510.  doi: 10.1073/pnas.1813476116. [8] A. Delorme and S. Makeig, EEGLAB: An open source toolbox for analysis of single-trial eeg dynamics including independent component analysis, Journal of Neuroscience Methods, 134 (2004), 9-21.  doi: 10.1016/j.jneumeth.2003.10.009. [9] P. W. Ferrez and J. d. R. Millán, Error-related EEG potentials generated during simulated brain–computer interaction, IEEE Transactions on Biomedical Engineering, 55 (2008), 923-929.  doi: 10.1109/TBME.2007.908083. [10] J. Grosek and J. N. Kutz, Dynamic mode decomposition for real-time background/foreground separation in video, arXiv preprint, arXiv: 1404.7592. [11] M. Gu and S. C. Eisenstat, A Stable and Fast Algorithm for Updating the Singular Value Decomposition, Technical Report YALEU/DCS/RR-966, Department of Computer Science, Yale University, New Haven, CT, 1993. [12] M. Hemati, E. Deem, M. Williams, C. W. Rowley and L. N. Cattafesta, Improving separation control with noise-robust variants of dynamic mode decomposition, in 54th AIAA Aerospace Sciences Meeting, (2016), 1103. doi: 10.2514/6.2016-1103. [13] M. S. Hemati, M. O. Williams and C. W. Rowley, Dynamic mode decomposition for large and streaming datasets, Physics of Fluids, 26 (2014), 111701. doi: 10.1063/1.4901016. [14] T. K. Huckle, Efficient computation of sparse approximate inverses, Numer. Linear Algebra Appl., 5 (1998), 57-71.  doi: 10.1002/(SICI)1099-1506(199801/02)5:1<57::AID-NLA129>3.0.CO;2-C. [15] R. Isermann and M. Münchhof, Identification of Dynamic Systems: An Introduction with Applications, Springer, Heidelberg, 2011. doi: 10.1007/978-3-540-78879-9. [16] S. M. Kay, Fundamentals of Statistical Signal Processing, Prentice Hall PTR, 1993. [17] B. O. Koopman, Hamiltonian systems and transformation in Hilbert space, Proceedings of the National Academy of Sciences, 17 (1931), 315-318.  doi: 10.1073/pnas.17.5.315. [18] M. Korda and I. Mezić, Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control, Automatica J. IFAC, 93 (2018), 149-160.  doi: 10.1016/j.automatica.2018.03.046. [19] J. N. Kutz, S. L. Brunton, B. W. Brunton and J. L. Proctor, Dynamic Mode Decomposition: Data-Driven Modeling of Complex Systems, vol. 149, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2016. doi: 10.1137/1.9781611974508. [20] S. Maćešić, N. Črnjarić-Žic and I. Mezić, Koopman operator family spectrum for nonautonomous systems-part 1, arXiv preprint, arXiv: 1703.07324. [21] D. Matsumoto and T. Indinger, On-the-fly algorithm for dynamic mode decomposition using incremental singular value decomposition and total least squares, arXiv preprint, arXiv: 1703.11004. [22] C. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719512. [23] I. Mezić, Spectral properties of dynamical systems, model reduction and decompositions, Nonlinear Dynam., 41 (2005), 309-325.  doi: 10.1007/s11071-005-2824-x. [24] I. Mezić, Analysis of fluid fows via spectral properties of the Koopman operator, Annual Review of Fluid Mechanics, 45 (2013), 357-378.  doi: 10.1146/annurev-fluid-011212-140652. [25] I. Mezić and A. Banaszuk, Comparison of systems with complex behavior, Phys. D, 197 (2004), 101-133.  doi: 10.1016/j.physd.2004.06.015. [26] G. M. Oxberry, T. Kostova-Vassilevska, W. Arrighi and K. Chand, Limited-memory adaptive snapshot selection for proper orthogonal decomposition, Internat. J. Numer. Methods Engrg., 109 (2017), 198-217.  doi: 10.1002/nme.5283. [27] J. L. Proctor, S. L. Brunton and J. N. Kutz, Dynamic mode decomposition with control, SIAM J. Appl. Dyn. Syst., 15 (2016), 142-161.  doi: 10.1137/15M1013857. [28] J. L. Proctor and P. A. Eckhoff, Discovering dynamic patterns from infectious disease data using dynamic mode decomposition, International Health, 7 (2015), 139-145.  doi: 10.1093/inthealth/ihv009. [29] C. W. Rowley, I. Mezić, S. Bagheri, P. Schlatter and D. S. Henningson, Spectral analysis of nonlinear flows, J. Fluid Mech., 641 (2009), 115-127.  doi: 10.1017/S0022112009992059. [30] P. J. Schmid, Dynamic mode decomposition of numerical and experimental data, J. Fluid Mech., 656 (2010), 5-28.  doi: 10.1017/S0022112010001217. [31] J. Sherman and W. J. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics, 21 (1950), 124-127.  doi: 10.1214/aoms/1177729893. [32] A. Surana, Koopman operator based nonlinear dynamic textures, in 2015 American Control Conference (ACC), IEEE, 2015, 1333–1338. doi: 10.1109/ACC.2015.7170918. [33] J. H. Tu, C. W. Rowley, D. M. Luchtenburg, S. L. Brunton and J. N. Kutz, On dynamic mode decomposition: Theory and applications, J. Comput. Dyn., 1 (2014), 391-421.  doi: 10.3934/jcd.2014.1.391. [34] M. O. Williams, I. G. Kevrekidis and C. W. Rowley, A data–driven approximation of the Koopman operator: Extending dynamic mode decomposition, J. Nonlinear Sci., 25 (2015), 1307-1346.  doi: 10.1007/s00332-015-9258-5. [35] H. Zhang, C. W. Rowley, E. A. Deem and L. N. Cattafesta, Online dynamic mode decomposition for time-varying systems, SIAM J. Appl. Dyn. Syst., 18 (2019), 1586-1609.  doi: 10.1137/18M1192329.
Topographical view for EEG channels with the channel FCz, where the ErrPs can be characterized, marked in red bold font
The average response to an event at $t = 0$: the mean ERP (confidence level = $95\%$) at the FCz channel (left panel) and the topographical view for brain activity across all channels (right panel). The top and middle panels show the patterns during the correct event and the erroneous event, respectively. The bottom panel shows that ErrP obtained by subtracting the signal associated with the correct event from that of the erroneous event. The topographical views are shown at the three characterizing peaks that occur at $200$ msec, $260$ msec, and $360$ msec, respectively
The mean of the normalized RMS prediction error computed over all iterations as well as the associated 95% confidence sets for (a) correct events and (b) erroneous events
Normalized RMS error for a future-window of $64$ samples of EEG states at channel FCz using incremental DMD with $\sigma_{\text{thr}} = 0.01$ (left panel), incremental DMD with $\sigma_{\text{thr}} = 0.001$ (middle panel), and online DMD (right panel) for (a) correct event, and (b) erroneous event
Predicted ERP signal at channel FCz using incremental DMD with $\sigma_{\text{thr}} = 0.01$ (left panel), incremental DMD with $\sigma_{\text{thr}} = 0.001$ (middle panel), and online DMD (right panel) for (a) correct event, and (b) erroneous event
Normalized RMS error for the predicted ERP signal at channel FCz for correct events (left panel) and erroneous events (right panel), using (a) incremental DMD, and (b) online DMD
Normalized RMS error of ERP prediction using weighted incremental DMD with initial window of $128$ samples during (a) correct event, and (b) Erroneous event
Normalized RMS error of ERP prediction using windowed incremental DMD with different window sizes during (a) correct event, and (b) Erroneous event
The predicted ERP signal at channel FCz based on well conditioned EEG datasets using incremental DMD model (left panel) and online DMD model (right panel) during (a) correct events and (b) erroneous events
Topographical views for the real part part of the $4$ dominant DMD modes during correct events using threshold values of (a) $\sigma_{\text{thr}} = 0.01$, and (b) $\sigma_{\text{thr}} = 0.001$
Topographical views for the real part of the $4$ dominant DMD modes during erroneous events using threshold values of (a) $\sigma_{\text{thr}} = 0.01$, and (b) $\sigma_{\text{thr}} = 0.001$
The left panel show the continuous time DMD eigenvalues for $\sigma_{\text{thr}} = 0.01$ and the right panel shows the continuous time DMD eigenvalues for $\sigma_{\text{thr}} = 0.001$ during (a) correct events (b) erroneous events
Reconstructed ERP signal at channel FCz using incremental DMD with $\sigma_{thr} = 0.01$ (left panel), incremental DMD with $\sigma_{thr} = 0.001$ (middle panel), and online DMD (right panel) for (a) correct events and (b) erroneous events.
Normalized RMS error for the reconstructed ERP signal at channel FCz for correct events (left panel) and erroneous events (right panel), using (a) incremental DMD, and (b) online DMD
The Frobenius norm of prediction error for a future-window of 10 samples using (a) weighted incremental DMD (red line) and weighted incremental DMDc(blue line), and (b) windowed incremental DMD (red line) and windowed incremental DMDc (blue line)

Impact Factor: