A quantitative and constructive proof of Willems' Fundamental Lemma and its implications

Julian Berberich, Andrea Iannelli, Alberto Padoan, Jeremy Coulson, Florian Dörfler, Frank Allgöwer

Abstract

Willems' Fundamental Lemma is a cornerstone of data-driven control, providing a mechanism to parametrize the trajectories of a controllable linear time-invariant (LTI) system using a single trajectory of data. However, traditional proofs are often qualitative, relying on binary rank conditions that do not account for data quality or noise. This paper presents a novel, quantitative, and constructive proof of the lemma. By leveraging techniques from classical adaptive control and shifting from rank-based conditions to singular value bounds, we derive explicit lower bounds for data richness. Our results reveal the critical role of system zeros in excitation and provide a robust framework for evaluating the reliability of data-driven system representations.

Introduction

In the field of data-driven control, Willems’ Fundamental Lemma serves as the theoretical bridge between raw data and system behavior. It asserts that for a controllable LTI system, a single trajectory generated by a "persistently exciting" (PE) input contains enough information to characterize all possible system trajectories. This allows for prediction and control without an explicit mathematical model (e.g., state-space matrices).

Despite its utility, the standard formulation of the lemma is qualitative. It defines persistence of excitation through rank conditions—essentially a "yes/no" check on whether a Hankel matrix is full rank. In practical applications involving measurement noise or near-singular dynamics, this binary approach fails to quantify the "richness" or reliability of the data. This paper addresses this gap by providing a constructive proof that establishes quantitative bounds on data excitation.

Methodology: From Qualitative to Quantitative

A State-Space Approach

While many proofs of the Fundamental Lemma utilize a behavioral framework, this work adopts a state-space approach inspired by the adaptive control literature of the 1980s. By using the Cayley-Hamilton theorem, we establish an input-output representation that directly links the richness of the input signal to the richness of the internal state and the resulting output.

Redefining Persistence of Excitation (PE)

We move beyond simple rank conditions to define PE using a matrix-valued lower bound, denoted as $K$. This allows for a "directional" understanding of excitation. Rather than simply asking if the system is excited, we can determine which specific directions in the state space are well-captured by the data. This is crucial for understanding how excitation propagates through the system dynamics.

Key Results and Theorem III.2

The central contribution of this research is Theorem III.2, which provides a quantitative version of the Fundamental Lemma. The theorem proves that if an input is $K_u$-PE of a specific order, the combined input-state data matrix satisfies the following constructive bound:

$$\begin{bmatrix} H_1(x) \\ H_L(u) \end{bmatrix} \begin{bmatrix} H_1(x) \\ H_L(u) \end{bmatrix}^\top \succeq \frac{1}{n+1} Z K_u Z^\top$$

In this expression, $Z$ is a matrix containing the system's coefficients (derived from the characteristic polynomial). This formula is significant because it is constructive: it allows engineers to calculate an explicit lower bound for data richness based on known input properties and the system's structural parameters. This provides a "safety margin" for data-driven algorithms, ensuring that the data used for control is sufficiently robust.

The Role of System Zeros

An unexpected insight from this quantitative approach is the role of system zeros. In Single-Input Single-Output (SISO) systems, the analysis reveals that the required order of input excitation is directly related to the number of system zeros. Specifically, to guarantee a PE output, the input must be PE of an order that accounts for these zeros. This generalizes existing results in adaptive control and clarifies how internal system structures can "filter" the richness of the input data.

Implications for Robustness

Because the proof is quantitative, it naturally extends to "Robust Fundamental Lemmas." In real-world scenarios where system parameters are only known approximately, the derived bounds can be adjusted to account for uncertainty. By incorporating error bounds into the $Z$ matrix, we can maintain guarantees on data richness even in the presence of modeling inaccuracies.

Additionally, this work clarifies the historical record. In the appendix, we provide a counterexample to a claim made in a classic 1986 paper regarding the necessity of certain PE conditions. This correction ensures that future research in data-driven control is built on a mathematically sound foundation.

Conclusion and Future Work

This paper provides a more rigorous and practical foundation for Willems' Fundamental Lemma. By shifting to a quantitative framework, we provide the tools necessary to evaluate data quality in a way that binary rank conditions cannot.

Future research will focus on extending these quantitative bounds to:

  1. Measurement Noise: Developing bounds that explicitly account for stochastic or bounded noise in the data trajectory.
  2. Nonlinear Systems: Investigating whether similar constructive proofs can be derived for classes of nonlinear systems.
  3. Data-Driven Predictive Control (DDPC): Applying these bounds to improve the stability and robustness of DDPC algorithms, which are often sensitive to the quality of the underlying data Hankel matrices.

Summary updated

Abstract

Willems' Fundamental Lemma provides a powerful data-driven parametrization of all trajectories of a controllable linear time-invariant system based on one trajectory with persistently exciting (PE) input. In this paper, we present a novel proof of this result which is inspired by the classical adaptive control literature and differs from existing proofs in multiple aspects. The proof involves a quantitative and directional PE notion, allowing to characterize robust PE properties via singular value bounds, as opposed to binary rank-based PE conditions. Further, the proof is constructive, i.e., we derive an explicit PE lower bound for the generated data. As a contribution of independent interest, we generalize existing PE results from the adaptive control literature and reveal a crucial role of the system's zeros.
BibTeX
@inproceedings{berberich2023quantitative,
  author = {Julian Berberich and Andrea Iannelli and Alberto Padoan and Jeremy Coulson and Florian Dörfler and Frank Allgöwer},
  title = {{A quantitative and constructive proof of Willems' Fundamental Lemma and its implications}},
  booktitle = {ACC},
  year = {2023},
  doi = {10.23919/acc55779.2023.10156227},
}
Figure