Koopman Representations for Non-Vanishing Time Intervals: An Optimization Approach and Sampling Effects

1. Problem Statement

The paper addresses the challenge of learning Koopman eigenfunctions and eigenvalues from observational data of dynamical systems when the data is sampled at arbitrary, non-vanishing time intervals.

• Context: Koopman operator theory lifts nonlinear dynamics into an infinite-dimensional linear space, allowing for spectral decomposition. However, practical applications require finite-dimensional approximations.
• The Gap: Existing methods, such as Extended Dynamic Mode Decomposition (EDMD), often assume fixed, small time steps or rely on convex formulations that may obscure information loss. When time intervals are large (coarse sampling) or irregular, standard methods suffer from:
  • Aliasing: High-frequency dynamics are indistinguishable from lower frequencies due to the sampling pattern.
  • Identifiability Limits: The inability to uniquely determine the true spectral objects.
  • Optimization Challenges: The loss landscape may contain steep valleys or plateaus that hinder convergence.
• Goal: To formulate the learning of Koopman eigenpairs as a direct optimization problem that handles arbitrary time intervals and to analyze how sampling patterns (regular vs. irregular) affect the identifiability and optimization of these spectral objects.

2. Methodology

A. Optimization Formulation

The authors propose a non-convex optimization framework that operates directly on state observations $\{x(t_n)\}_{n=1}^N$ at arbitrary times $t_n$.

• Objective: Minimize the residual of the Koopman invariance condition:
  $$\min_{\phi \in \mathcal{V}, \lambda \in \mathbb{C}} L(\phi, \lambda) = \frac{1}{N} \sum_{n=1}^N \left| \phi(x(t_{n+1})) - e^{\lambda(t_{n+1}-t_n)}\phi(x(t_n)) \right|^2$$
  where $\mathcal{V}$ is a subspace spanned by a dictionary of basis functions $\{g_m\}$.
• Parameterization: The eigenfunction is approximated as $\phi(x) = a^\dagger G(x)$, where $a$ is a coefficient vector. The problem is reduced to finding the optimal coefficients $a$ and eigenvalue $\lambda = \alpha + i\beta$.
• Reduction: For a fixed $\lambda$, the optimal $a$ corresponds to the eigenvector associated with the smallest eigenvalue of a Hermitian matrix $C(\lambda)$. The problem becomes a 1D/2D search over $\lambda$:
  $$\min_{\alpha, \beta} \lambda_{\min}(C(\alpha, \beta))$$

B. Theoretical Analysis of the Loss Landscape

The paper provides a rigorous analysis of the loss landscape $L(\alpha, \beta)$:

1. Differentiability: Under the assumption of a simple spectrum for $C(\lambda)$, the smallest eigenvalue map is differentiable. The authors derive explicit gradient formulas (Proposition 1) to enable gradient-based optimization.
2. Aliasing and Periodicity (Regular Sampling):
   • For regular sampling with interval $\delta$, the loss function is periodic in the frequency domain ($\beta$) with period $2\pi/\delta$.
   • This periodicity creates aliasing: frequencies separated by integer multiples of $2\pi/\delta$ are indistinguishable, establishing a fundamental identifiability limit.
3. Phase Alignment (Local Geometry):
   • Near the true frequency $\beta^*$, the phases of the error terms align.
   • This creates a steep valley in the loss landscape, resulting in large gradient magnitudes. This necessitates careful step-size selection during optimization to avoid overshooting.
4. Effect of Irregular Sampling:
   • Breaking Aliasing: Irregular sampling destroys the periodicity of the loss landscape, effectively breaking the aliasing structure and improving identifiability.
   • Phase Cancellation: When the prediction error is large, irregular sampling causes phase cancellation in the gradient sum, leading to a gentler slope compared to the steep valleys seen in regular sampling.

3. Key Contributions

1. Novel Formulation: Extends previous work (specifically [17]) to complex Koopman spectral objects using a direct optimization approach that handles arbitrary time intervals without assuming a fixed step size.
2. Identifiability Analysis: Explicitly characterizes the aliasing limit induced by sampling patterns. Unlike convex EDMD formulations where this loss manifests as bias, this approach reveals it as periodicity in the loss landscape.
3. Optimization Insights: Identifies the phase alignment phenomenon near the true frequency, explaining why high-precision line searches are necessary and why optimization can be sensitive to step sizes.
4. Irregular Sampling Advantage: Theoretically and numerically demonstrates that irregular sampling can break aliasing and improve the recovery of high-frequency spectral objects, potentially allowing for the recovery of signals below the Nyquist rate (analogous to compressed sensing).

4. Numerical Results

The authors tested their method against gEDMD (Generator Extended Dynamic Mode Decomposition) on two systems:

• Case A: Nonlinear System (Coarse Sampling)

  • System: A 2D nonlinear system with eigenvalues $\delta$ and combinations of $\gamma, \delta$.
  • Setup: Tested with large time intervals ($\Delta t = 0.05, 0.25, 0.5$).
  • Result: The proposed method successfully recovered true eigenvalues for all initial guesses across all time intervals. In contrast, gEDMD failed to recover true eigenvalues for larger intervals ($\Delta t \ge 0.25$) and produced spurious eigenvalues.

• Case B: Harmonic Oscillator (High Frequency)

  • System: A harmonic oscillator with high frequency ($\omega = 50$).
  • Setup: Compared regular sampling ($\Delta t = 0.2$ vs $0.01$) against irregular sampling (20 random points from a 400-point dense set).
  • Results:
    • Regular Sampling: The loss landscape exhibited periodicity. The method often converged to aliased frequencies or stalled on plateaus due to vanishing gradients far from the optimum.
    • Irregular Sampling: The periodicity vanished. The method successfully identified the true eigenvalues ($\pm 50i$) from most initial guesses, demonstrating that irregular sampling mitigates aliasing and improves identifiability.

5. Significance and Conclusion

• Robustness: The proposed optimization approach is more robust than gEDMD, particularly when dealing with coarse or irregular data, which is common in real-world applications (e.g., traffic sensors, biological gait data).
• Sampling Strategy: The work provides a theoretical justification for using irregular sampling in data acquisition for dynamical systems. It suggests that irregularity is not just a nuisance to be corrected but a feature that can enhance spectral recovery by breaking aliasing.
• Optimization Guidance: The analysis of the loss landscape (steep valleys vs. phase cancellation) offers practical guidance for designing optimization algorithms (e.g., adaptive step sizes, line searches) for Koopman-based learning.

In summary, this paper bridges the gap between theoretical Koopman operator theory and practical data assimilation by providing a robust optimization framework that explicitly accounts for and leverages the effects of sampling patterns on spectral identifiability.