# Data-driven Meets Geometric Control: Zero Dynamics, Subspace Stabilization,
and Malicious Attacks

Federico Celi and Fabio Pasqualetti This material is based upon work supported
in part by awards AFOSR FA9550-20-1-0140 and FA9550-19-1-0235, and ARO
W911NF2020267(NC4). Federico Celi and Fabio Pasqualetti are with the
Department of Mechanical Engineering, University of California at Riverside,
{fceli<EMAIL_ADDRESS>
###### Abstract

Studying structural properties of linear dynamical systems through invariant
subspaces is one of the key contributions of the geometric approach to system
theory. In general, a model of the dynamics is required in order to compute
the invariant subspaces of interest. In this paper we overcome this limitation
by finding data-driven formulas for some of the foundational tools of
geometric control. In particular, for an unknown linear system, we show how
controlled and conditioned invariant subspaces can be found directly from
experimental data. We use our formulas and approach to (i) find a feedback
gain that confines the system state within a desired subspace, (ii) compute
the invariant zeros of the unknown system, and (iii) design attacks that
remain undetectable.

##  I Introduction

The geometric approach is a collection of notions and algorithms for the
analysis and control of dynamical systems. Differently from the classic
methods in the frequency and state space domains [1, 2], the geometric
approach offers an intuitive and coordinate-free analysis of the properties of
dynamical systems in terms of appropriately defined subspaces, and synthesis
algorithms based on subspace operations, such as sum, intersection, and
orthogonal complementation. The geometric approach has been successfully used
to solve a variety of complex control and estimation problems; we refer the
interested reader to [3, 4, 5] for a detailed treatment of the main geometric
control notions and their applications.

Similarly to the frequency and state-space approaches to control, the
geometric approach assumes an accurate, in fact exact, representation of the
system dynamics. To overcome this limitation and in response to an ever-
increasing availability of sensors, historical data, and machine learning
algorithms, the behavioral approach, and more generally a data-driven
approach, has seen a rapid increase in popularity. Here, system analysis and
control synthesis do not require a model of the dynamics and are instead
obtained directly from experimental data reflecting the system dynamics [6].

While analysis, control and estimation problems can often be solved
equivalently using different methods, the frequency, state-space, geometric,
and data-driven approaches all offer complementary insights into the structure
and properties of the system dynamics, and together contribute to forming a
comprehensive theory of systems. In this paper we create the first connections
between the geometric and data-driven approach to system analysis and control.
In particular, we derive data-driven expressions of the fundamental sets used
in the geometric approach to solve a variety of control and estimation
problems, and show how these sets have an even more insightful and
straightforward interpretation when analyzed in the higher-dimensional data
space as compared to their geometric view in the lower-dimensional state
space.

Related work. From the seminal work [7] that introduced the notions of
controlled and conditioned invariants, the geometric approach to control has
evolved over the last decades into a full theory and a set of algorithms for
linear [3, 4, 5] and nonlinear [8] systems. Notable applications of the
geometric approach are the disturbance decoupling [9] and fault detection [10]
problems, the characterization of stealthy attacks in cyber-physical systems
[11], and the secure state estimation problem [12]. In this paper we follow
the notation and techniques of [3], which we briefly recall in Section II.

The data-driven approach to system analysis and control is receiving renewed
and increased interest. While traditional indirect data-driven methods use
data to identify a model of the system [13] and proceed to synthesize a
controller in a second step, direct data-driven methods bypass (at least
apparently [14, 15, 16]) the identification step and design control actions
directly from data. In this framework, recent results tackle various problems
for linear systems, including optimal [17, 18], robust [19, 20] and
distributed [21, 22, 23, 24] control, as well as unknown-input estimation
[25]. We refer the reader to [26] for a recent survey on data-driven control.

Main contributions of this paper. The main contributions of this paper are as
follows. First, for the linear, discrete, time-invariant systems described by
the triple $(A,B,C)$, we derive explicit, closed-form data-driven expressions
of (i) $\mathcal{V}^{*}$, the largest $(A,\operatorname{Im}(B))$-controlled
invariant subspace contained in $\operatorname{Ker}(C)$, (ii)
$\mathcal{S}^{*}$, the smallest $(A,\operatorname{Ker}(C))$-conditioned
invariant subspace containing $\operatorname{Im}(B)$, (iii) the feedback gain
$F$ such that $(A+BF)\mathcal{V}^{*}\subseteq\mathcal{V}^{*}$, and (iv) the
invariant zeros of $(A,B,C)$. Since $\mathcal{V}^{*}$ and $\mathcal{S}^{*}$
are the basis of the geometric approach developed in [3], our data-driven
formulas constitute the basis of a data-driven and model-free theory of
geometric control, and can be used to solve a variety of analysis, estimation,
and control problems in a purely data-driven setting. Second, our results show
that the fundamental invariant subspaces of the geometric approach, which are
often computed recursively when operating in the state space, have a simple
and direct interpretation in the higher-dimensional data space, where they can
be computed by solving appropriately defined sets of linear equations. Third,
we demonstrate the utility of our formulas to design undetectable data-driven
attacks in a consensus system.

Paper organization. Section II contains our problem setup and some preliminary
notions. Section III contains our data-driven formulas of the fundamental
invariant subspaces of the geometric approach. Finally, Sections IV and V
contain our illustrative examples and conclusion, respectively.

Notation. The set of real numbers is denoted with . The rank, range space,
null space, transpose, and Moore-Penrose pseudoinverse of the matrix
$A\in{}^{n\times m}$ are denoted with $\operatorname{rank}(A)$,
$\operatorname{Im}(A)$, $\operatorname{Ker}(A)$, $A^{\top}$, and $A^{\dagger}$
respectively. A basis of the subspace $\mathcal{V}\subseteq{}^{n}$ is denoted
with $\operatorname{Basis}(\mathcal{V})$. The Kronecker product between
matrices $A$ and $B$ is denoted by $A\otimes B$ and is defined as in [27].

##  II Problem setup and preliminary notions

We consider the discrete-time linear time-invariant system

$\displaystyle x(t+1)$ $\displaystyle=Ax(t)+Bu(t)$ (1a) $\displaystyle y(t)$
$\displaystyle=Cx(t)$ (1b)

where $x\in{}^{n}$, $u\in{}^{m}$ and $y\in{}^{p}$ are the state, input and
output vectors, respectively, and $(A,B,C)$ are constant matrices of
appropriate dimensions. For any horizon $T\geq 1$, the state and output
trajectories of (1) can be written as

$\tiny\underbrace{\begin{bmatrix}x(1)\\\ x(2)\\\ \vdots\\\
x(T)\end{bmatrix}}_{{X}_{T}}=\underbrace{\begin{bmatrix}A\\\ A^{2}\\\
\vdots\\\
A^{T}\end{bmatrix}}_{O_{T}^{X}}x(0)+\underbrace{\begin{bmatrix}B&\cdots&0&0\\\
AB&\cdots&0&0\\\ &\ddots&&\\\
A^{T-1}B&\cdots&AB&B\end{bmatrix}}_{F_{T}^{X}}\underbrace{\begin{bmatrix}u(0)\\\
u(1)\\\ \vdots\\\ u(T-1)\end{bmatrix}}_{{U}_{T}},$ (2)

and

$\tiny\underbrace{\begin{bmatrix}y(0)\\\ y(1)\\\ \vdots\\\
y(T-1)\end{bmatrix}}_{{Y}_{T}}=\underbrace{\begin{bmatrix}C\\\ CA\\\ \vdots\\\
CA^{T-1}\end{bmatrix}}_{O_{T}^{Y}}x(0)+\underbrace{\begin{bmatrix}0&\cdots&0&0\\\
CB&\cdots&0&0\\\ &\ddots&&\\\
CA^{T-2}B&\cdots&CB&0\end{bmatrix}}_{F_{T}^{Y}}{U}_{T}.$ (3)

Throughout the paper, we assume that the system matrices are not known and
base our approach on a set of prerecorded trajectories obtained by arbitrarily
probing the system (1).

###  II-A Data collection

The available data is collected from a set of $N$ open-loop control
experiments with horizon $T$, and consist of the state and output trajectories
obtained from (1) with initial condition $x^{i}_{0}$ and control sequence
$U_{T}^{i}$, for $i\in\\{1,\dots,N\\}$. In particular, the following data
matrices are available:

$\displaystyle X$
$\displaystyle=\begin{bmatrix}X_{T}^{1}&\\!\\!\cdots&X_{T}^{N}\end{bmatrix}\in{}^{nT\times
N},$ (4a) $\displaystyle X_{0}$
$\displaystyle=\begin{bmatrix}x^{1}_{0}&\,\cdots&x^{N}_{0}\end{bmatrix}\;\in{}^{n\times
N},$ (4b) $\displaystyle Y$
$\displaystyle=\begin{bmatrix}Y_{T}^{1}&\cdots&Y_{T}^{N}\end{bmatrix}\in{}^{pT\times
N},$ (4c) $\displaystyle U$
$\displaystyle=\begin{bmatrix}U_{T}^{1}&\cdots&U_{T}^{N}\end{bmatrix}\in{}^{mT\times
N}.$ (4d)

From (2)-(3), we note the following relationships:

$\begin{bmatrix}X\\\ Y\end{bmatrix}=\begin{bmatrix}O_{T}^{X}&F_{T}^{X}\\\
O_{T}^{Y}&F_{T}^{Y}\end{bmatrix}\begin{bmatrix}X_{0}\\\ U\end{bmatrix}.$ (5)

We make the following assumption of persistently-exciting experimental inputs,
which is generically satisfied by choosing the inputs and initial states
independently and randomly.

###### Assumption II.1

The experimental inputs and initial conditions are persistently exciting, that
is,

$\operatorname{rank}\begin{bmatrix}X_{0}\\\ U\end{bmatrix}=n+mT.$ (6)

$\square$

Let $K_{0}=\operatorname{Basis}(\operatorname{Ker}(X_{0}))$ and
$K_{U}=\operatorname{Basis}(\operatorname{Ker}(U))$. From the Rank-nullity
Theorem, Assumption II.1 ensures that $X_{0}K_{U}$ and $UK_{0}$ are full-row
rank, respectively. Assumption II.1 is a standard assumption in data driven
studies [28, 19].

###### Remark 1

_(Alternative data-driven representations)_ Different data formats can be used
to obtain a non-parametric data-driven representation of the system (1),
including our representation (4) as well as Hankel and Page matrices [19, 28].
While Hankel and Page matrices are generated from a single controlled
trajectory, the matrices in (4) use a collection of (possibly shorter)
controlled trajectories. Different data collections can be more convenient for
the solution of different problems, with, currently, Hankel and Page matrices
being used mostly for feedback control problems [19] and multiple trajectories
for robustness problems [17, 29]. $\square$

###  II-B Controlled and conditioned invariant subspaces

The notions of controlled and conditioned invariant subspaces are the basis of
the geometric approach for the analysis and control of linear systems [7]. We
now recall their definition and basic properties. We refer the interested
reader to [3, 4, 5] for a detailed treatment of this subject.

###### Definition 1

_( $(A,\mathcal{B})$-controlled invariant)_ Given a matrix $A\in{}^{n\times
n}$ and a subspace $\mathcal{B}\subseteq{}^{n}$, a subspace
$\mathcal{V}\subseteq{}^{n}$ is an $(A,\mathcal{B})$-controlled invariant
subspace if

$A\mathcal{V}\subseteq\mathcal{V}+\mathcal{B}.$ (7)

When $\mathcal{B}=\operatorname{Im}(B)$, the notion of a controlled invariance
refers to the possibility of confining the state trajectory of the system (1)
within a subspace. Specifically, the subspace $\mathcal{V}$ is an
$(A,\operatorname{Im}(B))$-controlled invariant subspace if, for every initial
state in $\mathcal{V}$, there exists a control input such that the state
belongs to $\mathcal{V}$ at all times. Of particular interest is
$\mathcal{V}^{*}$, the largest $(A,\operatorname{Im}(B))$-controlled invariant
subspace contained in $\operatorname{Ker}(C)$. The subspace $\mathcal{V}^{*}$
contains all trajectories of (1) that generate an identically zero output.
Hence, the subspace $\mathcal{V}^{*}$ vanishes if and only if the system (1)
features no invariant zeros, a notion that is at the basis of the analysis of
stealthy attacks and unknown-input observers [11], among others.

###### Definition 2

_( $(A,\mathcal{C})$-conditioned invariant)_ Given a matrix $A\in{}^{n\times
n}$ and a subspace $\mathcal{C}\subseteq{}^{n}$, a subspace
$\mathcal{S}\subseteq{}^{n}$ is an $(A,\mathcal{C})$-conditioned invariant
subspace if

$A(\mathcal{S}\cap\mathcal{C})\subseteq\mathcal{S}.$ (8)

When $\mathcal{C}=\operatorname{Ker}(C)$, the notion of conditioned invariance
arises in the context of state estimation. Specifically, the subspace
$\mathcal{S}$ is an $(A,\operatorname{Ker}(C))$-conditioned invariant subspace
if it is possible to design an (asymptotic) observer that reconstructs the
state $x\setminus\mathcal{S}$ by processing the initial condition, the input,
and the measurements of the system (1). Of particular interest is
$\mathcal{S}^{*}$, the smallest $(A,\operatorname{Ker}(C))$-conditioned
invariant subspace containing $\operatorname{Im}(B)$. In fact, the orthogonal
complement of the subspace $\mathcal{S}^{*}$ is the largest subspace of the
state space that can be estimated through a dynamic observer in the presence
of an unknown input.

The subspaces $\mathcal{V}^{*}$ and $\mathcal{S}^{*}$ can be conveniently
computed using simple recursive algorithms [3]. Further, these subspaces can
be used to characterize important properties of the system (1). For instance,
the system (1) is right invertible if and only if
$\mathcal{V}^{*}\cup\mathcal{S}^{*}={}^{n}$, and left invertible if and only
if the subspace $\mathcal{R}^{*}=\mathcal{V}^{*}\cap\mathcal{S}^{*}$ is empty
[3]. It should be noticed that $\mathcal{R}^{*}$ coincides with the largest
subspace that can be reached from the origin with trajectories that belong to
$\mathcal{V}^{*}$ at all times (hence, generating an identically zero output).

The definition of the subspaces $\mathcal{V}^{*}$, $\mathcal{S}^{*}$ and
$\mathcal{R}^{*}$, as well as the algorithms to compute them, assume the exact
knowledge of the system matrices. Instead, in the remainder of the paper we
derive purely data-driven expressions of these subspaces, which also offers an
alternative interpretation of them. Similarly to how $\mathcal{V}^{*}$,
$\mathcal{S}^{*}$ and $\mathcal{R}^{*}$ are used in the geometric approach,
our data-driven formulas can also be used to solve a variety of estimation and
control problems.

$\mathcal{S}^{*}$$\operatorname{Im}(B)$$\mathcal{V}^{*}$$\operatorname{Ker}(C)$n$\mathcal{R}^{*}$$0$
Figure 1: This figure shows the inclusion relationships between the
fundamental controlled and conditioned invariants defined in Section II.
Notice how, by their definitions,
$\mathcal{V}^{*}\subseteq\operatorname{Ker}(C)$,
$\operatorname{Im}(B)\subseteq\mathcal{S}^{*}$ and
$\mathcal{R}^{*}=\mathcal{V}^{*}\cap\mathcal{S}^{*}$, highlighted in a
different gradient.

##  III Data-driven geometric control

We begin with finding a data-driven expression of the subspace
$\mathcal{V}^{*}$ for the system (1), the largest
$(A,\operatorname{Im}(B))$-controlled invariant subspace contained in
$\operatorname{Ker}(C)$.

###### Theorem III.1

_(Data driven formula for $\mathcal{V}^{*}$)_ Let (4) be the data generated by
the system (1) with $T\geq n$. Then,

$\mathcal{V}^{*}=\begin{bmatrix}X_{0}K_{U}&0\end{bmatrix}\operatorname{Ker}\begin{bmatrix}YK_{U}&YK_{0}\end{bmatrix}.$
(9)

$\square$

To prove Theorem III.1, recall that $\mathcal{V}^{*}$ is the set of initial
states for which there exists a control input such that the resulting state
trajectory generates an identically zero output. Since the system is linear,
under our assumption of persistently exciting experimental inputs, any system
trajectory can be expressed as an appropriate linear combination of the
experimental trajectories. We next formalize this intuition.

###### Lemma III.2

_(Data-driven trajectories of ( 1))_ Let (4) be the data generated by the
system (1) with $T\geq n$. Let $\bar{X}_{T}$ and $\bar{Y}_{T}$ be the state
and output trajectories of (1) generated with some initial condition and
control input. Then,

$\begin{bmatrix}\bar{X}_{T}\\\
\bar{Y}_{T}\end{bmatrix}=\begin{bmatrix}XK_{U}&XK_{0}\\\
YK_{U}&YK_{0}\end{bmatrix}\begin{bmatrix}\alpha\\\ \beta\end{bmatrix},$ (10)

for some vectors $\alpha$ and $\beta$. $\square$

###### Proof:

Let $\bar{x}_{0}$ and $\bar{U}_{T}$ be the initial condition and input to (1).
Since the matrices $X_{0}K_{U}$ and $UK_{0}$ are full-row rank (see Assumption
II.1), there exists $\alpha$ and $\beta$ such that

$\displaystyle\bar{x}_{0}=X_{0}K_{U}\alpha\;\text{ and
}\;\bar{U}_{T}=UK_{0}\beta.$ (11)

From (2) we have

$\displaystyle\bar{X}_{T}$
$\displaystyle=O_{T}^{X}\bar{x}_{0}+F_{T}^{X}\bar{U}_{T}=O_{T}^{X}X_{0}K_{U}\alpha+F_{T}^{X}UK_{0}\beta$
$\displaystyle=XK_{U}\alpha+XK_{0}\beta,$

where the last equality follows from (5). Similarly from (3),

$\displaystyle\bar{Y}_{T}$
$\displaystyle=O_{T}^{Y}\bar{x}_{0}+F_{T}^{Y}\bar{U}_{T}=O_{T}^{Y}X_{0}K_{U}\alpha+F_{T}^{Y}UK_{0}\beta$
$\displaystyle=YK_{U}\alpha+YK_{0}\beta,$

which concludes the proof. ∎

Lemma III.2 shows how any state and output trajectory of (1) can be written as
a linear combination of the available data. In particular, state and output
trajectories are obtained in (10) as the sum of the free and forced responses,
which are reconstructed from data of arbitrary control experiments. In fact,
$XK_{U}\alpha$ is the state trajectory of (1) with initial condition
$X_{0}K_{u}\alpha$ and zero input (free response), while $XK_{0}\beta$ is the
state trajectory of (1) with zero initial condition and input $UK_{0}\beta$
(forced response). We remark that Assumption II.1 of persistently exciting
inputs is necessary to obtain this result.

The following instrumental Lemma shows that it is sufficient to consider
trajectories of any finite length $T\geq n$ to compute $\mathcal{V}^{*}$, and
is instrumental to the proof of Theorem III.1.

###### Lemma III.3

_(Computing $\mathcal{V}^{*}$ from trajectories of finite length)_ For the
system (1), any initial state $x_{0}$, and any finite horizon $T\geq n$, the
following statements are equivalent:

  1. (i)

$x_{0}\in\mathcal{V}^{*}$;

  2. (ii)

there exists an input sequence $u(0),\dots,u(T-1)$ such that $y(t)=0$ for all
$t\in\\{0,\dots,T-1\\}$.

###### Proof:

(i) $\Rightarrow$ (ii) Follows from the definition of $\mathcal{V}^{*}$.

(ii) $\Rightarrow$ (i) Notice that $y(T-1)=Cx(T-1)=0$. Thus,
$x(T-1)\in\operatorname{Ker}(C)=\mathcal{V}_{0}$. Similarly, $x(T-2)$
satisfies

$\displaystyle x(T-1)$ $\displaystyle=Ax(T-2)+Bu(T-2),\text{ and }$
$\displaystyle y(T-2)$ $\displaystyle=Cx(T-2)=0.$

This implies that

$\displaystyle x(T-2)$ $\displaystyle\in A^{-1}(x(T-1)-Bu(T-2))$
$\displaystyle\subseteq
A^{-1}(\mathcal{V}_{0}+\operatorname{Im}(B))\cap\operatorname{Ker}(C)=\mathcal{V}_{1}$

Iterating this procedure yields

$\displaystyle x(T-1)$
$\displaystyle\in\mathcal{V}_{0}=\operatorname{Ker}(C),\text{ and }$ (12a)
$\displaystyle x(T-i)$
$\displaystyle\in\mathcal{V}_{i}=A^{-1}(V_{i-1}+\operatorname{Im}(B))\cap\operatorname{Ker}(C).$
(12b)

Since $\mathcal{V}_{i}$ converges to $\mathcal{V}^{*}$ is at most $n$ steps
[7], we have that $x(T-\tau)\in\mathcal{V}^{*}$ for all $\tau\geq n$, which
concludes the proof. ∎

We now prove Theorem III.1 using Lemma III.2 and III.3.

Proof of Theorem III.1: From Lemma III.3 we seek all initial conditions
$x_{0}$ for which the output can be maintained at zero for $T\geq n$ steps.
From (10), the vectors $\alpha$ and $\beta$ that identify state trajectories
with identically zero output must satisfy

$\begin{bmatrix}\alpha\\\
\beta\end{bmatrix}\in\operatorname{Ker}\begin{bmatrix}YK_{U}&YK_{0}\end{bmatrix}.$
(13)

The initial condition corresponding to such trajectories is
$x_{0}=X_{0}K_{U}\alpha$ (see (11)). Thus, the set $\mathcal{V}^{*}$ can be
written as

$\mathcal{V}^{*}=\begin{bmatrix}X_{0}K_{U}&0\end{bmatrix}\operatorname{Ker}\begin{bmatrix}YK_{U}&YK_{0}\end{bmatrix}.$

$\blacksquare$

We next find a data-driven expression for $\mathcal{S}^{*}$, the smallest
$(A,\operatorname{Ker}(C))$ conditioned invariant containing
$\operatorname{Im}(B)$.

###### Theorem III.4

_(Data driven formula for $\mathcal{S}^{*}$)_ Let (4) be the data generated by
the system (1) with $T\geq n$. Then,

$\mathcal{S}^{*}=HXK_{0}\operatorname{Ker}\left(YK_{0}\right),$ (14)

where111We use $I_{n}\in{}^{n\times n}$ and $0_{n}\in{}^{n\times n}$ to denote
the identity and zero matrices of appropriate dimensions, respectively.
$H=\underbrace{\begin{bmatrix}0_{n}&\cdots&0_{n}&I_{n}\end{bmatrix}}_{T\text{
matrices}}$.

To prove Theorem III.4, we first show that, similarly to the case of
$\mathcal{V}^{*}$, the subspace $\mathcal{S}^{*}$ can be computed from a
collection of trajectories of finite length $T\geq n$.

###### Lemma III.5

_(Computing $\mathcal{S}^{*}$ from trajectories of finite length)_ For the
system (1) and any finite horizon $T\geq n$, the following statements are
equivalent:

  1. (i)

$x(T)\in\mathcal{S}^{*}$;

  2. (ii)

there exists an input sequence $u(0),\dots,u(T-1)$ such that $y(t)=0$ for all
$t\in\\{0,\dots,T-1\\}$ and $x(0)=0$.

###### Proof:

(i) $\Rightarrow$ (ii) Follows from the definition of $\mathcal{S}^{*}$. For
example, with $u(t)=0$, for $t\in\\{0,\dots,T-2\\}$ and $u(T-1)\neq 0$. Then
$x(T)=Ax(T-1)+Bu(T-1)=Bu(t-1)\in\operatorname{Im}(B)\subseteq\mathcal{S}^{*}$.

(ii) $\Rightarrow$ (i) Because $x(1)=Bu(0)$ and $y(1)=Cx(1)=0$, we have
$x(1)\in\operatorname{Im}(B)\cap\operatorname{Ker}(C)=\mathcal{S}_{1}\cap\operatorname{Ker}(C)$.
Similarly,

$\displaystyle x(2)$ $\displaystyle\in
A(\mathcal{S}_{1}\cap\operatorname{Ker}(C))+\operatorname{Im}(B)=\mathcal{S}_{2},$

and $x(2)\in\operatorname{Ker}(C)$ since $y(2)=Cx(2)=0$. Recursively:

$\displaystyle x(1)$
$\displaystyle\in\mathcal{S}_{1}=\operatorname{Im}(B),\text{ and }$ (15a)
$\displaystyle x(i)$
$\displaystyle\in\mathcal{S}_{i}=A(\mathcal{S}_{i-1}\cap\operatorname{Ker}(C))+\operatorname{Im}(B).$
(15b)

Since $\mathcal{S}_{i}$ converges to $\mathcal{S}^{*}$ in at most $n$ steps
[7], we have that $x(\tau)\in\mathcal{S}^{*}$ for all $\tau\geq n$, which
concludes the proof. ∎

We are now ready to prove Theorem III.4.

Proof of Theorem III.4: From (10), when $x(0)=0$, any state trajectory of
length $T$ that generates an identically zero output of length $T$ can be
parametrized with $\alpha=0$ and $\beta\in\operatorname{Ker}(YK_{0})$. Using
Lemma III.5, the set $\mathcal{S}^{*}$ can be equivalently written as the
final states reached by such trajectories, that is,
$\mathcal{S}^{*}=HXK_{0}\operatorname{Ker}(YK_{0})$, which concludes the
proof. $\blacksquare$

###### Remark 2

_(Obtaining $\mathcal{R}^{*}$ from $\mathcal{V}^{*}$ and $\mathcal{S}^{*}$)_
The combined knowledge of $\mathcal{V}^{*}$ and $\mathcal{S}^{*}$ allows us to
find $\mathcal{R}^{*}$ as [3]

$\mathcal{R}^{*}=\mathcal{V}^{*}\cap\mathcal{S}^{*}.$ (16)

Alternatively, one can also find explicit data-driven expression for
$\mathcal{R}^{*}$ using trajectories of finite-length. For example, one can
show that when the condition $u(0)\neq 0$ is imposed in Lemma III.5, then
$x(T)\in\mathcal{R}^{*}\subseteq\mathcal{S}^{*}$. We omit the proof of this
result, and use (16) to directly compute $\mathcal{R}^{*}$. $\square$

The state of a system can be confined within a subspace $\mathcal{V}$ through
a state-feedback controller if and only if $\mathcal{V}$ is a controlled
invariant subspace. We continue this section with the data-driven design of
such state-feedback controller, that is, the data-driven design of a matrix
$F$ such that

$\displaystyle(A+BF)\mathcal{V}\subseteq\mathcal{V}.$ (17)

For a trajectory $X_{T}$ and input $U_{T}$, let

$\displaystyle X_{0,T}$
$\displaystyle=\begin{bmatrix}x(1)&x(2)&\cdots&x(T-1)\end{bmatrix},$ (18a)
$\displaystyle X_{1,T}$
$\displaystyle=\begin{bmatrix}x(2)&x(3)&\cdots&x(T)\end{bmatrix},\text{ and }$
(18b) $\displaystyle U_{0,T}$
$\displaystyle=\begin{bmatrix}u(0)&u(1)&\cdots&u(T-1)\end{bmatrix}.$ (18c)

###### Theorem III.6

_(Data-driven feedback for invariant subspace)_ Let $X_{T}$ be the trajectory
of (1) with input $U_{T}$ and some initial condition. Let
$\mathcal{V}=\operatorname{Im}(V)$ be an $(A,\operatorname{Im}(B))$-controlled
invariant subspace, and let

$F=U_{0,T}(X_{0,T}^{\dagger}+K\gamma),$ (19)

with $K=\operatorname{Ker}(X_{0,T})$ and

$\gamma=-((I-VV^{\dagger})X_{1,T}K)^{\dagger}(I-VV^{\dagger})X_{1,T}X_{0,T}^{\dagger}VV^{\dagger}.$
(20)

If $[U_{0,T}^{\top}\;X_{0,T}^{\top}]^{\top}$ is full row rank,222This
condition requires the trajectory to be sufficiently informative and is
related to the notion of persistency of excitation [30, 28, 19]. then
$(A+BF)\mathcal{V}\subseteq\mathcal{V}$.

###### Proof:

From [19, Theorem 2], for any state-feedback gain $F$, the closed loop matrix
can be written as

$\displaystyle A+BF=X_{1,T}G,$

where the matrix $G$ satisfies $X_{0,T}G=I$ and $U_{0,T}G=F$. Further, $F$
renders the subspace $\mathcal{V}$ invariant if and only if

$\displaystyle(A+BF)\mathcal{V}=X_{1,T}G\mathcal{V}\subseteq\mathcal{V},$

or, equivalently,

$\displaystyle(I-VV^{\dagger})X_{1,T}GV=0,$

where $V=\operatorname{Basis}(\mathcal{V})$ and $(I-VV^{\dagger})$ is a
projector onto $\mathcal{V}^{\perp}$. From $X_{0,T}G=I$ we obtain
$G=X_{0,T}^{\dagger}+K\gamma$, where $\gamma$ is any matrix of

$\displaystyle(I-VV^{\dagger})X_{1,T}(X_{0,T}^{\dagger}+K\gamma)V=0.$

Solving for $\gamma$ (a solution $\gamma$ exists because $\mathcal{V}$ is an
$(A,B)$-controlled invariant subspace and
$[U_{0,T}^{\top}\;X_{0,T}^{\top}]^{\top}$ is full-row rank) and using
$U_{0,T}G=F$ concludes the proof. ∎

Theorem III.6 details the computation of a feedback matrix that renders a
subspace invariant, from sufficiently informative state and input
trajectories. It should be noticed that Theorem III.6 does not guarantee the
internal, nor external, stability of the subspace, which imposes additional
constraints on $\gamma$. This is left as a topic of future investigation.

To conclude this section we present a strategy to identify the invariant zeros
of (1) from data. We make the assumption that (1) is _non-degenerate_ , i.e.,
$\mathcal{R}^{*}$ is empty. Degenerate systems are intrinsically vulnerable
to, e.g., undetectable malicious attacks with unstable state trajectories. On
the other hand, for non-degenerate systems, the existence of unstable
invisible trajectories depends on the modulo of its invariant zeros. In fact,
the knowledge of the number and magnitude of the invariant zeros of a non-
degenerate system is essential when studying problems such as noninteracting
control [7] and malicious attack detection [11], motivating our interest in
their identification.

###### Theorem III.7

_(Data-driven invariant zeros)_ Let $X$ and $\mathcal{V}^{*}$ be as in (4a)
and (9), respectively, with $T\geq n$. Let
$V=\operatorname{Im}(\mathcal{V}^{*})$ and assume that
$\mathcal{R}^{*}=\emptyset$. Then, $z\in\mathbb{C}$ is an invariant zero of
(1) if and only if the matrix

$\left[XX^{\dagger}(I\otimes V)\quad-\left([z~{}z^{2}~{}\cdots~{}z^{T}]\otimes
I\right)^{\top}\right]$ (21)

has a nontrivial kernel.

###### Proof:

When $\mathcal{V}^{*}\neq\emptyset$ and $\mathcal{R}^{*}=\emptyset$, there
exists a trajectory $x(t)=z^{t}x(0)$, with $x(t)\in\mathcal{V}^{*}$ for all
$t\geq 0$ and $z$ an invariant zero of (1) [3]. We write such trajectory as

$X_{T}^{V}=\begin{bmatrix}zI\\\ z^{2}I\\\ \vdots\\\
z^{T}I\end{bmatrix}v=\left([z~{}z^{2}~{}\cdots~{}z^{T}]\otimes
I\right)^{\top}v.$ (22)

With Assumption II.1, any trajectory belongs to the image of the data matrix
$X$. Then, when the trajectory $X_{T}^{V}$ above exists, there also exists a
vector $\bar{w}\in X^{\dagger}(I\otimes V)$ such that $X\bar{w}=X_{T}^{V}$.
The condition on $\bar{w}$ imposes that the trajectory is compatible with (1)
while evolving inside $\mathcal{V}^{*}$. Both vectors $v\neq 0$ and
$\bar{w}=X^{\dagger}(I\otimes V)w\neq 0$ exist if and only if

$XX^{\dagger}(I\otimes V)w=\left([z~{}z^{2}~{}\cdots~{}z^{T}]\otimes
I\right)^{\top}v$ (23)

i.e., the kernel of $[XX^{\dagger}(I\otimes
V)\quad-\left([z~{}z^{2}~{}\cdots~{}z^{T}]\otimes I\right)^{\top}]$ is non-
empty, concluding the proof. ∎

The invariant zeros of the system (1) can be equivalently characterized using
data collected as in (18).

###### Lemma III.8

_(Data-driven invariant zeros)_ Let $\mathcal{V}^{*}$ be as in (9) and assume
that $\mathcal{R}^{*}=\emptyset$. Let
$T=\begin{bmatrix}T_{1}&T_{2}\end{bmatrix},$ with $T_{1}=\mathcal{V}^{*}$, and
$T_{2}$ chosen such that $T$ is nonsingular. Finally, let
$G=X_{0,T}^{\dagger}+K\gamma$, with $\gamma$ defined as in (20). Then, the
invariant zeros of (1) are the eigenvalues of $A_{11}$, where

$T^{-1}(X_{1,T}G)T=\begin{bmatrix}A_{11}&A_{12}\\\ 0&A_{22}\\\ \end{bmatrix}.$
(24)

###### Proof:

This result derives from the facts that (i) the closed loop system with the
state feedback $u=Fx$ satisfies

$A+BF=X_{1,T}G,$ (25)

(ii) the subspace $\mathcal{V}^{*}$ is invariant for the closed-loop matrix
$A+BF$, and (iii) the invariant zeros of (1) are the eigenvalues of the
closed-loop matrix $A+BF$ contained in $\mathcal{V}^{*}$. ∎

$1$$2$$3$$14$$12$$4$$5$$6$$8$$7$$11$$13$$9$$10$ Figure 2: An example of
consensus network from [31]. Agents are numbered from $1$ through $14$, where
nodes $\\{12,13,14\\}$ (in black) are the leaders and nodes $\\{4,11\\}$ (in
red) are the network monitors.

##  IV Malicious attacks: an illustrative example

To illustrate a possible use of the theory developed in this paper, consider
the leader-follower consensus network in Fig. 2. The dynamics of the followers
are given by the matrices

$\displaystyle A$
$\displaystyle=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}.8&.2&0&0&0&0&0&0&0&0&0\\\
.2&.4&.2&0&0&0&0&0&0&0&0\\\ 0&.2&.6&0&0&0&0&0&0&0&0\\\
0&0&0&.6&.2&0&0&0&0&0&0\\\ 0&0&0&.2&.4&.2&0&0&0&0&0\\\
0&0&0&0&.2&.6&0&.2&0&0&0\\\ 0&0&0&0&0&0&.8&.2&0&0&0\\\
0&0&0&0&0&.2&.2&.2&0&0&.2\\\ 0&0&0&0&0&0&0&0&.6&.2&0\\\
0&0&0&0&0&0&0&0&.2&.6&0\\\ 0&0&0&0&0&0&0&.2&0&0&.8\end{bmatrix},$
$\displaystyle B^{\top}$
$\displaystyle=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}0&.2&0&.2&.2&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&.2&.2&.2&0\\\ 0&0&.2&0&0&0&0&0&0&0&0\end{bmatrix},\text{ and }$
$\displaystyle C$
$\displaystyle=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}0&0&0&1&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&1\end{bmatrix}.$

