# Invertibility of Discrete-Time Linear Systems with Sparse Inputs

Kyle Poe, Enrique Mallada, and René Vidal The authors thank the support of the
ONR MURI grant 503405-78051, Control and Learning Enabled Verifiable Robust AI
(CLEVR-AI)K. Poe is with the Applied Mathematics and Computational Science
Group, University of Pennsylvania, PA 19104<EMAIL_ADDRESS>Mallada is
with the Department of Electrical and Computer Engineering, Johns Hopkins
University, MD 21218<EMAIL_ADDRESS>Vidal is with the Departments of
Electrical and Systems Engineering, Radiology, Computer and Information
Science, Statistics and Data Science, University of Pennsylvania, PA 19104
<EMAIL_ADDRESS>
###### Abstract

One of the fundamental problems of interest for discrete-time linear systems
is whether its input sequence may be recovered given its output sequence,
a.k.a. the left inversion problem. Many conditions on the state space
geometry, dynamics, and spectral structure of a system have been used to
characterize the well-posedness of this problem, without assumptions on the
inputs. However, certain structural assumptions, such as input sparsity, have
been shown to translate to practical gains in the performance of inversion
algorithms, surpassing classical guarantees. Establishing necessary and
sufficient conditions for left invertibility of systems with sparse inputs is
therefore a crucial step toward understanding the performance limits of system
inversion under structured input assumptions. In this work, we provide the
first necessary and sufficient characterizations of left invertibility for
linear systems with sparse inputs, echoing classic characterizations for
standard linear systems. The key insight in deriving these results is in
establishing the existence of two novel geometric invariants unique to the
sparse-input setting, the weakly unobservable and strongly reachable subspace
arrangements. By means of a concrete example, we demonstrate the utility of
these characterizations. We conclude by discussing extensions and applications
of this framework to several related problems in sparse control.

##  I Introduction

Dynamical systems, ubiquitous in modern applied mathematics, are often
characterized by their intrinsic properties, such as stability and orbit
structure. However, in many instances, one is less interested in the system
itself, and more interested in the relationship the system induces between
some _input_ time series, and the resulting _observations_ , usually produced
as some state-dependent function of the inputs. Nowhere is the importance of
this fundamental relationship more apparent than in signal processing, where
one observes some transformed or corrupted version of an input signal, and
wishes to recover the original signal.

In systems theory, the ability to uniquely recover a sequence of inputs given
a sequence of outputs, or demonstrate the existence of a sequence of inputs
which produces a desired output, is called _invertibility_ [1, 2]. In addition
to guaranteeing the well-posedness of signal recovery problems, left
invertibility is a necessary condition for the existence of unknown input
observers, and is closely related to fault detection [3, 4] and input
observability [5, 6].

In the linear setting, several equivalent and interpretable characterizations
of invertibility providing different perspectives on the problem have been
established. In particular, the geometric approach emphasizes certain
invariant subspaces of the system which give rise to the so-called special
coordinate basis [7], which has been used to great practical effect in
observer design [8]. Another characterization focuses on the algebraic
properties of the input-output map, establishing a clear path to the design of
delayed system inverses [1, 9]. Yet another characterization concerns the
zeros of the Rosenbrock system matrix [10], providing a connection to transfer
function methods and the stronger problem of stable invertibility [11]. These
differing characterizations illuminate complementary aspects of the system,
and have been used to great effect in the analysis of various recovery
problems.

In recent years, there has been an increased awareness of the benefit of
modeling input structure at the heart of various control applications.
Notably, sparsity in the inputs has been explored in some depth [12, 13, 14,
15], particularly in the context of networked systems [16, 17]. Various
algorithms have been developed for online recovery of sparse signals [18, 19,
20], and more recently, for the recovery of sparse inputs to general linear
systems [12, 21, 14]. Necessary and sufficient conditions for the finite-
horizon case have been established in [13], a problem for which a performant
Bayesian recovery algorithm was introduced in [14].

Despite the empirical success of these approaches, characterizations of the
well-posedness of the infinite-horizon left invertibility problem for linear
systems with sparse inputs have yet to emerge. Such characterizations are
vital in particular for applications to structured and networked systems, in
which the minimial required delay for input recovery may be generically
nontrivial [22].

In this work, we establish necessary and sufficient characterizations of left
invertibility for linear systems with sparse inputs, which parallel
established characterizations for standard linear systems. Our contributions
are as follows:

  1. 1.

We introduce the notion of weakly unobservable and strongly reachable subspace
arrangements, generalizing key invariants of classical geometric linear
systems theory to the sparse input setting, and show that these objects can be
computed and used to directly certify invertibility.

  2. 2.

We establish rank-based conditions for left sparse invertibility, and show
that if an inverse exists, it may be realized with finite delay.

  3. 3.

The invertibility of systems with sparse inputs having temporally periodic
support patterns is characterized via the zeros of a generalized Rosenbrock
matrix, and this construction is used to provide a final necessary and
sufficient condition for left invertibility under a generic sparse input
assumption.

  4. 4.

We present an example to illustrate application of these ideas, and conclude
by discussing extensions and connections to related problems in sparse
control.

##  II Preliminaries

In this section, we first introduce the basic notation that will be used
throughout the paper (see Section II-A). Then in Section II-B, we overview
several necessary and sufficient conditions for left invertibility of linear
systems, including geometric, rank-based and spectral characterizations.
Finally, in Section II-C we review basic properties of subspace arrangements
that are needed to extend classical invertibility results to linear systems
with sparse inputs.

###  II-A Notation

We denote $\mathbb{N}:=\\{0,1,2,\ldots\\}$, and for any natural number
$N\in\mathbb{N}$, $[\\![N]\\!]:=\\{0,1,\ldots,N-1\\}$. Let
$\Omega,\Omega^{\prime}$ be sets. We define the product
$\Omega\times\Omega^{\prime}=\\{(\omega,\omega^{\prime}):\omega\in\Omega,\omega^{\prime}\in\Omega^{\prime}\\}$,
and identify $\Omega^{N}$ with the set of functions
$\\{\omega:[\\![N]\\!]\to\Omega\\}$; and equivalently, the set of $N$-tuples
$(\omega_{0},\omega_{1},\ldots,\omega_{N-1})$. $|\Omega|$ is the cardinality
of $\Omega$. For a sequence $\omega:\mathbb{N}\to\Omega$, we denote by
$[\omega]_{k}^{N}\in\Omega^{N}$ the tuple
$(\omega_{k},\omega_{k+1},\ldots,\omega_{k+N-1})$, which may be read as the
_first $N$ elements of $\omega$ beginning at $k$_. We also define the shift
operator $\sigma$ on tuples and sequences such that $\forall
k,\sigma(\omega)_{k}=\omega_{k+1}$; note that
$\sigma:\Omega^{N}\to\Omega^{N-1}$ for tuples and
$\sigma:\Omega^{\mathbb{N}}\to\Omega^{\mathbb{N}}$ for sequences. We liberally
define $0$ to be the zero element in the relevant context. We denote the $k$th
canonical Euclidean basis vector by $\bm{e}_{k}\in\mathbb{R}^{n}$, the
canonical subspace associated with $S\subseteq[\\![m]\\!]$ as $\langle
S\rangle:=\text{span}\\{\bm{e}_{i}\\}_{i\in S}$, and the preimage of a set
$\mathcal{V}$ under a linear map/matrix $\bm{A}$ as
$\bm{A}^{-1}\mathcal{V}:=\\{\bm{x}:\bm{A}\bm{x}\in\mathcal{V}\\}$. If $\Delta$
is a set of sets, given $S,T:\mathbb{N}\to\Delta$, we define the sequence
$S\cup T:=(S_{k}\cup T_{k})_{k\in\mathbb{N}}$. If $\Delta$ consists of subsets
of the support of $\bm{A}$, for $S\in\Delta$, $\bm{A}_{S}$ is the matrix
consisting of columns indexed by $S$. For a block matrix $\bm{\Theta}_{N}$
with $N$ block columns $\\{\bm{\Theta}_{i}\\}_{i\in[\\![N]\\!]}$ and
$S\in\Delta^{N}$, we define the matrix $\bm{\Theta}_{S}$ to be the block
matrix with $N$ block columns
$\\{(\bm{\Theta}_{i})_{S_{i}}\\}_{i\in[\\![N]\\!]}$.

###  II-B Linear Systems

Throughout, we consider a fixed, finite-dimensional, discrete time linear
system $\Sigma=(\bm{A},\bm{B},\bm{C},\bm{D})\in\mathbb{R}^{n\times
n}\times\mathbb{R}^{n\times m}\times\mathbb{R}^{p\times
n}\times\mathbb{R}^{p\times m}$. To this system, for any $N>0$, we associate
the following block matrices; respectively, the _observability_ , _finite
response_ , and _controllability_ matrices:

