Source-linked AI summary
Willems' Fundamental Lemma for State-space Systems and its Extension to Multiple Datasets
Henk J. van Waarde, Claudio De Persis, M. Kanat Camlibel, Pietro Tesi
TL;DR
The paper addresses the absence of a fundamental-lemma result for multiple, possibly short trajectories, motivated by unstable systems and missing or poorly exciting data. It proves a state-space and multi-trajectory extension based on collective persistency of excitation, showing that finite datasets can parameterize all system trajectories and support missing-data identification and unstable-system control. In one unstable-system example, the computed feedback gain differs from the true optimal gain by 7.083 · 10^-11.
Problem
A proof of Willems’ fundamental lemma for multiple trajectories was missing, despite applications involving short, poorly excited, unstable, corrupted, or missing data.
Method
The paper gives a self-contained state-space proof and introduces collective persistency of excitation to extend trajectory parameterization from one dataset to multiple trajectories.
Results
The extended lemma shows that finitely many collectively persistently exciting trajectories parameterize all system trajectories and enable missing-data identification and unstable-system controller construction.
Takeaways & Limitations
The result supports data-driven identification with missing samples and controller design for unstable systems using multiple measured trajectories.
Abstract
from arXiv · showhide
Willems et al.'s fundamental lemma asserts that all trajectories of a linear system can be obtained from a single given one, assuming that a persistency of excitation condition holds. This result has profound implications for system identification and data-driven control, and has seen a revival over the last few years. The purpose of this paper is to extend Willems' lemma to the situation where multiple (possibly short) system trajectories are given instead of a single long one. To this end, we introduce a notion of collective persistency of excitation. We will then show that all trajectories of a linear system can be obtained from a given finite number of trajectories, as long as these are collectively persistently exciting. We will demonstrate that this result enables the identification of linear systems from data sets with missing data samples. Additionally, we show that the result is of practical significance in data-driven control of unstable systems.
I. INTRODUCTION
The paper extends Willems’ fundamental lemma from one persistently exciting trajectory to multiple trajectories, including short or incomplete datasets. It provides a state-space proof and applies the extension to missing-data identification and unstable-system control.
- A single sufficiently exciting trajectory can parameterize all trajectories of a linear system, supporting identification, simulation, and data-driven control.
- Multiple short trajectories are useful for unstable systems, poorly excited normal-operation data, and trajectories containing corrupted or missing samples.
- The paper supplies a complete, self-contained state-space proof using the Cayley-Hamilton theorem and the Kalman controllability test.
- The extension introduces collective persistency of excitation and shows that finitely many collectively exciting trajectories parameterize all system trajectories.
- Applications demonstrate identification from missing samples and controller computation for unstable systems using multiple short trajectories.
A. Notation
This section defines the signal restriction notation and the Hankel-matrix-based notion of persistent excitation used later in the paper.
- For a signal f, f[i,j] denotes its restriction to the integer interval [i,j], or the corresponding sequence of samples.
- The Hankel matrix of depth k is constructed from consecutive samples, with k denoting its number of block rows.
- A sequence is persistently exciting of order k when its depth-k Hankel matrix has full row rank.
II. WILLEMS et al.’S FUNDAMENTAL LEMMA IN THE CONTEXT OF STATE-SPACE SYSTEMS
The state-space formulation proves that sufficiently exciting input data satisfy a key rank condition and span every length-L input/output trajectory of the system.
- The forward direction follows from linearity because each data column is itself a length-L trajectory, so any real linear combination remains a trajectory.
- Every length-L input/output trajectory is a linear combination of the columns formed from the measured input and output data.
- The theorem considers a controllable LTI system whose measured input is persistently exciting of order n + L.
- Under these assumptions, the stacked state and input Hankel matrix has full row rank.
- The proof establishes the rank condition by showing that a left-kernel vector must vanish, using persistency of excitation, Cayley-Hamilton, and controllability.
III. EXTENSION OF WILLEMS et al.’S LEMMA TO MULTIPLE TRAJECTORIES
The paper extends Willems’ fundamental lemma from one trajectory to multiple trajectories by introducing collective persistency of excitation. Under this condition, finitely many trajectories parameterize every length-L system trajectory, including when individual datasets are short.
- Collective persistency of excitation: Collective persistency of excitation is defined by full row rank of a mosaic-Hankel matrix formed from multiple input sequences.At least one individual sequence being persistently exciting is sufficient, but collective excitation can also hold when none is individually exciting.
- Collective persistency of excitation: Collective excitation can be achieved with shorter datasets because the total length condition is Σ_i T_i ≥ k(m + q) − q, allowing T_i as short as k when q is sufficiently large.A single input sequence requires T ≥ k(m + 1) − 1 for persistency of excitation of order k.
- Extended fundamental lemma: Theorem 2 assumes controllability and collective persistency of excitation of order n + L, then establishes a full-row-rank condition for the combined data matrix.The theorem applies to q given input/state/output trajectories.
- Extended fundamental lemma: Every length-L input/output trajectory can be expressed as a linear combination of the given multiple trajectories’ input/output data.The representation uses a real coefficient vector g and is an if-and-only-if characterization of system trajectories.
- Extended fundamental lemma: When q = 1 and T_1 = T, Theorem 2 reduces to the original single-experiment fundamental lemma.Thus, the multiple-trajectory result contains the standard theorem as a special case.
A. Identification with missing data samples
The paper applies the multiple-trajectory lemma to identify linear systems from partially corrupted trajectories. Missing samples are handled by reconstructing unknown outputs through linear combinations of available trajectory data and extracting Markov parameters.
- Problem setup: A partially corrupted input/output trajectory is divided into three available system trajectories, whose inputs are collectively persistently exciting of order 5.The example considers a minimal LTI system of unknown state-space dimension n = 2 and rules out dimension 1.
- Reconstruction method: Theorem 2 is used to construct a length-7 trajectory containing unknown values, with the unknown entries computed as functions of a coefficient vector D.The construction exploits available partial trajectories and imposes zero past inputs and outputs to obtain a zero initial state.
- Reconstruction method: The iterative reconstruction computes missing outputs by solving linear systems for successive length-3 trajectories.The first recovered values include ȳ(0) = 1 and ȳ(1) = 0.
- Identification result: The recovered outputs are ȳ(2) = 1, ȳ(3) = 2, and ȳ(4) = 3, yielding Markov parameters D = 1, CB = 0, CAB = 1, CA^2B = 2, and CA^3B = 3.These Markov parameters can be converted into a state-space realization using the Ho–Kalman algorithm.
- Scope and limitation: The approach also applies to multiple consecutive missing samples, but requires enough partial trajectories of length at least 5 to ensure collective excitation of order 5.With more frequent missing data, identification may still be possible using left kernels of submatrices of the Hankel matrix.
B. Data-driven LQR of an unstable system
The paper applies a data-based semidefinite design procedure to an unstable batch reactor, comparing one long trajectory with multiple short, collectively exciting trajectories. Multiple short experiments accurately recover the optimal gain and yield a stable closed loop, although they require more samples overall.
- LQR objective: The example designs an optimal control input minimizing a cost functional subject to the zero endpoint constraint lim_t→∞x(t)=0.Under standard assumptions, the unique optimal input is generated by u*=Kx, with P+ linked to the algebraic Riccati equation.
- Single-trajectory design: The data-based procedure obtains P+ and K by solving a semidefinite program using measured input/state data.The method uses persistently exciting input data and a right inverse of the measured state matrix in the controller-design step.
- Multiple short experiments: The multiple-trajectory experiment uses q = 5 data sets of length Ti = 6 whose inputs are collectively persistently exciting of order 5.The data matrices are concatenated before solving the same semidefinite program.
- Multiple short experiments: ||Pmult − P+|| = 7.849 · 10^-10, while ||Kmult − K|| = 7.083 · 10^-11 and the closed-loop spectral radius is 0.188.The resulting closed-loop matrix A + BKmult is stable, showing accurate feedback-gain computation for the unstable system.
- Comparison and scope: Multiple trajectories require more samples overall: at least Σ_i Ti ≥ 30 here, versus T ≥ 14 for one trajectory to achieve order-5 excitation.Despite this sample requirement, multiple short trajectories enable accurate gains when a single long trajectory may be numerically problematic.
V. CONCLUSIONS
The paper extends Willems’ fundamental lemma from one persistently exciting trajectory to finitely many collectively persistently exciting trajectories. It applies this extension to missing-data identification and controller construction for unstable systems.
- V. CONCLUSIONS: The paper introduces collective persistency of excitation and proves that finitely many such trajectories parameterize all trajectories of the linear system.This generalizes the single-trajectory parameterization of Willems’ fundamental lemma.
- V. CONCLUSIONS: The extended lemma enables identification of linear systems from data sets with missing samples.
- V. CONCLUSIONS: The result can construct controllers for unstable systems from multiple measured trajectories even when a single trajectory cannot do so.