Dynamic mode decomposition in vector-valued reproducing kernel Hilbert spaces for extracting dynamical structure among observables

Keisuke Fujii, Yoshinobu Kawahara

Dynamic Mode Decomposition (DMD) has become a cornerstone for analyzing nonlinear dynamical systems (NLDSs) by leveraging Koopman operator theory. By "lifting" nonlinear dynamics into a linear, infinite-dimensional space, DMD identifies eigenvalues and modes that characterize a system's evolution. However, standard DMD often treats observables as flat vectors, discarding the inherent relational structure—such as graph connectivity—present in complex systems like traffic networks or neural circuits.

In their 2019 paper, Keisuke Fujii and Yoshinobu Kawahara introduce a significant extension to this toolset, moving from scalar-valued to vector-valued function spaces to extract global dynamics from complex, structured data.

The vvRKHS Framework

The authors address the limitations of conventional DMD by reformulating Koopman spectral analysis within vector-valued Reproducing Kernel Hilbert Spaces (vvRKHS). Unlike traditional scalar kernels, matrix-valued kernels allow the model to explicitly account for the "structure among observables." This shift enables the extraction of global dynamics directly from structured data, such as sequences of adjacency matrices, without destroying the underlying geometry of the system.

By using vvRKHS, the relationship between variables (the graph) is treated as a dynamical observable itself. This allows researchers to treat an entire graph as a single point in a function space, facilitating the observation of how the connectivity of a system oscillates over time.

Technical Implementation: TDMD and Graph DMD

To manage the high dimensionality of structured data, the authors utilize two key technical strategies:

  1. Reformulated Tensor-based DMD (TDMD): To avoid the "curse of dimensionality," the authors employ the Tensor-Train (TT) format. This approach decomposes large tensors into smaller, manageable "cores," providing a more stable and direct estimation procedure for TDMD than previous iterations.
  2. Graph DMD: As a specific application, the authors propose Graph DMD. In this setup, a sequence of adjacency matrices representing a graph changing over time is treated as a realization of the kernel structure. This allows the algorithm to find "graph modes" that correspond to specific temporal frequencies or growth rates.

Experimental Validation

The authors validated their approach using three distinct datasets, ranging from synthetic benchmarks to real-world traffic patterns:

  • Synthetic Data: Testing on noisy adjacency matrices (up to $256 \times 256$) showed that Graph DMD was significantly more accurate than "Exact DMD," with the performance gap widening as the dimensionality of the matrices increased.
  • Bike-Sharing Dynamics: Using data from Washington D.C.’s Capital Bikeshare (348 stations), the method successfully identified daily (1/24 hr) and weekly (1/168 hr) periodicities. It mapped spatial coherence, distinguishing between traffic patterns at the Lincoln Memorial (coherent across both cycles) and Union Station (dominant in the weekly cycle).
  • Fish-Schooling Simulation: In a multi-agent model simulating "fish" behaviors (swarm, torus, and parallel), Graph DMD achieved a classification error of only 0.022. This vastly outperformed Tensor DMD (0.311) and Exact DMD (0.511), demonstrating that preserving graph structure is critical for recognizing complex group behaviors.

Limitations and Future Directions

While the framework is powerful, it faces several practical challenges. Like all kernel methods, the choice of the matrix-valued kernel is crucial, and defining optimal kernels for diverse structured data remains an open research question. Additionally, the mathematical framework assumes symmetric positive semi-definite (SPSD) matrices; since real-world adjacency matrices often lack this property, the authors applied diagonal shifts to satisfy theoretical requirements. Finally, while the Tensor-Train format aids scaling, the reliance on sequential Singular Value Decompositions (SVDs) may present bottlenecks for extremely large-scale or real-time applications.

Conclusion

By integrating vvRKHS with Koopman theory, this research provides a robust method for analyzing systems where the relationship between variables is as vital as the variables themselves. Graph DMD represents a significant advancement in preserving structural integrity during dynamical analysis, offering a clearer lens into the rhythmic patterns of complex, networked systems.

Summary updated

Abstract

Understanding nonlinear dynamical systems (NLDSs) is challenging in a variety of engineering and scientific fields. Dynamic mode decomposition (DMD), which is a numerical algorithm for the spectral analysis of Koopman operators, has been attracting attention as a way of obtaining global modal descriptions of NLDSs without requiring explicit prior knowledge. However, since existing DMD algorithms are in principle formulated based on the concatenation of scalar observables, it is not directly applicable to data with dependent structures among observables, which take, for example, the form of a sequence of graphs. In this paper, we formulate Koopman spectral analysis for NLDSs with structures among observables and propose an estimation algorithm for this problem. This method can extract and visualize the underlying low-dimensional global dynamics of NLDSs with structures among observables from data, which can be useful in understanding the underlying dynamics of such NLDSs. To this end, we first formulate the problem of estimating spectra of the Koopman operator defined in vector-valued reproducing kernel Hilbert spaces, and then develop an estimation procedure for this problem by reformulating tensor-based DMD. As a special case of our method, we propose the method named as Graph DMD, which is a numerical algorithm for Koopman spectral analysis of graph dynamical systems, using a sequence of adjacency matrices. We investigate the empirical performance of our method by using synthetic and real-world data.
BibTeX
@article{fujii2019dynamic,
  author = {Keisuke Fujii and Yoshinobu Kawahara},
  title = {{Dynamic mode decomposition in vector-valued reproducing kernel Hilbert spaces for extracting dynamical structure among observables}},
  journal = {Neural Networks},
  year = {2019},
  doi = {10.1016/j.neunet.2019.04.020},
}
Figure