⚡ electrical engineering

A note on input signal generators: A relaxation of Willems' fundamental lemma in the SISO case

This paper presents a practical relaxation of Willems' fundamental lemma for discrete-time SISO systems by reformulating the problem through signal generators, establishing a necessary and sufficient condition for generating informative data that accommodates inputs like sinusoidal sequences with fewer frequencies and extends naturally to continuous-time systems.

Original authors: Yun Jeong Yang, Jin Gyu Lee

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yun Jeong Yang, Jin Gyu Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out how a mysterious machine works. You can't open it up to see the gears inside (the internal state), but you can feed it inputs (like pushing a button) and watch what comes out (the lights it flashes).

The big question is: How much data do you need to push and watch to perfectly understand the machine?

The Old Rule: "The More, The Merrier"

For a long time, the gold standard for this was a rule called Willems' Fundamental Lemma. Think of this rule as a very strict teacher.

The teacher says: "To understand a machine with $n$ gears, you must push the button with a signal that is persistently exciting."

What does that mean? It means your button-pushing pattern must be incredibly complex and random. It's like asking a musician to play a song that hits every single possible note in a specific range, over and over again, just to prove they know the whole scale.
The Cost: This requires a lot of time and a very complex signal. If the machine is complex, you need a huge amount of data. It's like trying to map a city by driving every single street, even the dead ends, multiple times.

The New Idea: "The Signal Generator"

The authors of this paper, Yun Jeong Yang and Jin Gyu Lee, say: "Wait a minute. Do we really need to drive every single street? Or can we just drive the main highways?"

They propose looking at the problem differently. Instead of asking "Is this specific button-push pattern complex enough?", they ask: "What kind of machine (Signal Generator) is creating the button pushes?"

Imagine you have a Signal Generator. This is a little robot that decides what signal to send to your mystery machine.

The Old Way: You tell the robot, "Be random! Be chaotic!"
The New Way: You build the robot with a specific number of gears (dimensions).

The Big Discovery: You Can Use a Smaller Robot

The paper's main breakthrough is a relaxation of the rules. They found that:

The Strict Teacher's Rule: To be 100% sure you understand the machine for any starting condition, you need a Signal Generator with $2n + 1$ gears (where $n$ is the complexity of the mystery machine).
The New Relaxation: If you are okay with understanding the machine for almost all starting conditions (which covers 99.9% of real-world scenarios), you only need a Signal Generator with $n + 1$ gears.

The Analogy:
Imagine the mystery machine is a piano with 88 keys.

Willems' Old Rule: You must play a song that hits every single key, in every possible combination, to prove you know the piano.
The New Rule: You only need a musician (the Signal Generator) who knows how to play a specific set of $n+1$ notes. If you listen to them play, you can figure out how the whole piano works, unless the piano was broken in a very specific, rare way (a "measure zero" case).

Why This Matters

This is a huge deal for three reasons:

Efficiency: You don't need to wait as long or generate as much data. You can use shorter, simpler signals (like a few specific musical notes instead of a chaotic noise storm).
Design: Instead of guessing random signals and hoping they work, you can now design a specific Signal Generator (a robot with a specific number of gears) that guarantees success. It's like building a custom key instead of trying to pick the lock with a bobby pin.
Flexibility: It opens the door to using signals that were previously rejected. For example, you can use a simple repeating wave (like a sine wave) with just a few frequencies, which is much easier to generate in the real world than a random noise signal.

The "Almost All" Caveat

The paper admits there is a tiny catch. If the machine starts in a very specific, weird state (like a clock that is stuck at exactly 12:00:00.000001), the smaller Signal Generator might not work. But in the real world, things rarely start in those exact, mathematically perfect "impossible" states. So, for all practical purposes, the new, smaller rule works perfectly.

Summary

The authors took a very rigid, complex rule for testing machines and replaced it with a more practical, flexible approach. By focusing on how the test signal is generated rather than just checking if the signal is "exciting" enough, they showed that we can get the same results with half the effort and simpler tools.

It's the difference between trying to paint a masterpiece by splashing paint everywhere (Old Way) versus using a precise, well-designed stencil to get the exact same picture with fewer strokes (New Way).

1. Problem Statement

The paper addresses the challenge of data-driven system identification and control for discrete-time and continuous-time Single-Input-Single-Output (SISO) Linear Time-Invariant (LTI) systems.

Context: Willems' Fundamental Lemma is the cornerstone of data-driven control, stating that if an input signal is persistently exciting (PE) of sufficiently high order, the resulting input-output data can completely characterize the system's behavior (i.e., span the space of all possible trajectories).
Limitations of Current Theory:
- Over-conservatism: The standard PE condition requires the input dimension to be at least $L + n$ (where $L$ is the window length and $n$ is the system order) to guarantee informative data for all initial conditions. This often necessitates long data sequences or complex signal designs (e.g., multisines with many frequencies).
- Verification vs. Design: The PE condition is defined via the rank of a Hankel matrix formed after the input is chosen. It does not provide a constructive rule for designing the input signal itself.
- Discrete-time focus: The classical lemma is formulated for discrete-time systems, making extensions to continuous-time non-trivial.
Core Question: Can we find a necessary and sufficient condition for generating informative data that is less restrictive than Willems' condition, specifically allowing for shorter inputs or inputs with fewer frequencies, while still working for "almost all" systems and initial conditions?

