×

Randomized dynamic mode decomposition. (English) Zbl 1427.65410

Summary: This paper presents a randomized algorithm for computing the near-optimal low-rank dynamic mode decomposition (DMD). Randomized algorithms are emerging techniques to compute low-rank matrix approximations at a fraction of the cost of deterministic algorithms, easing the computational challenges arising in the area of “big data”. The idea is to derive a small matrix from the high-dimensional data, which is then used to efficiently compute the dynamic modes and eigenvalues. The algorithm is presented in a modular probabilistic framework, and the approximation quality can be controlled via oversampling and power iterations. The effectiveness of the resulting randomized DMD algorithm is demonstrated on several benchmark examples of increasing complexity, providing an accurate and efficient approach to extract spatiotemporal coherent structures from big data in a framework that scales with the intrinsic rank of the data, rather than the ambient measurement dimension. For this work we assume that the dynamics of the problem under consideration is evolving on a low-dimensional subspace that is well characterized by a quickly decaying singular value spectrum.

MSC:

65P99 Numerical problems in dynamical systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
37M10 Time series analysis of dynamical systems
37N10 Dynamical systems in fluid mechanics, oceanography and meteorology

Software:

RSVDPACK; RandNLA; ARPACK
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H. Arbabi and I. Mezić, Ergodic theory, dynamic mode decomposition, and computation of spectral properties of the Koopman operator, SIAM J. Appl. Dyn. Syst., 16 (2017), pp. 2096-2126, https://doi.org/10.1137/17M1125236. · Zbl 1381.37096
[2] J. Basley, L. R. Pastur, N. Delprat, and F. Lusseyran, Space-time aspects of a three-dimensional multi-modulated open cavity flow, Phys. Fluids, 25 (2013), 064105.
[3] E. Berger, M. Sastuba, D. Vogt, B. Jung, and H. B. Amor, Estimation of perturbations in robotic behavior using dynamic mode decomposition, J. Adv. Robotics, 29 (2015), pp. 331-343.
[4] G. Berkooz, P. Holmes, and J. L. Lumley, The proper orthogonal decomposition in the analysis of turbulent flows, Ann. Rev. Fluid Mech., 23 (1993), pp. 539-575.
[5] D. Bistrian and I. Navon, Randomized dynamic mode decomposition for nonintrusive reduced order modelling, Internat. J. Numer. Methods Engrg., 112 (2017), pp. 3-25, https://doi.org/10.1002/nme.5499.
[6] D. Bistrian and I. Navon, Efficiency of randomised dynamic mode decomposition for reduced order modelling, Int. J. Comput. Fluid Dyn., 32 (2018), pp. 88-103. · Zbl 07474458
[7] 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, J. Neurosci. Methods, 258 (2016), pp. 1-15.
[8] S. L. Brunton and J. N. Kutz, Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control, Cambridge University Press, 2018.
[9] S. L. Brunton and B. R. Noack, Closed-loop turbulence control: Progress and challenges, Appl. Mech. Rev., 67 (2015), 050801.
[10] S. L. Brunton, J. L. Proctor, J. H. Tu, and J. N. Kutz, Compressed sensing and dynamic mode decomposition, J. Comput. Dyn., 2 (2015), pp. 165-191. · Zbl 1347.94012
[11] D. B. Chirila, Towards Lattice Boltzmann Models for Climate Sciences: The GeLB Programming Language with Applications, Ph.D. thesis, University of Bremen, 2018, https://elib.suub.uni-bremen.de/peid/D00106468.html.
[12] T. Colonius and K. Taira, A fast immersed boundary method using a nullspace approach and multi-domain far-field boundary conditions, Comput. Methods Appl. Mech. Engrg., 197 (2008), pp. 2131-2146. · Zbl 1158.76395
[13] S. Das and D. Giannakis, Delay-Coordinate Maps and the Spectra of Koopman Operators, preprint, https://arxiv.org/abs/1706.08544, 2017.
[14] S. T. Dawson, M. S. Hemati, M. O. Williams, and C. W. Rowley, Characterizing and correcting for the effect of sensor noise in the dynamic mode decomposition, Experiments in Fluids, 57 (2016), pp. 1-19.
[15] P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff, Fast approximation of matrix coherence and statistical leverage, J. Mach. Learn. Res., 13 (2012), pp. 3475-3506. · Zbl 1437.65030
[16] P. Drineas and M. W. Mahoney, RANDNLA: Randomized numerical linear algebra, Comm. ACM, 59 (2016), pp. 80-90, https://doi.org/10.1145/2842602.
[17] P. Drineas and M. W. Mahoney, Lectures on Randomized Numerical Linear Algebra, preprint, https://arxiv.org/abs/1712.08880, 2017.
[18] Z. Drmač and S. Gugercin, A new selection operator for the discrete empirical interpolation method–improved a priori error bound and extensions, SIAM J. Sci. Comput., 38 (2016), pp. A631-A648, https://doi.org/10.1137/15M1019271. · Zbl 1382.65193
[19] D. Duke, J. Soria, and D. Honnery, An error analysis of the dynamic mode decomposition, Experiments in Fluids, 52 (2012), pp. 529-542.
[20] N. B. Erichson, S. L. Brunton, and J. N. Kutz, Compressed dynamic mode decomposition for background modeling, J. Real-Time Image Process., 16 (2019), pp. 1479-1492, https://doi.org/10.1007/s11554-016-0655-2.
[21] N. B. Erichson and C. Donovan, Randomized low-rank dynamic mode decomposition for motion detection, Comput. Vision Image Understanding, 146 (2016), pp. 40-50, https://doi.org/10.1016/j.cviu.2016.02.005.
[22] J. E. Fowler, Compressive-projection principal component analysis, IEEE Trans. Image Process., 18 (2009), pp. 2230-2242, https://doi.org/10.1109/TIP.2009.2025089. · Zbl 1371.94130
[23] A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank approximations, J. ACM, 51 (2004), pp. 1025-1041. · Zbl 1125.65005
[24] M. Gavish and D. L. Donoho, The optimal hard threshold for singular values is \(4 \sqrt{3} \), IEEE Trans. Inform. Theory, 60 (2014), pp. 5040-5053. · Zbl 1360.94071
[25] I. F. Gorodnitsky and B. D. Rao, Analysis of error produced by truncated SVD and Tikhonov regularization methods, in Proceedings of 28th Asilomar Conference on Signals, Systems and Computers, IEEE, 1994, pp. 25-29.
[26] M. Gu, Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37 (2015), pp. A1139-A1173, https://doi.org/10.1137/130938700. · Zbl 1328.65088
[27] F. Guéniat, L. Mathelin, and L. Pastur, A dynamic mode decomposition approach for large and arbitrarily sampled systems, Phys. Fluids, 27 (2015), 025113.
[28] N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217-288, https://doi.org/10.1137/090771806. · Zbl 1269.65043
[29] P. C. Hansen, The truncated SVD as a method for regularization, BIT, 27 (1987), pp. 534-553. · Zbl 0633.65041
[30] P. C. Hansen, Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM J. Sci. Statist. Comput., 11 (1990), pp. 503-518, https://doi.org/10.1137/0911028. · Zbl 0699.65029
[31] P. C. Hansen, J. G. Nagy, and D. P. O’leary, Deblurring Images: Matrices, Spectra, and Filtering, Fundam. Algorithms 3, SIAM, Philadelphia, 2006, https://doi.org/10.1137/1.9780898718874. · Zbl 1112.68127
[32] P. C. Hansen, T. Sekii, and H. Shibahashi, The modified truncated SVD method for regularization in general form, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 1142-1150, https://doi.org/10.1137/0913066. · Zbl 0760.65044
[33] M. S. Hemati, C. W. Rowley, E. A. Deem, and L. N. Cattafesta, De-biasing the dynamic mode decomposition for applied Koopman spectral analysis, Theoret. Comput. Fluid Dynam., 31 (2017), pp. 349-368.
[34] P. J. Holmes, J. L. Lumley, G. Berkooz, and C. W. Rowley, Turbulence, Coherent Structures, Dynamical Systems and Symmetry, 2nd ed., Cambridge Monogr. Mech., Cambridge University Press, Cambridge, UK, 2012. · Zbl 1251.76001
[35] W. B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemp. Math., 26 (1984), pp. 189-206, https://doi.org/10.1090/conm/026/737400. · Zbl 0539.46017
[36] B. Kramer, P. Grover, P. Boufounos, M. Benosman, and S. Nabi, Sparse Sensing and DMD Based Identification of Flow Regimes and Bifurcations in Complex Flows, preprint, https://arxiv.org/abs/1510.02831, 2015. · Zbl 1373.37185
[37] J. N. Kutz, S. L. Brunton, B. W. Brunton, and J. L. Proctor, Dynamic Mode Decomposition: Data-Driven Modeling of Complex Systems, SIAM, Philadelphia, 2016, https://doi.org/10.1137/1.9781611974508. · Zbl 1365.65009
[38] J. N. Kutz, X. Fu, and S. L. Brunton, Multiresolution dynamic mode decomposition, SIAM J. Appl. Dynam. Syst., 15 (2016), pp. 713-735, https://doi.org/10.1137/15M1023543. · Zbl 1338.37121
[39] J. N. Kutz, X. Fu, S. L. Brunton, and N. B. Erichson, Multi-resolution dynamic mode decomposition for foreground/background separation and object tracking, in 2015 IEEE International Conference on Computer Vision Workshop (ICCVW), 2015, pp. 921-929.
[40] R. Lehoucq, D. Sorensen, and C. Yang, ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, Software Environ. Tools 6, SIAM, 1998, https://doi.org/10.1137/1.9780898719628. · Zbl 0901.65021
[41] F. Lusseyran, F. Gueniat, J. Basley, C. L. Douay, L. R. Pastur, T. M. Faure, and P. J. Schmid, Flow coherent structures and frequency signature: Application of the dynamic modes decomposition to open cavity flow, J. Phys. Conf. Ser., 318 (2011), 042036.
[42] P. Ma, M. W. Mahoney, and B. Yu, A statistical perspective on algorithmic leveraging, J. Mach. Learn. Res., 16 (2015), pp. 861-911. · Zbl 1337.62164
[43] M. W. Mahoney, Randomized algorithms for matrices and data, Found. Trends Mach. Learn., 3 (2011), pp. 123-224, https://doi.org/10.1561/2200000035. · Zbl 1232.68173
[44] K. Manohar, B. W. Brunton, J. N. Kutz, and S. L. Brunton, Data-driven sparse sensor placement, IEEE Control Syst. Mag., 38 (2018), pp. 63-86. · Zbl 1477.93128
[45] P.-G. Martinsson, Randomized Methods for Matrix Computations, preprint, https://arxiv.org/abs/1607.01649, 2016.
[46] P.-G. Martinsson and S. Voronin, A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices, SIAM J. Sci. Comput., 38 (2016), pp. S485-S507, https://doi.org/10.1137/15M1026080. · Zbl 1352.65095
[47] B. R. Noack, W. Stankiewicz, M. Morzynski, and P. J. Schmid, Recursive dynamic mode decomposition of a transient cylinder wake, J. Fluid Mech., 809 (2016), pp. 843-872. · Zbl 1383.76122
[48] D. L. Phillips, A technique for the numerical solution of certain integral equations of the first kind, J. ACM, 9 (1962), pp. 84-97. · Zbl 0108.29902
[49] J. L. Proctor, S. L. Brunton, and J. N. Kutz, Dynamic mode decomposition with control, SIAM J. Appl. Dyn. Syst., 15 (2016), pp. 142-161, https://doi.org/10.1137/15M1013857. · Zbl 1334.65199
[50] J. L. Proctor and P. A. Eckhoff, Discovering dynamic patterns from infectious disease data using dynamic mode decomposition, Internat. Health, 7 (2015), pp. 139-145.
[51] R. W. Reynolds, N. A. Rayner, T. M. Smith, D. C. Stokes, and W. Wang, An improved in situ and satellite SST analysis for climate, J. Climate, 15 (2002), pp. 1609-1625.
[52] R. W. Reynolds, T. M. Smith, C. Liu, D. B. Chelton, K. S. Casey, and M. G. Schlax, Daily high-resolution-blended analyses for sea surface temperature, J. Climate, 20 (2007), pp. 5473-5496.
[53] V. Rokhlin, A. Szlam, and M. Tygert, A randomized algorithm for principal component analysis, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1100-1124, https://doi.org/10.1137/080736417. · Zbl 1198.65035
[54] C. W. Rowley, I. Mezić, S. Bagheri, P. Schlatter, and D. Henningson, Spectral analysis of nonlinear flows, J. Fluid Mech., 645 (2009), pp. 115-127. · Zbl 1183.76833
[55] T. Sarlos, Improved approximation algorithms for large matrices via random projections, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 143-152.
[56] T. Sayadi and P. J. Schmid, Parallel data-driven decomposition algorithm for large-scale datasets: With application to transitional boundary layers, Theoret. Comput. Fluid Dynam., 30 (2016), pp. 415-428.
[57] P. Schmid, L. Li, M. Juniper, and O. Pust, Applications of the dynamic mode decomposition, Theoret. Comput. Fluid Dynam., 25 (2011), pp. 249-259. · Zbl 1272.76179
[58] P. J. Schmid, Dynamic mode decomposition of numerical and experimental data, J. Fluid Mech., 656 (2010), pp. 5-28. · Zbl 1197.76091
[59] A. Seena and H. J. Sung, Dynamic mode decomposition of turbulent cavity flows for self-sustained oscillations, Internat. J. Heat Fluid Flow, 32 (2011), pp. 1098-1110.
[60] T. M. Smith and R. W. Reynolds, A global merged land-air-sea surface temperature reconstruction based on historical observations (1880-1997), J. Climate, 18 (2005), pp. 2021-2036.
[61] K. Taira, S. L. Brunton, S. Dawson, C. W. Rowley, T. Colonius, B. J. McKeon, O. T. Schmidt, S. Gordeyev, V. Theofilis, and L. S. Ukeiley, Modal analysis of fluid flows: An overview, AIAA J., 55 (2017), pp. 4013-4041.
[62] K. Taira and T. Colonius, The immersed boundary method: A projection approach, J. Comput. Phys., 225 (2007), pp. 2118-2137. · Zbl 1343.76027
[63] N. Takeishi, Y. Kawahara, Y. Tabei, and T. Yairi, Bayesian dynamic mode decomposition, in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017, pp. 2814-2821.
[64] R. Taylor, J. N. Kutz, K. Morgan, and B. Nelson, Dynamic Mode Decomposition for Plasma Diagnostics and Validation, preprint, https://arxiv.org/abs/1702.06871, 2017.
[65] A. N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Math., 4 (1963), pp. 1035-1038. · Zbl 0141.11001
[66] J. A. Tropp, Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal., 3 (2011), pp. 115-126. · Zbl 1232.15029
[67] 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), pp. 391-421. · Zbl 1346.37064
[68] J. M. Varah, A practical examination of some numerical methods for linear discrete ill-posed problems, SIAM Rev., 21 (1979), pp. 100-111, https://doi.org/10.1137/1021007. · Zbl 0406.65015
[69] S. Voronin and P.-G. Martinsson, RSVDPACK: Subroutines for Computing Partial Singular Value Decompositions via Randomized Sampling on Single Core, Multi Core, and GPU Architectures, preprint, https://arxiv.org/abs/1502.05366, 2015.
[70] J. Wang, D. Wang, P. Lallemand, and L.-S. S. Luo, Lattice Boltzmann simulations of thermal convective flows in two dimensions, Comput. Math. Appl., 65 (2013), pp. 262-286, https://doi.org/10.1016/j.camwa.2012.07.001. · Zbl 1268.76050
[71] D. P. Woodruff, Sketching as a tool for numerical linear algebra, Found. Trends Theoret. Comput. Sci., 10 (2014), pp. 1-157. · Zbl 1316.65046
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.