On Controllability and Persistency of Excitation in Data-Driven Control: Extensions of Willems’ Fundamental Lemma

Willems’ fundamental lemma provides a data-based parameterization of trajectories generated by linear time invariant (LTI) systems [1]. In particular, consider the LTI system

	$\displaystyle x_{t+1}=$	$\displaystyle Ax_{t}+Bu_{t},$		(1a)
	$\displaystyle y_{t}=$	$\displaystyle Cx_{t}+Du_{t},$		(1b)

where $u_{t}\in\mathbb{R}^{m},x_{t}\in\mathbb{R}^{n},y_{t}\in\mathbb{R}^{p}$ denote the input, state and output of the system at discrete time $t$, respectively. If system (1) is controllable, the lemma asserts that every length-$L$ input-output trajectory of system (1) is a linear combination of a finite number of measured ones. These measured trajectories can be extracted from one single trajectory with persistent excitation of order $n+L$ [1], or multiple trajectories with collective persistent excitation of order $n+L$ [2]. By parameterizing trajectories of the system (1) using measured data, the lemma has profound implications in system identification [3, 4, 5], and inspired a series of recent results including data-driven simulation [3, 6], output matching [7], control by interconnection [8], set-invariance control [9], linear quadratic regulation [10], and predictive control [11, 12, 13, 14, 15, 16, 17].

In the meantime, whether conditions of controllability and persistency of excitation in Willems’ fundamental lemma are necessary has not been investigated in depth. The current work aims to address this issue by answering the following two questions. First, without controllability, to what extent can the linear combinations of a finite number of measured input-output trajectories parameterize all possible ones? Second, can the order of persistency of excitation be reduced?

Recent results on system identification has shown that, assuming sufficient persistency of excitation, the linear combinations of a finite number of measured input-output trajectories contain any trajectory whose initial state is in the controllable subspace [18, 19]. As we show subsequently, such results only partially answer the first question above: trajectories with initial state outside the controllable subspace can also be contained in said linear combinations.

We answer the aforementioned questions by introducing extensions of Willems’ fundamental lemma. First, we show that, with sufficient persistency of excitation, any length-$L$ input-output trajectory whose initial state is in some subspace is a linear combination of a finite number of measured ones. Said subspace is the sum of the controllable subspace, unobservable subspace, and a certain subspace associated with the measured trajectories. Second, we show that the order of persistency of excitation required by Willems’ fundamental lemma can be reduced from $n+L$ to $\delta_{\min}+L$, where $\delta_{\min}$ is the degree of the minimal polynomial of the system matrix $A$. Our first result completes those presented in [18, 19] by showing exactly which trajectories are parameterizable by a finite number of measured ones for an arbitrary LTI systems. Furthermore, this result shows that data-driven predictive control using online data is equivalent to model predictive control, not only for controllable systems, as shown in [12, 13], but also for uncontrollable ones. Our second result, compared with those in [2], can reduce the amount of data samples used in identifying homogeneous multi-agent systems by an order of magnitude.

The rest of the paper is organized as follows. We first prove an extended Willems’ fundamental lemma and discuss its implications in Section II. We provide ramifications of this extension for a representative set of applications in Section III before providing concluding remarks in Section IV.

Notation: We let $\mathbb{R}$, and $\mathbb{N}$ and $\mathbb{N}_{+}$ denote the set of real numbers, non-negative integers, and positive integers, respectively. The image and right kernel of matrix $M$ is denoted by $\operatorname{im}M$ and $\ker M$, respectively. Let $\left\lVert x\right\rVert_{M}=x^{\top}Mx$ for any matrix $M$ and vector $x$. When applied to subspaces, we let $+$ and $\times$ denote the sum [20, p.2] and Cartesian product operation [20, p.370], respectively. We let $\otimes$ denote the Kronecker product. Given a signal $f:\mathbb{N}\to\mathbb{R}^{q}$ and $i,j\in\mathbb{N}$ with $i\leq j$, we denote $f_{[i,j]}=\begin{bmatrix}f_{i}^{\top}&f_{i+1}^{\top}&\cdots&f_{j}^{\top}\end{bmatrix}^{\top}$, and the Hankel matrix of depth $d$ ($d\leq j-i+1$) associated with $f_{[i,j]}$ as

$$H_{d}(f_{[i,j]})=\begin{bmatrix}f_{i}&f_{i+1}&\cdots&f_{j-d+1}\\ f_{i+1}&f_{i+2}&\cdots&f_{j-d+2}\\ \vdots&\vdots&&\vdots\\ f_{i+d-1}&f_{i+d}&\cdots&f_{j}\end{bmatrix}.$$

In this section, we introduce extensions of Willems’ fundamental lemma. Throughout we let

$$(u^{i}_{[0,T^{i}-1]},x^{i}_{[0,T^{i}-1]},y^{i}_{[0,T^{i}-1]})$$

(2)

denote a length-$T^{i}$ ($T^{i}\in\mathbb{N}_{+}$) input-state-output trajectory generated by system (1) for all $i=1,2,\ldots,\tau$, where $\tau\in\mathbb{N}_{+}$ is the total number of trajectories. We let

$$\{u^{i}_{[0,T^{i}-1]}\}_{i=1}^{\tau},\enskip\{x^{i}_{[0,T^{i}-1]}\}_{i=1}^{\tau},\enskip\{y^{i}_{[0,T^{i}-1]}\}_{i=1}^{\tau},$$

(3)

