Source-linked AI summary
Online dynamic mode decomposition for time-varying systems
Hao Zhang, Clarence W. Rowley, Eric A. Deem, Louis N. Cattafesta
TL;DR
Time-varying systems require DMD descriptions that can be updated as new data arrive without retaining all past snapshots. The paper introduces exact online and windowed DMD updates, finding strong real-time efficiency and effective capture of time-varying dynamics, while windowed DMD requires storing recent snapshots.
Problem
Standard DMD is computationally expensive because it repeatedly computes a pseudoinverse and stores all snapshots as their number grows.
Method
The paper develops online and windowed DMD algorithms that update DMD matrices as snapshots arrive, with weighting or finite windows to emphasize recent data.
Results
The online and windowed algorithms are the most efficient for online computation and can be orders of magnitude more efficient than standard DMD.
Takeaways & Limitations
Weighted online DMD and windowed DMD effectively capture time-varying dynamics in a linear system and wind-tunnel examples.
Takeaways & Limitations
Windowed DMD requires storing two n × n matrices and the w most recent snapshots, exceeding the storage required by online approaches.
Abstract
from arXiv · showhide
Dynamic mode decomposition (DMD) is a popular technique for modal decomposition, flow analysis, and reduced-order modeling. In situations where a system is time varying, one would like to update the system's description online as time evolves. This work provides an efficient method for computing DMD in real time, updating the approximation of a system's dynamics as new data becomes available. The algorithm does not require storage of past data, and computes the exact DMD matrix using rank-1 updates. A weighting factor that places less weight on older data can be incorporated in a straightforward manner, making the method particularly well suited to time-varying systems. A variant of the method may also be applied to online computation of "windowed DMD", in which only the most recent data are used. The efficiency of the method is compared against several existing DMD algorithms: for problems in which the state dimension is less than about~200, the proposed algorithm is the most efficient for real-time computation, and it can be orders of magnitude more efficient than the standard DMD algorithm. The method is demonstrated on several examples, including a time-varying linear system and a more complex example using data from a wind tunnel experiment. In particular, we show that the method is effective at capturing the dynamics of surface pressure measurements in the flow over a flat plate with an unsteady separation bubble.
1 Introduction
DMD decomposes complex dynamical-system data into spatial modes with simple temporal behavior and fits a linear model to observed dynamics. The paper develops an online alternative that updates the exact DMD matrix without storing raw data, while accommodating time-varying behavior by reducing the weight of older snapshots.
- DMD decomposes spatio-temporal data into spatial modes whose temporal behavior is characterized by frequency and growth or decay rate.
- Streaming DMD updates modes and eigenvalues online while retaining only a small number of orthogonal basis vectors.
- The proposed method updates the exact DMD matrix in real time without storing raw data or restricting it to a projected basis.
- It also supports weighting recent snapshots more heavily than older ones to better approximate time-varying dynamics.
- The paper covers online DMD, windowed DMD, online system identification, and comparisons across several DMD algorithms.
2 Online dynamic mode decomposition
Online DMD updates a time-varying linear model as new snapshot pairs arrive, avoiding storage of all past snapshots while reproducing the exact batch DMD matrix. Rank-1 updates and optional extensions support efficient real-time computation, including EDMD and system identification.
- The problem: DMD fits a matrix A mapping observed state snapshots x_j to outputs y_j, with modes and eigenvalues obtained from A.
- The problem: The standard approach is costly because it repeatedly computes a pseudoinverse and stores the growing snapshot matrix X_k.
- Online algorithm: Online DMD updates A_k to A_k+1 from the current model and one new snapshot pair, without recomputing the full batch problem.
- Online algorithm: The rank-1 updates use the current prediction error y_k+1 − A_kx_k+1 to correct the DMD matrix and update the auxiliary matrix P_k.
- Efficiency: 4n^2 floating-point multiplies are required per update, versus O(kn^2) for standard DMD, while only A_k and P_k are stored.The large n × k matrices X_k and Y_k need not be retained.
3 Windowed dynamic mode decomposition
Windowed DMD identifies dynamics from a fixed set of recent snapshots and updates the model efficiently as the window advances. Low-rank updates preserve the exact least-squares solution while reducing computation, at the cost of storing the window.
- 3.1 The problem: Windowed DMD fits a linear model using only the most recent w snapshot pairs, with w ≥ n and rank(X_k) = n required for uniqueness.The model minimizes the DMD least-squares objective over the finite snapshot window.
- 3.1 The problem: At each step, windowed DMD adds the newest snapshot pair and drops the oldest, thereby adapting the fitted matrix to recent dynamics.The sliding-window update can be interpreted as forgetting the oldest snapshot and incorporating the newest one.
- 3.2 Algorithm for windowed DMD: Low-rank updates avoid recomputing a pseudoinverse and matrix multiplication directly, making windowed DMD more efficient as the window advances.The derivation uses a Sherman–Morrison/Woodbury-style update for the required matrices.
- 3.2 Algorithm for windowed DMD: The correction to the DMD matrix is proportional to a matrix-valued prediction error, paralleling the online DMD update.The prediction error is represented by V − A_kU, while Γ_k+1 generalizes the scalar update factor.
- 3.2 Algorithm for windowed DMD: 8n^2 multiplies are required for the windowed update, versus O(wn^2) for solving the standard windowed DMD problem directly.The rank-2 update cost applies when one snapshot is forgotten and one is incorporated.
- 3.2 Algorithm for windowed DMD: The updates compute the exact DMD solution without approximation, but implementation requires storing two n × n matrices and the w most recent snapshots.Windowed DMD can also incorporate exponential weighting and extend to EDMD and online linear or nonlinear system identification.
4 Online system identification
The DMD framework can identify controlled linear systems by fitting state and input data jointly, and it extends to nonlinear systems through chosen observable functions. Under an assumed nonlinear form, the coefficients remain recoverable by linear regression.
- 4 Online system identification: DMD system identification estimates the state-transition and control matrices from observed states and control inputs using least-squares fitting.The formulation uses matrices built from state snapshots and inputs, then minimizes a cost function to find A and B.
- 4 Online system identification: The online and windowed DMD updates extend to controlled identification by replacing the square DMD matrix with a rectangular matrix.A new snapshot column can be incorporated using the same update strategy as in the uncontrolled case.
- 4.2 Online nonlinear system identification: Nonlinear identification assumes the dynamics can be approximated using a selected dictionary of nonlinear observables of state and input.The resulting representation expresses the next state through coefficients multiplying observables such as x, x^2, u, u^2, and xu.
- 4.2 Online nonlinear system identification: Although the state evolves nonlinearly, the observable coefficients can be identified with linear regression.This amounts to finding a coefficient matrix in the assumed observable representation rather than a true linear representation of the original dynamics.
- 4.2 Online nonlinear system identification: Assuming a particular nonlinear form allows the coefficients of the nonlinear system to be found using the same techniques as linear system identification.The approach is distinct from seeking a finite-dimensional exact linearization of general nonlinear dynamics.
5 Application and results
The benchmarks compare DMD algorithms for final-step computation and online updates, while applications test tracking in a time-varying system and wind-tunnel pressure data.
- 5.1 Benchmarks: For final-step computation, standard DMD is most efficient on the tested problem sizes, while fixed-rank streaming DMD scales better with state dimension.
- 5.1 Benchmarks: For online updates with n < 256, online DMD is fastest and can be orders of magnitude faster than standard batch and mini-batch algorithms.
- 5.1 Benchmarks: Streaming DMD is fastest for larger state dimensions because it scales linearly in n, but it computes a rank-r projection rather than the exact DMD matrix.
- 5.1 Benchmarks: Streaming and online DMD require no past-snapshot storage, whereas windowed and mini-batch DMD store w snapshots and batch DMD stores all past snapshots.
- 5.2 Linear time-varying system: In the linear time-varying system, decreasing online DMD's ρ makes it forget old data more aggressively and adapt faster to the increasing frequency.
- 5.3 Pressure fluctuations in a separation bubble: In wind-tunnel pressure data, dominant frequencies near 105 Hz and 135 Hz persist throughout the interval, while other fluctuations vary slowly over time.
6 Conclusion and outlook
The paper develops efficient online and windowed DMD methods for large data streams and slowly varying dynamics. Comparisons and examples show strong real-time efficiency and effective capture of time-varying dynamics, with further system-identification study left for future work.
- The proposed online and windowed DMD algorithms are especially useful when snapshots greatly outnumber the state dimension or dynamics vary slowly.
- The methods incorporate weighting that emphasizes recent snapshots over older ones, providing a soft cutoff for outdated data.
- For online computation, the new online and windowed DMD algorithms are the most efficient and can be orders of magnitude more efficient than standard DMD.
- Examples involving a linear time-varying system and wind-tunnel data show that weighted online DMD and windowed DMD capture time-varying dynamics effectively.
- More detailed study of applying the proposed algorithms to system identification is identified as future work, particularly for varying dynamics or real-time control.