2. Methodology

The authors propose a paradigm shift from Behavioral Theory (focusing on signal properties like PE) back to Dynamical Systems Theory (focusing on the structure of the signal generator).

Signal Generator Model: Instead of treating the input $u(t)$ as an arbitrary sequence, they model it as the output of an autonomous LTI system (a "signal generator"):
$w(t+1) = S_g w(t), \quad u(t) = L_g w(t)$
where $w \in \mathbb{R}^{N_g}$ is the generator state, $S_g$ is the dynamics matrix, and $L_g$ is the output matrix.
Assumptions:
1. The pair $(L_g, S_g)$ is observable.
2. The pair $(S_g, w_0)$ is controllable (ensuring all modes are excited).
3. The spectra of the system matrix $A$ and generator matrix $S_g$ are disjoint ( $\sigma(A) \cap \sigma(S_g) = \emptyset$ ).
Decomposition Approach: By interconnecting the signal generator with the plant, the authors utilize the Sylvester equation ( $A\Pi + B L_g = \Pi S_g$ ) to define an invariant manifold. This allows them to decompose the input-output Hankel matrix into structural components related to the generator and the system's observability.
Rank Analysis: They analyze the rank of the Hankel matrix using the rank-nullity theorem, focusing on the intersection of the image of the generator's observability matrix and the kernel of the system's controllability matrix.

3. Key Contributions

Relaxation of Willems' Condition: The paper proves that the strict requirement of $N_g \geq L + n$ (dimension of the generator $\geq$ window length + system order) is only necessary for all initial conditions. For almost all initial conditions (in the sense of Lebesgue measure), a generator of dimension $N_g \geq L$ is sufficient.
Constructive Input Design: By framing the problem in terms of signal generators, the authors provide a direct design guideline. Instead of checking PE conditions post-hoc, researchers can simply design a generator with dimension $N_g = L$ (or $n+1$ for system identification) to guarantee informative data.
Extension to Continuous-Time: The methodology naturally extends to continuous-time systems, providing a unified framework for both discrete and continuous domains.
Identification of "Overlooked" Inputs: The theory validates the use of inputs that fail the classical Willems' condition (e.g., multisine signals with fewer frequencies or shorter random sequences) as long as they are generated by a low-dimensional signal generator.

4. Main Results

A. Discrete-Time Fundamental Lemma (Theorem 1)

For a system of order $n$ and a data window of length $L$ , let $N_g$ be the dimension of the signal generator and $T$ be the data length.

Case 1 ( $N_g < L$ ): Data is never informative for any initial condition.
Case 2 ( $L \leq N_g < L + n$ ): Data is informative for almost all initial conditions $x(0)$ , provided the data length $T \geq N_g + n + L - 1$ . The set of "bad" initial conditions has Lebesgue measure zero.
Case 3 ( $N_g \geq L + n$ ): Data is informative for all initial conditions (recovering the classical Willems result).

Practical Implication: To identify a system of order $n$ , one traditionally needs a PE input of order $2n+1$ (requiring $T \geq 4n+1$ ). The new result shows that a generator of dimension $N_g = n+1$ with length $T = 3n+1$ is sufficient for almost all systems and initial conditions.

B. Continuous-Time Fundamental Lemma (Theorem 2)

The same logic applies to continuous-time systems using "jets" (derivatives) instead of time-shifted windows.

If $N_g \geq L$ , informative data is obtained for almost all initial conditions.
If $N_g \geq L + n$ , informative data is obtained for all initial conditions.

C. Relationship to PE Order

The paper establishes a direct link: A signal generated by a signal generator of dimension $N_g$ (satisfying observability/controllability) has a maximum PE order of $N_g$ . Thus, the condition "PE order $\geq K$ " is equivalent to "Signal generator dimension $\geq K$ ."

5. Significance

Efficiency: The proposed relaxation allows for shorter data collection times and simpler input signals. For example, in system identification, one can use a signal generator of dimension $n+1$ instead of the traditionally required $2n+1$ , reducing the data length requirement from $4n+1$ to $3n+1$ .
Broader Applicability: It validates the use of practical signals (like specific multisines or random signals) that were previously discarded because they did not strictly satisfy the high-order PE condition.
Unified Framework: It bridges the gap between behavioral theory (data-driven) and dynamical systems theory (model-based), offering a more intuitive way to design experiments for system identification.
Robustness: The results hold for "almost all" systems and initial conditions, which is practically sufficient for engineering applications where pathological cases (measure zero sets) are negligible.

In summary, the paper demonstrates that by viewing input signals through the lens of signal generators, the constraints of Willems' Fundamental Lemma can be significantly relaxed, enabling more efficient and flexible data-driven control and identification strategies.