×

Low-rank dynamic mode decomposition: an exact and tractable solution. (English) Zbl 1484.65086

Summary: This work studies the linear approximation of high-dimensional dynamical systems using low-rank dynamic mode decomposition. Searching this approximation in a data-driven approach is formalized as attempting to solve a low-rank constrained optimization problem. This problem is non-convex, and state-of-the-art algorithms are all sub-optimal. This paper shows that there exists a closed-form solution, which is computed in polynomial time, and characterizes the \(\ell_2\)-norm of the optimal approximation error. The paper also proposes low-complexity algorithms building reduced models from this optimal solution, based on singular value decomposition or eigenvalue decomposition. The algorithms are evaluated by numerical simulations using synthetic and physical data benchmarks.

MSC:

65F55 Numerical methods for low-rank matrix approximation; matrix compression
65K05 Numerical mathematical programming methods

Software:

ADMiRA; redbKIT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Auliac, G., Caby, J.: Mathématiques 3e Année: Topologie et analyse, Objectif Licence, EdiScience (2005) · Zbl 1327.00006
[2] Bertsekas, D., Nonlinear Programming (1995), Belmont: Athena Scientific, Belmont · Zbl 0935.90037
[3] Budišić, M.; Mohr, R.; Mezić, I., Applied Koopmanism, Chaos Interdiscip. J. Nonlinear Sci., 22, 4, 047510 (2012) · Zbl 1319.37013
[4] Chandrasekhar, S., Hydrodynamic and Hydromagnetic Stability (2013), Chelmsford: Courier Corporation, Chelmsford · Zbl 0142.44103
[5] Chen, KK; Tu, JH; Rowley, CW, Variants of dynamic mode decomposition: boundary condition, Koopman, and Fourier analyses, J. Nonlinear Sci., 22, 6, 887-915 (2012) · Zbl 1259.35009
[6] Cohen, A.; DeVore, R., Approximation of high-dimensional parametric PDEs, Acta Numerica, 24, 1-159 (2015) · Zbl 1320.65016
[7] Cui, T.; Marzouk, YM; Willcox, KE, Data-driven model reduction for the Bayesian solution of inverse problems, Int. J. Numer. Methods Eng., 102, 966-990 (2015) · Zbl 1352.65445
[8] Dawson, STM; Hemati, MS; Williams, MO; Rowley, CW, Characterizing and correcting for the effect of sensor noise in the dynamic mode decomposition, Exp. Fluids, 57, 42 (2016)
[9] Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 3, 211-218 (1936) · JFM 62.1075.02
[10] Fazel, M.: Matrix Rank Minimization with Applications, Stanford University, Ph.D. Thesis (2002)
[11] Golub, G.; Van Loan, C., Matrix Computations (2013), Baltimore: Johns Hopkins University Press, Baltimore · Zbl 1268.65037
[12] Hackbusch, W., Tensor Spaces and Numerical Tensor Calculus (2012), Berlin: Springer, Berlin · Zbl 1244.65061
[13] Hasselmann, K., PIPs and POPs: the reduction of complex dynamical systems using principal interaction and oscillation patterns, J. Geophys. Res. Atmos., 93, D9, 11015-11021 (1988)
[14] Héas, P., Herzet, C.: Low-rank approximation of linear maps (2018) · Zbl 1390.37131
[15] Héas, P., Herzet, C.: State-of-the-art algorithms for low rank dynamic mode decomposition (2021) · Zbl 1390.37131
[16] Héas, P., Herzet, C., Combès, B.: Generalized kernel-based dynamic mode decomposition. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2020)
[17] Hemati, MS; Rowley, CW; Deem, EA; Cattafesta, LN, De-biasing the dynamic mode decomposition for applied Koopman spectral analysis of noisy datasets, Theoret. Comput. Fluid Dyn., 31, 4, 349-368 (2017)
[18] Horn, RA; Johnson, CR, Matrix Analysis (2012), Cambridge: Cambridge University Press, Cambridge
[19] Jain, P., Meka, R., Dhillon, I.S.: Guaranteed rank minimization via singular value projection. In: Advances in Neural Information Processing Systems, pp. 937-945 (2010)
[20] Jovanovic, M., Schmid, P., Nichols, J.: Low-rank and sparse dynamic mode decomposition. Center for Turbulence Research Annual Research Briefs, pp. 139-152 (2012)
[21] Klus, S., Koltai, P., Schütte, C.: On the numerical approximation of the Perron-Frobenius and Koopman operator. arXiv preprint arXiv:1512.05997 (2015) · Zbl 1353.37154
[22] Kutz, J.N., Brunton, S.L., Brunton, B.W., Proctor, J.L.: Dynamic mode decomposition: data-driven modeling of complex systems (2016) · Zbl 1365.65009
[23] Lee, K., Bresler, Y.: Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint(2009)
[24] Lee, K.; Bresler, Y., Admira: atomic decomposition for minimum rank approximation, IEEE Trans. Inf. Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[25] Li, Q., Dietrich, F., Bollt, E.M., Kevrekidis, I.G.: Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator. arXiv preprint arXiv:1707.00225 (2017) · Zbl 06876982
[26] Mesbahi, M.; Papavassilopoulos, GP, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Autom. Control, 42, 2, 239-243 (1997) · Zbl 0872.93029
[27] Mishra, B.; Meyer, G.; Bach, F.; Sepulchre, R., Low-rank optimization with trace norm penalty, SIAM J. Optim., 23, 4, 2124-2149 (2013) · Zbl 1286.65078
[28] Parrilo, PA; Khatri, S., On cone-invariant linear matrix inequalities, IEEE Trans. Autom. Control, 45, 8, 1558-1563 (2000) · Zbl 0988.93029
[29] Penland, C.; Magorian, T., Prediction of nino 3 sea surface temperatures using linear inverse modeling, J. Clim., 6, 6, 1067-1076 (1993)
[30] Quarteroni, A.; Manzoni, A.; Negri, F., Reduced Basis Methods for Partial Differential Equations: An Introduction (2015), Berlin: Springer, Berlin · Zbl 1337.65113
[31] Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev, 52, 3, 471-501 (2010) · Zbl 1198.90321
[32] Schmid, PJ, Dynamic mode decomposition of numerical and experimental data, J. Fluid Mech., 656, 5-28 (2010) · Zbl 1197.76091
[33] Taylor, G.; Green, A., Mechanism of the production of small eddies from large ones, Proc. R. Soc. Lond. A, 158, 895, 499-521 (1937) · JFM 63.1358.03
[34] Tu, JH; Rowley, CW; Luchtenburg, DM; Brunton, SL; Kutz, JN, On dynamic mode decomposition: theory and applications, J. Comput. Dyn., 1, 2, 391-421 (2014) · Zbl 1346.37064
[35] Williams, MO; Kevrekidis, I.; Rowley, C., A data-driven approximation of the Koopman operator: extending dynamic mode decomposition, J. Nonlinear Sci., 25, 6, 1307-1346 (2015) · Zbl 1329.65310
[36] Williams, M.O., Rowley, C.W., Kevrekidis, I.G.: A kernel-based approach to data-driven Koopman spectral analysis. arXiv preprint arXiv:1411.2260 (2014) · Zbl 1366.37144
[37] Wynn, A.; Pearson, D.; Ganapathisubramani, B.; Goulart, PJ, Optimal mode decomposition for unsteady flows, J. Fluid Mech., 733, 473-503 (2013) · Zbl 1294.76205
[38] Yeung, E., Kundu, S., Hodas, N.: Learning Deep Neural Network Representations for Koopman Operators of Nonlinear Dynamical Systems (2017)
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.