$\displaystyle\bm{\mathcal{O}}_{N}\\!$
$\displaystyle=\\!\\!\begin{bmatrix}\bm{C}\\\ \bm{C}\bm{A}\\\
\bm{C}\bm{A}^{2}\\\ \vdots\\\
\bm{C}\bm{A}^{N-1}\end{bmatrix}\\!,\bm{\Gamma}_{N}\\!=\\!\\!\begin{bmatrix}\bm{D}\\\
\bm{C}\bm{B}\\!&\\!\bm{D}\\\
\bm{C}\bm{A}\bm{B}\\!&\\!\bm{C}\bm{B}\\!&\\!\bm{D}\\\
\vdots\\!&\\!&\\!\ddots\\!&\\!\ddots\\\
\bm{C}\bm{A}^{N-2}\bm{B}\\!&\\!\cdots\\!&\\!&\\!\bm{C}\bm{B}\\!&\\!\bm{D}\end{bmatrix}\\!.$
$\displaystyle\bm{\mathcal{C}}_{N}\\!$
$\displaystyle=\\!\begin{bmatrix}\bm{A}^{N-1}\bm{B}&\cdots&\bm{A}^{2}\bm{B}&\bm{A}\bm{B}&\bm{B}\end{bmatrix}.$

Note that our definition of the controllability matrix has a reversed order of
powers from the typical definition; this permits concise identities like the
following, for any $M<N$:

$\bm{\Gamma}_{N}=\begin{bmatrix}\bm{\Gamma}_{N-M}&0\\\
\bm{\mathcal{O}}_{M}\bm{\mathcal{C}}_{N-M}&\bm{\Gamma}_{M}\end{bmatrix}=\begin{bmatrix}\bm{D}&0\\\
\bm{\mathcal{O}}_{N-1}\bm{B}&\bm{\Gamma}_{N-1}\end{bmatrix}.$ (1)

Given an input sequence $\bm{u}:\mathbb{N}\to\mathbb{R}^{m}$, we define the
_infinite response_ of $\Sigma$ from $\bm{x}_{0}\in\mathbb{R}^{n}$ to be the
sequence $\bm{\gamma}(\bm{x}_{0},\bm{u}):\mathbb{N}\to\mathbb{R}^{p}$ such
that for any $N,k$, the following conditions hold:

$\displaystyle[\bm{\gamma}(\bm{x}_{0},\bm{u})]_{k}^{N}$
$\displaystyle=\bm{\mathcal{O}}_{N}\bm{x}_{k}+\bm{\Gamma}_{N}[\bm{u}]_{k}^{N},$
(2) $\displaystyle\sigma^{k}(\bm{\gamma}(\bm{x}_{0},\bm{u}))$
$\displaystyle=\bm{\gamma}(\bm{A}^{k}\bm{x}_{0}+\bm{\mathcal{C}}_{k}[\bm{u}]_{0}^{k},\sigma^{k}(\bm{u})).$
(3)

Note that $(\bm{\gamma}(\bm{x}_{0},\bm{u})_{k})_{k\in\mathbb{N}}$ is just the
sequence of outputs for the linear system with initial state $\bm{x}_{0}$ and
inputs $(\bm{u}_{k})_{k\in\mathbb{N}}$, and that $\bm{\gamma}$ is linear:
$\bm{\gamma}(\alpha(\bm{x}_{0},\bm{u})+\beta(\bm{x}_{0}^{\prime},\bm{u}^{\prime}))=\alpha\bm{\gamma}(\bm{x}_{0},\bm{u})+\beta\bm{\gamma}(\bm{x}_{0}^{\prime},\bm{u}^{\prime})$.
To denote the zero-state response, we write
$\bm{\gamma}_{0}(\bm{u}):=\bm{\gamma}(0,\bm{u})$.

The geometric approach to analyzing system invertibility emphasizes certain
subspaces linking output behavior to choice of inputs:

######  Definition 1 (Invariant Subspaces)

  * •

The _weakly unobservable subspace_ $\mathcal{V}(m)\subseteq\mathbb{R}^{n}$
consists of $\bm{x}$ s.t. $\exists\bm{u}:\mathbb{N}\to\mathbb{R}^{m}$,
$\bm{\gamma}(\bm{x},\bm{u})=0$.

  * •

The _strongly reachable subspace_ $\mathcal{T}(m)\subseteq\mathbb{R}^{n}$
consists of $\bm{x}$ s.t. $\exists\bm{u}:\mathbb{N}\to\mathbb{R}^{m},\exists
N\in\mathbb{N}$, $\bm{\Gamma}_{N}[\bm{u}]_{0}^{N}=0$ and
$\bm{\mathcal{C}}_{N}[\bm{u}]_{0}^{N}=\bm{x}$.

Note that $\mathcal{V}(m)$ contains the unobservable subspace
$\ker\bm{\mathcal{O}}_{n}$, and $\mathcal{T}(m)$ is a subspace of the
reachable subspace $\operatorname{im}\bm{\mathcal{C}}_{n}$. They are thus
naturally viewed as respectively weakened and strengthened versions of these
spaces, accounting for particular choices of inputs.

An alternative viewpoint of the input-output characteristics of a linear
system involves its invariant zeros, which are defined as the $z\in\mathbb{C}$
such that the following matrix pencil drops rank:

######  Definition 2 (Rosenbrock System Matrix)

$\bm{R}(z)=\begin{bmatrix}\bm{A}-z\bm{I}&\bm{B}\\\ \bm{C}&\bm{D}\end{bmatrix}$
(4)

We now recall the definition of left invertibility for linear systems [1]:

######  Definition 3 (Left Invertibility)

We say that $\Sigma$ is _left invertible_ if for any
$\bm{u},\bm{u}^{\prime}:\mathbb{N}\to\mathbb{R}^{m}$,
$\bm{\gamma}_{0}(\bm{u})=\bm{\gamma}_{0}(\bm{u}^{\prime})$ implies
$\bm{u}=\bm{u}^{\prime}$.

There are several equivalent characterizations of when left invertibility
holds, which can be considered as arising from complementary _perspectives_ on
what it means for a system to be invertible. In the case of left
invertibility:

######  Theorem 1 (Left Invertibility, [10, 1])

The following are equivalent:

  1. 1.

$\Sigma$ is left invertible.

  2. 2.

$\mathcal{V}(m)\cap\mathcal{T}(m)=0$ and $\ker\begin{bmatrix}\bm{B}\\\
\bm{D}\end{bmatrix}=0$.

  3. 3.

$\exists N$,
$\operatorname{rank}\bm{\Gamma}_{N}-\operatorname{rank}\bm{\Gamma}_{N-1}=m$.

  4. 4.

$\exists z\in\mathbb{C}$, $\operatorname{rank}\bm{R}(z)=n+m$.

One may think of conditions (2-4) as providing _geometric, rank based_ , and
_spectral_ characterizations of left invertibility: (2) indicates that no
input is invisible to measurement results in a weakly unobservable
perturbation to the state; (3) indicates that if an inverse exists, it can be
implemented with some finite delay; and (4) can be used to show that the
associated transfer function matrix admits a rational polynomial left inverse.

###  II-C Subspace Arrangements

In the sparse recovery literature, one often considers the set of all vectors
with a particular sparsity pattern. If we denote
$\Delta_{s}:=\\{S\subseteq[\\![m]\\!]:|S|\leq s\\}$, this set of vectors may
be written as $\bigcup_{S\in\Delta_{s}}\langle S\rangle$. Generally speaking,
for any set $\Delta$ of subsets of $[\\![m]\\!]$, we will write

$\langle\Delta\rangle:=\bigcup_{S\in\Delta}\langle
S\rangle\subseteq\mathbb{R}^{m}$ (5)

This object is an example of a _finite subspace arrangement_ :

######  Definition 4 (Finite Subspace Arrangement)

Let $\mathcal{A}\subseteq\mathbb{R}^{n}$. We call $\mathcal{A}$ a _finite
subspace arrangement in $\mathbb{R}^{n}$_ if there exists an natural number
$c$ and a collection of subspaces
$(U_{i})_{i\in[\\![c]\\!]},U_{i}\subseteq\mathbb{R}^{n}$, such that
$\mathcal{A}=\bigcup_{i\in[\\![c]\\!]}U_{i}$. We denote the smallest such $c$
as $c(\mathcal{A})$, and call this the _size_ of $\mathcal{A}$.

For example, the set of $s$-sparse vectors $\langle\Delta_{s}\rangle$ in
$\mathbb{R}^{m}$ has size $\binom{m}{s}$. While this case only contains
subspaces of dimension $s$, in general, subspace arrangements may contain
subspaces of differing dimension.

######  Definition 5 (Dimension Vector)

Let $\mathcal{A}\subseteq\mathbb{R}^{n}$ be a finite subspace arrangement of
size $c$ such that $\mathcal{A}=\bigcup_{i\in[\\![c]\\!]}U_{i}$. Define
$d_{k}(\mathcal{A})=|\\{i\in[\\![c]\\!]:\dim U_{i}=k\\}|$, and
$\bm{d}(\mathcal{A})=(d_{1}(\mathcal{A}),\ldots,d_{n}(\mathcal{A}))\in\mathbb{N}^{n}$.
We refer to $\bm{d}(\mathcal{A})$ as the _dimension vector_ of $\mathcal{A}$.

Note that for a linear subspace $\mathcal{X}\subseteq\mathbb{R}^{n}$, we have
that $\bm{d}(\mathcal{X})=\bm{e}_{\dim(\mathcal{X})}\in\mathbb{N}^{n}$. This
provides a means of assessing the relative size of two subspace arrangements,
in a similar fashion as simple dimension for subspaces:

