Sampling and Inference of Networked Dynamics using Log-Koopman Nonlinear Graph Fourier Transform

Abstract

Networked nonlinear dynamics underpin the complex functionality of many engineering, social, biological, and ecological systems. Monitoring the networked dynamics via the minimum subset of nodes is essential for a variety of scientific and operational purposes. When there is a lack of a explicit model and networked signal space, traditional evolution analysis and non-convex methods are insufficient. An important data-driven state-of-the-art method use the Koopman operator to generate a linear evolution model for a vector-valued observable of original state-space. As a result, one can derive a sampling strategy via the linear evolution property of observable. However, current polynomial Koopman operators result in a large sampling space due to: (i) the large size of polynomial based observables ($O(N^2)$, $N$ number of nodes in network), and (ii) not factoring in the nonlinear dependency between observables. In this work, to achieve linear scaling ($O(N)$) and a small set of sampling nodes, we propose to combine a novel Log-Koopman operator and nonlinear Graph Fourier Transform (NL-GFT) scheme. First, the Log-Koopman operator is able to reduce the size of observables by transforming multiplicative poly-observable to logarithm summation. Second, a nonlinear GFT concept and sampling theory are provided to exploit the nonlinear dependence of observables for Koopman linearized evolution analysis. Combined, the sampling and reconstruction algorithms are designed and demonstrated on two established application areas. The results demonstrate that the proposed Log-Koopman NL-GFT scheme can (i) linearize unknown nonlinear dynamics using $O(N)$ observables, and (ii) achieve lower number of sampling nodes, compared with the state-of-the art polynomial Koopman linear evolution analysis.

References in corpus (18)

• A Data-Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition
• Deep learning for universal linear embeddings of nonlinear dynamics
• Discrete Signal Processing on Graphs: Sampling Theory
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Signals on Graphs: Uncertainty Principle and Sampling
• Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
• Dynamically induced cascading failures in power grids
• Pathways towards instability in financial networks
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Adaptive Least Mean Squares Estimation of Graph Signals
• Reconstruction of Graph Signals through Percolation from Seeding Nodes
• Distributed Adaptive Learning of Graph Signals
• Joint Sensing Matrix and Sparsifying Dictionary Optimization for Tensor Compressive Sensing
• Dynamics of organizational culture: Individual beliefs vs. social conformity
• Synchronization Patterns: From Network Motifs to Hierarchical Networks
• Observing and Tracking Bandlimited Graph Processes
• Thermodynamics of collective enhancement of precision
• Modeling Spread of Preferences in Social Networks for Sampling-based Preference Aggregation