Igor Mezić

Milan Korda, Mihai Putinar, Igor Mezić

Starting from measured data, we develop a method to compute the fine structure of the spectrum of the Koopman operator with rigorous convergence guarantees. The method is based on the observation that, in the measure-preserving ergodic setting, the moments of the spectral measure associated to a given observable are computable from a single trajectory of this observable. Having finitely many moments available, we use the classical Christoffel-Darboux kernel to separate the atomic and absolutely continuous parts of the spectrum, supported by convergence guarantees as the number of moments tends to infinity. In addition, we propose a technique to detect the singular continuous part of the spectrum as well as two methods to approximate the spectral measure with guaranteed convergence in the weak topology, irrespective of whether the singular continuous part is present or not. The proposed method is simple to implement and readily applicable to large-scale systems since the computational complexity is dominated by inverting an $N\times N$ Hermitian positive-definite Toeplitz matrix, where $N$ is the number of moments, for which efficient and numerically stable algorithms exist; in particular, the complexity of the approach is independent of the dimension of the underlying state-space. We also show how to compute, from measured data, the spectral projection on a given segment of the unit circle, allowing us to obtain a finite-dimensional approximation of the operator that explicitly takes into account the point and continuous parts of the spectrum. Finally, we describe a relationship between the proposed method and the so-called Hankel Dynamic Mode Decomposition, providing new insights into the behavior of the eigenvalues of the Hankel DMD operator. A number of numerical examples illustrate the approach, including a study of the spectrum of the lid-driven two-dimensional cavity flow.

Zlatko Drmač, Igor Mezić, Ryan Mohr

The goals and contributions of this paper are twofold. It provides a new computational tool for data driven Koopman spectral analysis by taking up the formidable challenge to develop a numerically robust algorithm by following the natural formulation via the Krylov decomposition with the Frobenius companion matrix, and by using its eigenvectors explicitly -- these are defined as the inverse of the notoriously ill-conditioned Vandermonde matrix. The key step to curb ill-conditioning is the discrete Fourier transform of the snapshots; in the new representation, the Vandermonde matrix is transformed into a generalized Cauchy matrix, which then allows accurate computation by specially tailored algorithms of numerical linear algebra. The second goal is to shed light on the connection between the formulas for optimal reconstruction weights when reconstructing snapshots using subsets of the computed Koopman modes. It is shown how using a certain weaker form of generalized inverses leads to explicit reconstruction formulas that match the abstract results from Koopman spectral theory, in particular the Generalized Laplace Analysis.

Yoshihiko Susuki, Igor Mezić

This paper addresses structures of state space in quasiperiodically forced dynamical systems. We develop a theory of ergodic partition of state space in a class of measure-preserving and dissipative flows, which is a natural extension of the existing theory for measure-preserving maps. The ergodic partition result is based on eigenspace at eigenvalue 0 of the associated Koopman operator, which is realized via time-averages of observables, and provides a constructive way to visualize a low-dimensional slice through a high-dimensional invariant set. We apply the result to the systems with a finite number of attractors and show that the time-average of a continuous observable is well-defined and reveals the invariant sets, namely, a finite number of basins of attraction. We provide a characterization of invariant sets in the quasiperiodically forced systems. A theoretical result on uniform boundedness of the invariant sets is presented. The series of theoretical results enables numerical analysis of invariant sets in the quasiperiodically forced systems based on the ergodic partition and time-averages. Using this, we analyze a nonlinear model of complex power grids that represents the short-term swing instability, named the coherent swing instability. We show that our theoretical results can be used to understand stability regions in such complex systems.

Matthew J. Colbrook, Igor Mezić, Alexei Stepanenko

Dynamical systems provide a comprehensive way to study complex and changing behaviors across various sciences. Many modern systems are too complicated to analyze directly or we do not have access to models, driving significant interest in learning methods. Koopman operators have emerged as a dominant approach because they allow the study of nonlinear dynamics using linear techniques by solving an infinite-dimensional spectral problem. However, current algorithms face challenges such as lack of convergence, hindering practical progress. This paper addresses a fundamental open question: \textit{When can we robustly learn the spectral properties of Koopman operators from trajectory data of dynamical systems, and when can we not?} Understanding these boundaries is crucial for analysis, applications, and designing algorithms. We establish a foundational approach that combines computational analysis and ergodic theory, revealing the first fundamental barriers -- universal for any algorithm -- associated with system geometry and complexity, regardless of data quality and quantity. For instance, we demonstrate well-behaved smooth dynamical systems on tori where non-trivial eigenfunctions of the Koopman operator cannot be determined by any sequence of (even randomized) algorithms, even with unlimited training data. Additionally, we identify when learning is possible and introduce optimal algorithms with verification that overcome issues in standard methods. These results pave the way for a sharp classification theory of data-driven dynamical systems based on how many limits are needed to solve a problem. These limits characterize all previous methods, presenting a unified view. Our framework systematically determines when and how Koopman spectral properties can be learned.