######  Definition 6 (Dimensional Order)

Define $(\mathbb{N}^{n},\preceq)$ the totally ordered set such that for
$\bm{a},\bm{b}\in\mathbb{N}^{n}$, $\bm{a}\preceq\bm{b}$ if for
$j=\max\\{i\in[\\![n]\\!]:\bm{a}_{i}\neq\bm{b}_{i}\\},\bm{a}_{j}\leq\bm{b}_{j}$,
and $\bm{a}\prec\bm{b}$ analogously. Given subspace arrangements
$\mathcal{A},\mathcal{B}\subseteq\mathbb{R}^{n}$, we define the _dimensional
order_ $\preceq$ such that $\mathcal{A}\preceq\mathcal{B}$ if
$\bm{d}(\mathcal{A})\preceq\bm{d}(\mathcal{B})$.

Lastly, we note that if $\mathcal{U},\mathcal{V}\subseteq\mathbb{R}^{n}$ are
finite subspace arrangements and $\bm{H}$ is a well-defined linear map, then
$\mathcal{U}\times\mathcal{V},\mathcal{U}\cup\mathcal{V},\mathcal{U}\cap\mathcal{V},\mathcal{U}+\mathcal{V},\bm{H}\mathcal{U},\bm{H}^{-1}\mathcal{U}$
are all finite subspace arrangements.

##  III Invertibility of Linear Systems with Sparse Inputs

In this section, we will generalize the classical notion of left invertibility
to systems with piecewise $s$-sparse inputs:

######  Definition 7 (Left $\mathcal{U}$-Invertibility)

Let $\mathcal{U}\subseteq(\mathbb{R}^{m})^{\mathbb{N}}$. We say that $\Sigma$
is left $\mathcal{U}$-invertible if
$\forall\bm{u},\bm{u}^{\prime}\in\mathcal{U},\quad\bm{\gamma}_{0}(\bm{u})=\bm{\gamma}_{0}(\bm{u}^{\prime})\implies\bm{u}=\bm{u}^{\prime}$.
We will say that $\Sigma$ is _left $s$-sparse invertible_ when
$\mathcal{U}=\\{\bm{u}:\mathbb{N}\to\langle\Delta_{s}\rangle\\}$.

One can interpret this as a statement about the _injectivity_ of
$\bm{\gamma}_{0}$ when restricted to a given input class $\mathcal{U}$. The
remainder of this section is dedicated to establishing analogous conditions
for $s$-sparse invertibility to those in Theorem 1, beginning with the
characterization of sparse counterparts to the weakly unobservable and
strongly reachable subspaces.

###  III-A Geometric Characterization

The notion of weak unobservability generalizes immediately to the sparse
setting:

######  Definition 8 (Weakly Unobservable Point)

Let $\bm{x}\in\mathbb{R}^{n}$. If there exists
$\bm{u}:\mathbb{N}\to\langle\Delta_{s}\rangle$ such that
$\bm{\gamma}(\bm{x},\bm{u})=0$, then we call $\bm{x}$ _weakly $s$-sparse
unobservable_, and denote by $\mathcal{V}(s)$ the set of all such $\bm{x}$.

We will proceed to show that $\mathcal{V}(s)$ is a finite subspace
arrangement. To compute $\mathcal{V}(s)$, consider the following set mapping:

$f_{s}(\mathcal{A})=\mathcal{A}\cap\begin{bmatrix}\bm{C}\\\
\bm{A}\end{bmatrix}^{-1}\left(0\times\mathcal{A}+\begin{bmatrix}\bm{D}\\\
\bm{B}\end{bmatrix}\langle\Delta_{s}\rangle\right)$ (6)

Intuitively, $f_{s}(\mathcal{A})$ returns the set of $\bm{x}\in\mathcal{A}$
such that there exists an $s$-sparse input $\bm{u}$ satisfying
$\bm{A}\bm{x}+\bm{B}\bm{u}\in\mathcal{A}$ and $\bm{C}\bm{x}+\bm{D}\bm{u}=0$.
Note that, by construction, for any $\mathcal{A}\subseteq\mathbb{R}^{n}$,
$f_{s}(\mathcal{A})\subseteq\mathcal{A}$; and if
$f_{s}(\mathcal{A})=\mathcal{A}$, $f_{s}^{2}(\mathcal{A}):=(f_{s}\circ
f_{s})(\mathcal{A})=\mathcal{A}$.

###### Lemma 1

$\forall k>0$,
$f_{s}^{k}(\mathbb{R}^{n})=\bm{\mathcal{O}}_{k}^{-1}(\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k})$

###### Proof:

We first remark
$\bm{\mathcal{O}}_{k+1}^{-1}(\bm{\Gamma}_{k+1}\langle\Delta_{s}\rangle^{k+1})\subseteq\bm{\mathcal{O}}_{k}^{-1}(\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k})$,
this is readily seen by considering that
$\bm{\mathcal{O}}_{k+1}\bm{x}\in\bm{\Gamma}_{k+1}\langle\Delta_{s}\rangle^{k+1}\implies\bm{\mathcal{O}}_{k}\bm{x}\in\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k}$.
The remaining proof is by induction on $k$. For $k=1$,
$f_{s}(\mathbb{R}^{n})=\bm{C}^{-1}\bm{D}\langle\Delta_{s}\rangle=\bm{\mathcal{O}}_{1}^{-1}\bm{\Gamma}_{1}\langle\Delta_{s}\rangle$.
Now suppose
$f_{s}^{k}(\mathbb{R}^{n})=\bm{\mathcal{O}}_{k}^{-1}(\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k})$:

$\displaystyle\bm{\mathcal{O}}_{k+1}^{-1}(\bm{\Gamma}_{k+1}\langle\Delta_{s}\rangle^{k+1})$
$\displaystyle=\begin{bmatrix}\bm{C}\\\
\bm{\mathcal{O}}_{k}\bm{A}\end{bmatrix}^{-1}\left(\begin{bmatrix}\bm{D}\\\
\bm{\mathcal{O}}_{k}\bm{B}\end{bmatrix}\langle\Delta_{s}\rangle+\begin{bmatrix}0\\\
\bm{\Gamma}_{k}\end{bmatrix}\langle\Delta_{s}\rangle^{k}\right)$
$\displaystyle\overset{*}{=}\begin{bmatrix}\bm{C}\\\
\bm{A}\end{bmatrix}^{-1}\left(\begin{bmatrix}\bm{I}&0\\\
0&\bm{\mathcal{O}}_{k}\end{bmatrix}^{-1}\begin{bmatrix}\bm{D}\\\
\bm{\mathcal{O}}_{k}\bm{B}\end{bmatrix}\langle\Delta_{s}\rangle\right.$
$\displaystyle+\left.\begin{bmatrix}\bm{I}&0\\\
0&\bm{\mathcal{O}}_{k}\end{bmatrix}^{-1}\begin{bmatrix}0\\\
\bm{\Gamma}_{k}\end{bmatrix}\langle\Delta_{s}\rangle^{k}\right)$
$\displaystyle=\begin{bmatrix}\bm{C}\\\
\bm{A}\end{bmatrix}^{-1}\left(\begin{bmatrix}\bm{D}\\\
\bm{B}\end{bmatrix}\langle\Delta_{s}\rangle+0\times\bm{\mathcal{O}}_{k}^{-1}(\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k})\right)$
$\displaystyle=f_{s}(f_{s}^{k}(\mathbb{R}^{n}))=f_{s}^{k+1}(\mathbb{R}^{n})$

Where $*$ follows from the subspace identity
$\bm{A}^{-1}(\mathcal{B}+\mathcal{C})=\bm{A}^{-1}\mathcal{B}+\bm{A}^{-1}\mathcal{C}$
when $\mathcal{B}\subseteq\operatorname{im}\bm{A}$ and distributivity of
preimage over unions, and the last step follows from the inductive hypothesis
together with the fact that
$\bm{\mathcal{O}}_{k+1}^{-1}(\bm{\Gamma}_{k+1}\langle\Delta_{s}\rangle^{k+1})\subseteq\bm{\mathcal{O}}_{k}^{-1}(\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k})$.
∎

###### Proposition 1

For every $s$, $\mathcal{V}(s)$ is a finite subspace arrangement. Furthermore,
defining

$\mathcal{V}_{k}(s):=\bm{\mathcal{O}}_{k}^{-1}(\bm{\Gamma}_{k}\langle\Delta_{s}\rangle^{k}),$
(7)

there exists $N$ such that
$\mathcal{V}_{N}(s)=\mathcal{V}_{N+1}(s)=\mathcal{V}(s)$. We define the _weak
$s$-sparse observability index_ $\nu_{s}$ to be the smallest such $N$.

###### Proof:

