Efficient streaming dynamic mode decomposition

Dynamic mode decomposition (DMD) is a widely used technique for revealing the discrete spectrum in complex dynamical systems, and this work proposes an efficient streaming variant that reduces computational redundancy by maintaining only a single orthonormal basis. This reformulation results in a constant-factor reduction in computational complexity and memory storage requirements while preserving the accuracy of the method for characterizing system dynamics in real-time data streams.

The gist

The primary contribution of this work is to demonstrate that maintaining only a single orthonormal basis is sufficient to characterize the system dynamics accurately, eliminating the need for dual basis updates inherent in standard streaming dynamic mode decomposition (sDMD).

Background and Motivation

Dynamic mode decomposition (DMD) has been extensively used across various fields, from epidemiology to power systems. While batch-processing DMD requires collecting data upfront, stream-processing DMD (sDMD) offers a way to analyze data sequentially as it arrives. The original sDMD method maintains two orthonormal bases, QXk and QYk, are maintained to span the evolving column spaces of Xk and Yk, respectively. This approach introduces redundancy because it expands and rotates two separate orthonormal bases corresponding to the column spaces of the same underlying dynamical system.

The Proposed Method: Efficient Streaming Dynamic Mode Decomposition (esDMD)

The core innovation is the reformulation into efficient streaming dynamic mode decomposition (esDMD), which maintains only a single orthonormal basis. This is possible because, given that each snapshot pair can be expressed as a sequence of consecutive states, i.e., xi = yi−1, it allows for the use of a single evolving basis without loss of generality. The method initializes this single basis using the QR decomposition on the joint column space: Initialize Q1 = QR(x1 y1), (8) where QR(·) returns an orthonormal basis obtained via QR decomposition.

Rank-Preserving Updates

The update procedure for the single basis is designed to handle new dynamics while maintaining a fixed rank, r. The paper outlines a specific sequence of steps for updating the basis at each time step i = k + 1:

1. Append a new column to the current basis: Q′k = Qk pk+1.

2. Pad the existing Gram matrix with zeros to match the dimensions of the expanded basis: G′Yk = GYk 0 0 0.

3. Retain only the top r eigenvectors of G′Yk: W˜ ′k = W′i[:,: r].

4. Rotate Q′k to obtain the updated basis: Qk+1 = Q′i W˜ ′i.

Computational Complexity and Efficiency

The computational costs in sDMD arise from performing eigendecompositions of the Gram matrices GYi and GYj, computing the Moore–Penrose pseudoinverse of GXi, and calculating and decomposing the matrix A˜i. These operations result in an overall complexity of O(nr3). The proposed esDMD algorithm shares this asymptotic complexity but achieves a constant factor speed-up by eliminating redundant computations. Specifically, a direct comparison reveals that the proposed method requires approximately 350 static bytecode instructions, whereas sDMD requires around 515.

Experimental Validation

The efficiency and accuracy of esDMD were validated on two representative systems: (i) an oscillatory system generated from a sum of scaled sinusoids, and (ii) a Kuramoto oscillator network. In both cases, the results indicate that the proposed esDMD algorithm performs comparably to sDMD in capturing the dominant dynamic modes. Furthermore, the comparison of execution times shows that esDMD is significantly faster than sDMD, with a shorter and less variable bar for esDMD highlights its computational advantage over standard sDMD. Both streaming variants successfully capture the dominant r spectral components.

Conclusion

The proposed method, esDMD, successfully reformulates sDMD by maintaining only a single orthonormal basis to eliminate redundancy. This simplification preserves the accuracy of the computed dynamic modes and eigenvalues while achieving substantial computational savings, making it more practical for streaming applications. The results confirm that esDMD is as effective as sDMD in capturing the dominant dynamics, but it achieves this in a fraction of the time required by sDMD.

How it works

The core innovation of esDMD lies in reducing the required basis maintenance from two separate bases (one for Xk and one for Yk) to just one. This is achieved by exploiting the temporal continuity of the data stream, where each snapshot pair can be equivalently expressed as (yi−1, yi), allowing a single evolving basis to span both column spaces.

The initialization phase sets this single basis using the QR decomposition on the joint snapshot pair (x1, y1).

Here are the specific improvements to AI systems derived from the proposed Efficient Streaming Dynamic Mode Decomposition (esDMD) method, along with what these improved systems can achieve:

) Improved AI System Capabilities:

1. A real-time, high-frequency dynamic system model capable of predicting future states based on continuous sensor streams (e.g., power grid stability or fluid dynamics).

2. A more computationally efficient method for extracting latent, low-dimensional representations (Koopman modes) from sequential, noisy data streams compared to standard Dynamic Mode Decomposition (DMD) or Streaming DMD (sDMD).

3. An adaptive system capable of recognizing and modeling evolving system dynamics in real-time without requiring a full historical dataset upfront.

4. Specific Technical Improvements:

a. Elimination of Computational Redundancy via Single Basis Maintenance:

A major bottleneck in sDMD is maintaining two separate orthonormal bases for the state matrix evolution (one for the input snapshots and one for the output snapshots). esDMD replaces this with a single evolving basis, exploiting the temporal continuity property where snapshot pairs are effectively sequential.

b. Constant-Factor Complexity Reduction:

The proposed method achieves a constant-factor reduction in computational complexity and memory storage compared to sDMD by eliminating redundant updates (e.g., consecutive eigendecompositions of Gram matrices) that occur when a new mode is introduced, as seen in the Rank-preserving updates step of Algorithm 1.

c. Optimized Mode Extraction for Low-Rank Data:

The algorithm leverages the structure of the input data (column spaces lying in low-dimensional subspaces) to efficiently compress and rotate the basis using proper orthogonal decomposition compression (Step 3 in Algorithm 1), ensuring that the rank remains capped at a manageable dimension 'r' without losing critical dynamic information.

d. Streamlined Update Procedure:

The update mechanism is consolidated into a single basis, requiring only one set of Gram matrix updates and rotations per time step, rather than the coupled updates required by sDMD for each base independently. This reduces the instruction count (e.g., 350 vs. 515 instructions in Algorithm 1).

3. Specific AI System Applications:

a. Real-Time Power System Monitoring and Control:

The system can ingest continuous synchrophasor data (like those from the Kuramoto model) to detect phase synchronization or incipient instability in power grids much faster than traditional DMD methods, allowing for immediate corrective actions based on predicted modes.

b. Adaptive Neural Network Modeling (Koopman Filtering):

By generating a more efficient linear operator representation of the system dynamics using esDMD, the resulting reduced-order model can be used to train or initialize a Koopman Kalman Filter (as suggested in Section V), enabling more robust and adaptive state estimation for systems with time-varying dynamics.

c. High-Frequency Signal Processing:

The ability to process data incrementally and maintain low memory overhead makes this framework suitable for applications where data arrives continuously (e.g., high-speed sensor arrays or real-time control loops) where batch processing is infeasible.

We propose a reformulation of the streaming dynamic mode decomposition method that requires maintaining a single orthonormal basis, thereby reducing computational redundancy. The proposed efficient streaming dynamic mode decomposition method results in a constant-factor reduction in computational complexity and memory storage requirements. Numerical experiments on representative canonical dynamical systems show that the enhanced computational efficiency does not compromise the accuracy of the proposed method.