The network is equipped with two monitoring nodes, specifically, nodes $4$ and
$11$. The state of the monitoring nodes is used to detect any anomalous
behavior of the network from its nominal dynamics (see also [32]). We let an
attacker take control of the leader nodes, and seek for an attack strategy
that remains undetectable from the monitoring nodes, and leverages only
historical data of the network dynamics. In particular, the attacker strategy
is designed as follows: (i) compute $\mathcal{V}^{*}$ and $\mathcal{S}^{*}$
using Theorems III.1 and III.4, respectively, and find
$\mathcal{R}^{*}=\mathcal{V}^{*}\cap\mathcal{S}^{*}$; (ii) for
$R=\operatorname{Basis}(\mathcal{R}^{*})$, and $X$, $U$ and $K_{0}$ defined as
in (4a), (4d) and Assumption II.1, compute333Similarly to the proof of Theorem
III.7, it can be shown that, for nontrivial $v$ and $w$, any trajectory
satisfying $XK_{0}v=(I\otimes R)w$ (i) starts at the origin, (ii) evolves in
$\mathcal{R}^{*}$, and (iii) is compatible with the data (4) of (1). $P$ as

$\begin{bmatrix}XK_{0}&I\otimes R\end{bmatrix}\begin{bmatrix}P\\\
Q\end{bmatrix}=0;$ (26)