Suppose that there exists $N$ such that
$f_{s}^{N}(\mathbb{R}^{n})=f_{s}^{N+1}(\mathbb{R}^{n})=f_{s}(f_{s}^{N}(\mathbb{R}^{n}))$,
then $\mathcal{V}^{*}:=f_{s}^{N}(\mathbb{R}^{n})$ is a fixed point of $f_{s}$.
Hence, suppose $\bm{x}\in\mathcal{V}^{*}$, it follows that there exists
$\bm{u}_{0}\in\langle\Delta_{s}\rangle$ such that
$\bm{A}\bm{x}+\bm{B}\bm{u}_{0}\in\mathcal{V}^{*}$ and
$\bm{C}\bm{x}+\bm{D}\bm{u}_{0}=0$, hence we we may construct
$\bm{u}:\mathbb{N}\to\langle\Delta_{s}\rangle$ such that
$\gamma_{\bm{x}}(\bm{u})=0$, so $\bm{x}\in\mathcal{V}(s)$.

Fix $s$, and denote
$\mathcal{V}_{k}:=f_{s}^{k}(\mathbb{R}^{n})=\mathcal{V}_{k}(s)$. Consider
that, if $\mathcal{A},\mathcal{B}$ are subspace arrangments,
$\mathcal{A}\subsetneq\mathcal{B}\implies d(\mathcal{A})\prec d(\mathcal{B})$.
Note that $c(\mathcal{V}_{k+1})\leq c(\mathcal{V}_{k})C(m,s)$, as there are at
most $c(\langle\Delta_{s}\rangle)$ subspaces in $\mathcal{V}_{k+1}$ for every
subspace in $\mathcal{V}_{k}$.

Suppose that for some $k$, there exists $\mathcal{A}$ such that
$\mathcal{V}_{k}\subseteq\mathcal{A}$ and
$\mathcal{V}_{k}\neq\mathcal{V}_{k+1}$. Suppose that
$f_{s}(\mathcal{A})=\mathcal{A}$. We have that
$\mathcal{A}\subseteq\mathbb{R}^{n}$, so
$\mathcal{A}=f_{s}^{k}(\mathcal{A})\subseteq\mathcal{V}_{k}\implies\mathcal{A}=\mathcal{V}_{k}$.
But $\mathcal{V}_{k}\neq\mathcal{V}_{k+1}$, this is a contradiction, hence if
$\mathcal{V}_{k}\neq\mathcal{V}_{k+1}$,
$\mathcal{V}_{k}\subseteq\mathcal{A}\implies
f_{s}(\mathcal{A})\subsetneq\mathcal{A}$, and therefore
$d(f_{s}(\mathcal{A}))\prec d(\mathcal{A})$.

By way of contradiction, suppose there does not exist $N$ such that
$\mathcal{V}_{N}=\mathcal{V}_{N+1}$. Then the sequence $\mathcal{V}_{k}$ is
strictly decreasing by inclusion in $k$, and therefore strictly decreasing in
dimension. By the above, $\mathcal{V}_{k}\subseteq\mathcal{A}\implies
d(f_{s}(\mathcal{A}))\prec d(\mathcal{A})$. We show a contradiction by
induction on $\mu(\mathcal{V}_{k})=\min\\{i:d_{i}(\mathcal{V}_{k})\neq 0\\}$.

Suppose $\exists k,(d_{1},\ldots,d_{n})$ such that $d_{1}\neq 0$ and
$d(\mathcal{V}_{k})\preceq(d_{1},\ldots,d_{n})$. Since
$f_{s}(\mathcal{V}_{k})\prec\mathcal{V}_{k}$,
$d(f_{s}^{d_{1}}(\mathcal{V}_{k}))=d(\mathcal{V}_{k+d_{1}})\preceq(0,d_{2},\ldots,d_{n})$.

Now assume, by induction, that if $\exists k,\bm{d}$ such that
$\bm{d}=(0,\ldots,0,d_{r-1},d_{r},\ldots,d_{n})$ and
$d(\mathcal{V}_{k})\leq\bm{d}$, that $\exists N$ such that
$d(\mathcal{V}_{k+N})\preceq(0,\ldots,0,d_{r},d_{r+1},\ldots,d_{n})$. Suppose
that $\exists k,\bm{d}$ such that $\bm{d}=(0,\ldots,0,d_{r},\ldots,d_{n})$ and
$d(\mathcal{V}_{k})\preceq\bm{d}$. Let $\mathcal{A}$ be such that
$\mathcal{V}_{k}\subseteq\mathcal{A}$, and $d(\mathcal{A})=\bm{d}$. Then since
$c(f(\mathcal{A}))\leq c(\mathcal{A})c(\langle\Delta_{s}\rangle)$,
$d(\mathcal{V}_{k+1})\preceq
d(f(\mathcal{A}))\preceq(0,\ldots,c(\mathcal{A})(c(\langle\Delta_{s}\rangle)-1)+1,d_{r}^{k}-1,\ldots,d_{n}^{k})=\bm{d}^{\prime}$.
Then there exists $k^{\prime}=k+1,\bm{d}^{\prime}$ such that
$d(\mathcal{V}_{k^{\prime}})\preceq\bm{d}^{\prime}$ and
$\bm{d}^{\prime}=(0,\ldots,0,d_{r-1}^{\prime},d_{r}-1,d_{r+1},\ldots,d_{n})$.
So, by the inductive hypothesis, there exists $N$ such that
$d(\mathcal{V}_{k^{\prime}+N})\preceq(0,\ldots,0,d_{r}-1,d_{r+1},\ldots,d_{n})$.
By repeated application of this fact, $\exists N^{\prime}$ such that
$d(\mathcal{V}_{k^{\prime}+N^{\prime}})\preceq(0,\ldots,0,0,d_{r+1},\ldots,d_{n})$.

It follows by induction that as
$d(\mathcal{V}_{0})=d(\mathbb{R}^{n})=(0,\ldots,1)$, there exists $N$ such
that $d(\mathcal{V}_{N})\preceq 0$. But then $\mathcal{V}_{N}=0$, and so
$\mathcal{V}_{N+1}=\mathcal{V}_{N}$, a contradiction.

To see that the resulting subspace arrangement is finite, it suffices to note
that the subspace arrangement is of size at most $\binom{m}{s}^{\nu_{s}}$. ∎

The set of strongly $s$-sparse reachable points likewise is readily
generalized from the linear case:

###### Definition 9

Let $\bm{x}\in\mathbb{R}^{n}$. If there exists
$\bm{u}:\mathbb{N}\to\langle\Delta_{s}\rangle$ and $N$ such that
$\bm{x}=\bm{\mathcal{C}}_{N}[\bm{u}]_{0}^{N}$ and
$\bm{\Gamma}_{N}[\bm{u}]_{0}^{N}=0$, then $\bm{x}$ is said to be _strongly
$s$-sparse reachable_. We denote the set of all such $\bm{x}$ as
$\mathcal{T}(s)$.

We omit the proof for the following, as it follows from essentially the same
argument as for $\mathcal{V}(s)$:

###### Proposition 2

For every $s$, $\mathcal{T}(s)$ is a finite subspace arrangement. Furthermore,
defining

$\mathcal{T}_{k}(s):=\bm{\mathcal{C}}_{k}(\ker\bm{\Gamma}_{k}\cap\langle\Delta_{s}\rangle^{k})$
(8)

there exists $N$ such that
$\mathcal{T}_{N}(s)=\mathcal{T}_{N+1}(s)=\mathcal{T}(s)$. We define the
_strong $s$-sparse reachability index_ $\tau_{s}$ to be the smallest such $N$.

It may be in turn shown that $\mathcal{T}(s)$ is obtained as the fixed point
of an iterated set map, as in (6)

###### Corollary 1

$\mathcal{T}_{k}(s)$ satisfies the recursion

$\mathcal{T}_{k+1}(s)=\begin{bmatrix}\bm{A}&\bm{B}\end{bmatrix}\left((\mathcal{T}_{k}(s)\times\langle\Delta_{s}\rangle)\cap\ker\begin{bmatrix}\bm{C}&\bm{D}\end{bmatrix}\right)$
(9)

Using these subspace arrangements, we may geometrically characterize left
invertibility.

###### Proposition 3

The following are equivalent:

  1. 1.

$\Sigma$ is left $s$-sparse invertible.

  2. 2.

$\mathcal{T}(2s)\cap\mathcal{V}(2s)=0$ and $\forall
S\in\Delta_{2s},\ker\begin{bmatrix}\bm{D}_{S}\\\ \bm{B}_{S}\end{bmatrix}=0.$

  3. 3.

For any $S,T\in\Delta_{s}$, $\ker\bm{D}_{S\cup
T}\cap\bm{B}^{-1}\mathcal{V}(2s)=0$.

###### Proof:

$(1\Rightarrow 2)$ Suppose $\Sigma$ is left $s$-sparse invertible. Toward
contradiction, take $S\in\Delta_{2s}$ such that
$\ker\bm{D}_{S}\cap\ker\bm{B}_{S}\neq 0$, then there exists
$T,T^{\prime}\in\Delta_{s}$ such that $T\cup T^{\prime}=S$ and
$\bm{u}:\mathbb{N}\to\langle T\rangle,\bm{v}:\mathbb{N}\to\langle
T^{\prime}\rangle$ not equal such that $\forall
k\in\mathbb{N},\bm{D}(\bm{u}_{k}-\bm{v}_{k})=0$ and
$\bm{B}(\bm{u}_{k}-\bm{v}_{k})=0$, so necessarily
$\gamma_{0}(\bm{u}-\bm{v})=0\implies\gamma_{0}(\bm{u})=\gamma_{0}(\bm{v})$,
this is a contradiction. Now suppose instead that
$\exists\bm{x}\in\mathcal{T}(2s)\cap\mathcal{V}(2s)$, then there exists
$\bm{u},\bm{v}:\mathbb{N}\to\langle\Delta_{s}\rangle$ and $N\in\mathbb{N}$
such that $\bm{\Gamma}_{N}[\bm{u}-\bm{v}]_{0}^{N}=0$ and
$\bm{\mathcal{C}}_{N}[\bm{u}-\bm{v}]_{0}^{N}=\bm{x}\in\mathcal{V}(2s)$, and
$\bm{\gamma}(\bm{x},\sigma^{N}(\bm{u}-\bm{v}))=0$.

$(2\Rightarrow 3)$ Suppose $\ker\bm{D}_{S\cup
T}\cap\bm{B}^{-1}\mathcal{V}(2s)\neq 0$, then there exists
$\bm{u}_{0}\in\langle S\rangle,\bm{v}_{0}\in\langle T\rangle$ such that
$\bm{D}(\bm{u}_{0}-\bm{v}_{0})=0$ and
$\bm{B}(\bm{u}_{0}-\bm{v}_{0})\in\mathcal{V}(2s)$. But then
$\bm{B}(\bm{u}_{0}-\bm{v}_{0})\in\mathcal{T}_{1}(2s)\cap\mathcal{V}(2s)\subseteq\mathcal{T}(2s)\cap\mathcal{V}(2s)$,
contradicting $(2)$.

$(3\Rightarrow 1)$ Let $\bm{u},\bm{v}:\mathbb{N}\to\langle\Delta_{s}\rangle$,
and suppose $\bm{\gamma}_{0}(\bm{u})=\bm{\gamma}_{0}(\bm{v})$. Then
$\bm{D}(\bm{u}_{0}-\bm{v}_{0})=0$ and
$\bm{\gamma}(\bm{B}\bm{u}_{0},\sigma(\bm{u}))=\bm{\gamma}(\bm{B}\bm{v}_{0},\sigma(\bm{v}))\iff\bm{\gamma}(\bm{B}(\bm{u}_{0}-\bm{v}_{0}),\sigma(\bm{u}-\bm{v}))=0$,
so $\bm{u}_{0}-\bm{v}_{0}\in\bm{B}^{-1}\mathcal{V}(2s)$. So by $(3)$,
$\bm{u}_{0}=\bm{v}_{0}$. Hence we conclude $\Sigma$ is left $s$-sparse
invertible. ∎

###  III-B Rank-Based Characterization

While informative from a geometric perspective, it is not clear how one could
approach the problem of actually building an inverse system from the geometric
characterization. By considering the rank of $\bm{\Gamma}$ when restricted to
piecewise-$2s$-sparse supports, we show that if the system is $s$-sparse
invertible, then it is possible to construct an inverse with a finite delay.

###### Proposition 4

The system $\Sigma$ is $s$-sparse invertible if and only if there exists
$N<\nu_{2s}$ s.t. for any $S=(S_{0},S_{1},\ldots,S_{N})\in\Delta_{2s}^{N+1}$,

$\operatorname{rank}\bm{\Gamma}_{S}-\operatorname{rank}\bm{\Gamma}_{\sigma(S)}=|S_{0}|.$
(10)

In this event, we say $\Sigma$ is $s$-sparse invertible with delay $N$.

###### Proof:

Recall that for $S\in\Delta_{2s}^{N+1}$,
$\sigma(S)=(S_{1},\ldots,S_{N})\in\Delta_{2s}^{N}$.

$(\Rightarrow)$ Note that
$\operatorname{rank}\bm{\Gamma}_{S}=\operatorname{rank}\begin{bmatrix}\bm{D}_{S_{0}}&0\\\
\bm{\mathcal{O}}_{N-1}\bm{B}_{S_{0}}&\bm{\Gamma}_{\sigma(S)}\end{bmatrix}$ is
equal to $|S_{0}|-\dim\begin{bmatrix}\bm{D}_{S_{0}}\\\
\bm{\mathcal{O}}_{N}\bm{B}_{S_{0}}\end{bmatrix}^{-1}(0\times\operatorname{im}\bm{\Gamma}_{\sigma(S)})+\operatorname{rank}\bm{\Gamma}_{\sigma(S)}$,
so this characterization is equivalent to showing that
$\begin{bmatrix}\bm{D}_{S_{0}}\\\
\bm{\mathcal{O}}_{N}\bm{B}_{S_{0}}\end{bmatrix}^{-1}(0\times\operatorname{im}\bm{\Gamma}_{\sigma(S)})=0$.
Suppose that for all $N\in\mathbb{N}$, there exists $S\in\Delta_{2s}^{N+1}$
such that $\begin{bmatrix}\bm{D}_{S_{0}}\\\
\bm{\mathcal{O}}_{N}\bm{B}_{S_{0}}\end{bmatrix}^{\smash{-1}}(0\times\operatorname{im}\bm{\Gamma}_{\sigma(S)})\neq
0$. Then there exists $\bm{u}_{0},\bm{v}_{0}\in\langle\Delta_{s}\rangle$ such
that $\bm{D}(\bm{u}_{0}-\bm{v}_{0})=0$, and
$\bm{B}(\bm{u}_{0}-\bm{v}_{0})\in\bm{\mathcal{O}}_{N}^{-1}(\bm{\Gamma}_{N}\langle\Delta_{2s}\rangle^{N})$.
But then for $N\geq\nu_{2s}$,
$\bm{B}(\ker\bm{D}\cap\langle\Delta_{2s}\rangle)\cap\mathcal{V}(2s)\neq 0$,
contradicting invertibility.

$(\Leftarrow)$ Suppose that there exists $N$ such that for any
$S\in\Delta_{2s}^{N+1}$, the rank condition holds. Then for any
$\bm{u},\bm{u}^{\prime}:\mathbb{N}\to\langle\Delta_{s}\rangle$,
$\bm{\Gamma}_{N+1}[\bm{u}-\bm{u}^{\prime}]_{k}^{N+1}=0\implies\bm{u}_{k}=\bm{u}^{\prime}_{k}$.
Suppose $\forall j<k,\bm{u}_{j}=\bm{u}^{\prime}_{j}$. It follows that
$[\gamma_{0}(\bm{u}-\bm{u}^{\prime})]_{k}^{N+1}=0\implies\bm{\mathcal{O}}_{N+1}(\bm{\mathcal{C}}_{k}[\bm{u}-\bm{u}^{\prime}]_{0}^{k})+\bm{\Gamma}_{N+1}[\bm{u}-\bm{u}^{\prime}]_{k}^{N+1}=\bm{\Gamma}_{N+1}[\bm{u}-\bm{u}^{\prime}]_{k}^{N+1}=0\implies\bm{u}_{k}=\bm{u}_{k}^{\prime}$.
It follows by strong induction on $k$ that
$\gamma_{0}(\bm{u})=\gamma_{0}(\bm{u}^{\prime})\implies\bm{u}=\bm{u}^{\prime}$.
∎

In light of this result, we will define the _inherent $s$-sparse delay_
$d_{s}$ of the system as follows:

$d_{s}:=\min\\{N:\forall
S\in\Delta_{2s}^{N+1},\operatorname{rank}\bm{\Gamma}_{S}-\operatorname{rank}\bm{\Gamma}_{\sigma(S)}=|S_{0}|\\}$

By definition, if $d_{s}$ is finite, $d_{s}<\nu_{2s}$. As is the case with the
inherent delay of linear systems with generic inputs, $d_{s}$ provides a lower
bound on the delay of any $s$-sparse inversion algorithm.

###  III-C Spectral Characterization

The characterization of invertibility based on the Rosenbrock matrix is unique
in its apparent simplicity, relying on no complicated block matrices or
subspaces far removed from basic system parameters. Unfortunately, this
simplicity prevents it from being able to capture the complex properties of
changing input support patterns. To obtain a spectral characterization of left
$s$-sparse invertibility, it is thus necessary to work with a version of the
Rosenbrock matrix generalized to a pattern of $\tau$ supports
$S\in\\{T:T\subseteq[\\![m]\\!]\\}^{\tau}$:

$\bm{R}_{S}(z):=\begin{bmatrix}\bm{A}^{\tau}-z\bm{I}&\bm{\mathcal{C}}_{S}\\\
\bm{\mathcal{O}}_{\tau}&\bm{\Gamma}_{S}\end{bmatrix}.$ (11)

Before addressing the general case, it is worth considering what the
properties of this matrix can tell us about invertibility of the system over
the set of $s$-piecewise sparse inputs with _$\tau$ -periodic_ supports, that
is:

$\mathcal{U}_{\tau}(s):=\\{\bm{u}:\mathbb{N}\to\langle\Delta_{s}\rangle:\exists
S\in\Delta_{s}^{\tau},\bm{u}_{k}\in\langle S_{k\text{ mod }\tau}\rangle\\}.$

###### Lemma 2

