Fassler, Daniel 
ORCID: https://orcid.org/0009-0007-0785-9108
(2025)
Finite-data Error Bounds for Approximating the Koopman Operator.
Masters thesis, Concordia University.
Preview |
Text (application/pdf)
3MBFASSLER_MSc_F2025.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
The Koopman operator is a powerful tool for the study of dynamical systems that allows the study of nonlinear systems through the lens of observables functions forming an equivalent linear formulation of the dynamics in an infinite-dimensional space. Recent developments in data-driven approximation techniques allow the approximation of the Koopman operator without any a priori knowledge of the underlying system. However, despite the existence of asymptotic results on the capabilities of such techniques, only a few guarantees exist in the more realistic finite-data setting.
Approximation of the Koopman operator through Extended Dynamic Mode Decomposition (EDMD) has been observed to converge at the Monte Carlo rate of the inverse, i.e., proportionally to the square root of number of samples. In this thesis, we bridge the gap between EDMD and the theory of least squares to provide a proof of this statement with minimal assumptions. Moreover, leveraging known results from function approximation via least squares, we investigate the effect of the sampling routine and the choice and size of dictionary on the convergence of the EDMD method. Additionally, we develop a similar approach in the context of compressed sensing, where we provide recovery guarantees when the Koopman operator is sparse. Finally, we validate theoretical findings through extensive numerical illustrations.
| Divisions: | Concordia University > Faculty of Arts and Science > Mathematics and Statistics |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Fassler, Daniel |
| Institution: | Concordia University |
| Degree Name: | M. Sc. |
| Program: | Mathematics |
| Date: | 23 June 2025 |
| Thesis Supervisor(s): | Brugiapaglia, Simone and Bramburger, Jason |
| Keywords: | Dynamical Systems, Koopman Operator, Operator approximation |
| ID Code: | 995677 |
| Deposited By: | Daniel Fassler |
| Deposited On: | 04 Nov 2025 17:05 |
| Last Modified: | 04 Nov 2025 17:05 |
References:
[1] Ben Adcock. Optimal sampling for least-squares approximation. 2024. arXiv: 2409.02342 [stat.ML]. url: https://arxiv.org/abs/2409.02342.
[2] Ben Adcock and Simone Brugiapaglia. Monte Carlo is a good sampling strategy for
polynomial approximation in high dimensions. Nov. 5, 2023. arXiv: 2208.09045[cs,
math]. url: http://arxiv.org/abs/2208.09045 (visited on 07/09/2024).
[3] Ben Adcock, Simone Brugiapaglia, and Clayton G. Webster. Sparse Polynomial Ap-
proximation of High-Dimensional Functions. Computational Science & Engineering.
SIAM, Jan. 2022. isbn: 978-1-61197-687-8. doi: 10 . 1137 / 1 . 9781611976885 . ch5.
url: https://epubs.siam.org/doi/10.1137/1.9781611976885.ch5 (visited on
07/22/2024).
[4] Ben Adcock, Nick Dexter, and Sebastian Moraga. “Optimal approximation of in昀椀nite-
dimensional holomorphic functions II: Recovery from i.i.d. pointwise samples”. In:
Journal of Complexity 89 (2025), p. 101933. issn: 0885-064X. doi: https : / / doi .
org / 10 . 1016 / j . jco . 2025 . 101933. url: https : / / www . sciencedirect . com /
science/article/pii/S0885064X25000111.
[5] Ben Adcock and Anders C. Hansen. Compressive Imaging: Structure, Sampling, Learn-
ing. Cambridge University Press, 2021.
[6] H. M. Antia. Numerical Methods for Scientists and Engineers. Vol. 2. Texts and
Readings in Physical Sciences. Gurgaon: Hindustan Book Agency, 2012. isbn: 978-
93-80250-40-3 978-93-86279-52-1. doi: 10.1007/978- 93- 86279- 52- 1. url: http:
//link.springer.com/10.1007/978-93-86279-52-1 (visited on 05/13/2025).
[7] Heinz H. Bauschke and Walaa M. Moursi. An Introduction to Convexity, Optimization,
and Algorithms. SIAM, pp. 39–43. doi: 10 . 1137 / 1 . 9781611977806 . ch8. eprint:
https://epubs.siam.org/doi/pdf/10.1137/1.9781611977806.ch8. url: https:
//epubs.siam.org/doi/abs/10.1137/1.9781611977806.ch8.
[8] Aaron Berk, Simone Brugiapaglia, and Tim Hoheisel. “LASSO Reloaded: A Variational
Analysis Perspective with Applications to Compressed Sensing”. In: SIAM Journal on
Mathematics of Data Science 5.4 (2023), pp. 1102–1129. doi: 10.1137/22M1498991.
[9] Jason J. Bramburger. Data-Driven Methods for Dynamic Systems. Philadelphia, PA:
SIAM, 2024. doi: 10.1137/1.9781611978162. eprint: https://epubs.siam.org/
doi/pdf/10.1137/1.9781611978162. url: https://epubs.siam.org/doi/abs/10.
1137/1.9781611978162.
[10] Jason J. Bramburger and Giovanni Fantuzzi. “Auxiliary Functions as Koopman Ob-
servables: Data-Driven Analysis of Dynamical Systems via Polynomial Optimization”.
In: Journal of Nonlinear Science 34.1 (Oct. 30, 2023), p. 8. issn: 1432-1467. doi:
10.1007/s00332- 023- 09990- 2. url: https://doi.org/10.1007/s00332- 023-
09990-2 (visited on 07/09/2024).
[11] Jason J. Bramburger and Giovanni Fantuzzi. “Data-driven discovery of invariant mea-
sures”. In: Proceedings of the Royal Society A: Mathematical, Physical and Engineering
Sciences 480.2286 (2024), p. 20230627. doi: 10.1098/rspa.2023.0627. url: https:
//royalsocietypublishing.org/doi/abs/10.1098/rspa.2023.0627.
[12] Steven L. Brunton and J. Nathan Kutz. Data-Driven Science and Engineering: Ma-
chine Learning, Dynamical Systems, and Control. 2nd ed. Cambridge University Press,
2022.
[13] Steven L. Brunton, Joshua L. Proctor, and J. Nathan Kutz. “Discovering governing
equations from data by sparse identi昀椀cation of nonlinear dynamical systems”. In: Pro-
ceedings of the National Academy of Sciences 113.15 (2016), pp. 3932–3937. doi: 10.
1073/pnas.1517384113. eprint: https://www.pnas.org/doi/pdf/10.1073/pnas.
1517384113. url: https://www.pnas.org/doi/abs/10.1073/pnas.1517384113.
[14] Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Stable Signal Recovery
from Incomplete and Inaccurate Measurements. 2005. doi: https://doi.org/10.
1002/cpa.20124. eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/
cpa.20124. url: https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.
20124.
[15] Giuseppe Alessio D’Inverno, Kylian Ajavon, and Simone Brugiapaglia. Surrogate mod-
els for di昀昀usion on graphs via sparse polynomials. 2025. arXiv: 2502.06595 [math.NA].
url: https://arxiv.org/abs/2502.06595.
[16] D.L. Donoho. “Compressed sensing”. In: IEEE Transactions on Information Theory
52.4 (2006), pp. 1289–1306. doi: 10.1109/TIT.2006.871582.
[17] Daniel Fassler. Finite-data Error Bounds for Approximating the Koopman Operator.
Version 1.0.0. Apr. 2025. url: https://github.com/Falsorr/EDMD_Master.
[18] Simon Foucart. Mathematical Pictures at a Data Science Exhibition. Cambridge Uni-
versity Press, 2022.
[19] Simon Foucart. “The sparsity of LASSO-type minimizers”. In: Applied and Compu-
tational Harmonic Analysis 62 (2023), pp. 441–452. issn: 1063-5203. doi: https :
//doi.org/10.1016/j.acha.2022.10.004.
[20] Simon Foucart and Holger Rauhut. An Invitation to Compressive Sensing. New York,
NY: Springer New York, 2013, pp. 1–39. isbn: 978-0-8176-4948-7. doi: 10.1007/978-
0-8176-4948-7_1. url: https://doi.org/10.1007/978-0-8176-4948-7_1.
[21] Michael Garstka, Mark Cannon, and Paul Goulart. “COSMO: A Conic Operator Split-
ting Method for Convex Conic Problems”. In: Journal of Optimization Theory and
Applications 190.3 (2021), pp. 779–810. doi: 10.1007/s10957- 021- 01896- x. url:
https://doi.org/10.1007/s10957-021-01896-x.
[22] Walter Gautschi and Gabriele Inglese. “Lower bounds for the condition number of
Vandermonde matrices”. In: Numerische Mathematik 52.3 (May 1, 1987), pp. 241–250.
issn: 0945-3245. doi: 10 . 1007 / BF01398878. url: https : / / doi . org / 10 . 1007 /
BF01398878 (visited on 05/06/2025).
[23] Ilon Joseph. “Koopman–von Neumann approach to quantum simulation of nonlin-
ear classical dynamics”. In: Phys. Rev. Res. 2 (4 Oct. 2020), p. 043102. doi: 10 .
1103/PhysRevResearch.2.043102. url: https://link.aps.org/doi/10.1103/
PhysRevResearch.2.043102.
[24] Bernard O. Koopman. “Hamiltonian Systems and Transformation in Hilbert Space.”
In: Proc Natl Acad Sci U S A 17(5) (1931), pp. 315–318.
[25] Milan Korda and Igor Mezić. “Linear predictors for nonlinear dynamical systems:
Koopman operator meets model predictive control”. In: Automatica 93 (2018), pp. 149–
160. issn: 0005-1098. doi: https://doi.org/10.1016/j.automatica.2018.03.046.
[26] Ulrich Krengel. “On the speed of convergence in the ergodic theorem”. In: Monat-
shefte für Mathematik 86.1 (Mar. 1, 1978), pp. 3–6. issn: 1436-5081. doi: 10.1007/
BF01300052. url: https://doi.org/10.1007/BF01300052.
[27] Andrzej Lasota and Michael C. Mackey. Chaos, Fractals, and Noise. Red. by J. E.
Marsden and L. Sirovich. Vol. 97. Applied Mathematical Sciences. New York, NY:
Springer, 1994. isbn: 978-1-4612-8723-0 978-1-4612-4286-4. doi: 10 . 1007 / 978 - 1 -
4612- 4286- 4. url: http://link.springer.com/10.1007/978- 1- 4612- 4286- 4
(visited on 05/12/2025).
[28] Igor Mezić. “Analysis of Fluid Flows via Spectral Properties of the Koopman Operator”.
In: Annual Review of Fluid Mechanics 45.Volume 45, 2013 (2013), pp. 357–378. issn:
1545-4479. doi: https://doi.org/10.1146/annurev-fluid-011212-140652.
[29] B. K. Natarajan. “Sparse Approximate Solutions to Linear Systems”. In: SIAM Journal
on Computing 24.2 (1995), pp. 227–234. doi: 10 . 1137 / S0097539792240406. url:
https://doi.org/10.1137/S0097539792240406.
[30] Feliks Nüske, Sebastian Peitz, Friedrich Philipp, Manuel Schaller, and Karl Worth-
mann. “Finite-Data Error Bounds for Koopman-Based Prediction and Control”. In:
Journal of Nonlinear Science 33.1 (Nov. 23, 2022), p. 14. issn: 1432-1467. doi: 10.
1007/s00332-022-09862-1. url: https://doi.org/10.1007/s00332-022-09862-1
(visited on 03/20/2025).
[31] Art B. Owen. Monte Carlo theory, methods and examples. https://artowen.su.
domains/mc/, 2013.
[32] Hayden Schae昀昀er, Giang Tran, and Rachel Ward. “Extracting Sparse High-Dimensional
Dynamics from Limited Data”. In: SIAM Journal on Applied Mathematics 78.6 (2018),
pp. 3279–3295. doi: 10.1137/18M116798X.
[33] Terence Tao. Topics in Random Matrix Theory. Vol. 132. American Mathematical Soc.,
2018. isbn: 0-8218-7430-6.
[34] René Thomas. “Deterministic Chaos Seen in Terms of Feedback Circuits: Analysis,
Synthesis, ”Labyrinth Chaos””. In: International Journal of Bifurcation and Chaos
09.10 (1999), pp. 1889–1905. eprint: https://doi.org/10.1142/S0218127499001383.
[35] Giang Tran and Rachel Ward. “Exact Recovery of Chaotic Systems from Highly Cor-
rupted Data”. In: Multiscale Modeling & Simulation 15.3 (2017), pp. 1108–1129. doi:
10.1137/16M1086637.
[36] Joel A. Tropp. “User-Friendly Tail Bounds for Sums of Random Matrices”. In: Foun-
dations of Computational Mathematics 12.4 (2012), pp. 389–434. issn: 16153375. doi:
10.1007/s10208-011-9099-z. (Visited on 05/13/2025).
[37] Jonathan H. Tu, Clarence W. Rowley, Dirk M. Luchtenburg, Steven L. Brunton, and
J. Nathan Kutz. “On dynamic mode decomposition: Theory and applications”. In:
Journal of Computational Dynamics 1.2 (2014), pp. 391–421. issn: 2158-2491. doi:
10.3934/jcd.2014.1.391. url: https://www.aimsciences.org/article/id/
1dfebc20-876d-4da7-8034-7cd3c7ae1161.
[38] Madeleine Udell, Karanveer Mohan, David Zeng, Jenny Hong, Steven Diamond, and
Stephen Boyd. “Convex Optimization in Julia”. In: SC14 Workshop on High Per-
formance Technical Computing in Dynamic Languages (2014). arXiv: 1410 . 4821
[math-oc].
[39] Caroline Wormell. “Orthogonal Polynomial Approximation and Extended Dynamic
Mode Decomposition in Chaos”. In: SIAM Journal on Numerical Analysis 63.1 (2025),
pp. 122–148. doi: 10.1137/23M1597873. url: https://doi.org/10.1137/23M1597873.
[40] Rishikesh Yadav and Alexandre Mauroy. Approximation of the Koopman operator via
Bernstein polynomials. 2025. arXiv: 2403.02438 [math.DS]. url: https://arxiv.
org/abs/2403.02438.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics