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

**Authors:** Zhuangkun Wei, Bin Li, Chengyao Sun, Weisi Guo  
**arXiv:** [2004.09615](https://arxiv.org/abs/2004.09615)  
**Date:** 2020-04-20  
**Summary page:** https://www.summarizepaper.com/en/paper/2004.09615v2/

## Key points

- The paper addresses the challenge of monitoring networked dynamics in various systems
- Monitoring these dynamics through a minimum subset of nodes is crucial for scientific and operational purposes
- Traditional evolution analysis and non-convex methods are often inadequate when explicit models and networked signal spaces are lacking
- The authors propose a novel approach that combines the Log-Koopman operator and nonlinear Graph Fourier Transform (NL-GFT) scheme
- The Log-Koopman operator reduces the size of observables by transforming multiplicative poly-observables into logarithm summations
- Current polynomial Koopman operators result in a large sampling space due to the large size of polynomial-based observables and their failure to account for nonlinear dependencies between observables
- The authors introduce a nonlinear GFT concept and sampling theory to exploit the nonlinear dependence of observables for Koopman linearized evolution analysis
- Sampling and reconstruction algorithms are designed using these techniques, achieving linear scaling while requiring fewer sampling nodes compared to existing methods
- The proposed scheme is evaluated on two application areas, demonstrating its ability to linearize unknown nonlinear dynamics using only O(N) observables while requiring fewer sampling nodes compared to state-of-the-art approaches
- The approach reduces computational complexity while maintaining accuracy in capturing nonlinear dependencies

## Summary

The paper titled "Sampling and Inference of Networked Dynamics using Log-Koopman Nonlinear Graph Fourier Transform" addresses the challenge of monitoring networked dynamics in various engineering, social, biological, and ecological systems. The ability to monitor these dynamics through a minimum subset of nodes is crucial for scientific and operational purposes. However, traditional evolution analysis and non-convex methods are often inadequate when explicit models and networked signal spaces are lacking. To overcome these limitations, the authors propose a novel approach that combines the Log-Koopman operator and nonlinear Graph Fourier Transform (NL-GFT) scheme. The Log-Koopman operator reduces the size of observables by transforming multiplicative poly-observables into logarithm summations. This reduction is significant because current polynomial Koopman operators result in a large sampling space due to the large size of polynomial-based observables (proportional to the square of the number of nodes in the network) and their failure to account for nonlinear dependencies between observables. In addition to the Log-Koopman operator, the authors introduce a nonlinear GFT concept and sampling theory to exploit the nonlinear dependence of observables for Koopman linearized evolution analysis. By combining these techniques, they design sampling and reconstruction algorithms that achieve linear scaling (proportional to the number of nodes) while requiring a smaller set of sampling nodes compared to existing polynomial Koopman linear evolution analysis methods. The proposed Log-Koopman NL-GFT scheme is evaluated on two established application areas, demonstrating its ability to linearize unknown nonlinear dynamics using only O(N) observables (where N is the number of nodes) while achieving a lower number of required sampling nodes compared to state-of-the-art approaches. Overall, this paper presents an innovative approach for monitoring networked dynamics by leveraging the Log-Koopman operator and NL-GFT scheme. The results highlight its effectiveness in reducing computational complexity while maintaining accuracy in capturing nonlinear dependencies. This research has implications for a wide range of fields that rely on understanding and monitoring complex networked systems.