If there exists $S\in\Delta_{2s}^{\tau}$ such that
$\begin{bmatrix}\bm{\mathcal{C}}_{S}\\\ \bm{\Gamma}_{S}\end{bmatrix}$ is rank
deficient, then $\Sigma$ is not left $\mathcal{U}_{\tau}(s)$-invertible.

###### Proof:

Suppose that for some $S$, $\begin{bmatrix}\bm{\mathcal{C}}_{S}\\\
\bm{\Gamma}_{S}\end{bmatrix}$ is not full rank. Then there exists
$\bm{u},\bm{u}^{\prime}\in\mathcal{U}_{\tau}(s)$, $\forall
k\geq\tau,\bm{u}_{k}=\bm{u}^{\prime}_{k}=0$, but $\bm{u}\neq\bm{u}^{\prime}$
such that $\bm{\mathcal{C}}_{\tau}[\bm{u}-\bm{u}^{\prime}]_{0}^{\tau}=0$ and
$\bm{\Gamma}_{\tau}[\bm{u}-\bm{u}^{\prime}]_{0}^{\tau}=0$. Then
$[\bm{\gamma}_{0}(\bm{u}-\bm{u}^{\prime})]_{0}^{\tau}=0$, and
$\sigma^{\tau}(\bm{\gamma}_{0}(\bm{u}-\bm{u}^{\prime}))=\bm{\gamma}(\bm{\mathcal{C}}_{\tau}[\bm{u}-\bm{u}^{\prime}]_{0}^{\tau},\sigma^{\tau}(\bm{u}-\bm{u}^{\prime}))=0$,
so $\bm{\gamma}(\bm{u})=\bm{\gamma}(\bm{u}^{\prime})$. Therefore, $\Sigma$ is
not left $\mathcal{U}_{\tau}(s)$-invertible. ∎

###### Proposition 5

$\Sigma$ is left $\mathcal{U}_{\tau}(s)$-invertible if and only if for any
$S\in\Delta_{2s}^{\tau}$, there exists $z\in\mathbb{C}$ such that
$\operatorname{rank}\bm{R}_{S}(z)=n+\sum_{i\in[\\![\tau]\\!]}|S_{i}|$.

###### Proof:

$(\Rightarrow)$ Suppose that there exists $S\in\Delta_{2s}^{\tau}$ such that
for any $z\in\mathbb{C}$, $\bm{R}_{S}(z)$ is rank deficient. Denote the LTI
system
$\Sigma_{S}:=(\bm{A}^{\tau},\bm{\mathcal{C}}_{S},\bm{\mathcal{O}}_{\tau},\bm{\Gamma}_{S})$,
then $\bm{R}_{S}$ is the Rosenbrock matrix of this system. Hence, by theorem
1, $\Sigma_{S}$ is not left invertible, so there exists
$\bm{v},\bm{v}^{\prime}:\mathbb{N}\to\mathbb{R}^{|S|}$ not equal such that
this system’s response $\bm{\gamma}^{(\Sigma_{S})}$ satisfies
$\bm{\gamma}_{0}^{\smash{\smash{{(\Sigma_{S})}}}}(\bm{v}-\bm{v}^{\prime})=0$.
Choose $T,T^{\prime}\subseteq\Delta_{s}^{\tau}$ such that $T\cup
T^{\prime}=S$, and define
$\bm{u},\bm{u}^{\prime}:\mathbb{N}\to\langle\Delta_{s}\rangle$ such that
$\bm{u}_{k}\in\langle T_{k\text{ mod }\tau}\rangle$,
$\bm{u}^{\prime}_{k}\in\langle T^{\prime}_{k\text{ mod }\tau}\rangle$, and
$(\bm{u}_{k}-\bm{u}_{k}^{\prime})_{S_{k\text{ mod
}\tau}}=\bm{v}_{k}-\bm{v}_{k}^{\prime}$, then $\bm{u}\neq\bm{u}^{\prime}$ and
$\gamma_{0}(\bm{u}-\bm{u}^{\prime})=0$. It follows that $\Sigma$ is not left
$\mathcal{U}_{\tau}(s)$-invertible.

($\Leftarrow$) Suppose $\Sigma$ is not left
$\mathcal{U}_{\tau}(s)$-invertible, then there exists
$\bm{u},\bm{u}^{\prime}\in\mathcal{U}_{\tau}(s)$ distinct such that
$\gamma_{0}(\bm{u}-\bm{u}^{\prime})=0$. Denote
$S,S^{\prime}\in\Delta_{s}^{\tau}$ such that $[\bm{u}]_{\tau
k}^{\tau}\in\langle S\rangle,[\bm{u}^{\prime}]_{\tau k}^{\tau}\in\langle
S^{\prime}\rangle$, it follows that there exists
$\bm{w},\bm{w}^{\prime}:\mathbb{N}\to\mathbb{R}^{|S\cup S^{\prime}|}$ not
equal such that, denoting $\bm{\gamma}^{(S\cup S^{\prime})}$ the response of
the system $\Sigma_{S\cup S^{\prime}}:=(\bm{A}^{\tau},\bm{\mathcal{C}}_{S\cup
S^{\prime}},\bm{\mathcal{O}}_{\tau},\bm{\Gamma}_{S\cup S^{\prime}})$,
$\bm{\gamma}^{(S\cup S^{\prime})}_{0}(\bm{w})=\bm{\gamma}^{(S\cup
S^{\prime})}_{0}(\bm{w}^{\prime})$, so $\Sigma_{S\cup S^{\prime}}$ is not
invertible. It follows that for all $z\in\mathbb{C}$, $\bm{R}_{S\cup
S^{\prime}}(z)$ is rank deficient. ∎

In particular, we obtain a necessary and sufficient characterization of
invertibility with respect to inputs with constant support:

###### Corollary 2

$\Sigma$ is left $\mathcal{U}_{1}(s)$-invertible if and only if $\forall
S\in\Delta_{2s}$,

$\operatorname{rank}\begin{bmatrix}\bm{A}-z\bm{I}&\bm{B}_{S}\\\
\bm{C}&\bm{D}_{S}\end{bmatrix}=n+|S|.$ (12)

It is probably clear that, for a system $\Sigma$ to be left $s$-sparse
invertible, it must be left $\mathcal{U}_{\tau}(s)$ invertible for all $\tau$.
However, there is no guarantee that generic $s$-piecewise sparse inputs will
have periodic supports. Our final result shows that we may bound the required
$\tau$ to check, by considering the size of the strongly reachable subspace
arrangement $c(\mathcal{T}(2s))$.

###### Proposition 6

Suppose $\mathcal{T}(2s)=\bigcup_{i\in I}V_{i}$, and let $\bm{\Psi}_{i}$ be a
basis for $V_{i}$. Then $\Sigma$ is left $s$-sparse invertible if and only if
$\forall i\in I,\forall\tau\leq c(\mathcal{T}(2s))$, $\forall
S\in\Delta_{2s}^{\tau},\forall z\in\mathbb{C}$,

$\operatorname{rank}\begin{bmatrix}(\bm{A}^{\tau}-z\bm{I})\bm{\Psi}_{i}&\bm{\mathcal{C}}_{S}\\\
\bm{\mathcal{O}}_{\tau}\bm{\Psi}_{i}&\bm{\Gamma}_{S}\end{bmatrix}=\dim
V_{i}+\sum_{k\in[\\![\tau]\\!]}|S_{k}|.$ (13)

###### Proof:

$(\Rightarrow)$ Suppose there exists $i\in I$, $\tau$,
$S\in\Delta_{s}^{\tau}$, and $z\in\mathbb{C}$ such that the rank condition
fails. Then there exists $\bm{x}\in\mathcal{T}(2s)$ and
$U,V\in\langle\Delta_{s}\rangle^{\tau}$ such that
$\bm{A}^{\tau}\bm{x}+\bm{\mathcal{C}}_{\tau}(U-V)=z\bm{x}$ and
$\bm{\mathcal{O}}_{\tau}\bm{x}+\bm{\Gamma}_{\tau}(U-V)=0$. Let
$\bm{u},\bm{v}:\mathbb{N}\to\langle\Delta_{s}\rangle$ be defined such that for
some $M$,
$\bm{x}=\bm{\mathcal{C}}_{M}[\bm{u}-\bm{v}]_{0}^{M},\bm{\Gamma}_{M}[\bm{u}-\bm{v}]_{0}^{M}=0$,
this is possible as $\bm{x}\in\mathcal{T}(2s)$. Further, $\forall
k\in\mathbb{N}$ we have that $[\sigma^{M}(\bm{u})]_{k\tau}^{\tau}=z^{k}U$ and
$[\sigma^{M}(\bm{v})]_{k\tau}^{\tau}=z^{k}V$, it follows that
$\bm{\gamma}_{0}(\bm{u})=\bm{\gamma}_{0}(\bm{v})$, hence the system is not
invertible.

$(\Leftarrow)$ Suppose that $\Sigma$ is not left $s$-sparse invertible. If
there exists $\tau$ and $S\in\Delta_{2s}^{\tau}$ such that
$\begin{bmatrix}\bm{\mathcal{C}}_{S}\\\ \bm{\Gamma}_{S}\end{bmatrix}$ is rank
deficient, then we have the claim. So in light of proposition 3, assume
instead that $\mathcal{T}(2s)\cap\mathcal{V}(2s)\neq 0$. Let
$\bm{x}_{0}\in\mathcal{T}(2s)\cap\mathcal{V}(2s)$, there exists an input
$\bm{u}:\mathbb{N}\to\langle\Delta_{2s}\rangle$ such that $\forall
k\in\mathbb{N},\bm{x}_{k}:=\bm{A}^{k}\bm{x}_{0}+\bm{\mathcal{C}}_{k}[\bm{u}]_{0}^{k}\in\mathcal{T}(2s)\cap\mathcal{V}(2s)\subseteq\mathcal{T}(2s)$.
Since $\mathcal{T}(2s)$ is a finite subspace arrangement, there exists a
subspace $V\subseteq\mathcal{T}(2s)$ which occurs twice in this trajectory
within $c(\mathcal{T}(2s))$ time steps. Therefore, denoting
$\bm{x}_{k_{0}},\bm{x}_{k_{1}}\in V$ the points where this trajectory passes
through $V$ and $\tau=k_{1}-k_{0}$, there exists $S\in\Delta_{2s}^{\tau}$ and
$U$ such that
$\bm{A}^{\tau}\bm{x}_{k_{0}}+\bm{\mathcal{C}}_{S}U=\bm{x}_{k_{1}}$ and
$\bm{\mathcal{O}}_{\tau}\bm{x}_{k_{0}}+\bm{\Gamma}_{S}U=0$. It may then be
shown based on the subspace-preserving property of the iteration (9) that
there exists a linear map $\bm{F}:V\to\langle S\rangle$ such that
$(\bm{A}^{\tau}+\bm{\mathcal{C}}_{\tau}\bm{F})V\subseteq V$ and
$(\bm{\mathcal{O}}_{\tau}+\bm{\Gamma}_{\tau}\bm{F})V=0$. As it is therefore an
invariant subspace, $V$ contains an eigenvector $\bm{v}$ of
$\bm{A}^{\tau}+\bm{\mathcal{C}}_{\tau}\bm{F}$. Denote $\bm{\Psi}_{i}$ a basis
for $V$, and $\bm{v}=\bm{\Psi}_{i}\bm{x}$ and
$\tilde{U}=\bm{F}\bm{v}\in\langle S\rangle$, we have that there exists
$z\in\mathbb{C}$ satisfying

$\bm{A}^{\tau}\bm{\Psi}_{i}\bm{x}+\bm{\mathcal{C}}_{\tau}\tilde{U}=z\bm{\Psi}_{i}\bm{x},\quad\bm{\mathcal{O}}_{\tau}\bm{\Psi}_{i}\bm{x}+\bm{\Gamma}_{\tau}\tilde{U}=0$

We then conclude
$\begin{bmatrix}(\bm{A}^{\tau}-z\bm{I})\bm{\Psi}_{i}&\bm{\mathcal{C}}_{S}\\\
\bm{\mathcal{O}}_{\tau}\bm{\Psi}_{i}&\bm{\Gamma}_{S}\end{bmatrix}$ is not full
rank. ∎

This result may be alternatively characterized without detailed knowledge of
$\mathcal{T}(2s)$, using only its size and the strong $2s$-sparse reachability
index:

###### Corollary 3

$\Sigma$ is left $s$-sparse invertible if and only if $\forall
N\leq\tau_{2s}+c(\mathcal{T}(2s)),\forall M<N$, $\forall S\in\Delta_{2s}^{N}$,
$\forall z\in\mathbb{C}$,

$\operatorname{rank}\begin{bmatrix}\bm{\Gamma}_{S}\\\
\bm{\mathcal{C}}_{S}-z\begin{bmatrix}\bm{\mathcal{C}}_{[S]_{0}^{M}}&0\end{bmatrix}\end{bmatrix}=\sum_{i\in[\\![N]\\!]}|S_{i}|.$
(14)

##  IV Example: Network with Edge Attacks

Figure 1: The system $\Sigma_{\alpha}$ depicted as a network. Solid black
arrows indicate a weight of $+1$, dashed indicates $-1$. Red vertices are
inputs, and others are states. Blue indicates the vertex state is included in
the measurement $\bm{C}_{\alpha}\bm{x}$, and green indicates inclusion when
$\alpha=1$.

In this section, we demonstrate our results on two linear systems, one which
is left $1$-sparse invertible and one which is not, illustrating the three
primary characterizations of left $s$-sparse invertibility introduced in
section III, as well as an instance of a nontrivial weakly unobservable
subspace arrangement $\mathcal{V}(1)$.

Consider the following system
$\Sigma_{\alpha}=(\bm{A},\bm{B},\bm{C}_{\alpha},\bm{D})$, where
$\alpha\in\\{0,1\\}$, depicted as a network in figure 1:

$\left[\begin{array}[]{c|c}\bm{A}&\bm{B}\\\
\hline\cr\bm{C}_{\alpha}&\bm{D}\end{array}\right]=\left[\begin{array}[]{cccc|cccc}0&0&0&1&-1&0&0&1\\\
1&0&0&0&1&-1&0&0\\\ 0&1&0&0&0&1&-1&0\\\ 0&0&1&0&0&0&1&-1\\\ \hline\cr
1&0&0&0&0&0&0&0\\\ 0&\alpha&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\end{array}\right].$

The dynamics simply permute the state of four nodes, and $\bm{C}_{\alpha}$
measures the state of nodes $1$ and $3$, and $2$ if $\alpha=1$. The inputs may
be thought of as edge attacks which could “interfere” with the transmission of
information from a given node to the next, by changing the apparent amount of
information transmitted. Since $3=p<m=4$ in this example, the system is not
classically left invertible, but here we will suppose that inputs are
$1$-sparse. We will demonstrate that the system is not left $1$-sparse
invertible with $\alpha=0$ but is left $1$-sparse invertible when $\alpha=1$,
using propositions 3, 4, and 6.

###  IV-A $\alpha=0$, Geometric Characterization

Consider the state $\bm{x}_{k}=\bm{e}_{4}\in\ker\bm{C}_{0}$. By choosing
$\bm{u}_{k}=-\bm{e}_{4}$,
$\bm{x}_{k+1}=\bm{A}\bm{x}_{k}+\bm{B}\bm{u}_{k}=\bm{e}_{1}+\bm{e}_{4}-\bm{e}_{1}=\bm{e}_{4}$.
Hence, for all $s\geq 1$, $\langle 4\rangle\subseteq\mathcal{V}(s)$. Likewise,
$\bm{x}_{k}=\bm{e}_{2}$ implies $\bm{x}_{k}\in\ker\bm{C}_{0}$, and a choice of
$\bm{u}_{k}=-\bm{e}_{2}$ results in $\bm{x}_{k+1}\in\bm{C}_{0}$. So $\langle
2\rangle\subseteq\mathcal{V}(s)$. However, suppose $\bm{x}_{k}\in\langle
2,4\rangle\setminus(\langle 2\rangle\cup\langle 4\rangle)$, then no 1-sparse
input can result in $\bm{x}_{k+1}\in\ker\bm{C}_{0}$, but there does exist a
2-sparse input satisfying this requirement. It follows that
$\mathcal{V}(1)=\langle 2\rangle\cup\langle 4\rangle$ and
$\mathcal{V}(2)=\langle 2,4\rangle$.

Observe that $\ker\bm{\Gamma}_{1}=\ker\bm{D}=\mathbb{R}^{m}$, so
$\bm{B}\langle\Delta_{2}\rangle\subseteq\mathcal{T}(2)$. In particular, it
contains $\bm{B}(\bm{e}_{1}+\bm{e}_{4})=\bm{e}_{2}-\bm{e}_{4}$, which is also
contained in $\mathcal{V}(2)$. Therefore, by proposition 3, $\Sigma_{0}$ is
not $1$-sparse invertible.

###  IV-B $\alpha=1$, Rank-Based Characterization

Consider that the matrix

$\displaystyle\bm{C}_{1}\bm{B}=\begin{bmatrix}-1&0&0&1\\\ 1&-1&0&0\\\
0&1&-1&0\end{bmatrix}$ (15)

satisfies $\operatorname{rank}\bm{C}_{1}\bm{B}_{S_{0}}=|S_{0}|$ for any
$S_{0}\in\Delta_{2}$. Since $\bm{D}=0$, for any other $S_{1}\in\Delta_{2}$,
$\operatorname{rank}\bm{\Gamma}_{(S_{0},S_{1})}-\bm{\Gamma}_{S_{1}}=\operatorname{rank}\bm{C}_{1}\bm{B}_{S_{0}}=|S_{0}|$,
so by proposition 4, $\Sigma_{1}$ is left $1$-sparse invertible with delay 1.

###  IV-C $\alpha=0$, Spectral Characterization