William T. Redman, Juan M. Bello-Rivas, Maria Fonoberova et al.

Study of the nonlinear evolution deep neural network (DNN) parameters undergo during training has uncovered regimes of distinct dynamical behavior. While a detailed understanding of these phenomena has the potential to advance improvements in training efficiency and robustness, the lack of methods for identifying when DNN models have equivalent dynamics limits the insight that can be gained from prior work. Topological conjugacy, a notion from dynamical systems theory, provides a precise definition of dynamical equivalence, offering a possible route to address this need. However, topological conjugacies have historically been challenging to compute. By leveraging advances in Koopman operator theory, we develop a framework for identifying conjugate and non-conjugate training dynamics. To validate our approach, we demonstrate that comparing Koopman eigenvalues can correctly identify a known equivalence between online mirror descent and online gradient descent. We then utilize our approach to: (a) identify non-conjugate training dynamics between shallow and wide fully connected neural networks; (b) characterize the early phase of training dynamics in convolutional neural networks; (c) uncover non-conjugate training dynamics in Transformers that do and do not undergo grokking. Our results, across a range of DNN architectures, illustrate the flexibility of our framework and highlight its potential for shedding new light on training dynamics.

William T. Redman, Dean Huang, Maria Fonoberova et al.

Koopman operator theory has found significant success in learning models of complex, real-world dynamical systems, enabling prediction and control. The greater interpretability and lower computational costs of these models, compared to traditional machine learning methodologies, make Koopman learning an especially appealing approach. Despite this, little work has been performed on endowing Koopman learning with the ability to leverage its own failures. To address this, we equip Koopman methods -- developed for predicting non-autonomous time-series -- with an episodic memory mechanism, enabling global recall of (or attention to) periods in time where similar dynamics previously occurred. We find that a basic implementation of Koopman learning with episodic memory leads to significant improvements in prediction on synthetic and real-world data. Our framework has considerable potential for expansion, allowing for future advances, and opens exciting new directions for Koopman learning.

Tomislav Bazina, Ervin Kamenar, Maria Fonoberova et al.

Loss of hand function due to conditions like stroke or multiple sclerosis significantly impacts daily activities. Robotic rehabilitation provides tools to restore hand function, while novel methods based on surface electromyography (sEMG) enable the adaptation of the device's force output according to the user's condition, thereby improving rehabilitation outcomes. This study aims to achieve accurate force estimations during medium wrap grasps using a single sEMG sensor pair, thereby addressing the challenge of escalating sensor requirements for precise predictions. We conducted sEMG measurements on 13 subjects at two forearm positions, validating results with a hand dynamometer. We established flexible signal-processing steps, yielding high peak cross-correlations between the processed sEMG signal (representing meaningful muscle activity) and grip force. Influential parameters were subsequently identified through sensitivity analysis. Leveraging a novel data-driven Koopman operator theory-based approach and problem-specific data lifting techniques, we devised a methodology for the estimation and short-term prediction of grip force from processed sEMG signals. A weighted mean absolute percentage error (wMAPE) of approx. 5.5% was achieved for the estimated grip force, whereas predictions with a 0.5-second prediction horizon resulted in a wMAPE of approx. 17.9%. The methodology proved robust regarding precise electrode positioning, as the effect of sensing position on error metrics was non-significant. The algorithm executes exceptionally fast, processing, estimating, and predicting a 0.5-second sEMG signal batch in just approx. 30 ms, facilitating real-time implementation.

Ryan Mohr, Maria Fonoberova, Zlatko Drmač et al.