and (iii) choose the attack input $A_{T}$ as
$A_{T}\in\operatorname{Im}(UK_{0}P)$. Then, for any initial state $x(0)$ and
nominal control input $U_{T}$, the output of (2)-(3) with input $U_{T}$ is
indistinguishable from the output with input $U_{T}+A_{T}$. As can be seen in
Fig. 3 from time $t=24s$, the attacker strategy perturbs the state of the
network but does not affect the monitoring nodes, thus remaining undetectable.
In fact, it can be shown that any input $A_{T}\in\operatorname{Im}(UK_{0}P)$
moves the state trajectory within the controlled invariant
$\mathcal{R}^{*}\subseteq\operatorname{Ker}(C)$, thus affecting the state of
the system but not its output.

Figure 3: In this figure we show an attack on the network of Fig. 2. The
systems initial condition is chosen randomly and the leaders impose
$u=[-2~{}2~{}4]^{\top}$. The attacker waits for the system to reach its
equilibrium and then, at time $t=24s$, injects an attack $A_{T}$ as proposed
in Sec IV. We notice how the system state its perturbed from the equilibrium,
while the output of the system remains unaffected by the attack, rendering the
attack action effectively invisible at the output.

##  V Conclusion

In this paper we show how experimental data can be used to learn key invariant
subspaces of a linear system. In particular, we derive data-driven expressions
for $\mathcal{V}^{*}$, the largest $(A,\operatorname{Im}(B))$-controlled
invariant contained in $\operatorname{Ker}(C)$, and $\mathcal{S}^{*}$, the
smallest $(A,\operatorname{Ker}(C))$-conditioned invariant containing
$\operatorname{Im}(B)$. Being able to identify these subspaces from data
suggests that much of the results and intuitions of the geometric approach to
control can be conveniently reworked in a data-driven framework. To support
this point, we leverage the identified invariant subspaces to design a data-
driven feedback controller to force the state inside a desired controlled
invariant subspace, and to compute the invariant zeros of the system. Finally,
as an example of the theoretical results, we design a data-driven undetectable
attack. Applications and extensions of the proposed results are numerous, and
are left as the subject of future investigation.