Consider the strongly $2s$-sparse reachable point
$\bm{x}_{0}=\bm{e}_{2}-\bm{e}_{4}$. The input
$\bm{u}_{0}=\bm{e}_{3}-\bm{e}_{1}$ results in
$\bm{x}_{1}=\bm{A}\bm{x}_{0}+\bm{B}\bm{u}_{0}=\bm{e}_{4}-\bm{e}_{2}$. Let
$\bm{\Psi}_{i}$ denote a basis for the subspace of $\mathcal{T}(2s)$ to which
$\bm{x}_{0}$ belongs, we may write $\bm{x}_{0}=\bm{\Psi}_{i}\bm{v}_{0}$.
Setting $z=-1$, we have that

$\begin{bmatrix}\bm{A}\bm{\Psi}_{i}&\bm{B}\\\
\bm{C}\bm{\Psi}_{i}&\bm{D}\end{bmatrix}\begin{bmatrix}\bm{v}_{0}\\\
\bm{u}_{0}\end{bmatrix}=\begin{bmatrix}z\bm{\Psi}_{i}\bm{v}_{0}\\\
0\end{bmatrix}.$ (16)

By proposition 6, we may conclude that $\Sigma_{0}$ is not left $1$-sparse
invertible.

##  V Discussion

As a collection of necessary and sufficient conditions for the well-posedness
of sparse recovery problems, this work deals with conditions that are by their
nature computationally hard [23]. However, they provide a natural scaffolding
to deal with sparse inversion problems, and in particular for structured and
networked systems, where the inherent delay of a system can be generically
nontrivial [22]. We expect that, as in the case of the classical $\ell_{1}$
relaxation for sparse recovery, optimal and computationally tractable
implementations will arise as relaxations of appropriate combinatorial
problems in this setting. The following are interesting future directions and
applications of our results:

###  V-A Bounding constants associated with $\mathcal{T}(s),\mathcal{V}(s)$

The difficulty of verifying the conditions in this work is determined by the
size of $\mathcal{V}(s),\mathcal{T}(s)$ and their indices $\nu_{s},\tau_{s}$.
We expect that the magnitude of $\nu_{s}$ implied by the proof of proposition
1 is a dramatic overshoot in most cases, and future work should seek to
establish general bounds.

###  V-B Connections to Inversion of Switched Systems

One may formally identify linear systems with sparse inputs with a class of
switched systems: consider the support $S:\mathbb{N}\to\Delta_{s}$ to be an
unknown switching signal determining the time varying system
$\Sigma_{S}(k)=(\bm{A},\bm{B}_{S_{k}},\bm{C},\bm{D}_{S_{k}})$. We expect that
our results on invertibility may therefore be generalized to a class of
switched systems, where switching is restricted to the $\bm{B}$ and $\bm{D}$
matrices.

###  V-C Generalization to Inputs taking values in Subspace Arrangements

All of our results use properties of sparsity which are also features of
subspace arrangements generally. We therefore expect immediate generalization
to the setting where $\bm{u}:\mathbb{N}\to\mathcal{U}\subseteq\mathbb{R}^{m}$,
and $\mathcal{U}=\bigcup_{i\in I}U_{i}$ is a finite subspace arrangement. In
the case that $\mathcal{U}$ is a subspace arrangement that is not finite–for
example, $\mathcal{U}$ taken to be the set of rank 1 matrices–generalization
is less clear, and is an interesting direction for future work. Such results
could

###  V-D Strong Observability and Unknown Input Observers

Strong observability, the ability to recover the initial state in finite time
in the presence of unknown inputs, may be geometrically characterized for
linear systems as having a trivial weakly unobservable subspace. Analogously,
$\mathcal{V}(2s)=0$ is necessary and sufficient for initial state recovery in
the presence of unknown $s$-sparse inputs. Exploring a characterization of
strong detectability, known to be a necessary and sufficient condition for the
existence of an unknown input observer for linear systems, is a direction of
interest in the sparse case.

###  V-E Right Invertibility

Right invertibility is formally the ability to construct an input and initial
condition which produces any desired output. Due to space constraints, we have
restricted our exposition in this work to focus on left invertibility;
however, we expect similar arguments to lead to characterizations of right
invertibility in the sparse input setting.

##  VI Conclusions

In this work, we have established the first necessary and sufficient
conditions for the left invertibility of linear systems with sparse inputs.
Leveraging properties of the novel weakly unobservable and strongly reachable
subspace arrangements, these characterizations echo the fundamental
characterizations of invertibility for standard linear systems. We expect that
these characterizations will lead to the generalization of a variety of
techniques for inversion of linear systems, and enable a systematic approach
to related problems in sparse control.

## References

  * [1] M. Sain and J. Massey, “Invertibility of linear time-invariant dynamical systems,” _IEEE Transactions on automatic control_ , vol. 14, no. 2, pp. 141–149, 1969.
  * [2] R. M. Hirschorn, “Invertibility of nonlinear control systems,” _SIAM Journal on Control and Optimization_ , vol. 17, no. 2, pp. 289–297, 1979.
  * [3] B. Liu and J. Si, “Fault detection and isolation for linear time-invariant systems,” in _Proceedings of 1994 33rd IEEE Conference on Decision and Control_ , vol. 3, 1994, pp. 3048–3053 vol.3.
  * [4] A. Edelmayer, J. Bokor, Z. Szabó, and F. Szigeti, “Input reconstruction by means of system inversion: A geometric approach to fault detection and isolation in nonlinear systems,” _International Journal of Applied Mathematics and Computer Science_ , vol. 14, no. 2, pp. 189–199, 2004.
  * [5] M. Hou and R. J. Patton, “Input observability and input reconstruction,” _Automatica_ , vol. 34, no. 6, pp. 789–794, 1998.
  * [6] A. Martinelli, “Nonlinear unknown input observability: Extension of the observability rank condition,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 1, pp. 222–237, 2019.
  * [7] P. Sannuti and A. Saberi, “Special coordinate basis for multivariable linear systems—finite and infinite zero structure, squaring down and decoupling,” _International Journal of Control_ , vol. 45, no. 5, pp. 1655–1704, 1987.
  * [8] M. Tranninger, H. Niederwieser, R. Seeber, and M. Horn, “Unknown input observer design for linear time-invariant systems—a unifying framework,” _International Journal of Robust and Nonlinear Control_ , vol. 33, no. 15, pp. 8911–8934, 2023.
  * [9] A. Ansari and D. S. Bernstein, “Deadbeat unknown-input state estimation and input reconstruction for linear discrete-time systems,” _Automatica_ , vol. 103, pp. 11–19, 2019.
  * [10] H. L. Trentelman, A. A. Stoorvogel, M. Hautus, and L. Dewell, “Control theory for linear systems,” _Appl. Mech. Rev._ , vol. 55, no. 5, pp. B87–B87, 2002.
  * [11] P. Moylan, “Stable inversion of linear systems,” _IEEE Transactions on Automatic Control_ , vol. 22, no. 1, pp. 74–78, 1977.
  * [12] S. Sefati, N. J. Cowan, and R. Vidal, “Linear systems with sparse inputs: Observability and input recovery,” in _IEEE American Control Conference (ACC)_ , 2015, pp. 5251–5257.
  * [13] K. Poe, E. Mallada, and R. Vidal, “Necessary and sufficient conditions for simultaneous state and input recovery of linear systems with sparse inputs by $\ell_{1}$-minimization,” in _IEEE Conference on Decision and Control (CDC)_ , 2023, pp. 6499–6506.
  * [14] R. K. Chakraborty, G. Joseph, and C. R. Murthy, “Joint state and input estimation for linear dynamical systems with sparse control,” _arXiv preprint arXiv:2312.02082_ , 2023.
  * [15] C. Sriram, G. Joseph, and C. R. Murthy, “Control of linear dynamical systems using sparse inputs,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 5765–5769.
  * [16] A. J. Florez and L. F. Giraldo, “Structural sparsity in networked control systems,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 50, no. 12, pp. 5152–5161, 2020.
  * [17] M. Zhang, B. Alenezi, S. Hui, and S. H. Żak, “State estimation of networked control systems corrupted by unknown input and output sparse errors,” in _American Control Conference (ACC)_ , 2020, pp. 4393–4398.
  * [18] A. S. Charles, A. Balavoine, and C. J. Rozell, “Dynamic filtering of time-varying sparse signals via $\ell_{1}$ minimization,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 21, pp. 5644–5656, 2016.
  * [19] N. P. Bertrand, A. S. Charles, J. Lee, P. B. Dunn, and C. J. Rozell, “Efficient tracking of sparse signals via an earth mover’s distance dynamics regularizer,” _IEEE Signal Processing Letters_ , vol. 27, pp. 1120–1124, 2020.
  * [20] G. Joseph, C. R. Murthy, R. Prasad, and B. D. Rao, “Online recovery of temporally correlated sparse signals using multiple measurement vectors,” in _IEEE Global Communications Conference (GLOBECOM)_ , 2015, pp. 1–6.
  * [21] G. Joseph and C. R. Murthy, “A noniterative online bayesian algorithm for the recovery of temporally correlated sparse vectors,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 20, pp. 5510–5525, 2017.
  * [22] F. Garin, “Generic delay-l left invertibility of structured systems,” _IFAC-PapersOnLine_ , vol. 55, no. 13, pp. 210–215, 2022.
  * [23] S. T. McCormick, _A combinatorial approach to some sparse matrix problems_. Stanford University Stanford, CA, 1983, vol. 83.