A New Perspective on Willems’ Fundamental Lemma: Universality of Persistently Exciting Inputs

Amir Shakouri, Henk J. van Waarde, M. Kanat Camlibel · 2025

Read A New Perspective on Willems’ Fundamental Lemma: Universality of Persistently Exciting Inputs by Amir Shakouri, Henk J. van Waarde, M. Kanat Camlibel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-12489.txt.

Introduction

Amir Shakouri, Henk van Waarde, and Kanat Camlibel wrote a 2025 control theory letter giving a new view of Willems' fundamental lemma. The lemma is a cornerstone of data driven control: it says one rich dataset can describe every possible behavior of a linear system. The richness needed is called persistent excitation of the input.

The authors define universal inputs, signals that work for any controllable system, yielding data that parametrize all finite trajectories. The fundamental lemma already showed that persistently exciting inputs are universal. Their contribution is the converse: every universal input must be persistently exciting. Universality and persistent excitation are thus the same property seen from two sides. The equivalence tightens the theory behind learning control from data.

Catalog record

CREATORAmir Shakouri, Henk J. van Waarde, M. Kanat Camlibel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-12489

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A New Perspective on Willems’ Fundamental Lemma: Universality of Persistently Exciting Inputs Amir Shakouri, Henk J. van Waarde, M. Kanat Camlibel Abstract In this letter, we provide new insight into Willems et al.’s fundamental lemma by studying the concept of universal inputs. An input is called universal if, when applied to any controllable system, it leads to input-output data that parametrizes all finite trajectories of the system. By the fundamental lemma, inputs that are persistently exciting of sufficiently high order are universal. The main contribution of this work is to prove the converse. Therefore, universality and persistency of excitation are equivalent. I Introduction Willems et al.’s fundamental lemma [ 1 ] states that all finite-length input-output trajectories of a controllable linear system can be parametrized using a single input-output trajectory generated by a persistently exciting sequence of inputs. This result plays an important role in system identification using subspace methods [ 2 ] , where sufficiently rich input-output data can be used to identify the state-space system’s parameters up to a similarity transformation. In addition, one of the most popular approaches to modern data-driven control is to employ the trajectory parametrization implied by the fundamental lemma in order to bypass explicit system identification. For instance, trajectory simulation [ 3 ] , design of stabilizing feedback gains [ 4 ] , and construction of predictive controllers [ 5 , 6 ] can be performed directly on the basis of input-output data. We refer the reader to [ 7 , 8 ] for an alternative approach that avoids the use of persistently exciting input data. The fundamental lemma has been initially proven in [ 1 ] within the context of behavioral theory. Other proofs of this lemma using state-space formulation have been presented in [ 9 , 10 , 11 ] . Various extensions of this lemma have been studied in recent years. The extension of the fundamental lemma to multiple datasets has been studied in [ 9 ] and to uncontrollable systems in [ 12 ] . A robust version of this lemma for the case where the data are subject to noise is studied in [ 10 ] . A counterpart of the fundamental lemma for linear parameter varying systems has been provided in [ 13 ] , and a version of this lemma in the frequency domain has been presented in [ 14 ] . Extensions of this lemma to stochastic systems [ 15 ] , 2D systems [ 16 ] , and several classes of nonlinear systems [ 17 , 18 , 19 ] are also among the recent works. In addition, counterparts of the fundamental lemma for continuous-time systems have been studied in [ 20 , 21 ] . The persistency of excitation condition imposes a lower bound on the required number of data samples. As shown for the first time in [ 22 ] , for a single controllable system, one can improve the sample efficiency by generating an online experiment of shorter length that still enables the parametrization of all system trajectories. Moreover, [ 23 ] constructed the shortest possible experiment for linear system identification, based on the necessary and sufficient conditions in [ 24 ] . Nonetheless, the persistency of excitation condition guarantees a stronger property than the online input design. In fact, a persistently exciting input guarantees sufficiently rich data when applied to any controllable system. In this sense, persistently exciting inputs are universal as they work for the whole class of controllable systems. This is in contrast to online experiment design methods in [ 22 , 23 ] that are tailored to a specific controllable system, because the online input design is guided by the outputs of the data-generating system. The existing literature lacks a full characterization of universal inputs. In this work, we investigate whether there exist other universal inputs than persistently exciting ones. In particular, we answer the following question: What are necessary and sufficient conditions for an input to be universal? It turns out that persistency of excitation of a certain order is necessary and sufficient for the universality of the input. The sufficiency obviously follows from the fundamental lemma. The main contribution of this letter is to prove the necessity. To this end, given an input that is not persistently exciting, we show how one can construct a controllable system and an initial condition such that the resulting input-output data do not parametrize all finite-length trajectories of the system. The presented results provide insight into Willems et al.’s fundamental lemma by showing that persistency of excitation is not a conservative condition to guarantee universality. In the particular case of single-input systems, we further prove that if the input is not persistently exciting of a sufficiently high order, then almost any controllable system can generate data that are not suitable for parametrization of the system trajectories. This also makes a connection to the recent work [ 25 ] , where a similar observation was made. The remainder of this letter is organized as follows. Section II includes the problem statement. Section III presents the main result of the letter. Section IV is devoted to discussions on the main results. In Section V we study numerical examples. Finally, Section VI concludes the paper. Notation Let \mathbb{Z} , \mathbb{Z}_{+} and \mathbb{N} denote the sets of integers, non-negative integers, and positive integers, respectively. For a,b\in\mathbb{Z} we define the integer interval [a,b]\coloneqq\left\{c\in\mathbb{Z}\mid a\leq c\leq b\right\} . Note that [a,b]=\varnothing if a>b . Given v:\mathbb{Z}_{+}\rightarrow\mathbb{R}^{n} and T\in\mathbb{N} , we define v_{[0,T-1]}\coloneqq\begin{bmatrix}v(0)^{\top}&v(1)^{\top}&\cdots&v(T-1)^{\top}\end{bmatrix}^{\top}. (1) The Hankel matrix of v_{[0,T-1]} of depth k\in[1,T] is denoted by \mathcal{H}_{k}(v_{[0,T-1]})\coloneqq\begin{bmatrix}v(0)&v(1)&\cdots&v(T-k)\\ v(1)&v(2)&\cdots&v(T-k+1)\\ \vdots&\vdots&\ddots&\vdots\\ v(k-1)&v(k)&\cdots&v(T-1)\end{bmatrix}. (2) We say that v_{[0,T-1]} is persistently exciting of order k if \mathcal{H}_{k}(v_{[0,T-1]}) has full row rank 1 1 1 This definition of persistency of excitation is different from the one that typically appears in the adaptive control literature, defined for signals on an infinite time horizon (see, e.g., [ 26 , Def. 3.6.1] ). . We denote the kernel of matrix M\in\mathbb{R}^{n\times m} by \ker M\coloneqq\left\{x\in\mathbb{R}^{m}\mid Mx=0\right\} , and its image by \im M\coloneqq\left\{Mx\mid x\in\mathbb{R}^{m}\right\} . The set of eigenvalues of a matrix M\in\mathbb{R}^{n\times n} is denoted by \spec M . We say a matrix M\in\mathbb{R}^{n\times n} is cyclic if there exists \zeta\in\mathbb{R}^{n} such that the pair (M,\zeta) is controllable (see [ 27 , p. 67] and [ 28 , Def. 7.7.4] ). II Problem Statement Let n,m,p\in\mathbb{N} . Consider the input-state-output system \displaystyle x(t+1) \displaystyle=Ax(t)+Bu(t), (3a) \displaystyle y(t) \displaystyle=Cx(t)+Du(t), (3b) where u(t)\in\mathbb{R}^{m} is the input, x(t)\in\mathbb{R}^{n} is the state, and y(t)\in\mathbb{R}^{p} is the output. We identify system ( 3 ) with the quadruple of matrices (A,B,C,D)\in\mathcal{M} , where \mathcal{M}\coloneqq\mathbb{R}^{n\times n}\times\mathbb{R}^{n\times m}\times\mathbb{R}^{p\times n}\times\mathbb{R}^{p\times m}. We also define \mathcal{M}_{\text{cont}}\coloneqq\left\{(A,B,C,D)\in\mathcal{M}\mid(A,B)\text{ is controllable}\right\}. (4) For an (A,B,C,D)\in\mathcal{M} , we denote its input-output behavior by \begin{split}\mathfrak{B}(A,B,C,D)\!\coloneqq\!\{(u,y)\!:\!\mathbb{Z}_{+}\!\rightarrow\!\mathbb{R}^{m}\!\times\!\mathbb{R}^{p}\mid\exists x:\mathbb{Z}_{+}\!\rightarrow\!\mathbb{R}^{n}\\ \text{ such that }\eqref{eq:1(a)}\text{ and }\eqref{eq:1(b)}\text{ hold}\},\end{split} (5) and its k –restricted input-output behavior by \mathfrak{B}_{k}(A,B,C,D)\!\coloneqq\!\left\{\!\begin{bmatrix}u_{[0,k-1]}\\ y_{[0,k-1]}\end{bmatrix}\mid(u,y)\in\mathfrak{B}(A,B,C,D)\!\right\}\!. (6) In addition, we define the k –restricted input-state behavior of ( 3a ) as \mathfrak{B}_{k}(A,B)\coloneqq\mathfrak{B}_{k}(A,B,I_{n},0). (7) For any trajectory \begin{bmatrix}u_{[0,T-1]}\\ y_{[0,T-1]}\end{bmatrix}\in\mathfrak{B}_{T}(A,B,C,D) , it is evident that \im\begin{bmatrix}\mathcal{H}_{k}(u_{[0,T-1]})\\ \mathcal{H}_{k}(y_{[0,T-1]})\end{bmatrix}\subseteq\mathfrak{B}_{k}(A,B,C,D) (8) for all k\in[1,T] . The celebrated fundamental lemma states that, under suitable conditions, ( 8 ) holds with equality (see [ 1 , Thm. 1] and

Read the complete text