## References

  * [1] K. J. Åström and R. M. Murray, Feedback systems: an introduction for scientists and engineers.  Princeton university press, 2010.
  * [2] T. Kailath, Linear Systems.  Prentice-Hall, 1980.
  * [3] G. Basile and G. Marro, Controlled and Conditioned Invariants in Linear System Theory.  Prentice Hall, 1991.
  * [4] W. M. Wonham, Linear Multivariable Control: A Geometric Approach.  Springer, 3 ed., 1985.
  * [5] H. L. Trentelman, A. Stoorvogel, and M. Hautus, Control Theory for Linear Systems.  Springer, 2001.
  * [6] I. Markovsky and P. Rapisarda, “Data-driven simulation and control,” International Journal of Control, vol. 81, no. 12, pp. 1946–1959, 2008.
  * [7] G. Basile and G. Marro, “Controlled and conditioned invariant subspaces in linear system theory,” Journal of Optimization Theory and Applications, vol. 3, no. 5, pp. 306–315, 1969.
  * [8] A. Isidori, Nonlinear Control Systems.  Communications and Control Engineering Series, Springer, 3 ed., 1995.
  * [9] W. M. Wonham and A. S. Morse, “Decoupling and pole assignment in linear multivariable systems: a geometric approach,” SIAM Journal on Control, vol. 8, no. 1, pp. 1–18, 1970.
  * [10] M. A. Massoumnia, G. C. Verghese, and A. S. Willsky, “Failure detection and identification,” IEEE Transactions on Automatic Control, vol. 34, no. 3, pp. 316–321, 1989.
  * [11] F. Pasqualetti, F. Dörfler, and F. Bullo, “Attack detection and identification in cyber-physical systems,” IEEE Transactions on Automatic Control, vol. 58, no. 11, pp. 2715–2729, 2013.
  * [12] H. Fawzi, P. Tabuada, and S. Diggavi, “Secure estimation and control for cyber-physical systems under adversarial attacks,” IEEE Transactions on Automatic Control, vol. 59, no. 6, pp. 1454–1467, 2014.
  * [13] M. Gevers, “Identification for control: From the early achievements to the revival of experiment design,” European Journal of Control, vol. 11, pp. 1–18, 2005.
  * [14] V. Krishnan and F. Pasqualetti, “On direct vs indirect data-driven predictive control,” in IEEE Conf. on Decision and Control, (Austin, TX), pp. 736–741, Dec. 2021.
  * [15] F. Dörfler, J. Coulson, and I. Markovsky, “Bridging direct & indirect data-driven control formulations via regularizations and relaxations,” January 2021.  Submitted. Available at https://arxiv.org/abs/2101.01273.
  * [16] H. van Waarde, J. Eising, H. L. Trentelman, and M. K. Camlibel, “Data informativity: a new perspective on data-driven analysis and control,” arXiv preprint arXiv:1908.00468, 2019.
  * [17] G. Baggio, D. S. Bassett, and F. Pasqualetti, “Data-driven control of complex networks,” Nature Communications, vol. 12, no. 1429, 2021.
  * [18] N. Monshizadeh, “Amidst data-driven model reduction and control,” IEEE Control Systems Letters, vol. 4, no. 4, pp. 833–838, 2020.
  * [19] C. De Persis and P. Tesi, “Formulas for data-driven control: Stabilization, optimality and robustness,” IEEE Transactions on Automatic Control, vol. 65, no. 3, pp. 909–924, 2020.
  * [20] A. Bisoffi, C. De Persis, and P. Tesi, “Data-driven control via petersen’s lemma,” arXiv preprint arXiv:2109.12175, 2021.
  * [21] A. Allibhoy and J. Cortés, “Data-based receding horizon control of linear network systems,” IEEE Control Systems Letters, vol. 5, no. 4, pp. 1207–1212, 2020.
  * [22] F. Celi, G. Baggio, and F. Pasqualetti, “Distributed learning of optimal controls for linear systems,” in IEEE Conf. on Decision and Control, (Austin, TX), pp. 5764–5769, Dec. 2021.
  * [23] É. Garrabé and G. Russo, “On the design of autonomous agents from multiple data sources,” IEEE Control Systems Letters, vol. 6, pp. 698 – 703, 2021.
  * [24] J. Jiao, H. J. van Waarde, H. L. Trentelman, M. K. Camlibel, and S. Hirche, “Data-driven output synchronization of heterogeneous leader-follower multi-agent systems,” in IEEE Conf. on Decision and Control, (Austin, TX), pp. 466–471, Dec. 2021.
  * [25] S. M. Turan and G. Ferrari-Trecate, “Data-driven unknown-input observers and state estimation,” IEEE Control Systems Letters, vol. 6, pp. 1424–1429, 2021.
  * [26] I. Markovsky and F. Dörfler, “Behavioral systems theory in data-driven analysis, signal processing, and control,” July 2021.
  * [27] D. S. Bernstein, Matrix Mathematics.  Princeton University Press, 2 ed., 2009.
  * [28] J. Coulson, J. Lygeros, and F. Dörfler, “Data-enabled predictive control: In the shallows of the DeePC,” in European Control Conference, (Naples, Italy), pp. 307–312, 2019.
  * [29] V. Breschi, C. De Persis, S. Formentin, and P. Tesi, “Direct data-driven model-reference control with Lyapunov stability guarantees,” arXiv preprint arXiv:2103.12663, 2021.
  * [30] J. C. Willems, P. Rapisarda, I. Markovsky, and B. L. M. De Moor, “A note on persistency of excitation,” Systems & Control Letters, vol. 54, no. 4, pp. 325–329, 2005.
  * [31] M. Egerstedt, S. Martini, M. Cao, K. Camlibel, and A. Bicchi, “Interacting with networks: How does structure relate to controllability in single-leader, consensus networks?,” IEEE Control Systems Magazine, vol. 32, no. 4, pp. 66–73, 2012.
  * [32] F. Pasqualetti, A. Bicchi, and F. Bullo, “Consensus computation in unreliable networks: A system theoretic approach,” IEEE Transactions on Automatic Control, vol. 56, no. 12, pp. 90–104, 2011.