Willems' Fundamental Lemma for Nonlinear Systems With Koopman Linear Embedding

Xu Shang, Jorge Cortés, Yang Zheng

TL;DR

This paper extends the famous Willems’ Fundamental Lemma—a cornerstone of data-driven control for linear systems—to a broad class of nonlinear systems. By leveraging Koopman operator theory, the authors prove that you can represent nonlinear dynamics using only raw data trajectories, completely bypassing the need to manually design or learn complex "lifting functions."

What Problem Does This Paper Address?

In the world of control theory, linear systems are the "easy mode" because we have powerful, well-understood tools to manage them. Nonlinear systems are the "hard mode." To bridge this gap, researchers often use two strategies:

  1. Willems’ Fundamental Lemma (WFL): This allows us to represent a linear system using a library of its past trajectories instead of a formal mathematical model. It’s great for "model-free" control, but it’s strictly for linear systems.
  2. Koopman Operator Theory: This maps a nonlinear system into a higher-dimensional "lifted" space where the dynamics look linear. The catch? You have to choose the right "lifting functions" (observables), which is often a trial-and-error "black art" that introduces significant bias if done incorrectly.

The authors tackle the missing link: How can we use the trajectory-based simplicity of WFL for nonlinear systems without the headache of choosing Koopman lifting functions?

Methods

The authors introduce a framework for nonlinear systems that admit a Koopman Linear Embedding. Their approach relies on three main pillars:

  • Trajectory Space Mapping: They characterize the exact relationship between the trajectories of the original nonlinear system and its high-dimensional linear Koopman counterpart.
  • Lifted Excitation: They propose a new condition for data richness. While standard control requires "persistently exciting" inputs, this paper introduces "lifted excitation," which ensures the collected data trajectories are diverse enough to capture the "hidden" dimensions of the Koopman space.
  • Data-Driven Representation: They prove that a linear combination of "rich enough" raw nonlinear trajectories can perfectly represent the system's evolution. This allows them to build a predictive model (similar to Data-enabled Predictive Control or DeePC) using only a matrix of raw input-output data.

Datasets

The paper validates its theory using a synthetic numerical experiment rather than a public benchmark dataset.

  • The System: A 2D nonlinear system with polynomial terms (up to the 4th power).
  • Baselines: The authors compare their proposed DD-K (Data-Driven Koopman) method against:
  • DD-A: Data-driven affine representation.
  • EDMD-K: Standard Koopman approximation using Extended Dynamic Mode Decomposition.
  • DNN-K: A Deep Neural Network-based Koopman representation.

Key Insights and Ideas

  • Lifting is Redundant: The most striking insight is that if a Koopman embedding exists, the raw data trajectories already contain the information of the lifting functions. You don't need to find $\phi(x)$; you just need enough trajectories to span the space.
  • The Importance of "Depth": While most data-driven methods focus on getting more trajectories (width), this paper highlights that the length of the initial trajectory (depth) is critical. A longer initial sequence is required to uniquely "pin down" the state in the hidden high-dimensional Koopman space.
  • Exactness vs. Approximation: Unlike neural networks or EDMD, which provide an approximation of the dynamics, this method is theoretically exact for systems that admit a linear embedding.

Key Results

  • Perfect Prediction: In simulations, the DD-K method perfectly matched the true system trajectory once the initial trajectory length ($T_{ini}$) reached the required threshold (in this case, $T_{ini} = 4$).
  • Superior Control: In tracking tasks (following a sine wave or a step signal), the DD-K controller achieved significantly lower "realized control costs" compared to Affine, EDMD, and Deep Learning models.
  • Data Efficiency: The DD-K method outperformed Deep Learning approaches while requiring an order of magnitude less data. The DNN-based models showed high variance and required $10^5$ trajectories, whereas DD-K succeeded with just a handful of well-chosen trajectories.

Limitations and Future Work

  • Existence of Embedding: The theory assumes the nonlinear system can be embedded into a finite-dimensional linear space. Not all systems satisfy this, and determining if one does remains an open challenge.
  • Noise Sensitivity: The current proofs assume clean data. While the authors mention that regularization can help, a rigorous analysis of how measurement noise affects the "lifted excitation" condition is needed.
  • Estimating Dimension: To use this method, one needs to know (or guess) the dimension of the Koopman space ($n_z$). The authors suggest this is non-trivial and propose it as a direction for future research.

Summary updated

Abstract

Koopman operator theory and Willems’ fundamental lemma both can provide (approximated) data-driven linear representation for nonlinear systems. However, choosing lifting functions for the Koopman operator is challenging, and the quality of the data-driven model from Willems’ fundamental lemma has no guarantee for general nonlinear systems. In this letter, we extend Willems’ fundamental lemma for a class of nonlinear systems that admit a Koopman linear embedding. We first characterize the relationship between the trajectory space of a nonlinear system and that of its Koopman linear embedding. We then prove that the trajectory space of Koopman linear embedding can be formed by a linear combination of rich-enough trajectories from the nonlinear system. Combining these two results leads to a data-driven representation of the nonlinear system, which bypasses the need for the lifting functions and thus eliminates the associated bias errors. Our results illustrate that both the width (more trajectories) and depth (longer trajectories) of the trajectory library are important to ensure the accuracy of the data-driven model.
BibTeX
@inproceedings{shang2024willems,
  author = {Xu Shang and Jorge Cortés and Yang Zheng},
  title = {{Willems' Fundamental Lemma for Nonlinear Systems With Koopman Linear Embedding}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2024},
  url = {https://openreview.net/forum?id=6JFPAsHO1X},
}

Loading related content...

Figure