denote the set of input, state, and output trajectories, respectively. We will use the following subspaces,

		$\displaystyle\mathcal{R}=\operatorname{im}\begin{bmatrix}B&AB&\cdots&A^{n-1}B\end{bmatrix},$		(4)
		$\displaystyle\mathcal{O}=\ker\begin{bmatrix}C^{\top}&(CA)^{\top}&\cdots&(CA^{n-1})^{\top}\end{bmatrix}^{\top},$
		$\displaystyle\mathcal{K}[x_{0}^{1},x_{0}^{2},\ldots,x_{0}^{\tau}]=\operatorname{im}\begin{bmatrix}X_{0}&AX_{0}&\cdots&A^{n-1}X_{0}\end{bmatrix},$

where $X_{0}=\begin{bmatrix}x_{0}^{1}&x_{0}^{2}&\cdots&x_{0}^{\tau}\end{bmatrix}$, and $x_{0}^{i}$ is the first state in the trajectory $x_{[0,T^{i}-1]}^{i}$ for all $1\leq i\leq\tau$. In particular, $\mathcal{R}$ is known as the controllable subspace (we say that system (1) is controllable if $\mathcal{R}=\mathbb{R}^{n}$), $\mathcal{O}$ is known as the unobservable subspace, and $\mathcal{K}[x_{0}^{1},x_{0}^{2},\ldots,x_{0}^{\tau}]$ is the smallest $A$-invariant subspace containing $x_{0}^{1},x_{0}^{2},\ldots,x_{0}^{\tau}$. Using the Cayley-Hamilton theorem, one can verify that (1) ensures

$$x_{t}=\textstyle A^{t}x_{0}+\sum_{j=0}^{t-1}A^{t-j-1}Bu_{j}\in\mathcal{R}+\mathcal{K}[x_{0}],$$

(5)

for all $t\in\mathbb{N}$, where $\mathcal{K}[x_{0}]$ is defined similar to $\mathcal{K}[x_{0}^{1},x_{0}^{2},\ldots,x_{0}^{\tau}]$. We let $\delta\in\mathbb{N}_{+}$ be such that

$$\delta\geq\delta_{\min}\coloneqq\text{degree of }p_{\min}(A),$$

(6)

where $p_{\min}(A)$ is the minimal polynomial of matrix $A$ [20, Def. 3.3.2], and, due to the Cayley-Hamilton theorem, $\delta_{\min}$ is upper bounded by $n$. We will also use the following definitions that streamline our subsequent analysis.

As an example, if $\tau=2$, $L=2$, $T^{1}=3,T^{2}=4$, then (7) assumes the form,

$$\left[\begin{array}[]{c}\widebar{u}_{0}\\ \widebar{u}_{1}\\ \hdashline[2pt/2pt]\widebar{y}_{0}\\ \widebar{y}_{1}\end{array}\right]=\left[\begin{array}[]{cc;{2pt/2pt}ccc}u_{0}^{1}&u_{1}^{1}&u_0^2&u_1^2&u_{2}^{2}\\ u_{1}^{1}&u_{2}^{1}&u_1^2&u_2^2&u_{3}^{2}\\ \hdashline[2pt/2pt]y_{0}^{1}&y_{1}^{1}&y_0^2&y_1^2&y_{2}^{2}\\ y_{1}^{1}&y_{2}^{1}&y_1^2&y_2^2&y_{3}^{2}\end{array}\right]g.$$

If $\tau=1$, then Definition 2 reduces to the traditional notion of persistency of excitation [1].

The Willems’ fundamental lemma asserts that: if the system (1) is controllable and $\{u^{i}_{[0,T^{i}-1]}\}_{i=1}^{\tau}$ is collectively persistently exciting of order $n+L$, then $(\widebar{u}_{[0,L-1]},\widebar{y}_{[0,L-1]})$ is parameterizable by $\{u_{[0,T^{i}-1]},y_{[0,T^{i}-1]}\}_{i=1}^{\tau}$ if and only if it is an input-output trajectory of the system (1) [1, 2]. As our main contribution, the following theorem shows that not only the controllability assumption can be relaxed, but also the required order of collective persistent excitation can be reduced from $n+L$ to, at best, $\delta_{\min}+L$.

Due to its dependence on state $\widebar{x}_{0}$ and the unknown subspaces in (4), the condition in (10) is difficult to verify, especially if merely input-output trajectories are available. One approach to guarantee its satisfaction is to ensure the right hand side of (10) equals $\mathbb{R}^{n}$, either by assuming controllability (i.e., $\mathcal{R}=\mathbb{R}^{n}$) as in [1] and [2], or requiring the input-state-output trajectories in (2) satisfy $\operatorname{im}\begin{bmatrix}x_{0}^{1}&x_{0}^{2}&\ldots&x_{0}^{\tau}\end{bmatrix}=\mathbb{R}^{n}$. The following corollary, however, provides an alternative approach that requires neither controllability nor state measurements.

Corollary 1 shows that any length-$L$ segment of an input-output trajectory is parameterizable by its first length-$T$ segment, assuming sufficient persistency of excitation. This result is particularly useful in predictive control as we will show in Section III-A.

Another implication of Theorem 1 is that the order of persistent excitation required by trajectory parameterization only depends on the degree of the minimal polynomial of matrix $A$ in (1), instead of its dimension. In general, it is difficult to establish a bound on the degree of the minimal polynomial of an unknown matrix tighter than its dimension. However, the following corollary shows an exception; its usefulness will be illustrated later in Section III-B.

The proof follows from Theorem 1 and the fact that the minimal polynomial of $A$ is the same as that of $\widebar{A}$, which has degree at most $\widebar{n}$.

In this section, we provide two examples that illustrate the distinct implications of Theorem 1.

We introduced an extension of Willems’ fundamental lemma by relaxing the controllability and persistency of excitation assumptions. We demonstrate the usefulness of our results in the context of DeePC and identification of homogeneous multi-agent system. Future directions include generalizations to noisy data and nonlinear systems.