Hierarchical support vector regression (HSVR) models a function from data as a linear combination of SVR models at a range of scales, starting at a coarse scale and moving to finer scales as the hierarchy continues. In the original formulation of HSVR, there were no rules for choosing the depth of the model. In this paper, we observe in a number of models a phase transition in the training error -- the error remains relatively constant as layers are added, until a critical scale is passed, at which point the training error drops close to zero and remains nearly constant for added layers. We introduce a method to predict this critical scale a priori with the prediction based on the support of either a Fourier transform of the data or the Dynamic Mode Decomposition (DMD) spectrum. This allows us to determine the required number of layers prior to training any models.

David A. Haggerty, Michael J. Banks, Patrick C. Curtis et al.

Soft robots promise improved safety and capability over rigid robots when deployed in complex, delicate, and dynamic environments. However, the infinite degrees of freedom and highly nonlinear dynamics of these systems severely complicate their modeling and control. As a step toward addressing this open challenge, we apply the data-driven, Hankel Dynamic Mode Decomposition (HDMD) with time delay observables to the model identification of a highly inertial, helical soft robotic arm with a high number of underactuated degrees of freedom. The resulting model is linear and hence amenable to control via a Linear Quadratic Regulator (LQR). Using our test bed device, a dynamic, lightweight pneumatic fabric arm with an inertial mass at the tip, we show that the combination of HDMD and LQR allows us to command our robot to achieve arbitrary poses using only open loop control. We further show that Koopman spectral analysis gives us a dimensionally reduced basis of modes which decreases computational complexity without sacrificing predictive power.

Iva Manojlović, Maria Fonoberova, Ryan Mohr et al.

We consider the training process of a neural network as a dynamical system acting on the high-dimensional weight space. Each epoch is an application of the map induced by the optimization algorithm and the loss function. Using this induced map, we can apply observables on the weight space and measure their evolution. The evolution of the observables are given by the Koopman operator associated with the induced dynamical system. We use the spectrum and modes of the Koopman operator to realize the above objectives. Our methods can help to, a priori, determine the network depth; determine if we have a bad initialization of the network weights, allowing a restart before training too long; speeding up the training time. Additionally, our methods help enable noise rejection and improve robustness. We show how the Koopman spectrum can be used to determine the number of layers required for the architecture. Additionally, we show how we can elucidate the convergence versus non-convergence of the training process by monitoring the spectrum, in particular, how the existence of eigenvalues clustering around 1 determines when to terminate the learning process. We also show how using Koopman modes we can selectively prune the network to speed up the training procedure. Finally, we show that incorporating loss functions based on negative Sobolev norms can allow for the reconstruction of a multi-scale signal polluted by very large amounts of noise.

Stefan Ivić, Bojan Crnković, Hassan Arbabi et al.

Search and detection of objects on the ocean surface is a challenging task due to the complexity of the drift dynamics and lack of known optimal solutions for the path of the search agents. This challenge was highlighted by the unsuccessful search for Malaysian Flight 370 (MH370) which disappeared on March 8, 2014. In this paper, we propose an improvement of a search algorithm rooted in the ergodic theory of dynamical systems which can accommodate complex geometries and uncertainties of the drifting search areas on the ocean surface. We illustrate the effectiveness of this algorithm in a computational replication of the conducted search for MH370. In comparison to conventional search methods, the proposed algorithm leads to an order of magnitude improvement in success rate over the time period of the actual search operation. Simulations of the proposed search control also indicate that the initial success rate of finding debris increases in the event of delayed search commencement. This is due to the existence of convergence zones in the search area which leads to local aggregation of debris in those zones and hence reduction of the effective size of the area to be searched.

Zlatko Drmač, Igor Mezić, Ryan Mohr

The Dynamic Mode Decomposition (DMD) is a tool of trade in computational data driven analysis of fluid flows. More generally, it is a computational device for Koopman spectral analysis of nonlinear dynamical systems, with a plethora of applications in applied sciences and engineering. Its exceptional performance triggered developments of several modifications that make the DMD an attractive method in data driven framework. This work offers further improvements of the DMD to make it more reliable, and to enhance its functionality. In particular, data driven formula for the residuals allows selection of the Ritz pairs, thus providing more precise spectral information of the underlying Koopman operator, and the well-known technique of refining the Ritz vectors is adapted to data driven scenarios. Further, the DMD is formulated in a more general setting of weighted inner product spaces, and the consequences for numerical computation are discussed in detail. Numerical experiments are used to illustrate the advantages of the proposed method, designated as DDMD_RRR (Refined Rayleigh Ritz Data Driven Modal Decomposition).