# Minimal covariance realization and system identification algorithm for a
class of stochastic linear switched systems with i.i.d. switching

Elie Rouphael, Manas Mejari, Mihaly Petreczky, Lotfi Belkoura E. Rouphael, M.
Petreczky and L. Belkoura are with Univ. Lille, CNRS, Centrale Lille, UMR 9189
CRIStAL, F-59000 Lille, France<EMAIL_ADDRESS>Mejari is with
Swiss AI lab IDSIA-SUPSI, Lugano, Switzerland<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider stochastic realization theory of Linear Switched
Systems (LSS) with i.i.d. switching. We characterize minimality of stochastic
LSSs and show existence and uniqueness (up to isomorphism) of minimal LSSs in
innovation form. We present a realization algorithm to compute a minimal LSS
in innovation form from output and input covariances. Finally, based on this
realization algorithm, by replacing true covariances with empirical ones, we
propose a statistically consistent system identification algorithm.

##  I Introduction

In this paper we consider the stochastic realization problem for _stochastic
linear switched systems (abbreviated as LSS)_ , i.e. for state-space
representations:

$\mathcal{S}\left\\{\begin{aligned}
&\mathbf{x}(t+1)=A_{\bm{\theta}(t)}\mathbf{x}(t)+B_{\bm{\theta}(t)}\mathbf{u}(t)+K_{\bm{\theta}(t)}\mathbf{v}(t)\\\
&\textbf{y}(t)=C\mathbf{x}(t)+D\mathbf{u}(t)+F\mathbf{v}(t)\end{aligned}\right.$
(1)

where $A_{\sigma}\\!\\!\in\\!\\!\mathbb{R}^{n_{x}\times
n_{x}},B_{\sigma}\\!\in\\!\mathbb{R}^{n_{x}\times
n_{u}},K_{\sigma}\\!\in\\!\mathbb{R}^{n_{x}\times n_{n}}$,
$\sigma\\!\in\\!\Sigma=\\{1,\ldots,n_{\mu}\\}$,
$C\\!\in\\!\mathbb{R}^{n_{y}\times n_{x}}$, $F\\!\in\\!\mathbb{R}^{n_{y}\times
n_{n}}$, $D\\!\in\\!\mathbb{R}^{n_{y}\times n_{u}}$ and $\mathbf{x}$,
$\mathbf{v}$, u, y, $\bm{\theta}$ are the stochastic state, noise, input,
output and switching processes. The process $\bm{\theta}$ takes values in the
set of discrete states $\Sigma$. We call $\mathcal{S}$ from (1) a
_realization_ of the tuple $(\tilde{\textbf{y}},\textbf{u},\bm{\theta})$, if
$\tilde{\textbf{y}}=\textbf{y}$. We call $n_{x}$ the _dimension_ of
$\mathcal{S}$.

LSSs of the form (1) contain LTI systems as a special case, when $n_{\mu}=1$.
Moreover, they correspond to _jump-Markov linear systems_ if $\bm{\theta}$ is
a Markov process [7]. Both switched and jump-Markov systems have a rich
literature and a wide variety of applications, e.g., [31, 7]. We refer to (1)
as switched rather than jump-Markov systems, because in contrast to the
latter, in the formulation of the system identification problem, we treat the
switching process as an external input, whose role is similar to that of u. In
contrast to the standard definition [7, 31] for the sake of simplicity, we
assume that the matrices of the output equation do not depend on the current
discrete mode.

Motivation and context: In order to motivate the contribution of the paper, we
firs define the system identification problem of LSSs. To this end, let us
define the _deterministic behavior_ $\mathcal{B}$ of a tuple
$S=(\\{A_{i},B_{i},K_{i}\\}_{i=1}^{n_{\mu}},C,D,F)$ of matrices as the set of
all deterministic signals $(y,u,q)$, all defined on $\mathbb{Z}$, taking
values in $\mathbb{R}^{n_{y}},\mathbb{R}^{n_{u}},\Sigma$ such that there
exists state a trajectory $x$ and noise realization $v$ satisfying:

$\displaystyle x(t+1)=A_{q(t)}x(t)+B_{q(t)}u(t)+K_{q(t)}v(t)$ (2)
$\displaystyle y(t)=Cx(t)+Du(t)+Fv(t)$

That is, $\mathcal{S}$ can be viewed as a stochastic version of (2), in
particular, all samples paths of $(\textbf{y},\textbf{u},\bm{\theta})$ are
elements of the deterministic behavior of $S$.

Assume that $\mathcal{S}$ from (1), referred to as the true system, is a
realization of $(\textbf{y},\textbf{u},\bm{\theta})$, and we observe a finite
portion $\\{(y(t),u(t),q(t))\\}_{t=0}^{N}$ of a sample path of
$(\textbf{y},\textbf{u},\bm{\theta})$. The _identification_ task is to find
matrices
$\hat{S}=(\\{\hat{A}_{i},\hat{B}_{i},\hat{K}_{i}\\}_{i=1}^{n_{\mu}},\hat{C},\hat{D},\hat{F})$
from $\\{(y(t),u(t),q(t))\\}_{t=0}^{N}$ such that in the limit, as
$N\rightarrow\infty$, the deterministic behavior of $\hat{S}$ equals
(approximates) the deterministic behavior of the true systems. The motivation
for this problem formulation is that in many control problems, the switching
signal is viewed either as a control input or as an arbitrary external
input/disturbance. That is, the output of the estimated model should be close
to the that of the true one for switching and inputs different from
$\bm{\theta}$ and u. For jump-Markov systems, this can be relaxed by requiring
that the estimated model has the same output response as the true one for
arbitrary inputs but for the fixed switching process $\bm{\theta}$. In
particular, we think of the stochasticity of the observed signals as a
persistency of excitation assumption, not an assumption on the desired model.

One way to make the problem above well-posed is to ensure that both the
estimated and true systems belong to a class of LSSs with the following
property: if two elements of this class generate the same output for some
stochastic input, switching and noise process, then their matrices differ only
by a change of basis, i.e., they are isomorphic. Then if the output response
of the estimated system is approximately the same as that of the true one for
the designated processes u and $\bm{\theta}$, then the it is isomorphic to the
true one, and hence the two systems have the same deterministic behavior.

For LTI systems, minimal systems in innovation form [17] represent such a
class, as any two minimal LTI systems in innovation form realizing the same
output are isomorphic. Moreover, under suitable conditions, any stochastic LTI
system can be transformed into a minimal one in innovation form while
preserving its output [17]. Hence, it is reasonable to assume that the true
system is of this class. In addition,are also several algorithms which return
minimal systems in innovation form, e.g., subspace identification methods [33,
15] and some parametric methods [18]. For the latter, the use of minimal
systems in innovation form also justifies viewing LTI systems as optimal
predictors of the current output based on past outputs and inputs. The
uniqueness (up to isomorphism) of minimal systems in innovation form is also
used for proving consistency of parametric [13, 14] and subspace methods [17,
5]. In fact, the covariance realization algorithm for LTI systems in
innovation form [17] is the basis for subspace identification algorithms.

Contribution: We extend the concept of minimal (dimensional) systems in
innovation form to a subclass LSSs and apply it to system identification. We
assume that both $\bm{\theta}$ and u are i.i.d. processes. These assumptions
represent the simplest case of persistently exciting data, and there is little
hope to tackle the more general case without solving this one first.

We present a necessary and sufficient condition for minimality LSS realization
of $(\textbf{y},\textbf{u},\bm{\theta})$ in innovation form, and we show that
all such realizations of an output are isomorphic. In addition, we present a
realization algorithm for computing such LSSs from covariances of inputs and
outputs.

Finally, we present a statistically consistent system identification algorithm
which is based on the latter realization algorithm, and which returns, in the
limit, a minimal LSS in innovation form. In particular, if the true system is
a minimal LSS in innovation form, then in the limit this identification
algorithm returns a LSS which is isomorphic to the true LSS, hence, it has the
same deterministic behavior. We further improve this identification algorithm
by combining it with Gradient-Based (GB) methods [9].

Related work: Realization theory of deterministic switched systems was studied
in [23], for stochastic switched systems with no inputs in [25, 26, 29]. To
the best of our knowledge, our results on realization theory of stochastic LSS
with inputs are completely new.

Identification of switched and jump-Markov systems is an active research area,
see the [16, 12, 3, 6, 1, 2], and the references therein. However, most of the
literature assumes that the switching signal is unobserved, which makes the
problem more challenging but also leads to lack of consistency results for
state-space representations. A consistent subspace identification algorithms
was presented in [22] for noiseless LSSs. In [30] a consistent identification
algorithm for noisy LSSs was presented, but the noise gain matrix and the
noise covariance were not estimated, and the identification was based on
several i.i.d. time series.

LSSs can be viewed as a subclass of linear-parameter varying (LPV) systems, if
the switching signal viewed as a discrete scheduling. There is a wealth of
literature on system identification for LPV systems, including subspace
methods, [32, 10, 20, 36, 35] and the references therein. Stochastic
realization theory of LPV systems was invetsigated in [20, 8]. In [8] the
existence of LPV systems in innovation form was investigated, but the noise
gain matrices of the obtained system depended on the current and past
scheduling. Moreover, [8] did not address minimality and uniqueness of systems
in innovation form. Unlike the identification algorithm of this paper, the
existing subspace methods, see the overview [10], are not proven to be
consistent or to return a minimal system in innovation form.

A statistically consistent identification algorithm was presented in [19] for
noisy LPV systems with no inputs, and in [20] for noisy LPV systems with
inputs. This paper is an extension of [20], the main difference w.r.t. [20] is
as follows: (1) the conditions on the scheduling signals from [20] do not
directly apply for i.i.d. switching signals (see Remark 1); (2) we
characterize minimality and uniqueness (up to isomorphism) of systems in
innovation form; (3) the proposed identification algorithm returns a minimal
system in innovation form, while the one of [20] returns a non-minimal one;
that is, the system returned by the algorithm from [20] need not have the
deterministic behavior as the true system; (4) we present novel modifications
to improve the empirical behavior of the identification algorithm.

To sum up, the identification algorithm of this paper is the first algorithm
for noisy LSSs that has all of the following properties: (a) it estimates the
noise gain and the noise covariance, (b) returns a minimal LSSs in innovation
form, and (c) applies to one single long time series.

This paper uses technical results from [28] on the decomposition of outputs of
LSSs into stochastic and deterministic components. The latter is used in [28]
to show existence of a realization in innovation form and to provide
_sufficient_ conditions for minimality and uniqueness of LSSs in innovation
form. In contrast, we formulate _necessary and sufficient_ conditions for
minimality, and we show isomorpĥism of a much wider class of LSSs in
innovation forms, see Remark 3 for a detailed explanation of the gap between
the two results. Moreover, in contrast to this paper, [28] proposes no
realization or identification algorithm.

##  II Technical preliminaries

In this section we recall some concepts from [26] which we use to define a
suitable subclass of LSSs.
Probability theory: We use the usual notation and terminology of probability
theory [4]. All the random variables and stochastic processes are understood
w.r.t. to a probability space $\left(\Omega,\mathcal{F},\mathcal{P}\right)$.
We use $E$ for expected values. All the stochastic processes in this paper are
discrete-time ones defined over the time-axis $\mathbb{Z}$ of the set of
integers. We use bold letters for random variables and stochastic processes.
Switching process: The process $\bm{\theta}$ is independent, identically
distributed taking values in $\Sigma=\\{1,\ldots,n_{\mu}\\}$, and

$p_{\sigma}=\mathcal{P}(\bm{\theta}(t)=\sigma),\quad\sigma\in\Sigma.$ (3)

Sequences of discrete modes: A _non empty word_ over $\Sigma$ is a finite
sequence of letters, i.e., $w=\sigma_{1}\sigma_{2}\cdots\sigma_{k}$, where
$0<k\in\mathbb{Z}$, $\sigma_{1},\sigma_{2},\ldots,\sigma_{k}\in\Sigma$. The
set of _all_ nonempty words is denoted by $\Sigma^{+}$. We denote an _empty
word_ by $\epsilon$. Let $\Sigma^{*}=\epsilon\cup\Sigma^{+}$. We define the
concatenation of words in the standard manner. The length of the word
$w\in\Sigma^{*}$ is denoted by $|w|$, and $|\epsilon|=0$.
Matrices and matrix products: Denote by $I_{n}$ $n\times n$ identity matrix.
Consider $n\times n$ square matrices $\\{A_{\sigma}\\}_{\sigma\in\Sigma}$. For
the empty word $\epsilon$, let $A_{\epsilon}=I_{n}$. for any word
$w=\sigma_{1}\sigma_{2}\cdots\sigma_{k}\in\Sigma^{+}$, $k\\!>\\!0$ and
$\sigma_{1},\ldots,\sigma_{k}\in\Sigma$, we define

$A_{w}=A_{\sigma_{k}}A_{\sigma_{k-1}}\cdots A_{\sigma_{1}}.$ (4)

ZMWSII processes: Next, we recall the concept of zero-mean wide-sense
stationary (ZMWSII) process w.r.t. $\bm{\theta}$ from [26]. To this end, we
introduce the following indicator process
$\bm{\mu}(t)=\begin{bmatrix}\bm{\mu}_{1}(t),&\ldots,&\bm{\mu}_{n_{\mu}}(t)\end{bmatrix}^{T}$
where

$\bm{\mu}_{\sigma}(t)=\chi(\bm{\theta}(t)=\sigma)=\left\\{\begin{array}[]{ll}1&\mbox{
if }\bm{\theta}(t)=\sigma\\\ 0&\mbox{ otherwise}\end{array}\right.$ (5)

where $\chi$ is the indicator function. The process $\bm{\mu}$ is admissible
in the terminology of [26].

######  Remark 1 (Relationship with [20])

If we view $\bm{\mu}$ as a scheduling signal, then it does not satisfy the
assumptions of [20]: while it is an i.i.d. process , it is not zero mean,
$\bm{\mu}_{i}(t),\bm{\mu}_{j}(t)$ are not uncorrelated for $i,j\in\Sigma$, and
$\bm{\mu}_{1}(t)\neq 1$. By applying a suitable normalizing affine
transformation to $\bm{\mu}$ we can bring it to a form which satisfies [20];
for example, for $n_{\mu}=2$, we can take
$\tilde{\bm{\mu}}(t)=(\bm{\mu}_{1}(t)+\bm{\mu}_{2}(t),\bm{\mu}_{2}(t)-p_{2})^{T}=(1,\bm{\mu}_{2}(t)-p_{2})^{T}$.
The system matrices of the thus arising LPV system are affine combinations of
the system matrices of original LSS. However, this transformation does not
appear to simplify the derivation of the results. To the contrary, it would
require handling the affine transformation between system matrices when
analyzing minimality.

Next, we need the following products of components of $\bm{\mu}$. For every
word $w\in\Sigma^{+}$ where $w=\sigma_{1}\sigma_{2}\cdots\sigma_{k}$, $k\geq
1$, $\sigma_{1},\ldots,\sigma_{k}\in\Sigma$, we define the process
$\bm{\mu}_{w}$ as follows:

$\bm{\mu}_{w}(t)=\bm{\mu}_{\sigma_{1}}(t-k+1)\bm{\mu}_{\sigma_{2}}(t-k+2)\cdots\bm{\mu}_{\sigma_{k}}(t)$
(6)

For an empty word $w=\epsilon$, we set $\bm{\mu}_{\epsilon}(t)=1$. For the
constants $\\{p_{\sigma}\\}_{\sigma\in\Sigma}$ from (3) define the products

$\displaystyle p_{w}$ $\displaystyle=p_{\sigma_{1}}p_{\sigma_{2}}\cdots
p_{\sigma_{k}}$ (7)

for any $w\in\Sigma^{+}$, $\sigma_{i}\in\Sigma$. For an empty word
$w=\epsilon$, we set $p_{\epsilon}=1$. For a stochastic process
$\mathbf{r}\in\mathbb{R}^{r}$ and for each $w\in\Sigma^{*}$ we define the
stochastic process $\mathbf{z}^{\mathbf{r}}_{w}$ as

$\mathbf{z}^{\mathbf{r}}_{w}(t)=\mathbf{r}(t-|w|)\bm{\mu}_{w}(t-1)\frac{1}{\sqrt{p_{w}}},$
(8)

where $\bm{\mu}_{w}$ and $p_{w}$ are as in (6) and (7). For $w=\epsilon$,
$\mathbf{z}^{\mathbf{r}}_{w}(t)=\mathbf{r}(t)$. The process
$\mathbf{z}^{\mathbf{r}}_{w}$ in (8) is interpreted as the product of the
_past_ of $\mathbf{r}$ and $\bm{\mu}$. The process
$\mathbf{z}^{\mathbf{r}}_{w}$ will be used as predictors for future values of
$\mathbf{r}$ for various choices of $\mathbf{r}$.
We are now ready to recall from [26] the definition of ZMWSII process w.r.t.
$\bm{\theta}$ (w.r.t; $\bm{\mu}$ in the terminology of [26]).

######  Definition 1 ([26])

A stochastic process $\mathbf{r}$ is _Zero Mean Wide Sense Stationary_
(ZMWSSI) if

  1. 1.

For $t\in\mathbb{Z}$, the $\sigma$-algebras generated by
$\\{\mathbf{r}(k)\\}_{k\leq t}$, and $\\{\bm{\mu}_{\sigma}(k)\\}_{k\geq
t,\sigma\in\Sigma}$ respectively are conditionally independent w.r.t
$\sigma$-algebra generated by
$\\{\bm{\mu}_{\sigma}(k)\\}_{k<t,\sigma\in\Sigma}$,

  2. 2.

The processes $\\{\mathbf{z}^{\mathbf{r}}_{w}\\}_{w\in\Sigma^{*}}$ are zero
mean, square integrable and jointly wide sense stationary, i.e. the
covariances
$\\{E\left[\mathbf{z}^{\mathbf{r}}_{w}(t)(\mathbf{z}^{\mathbf{r}}_{v}(t))^{T}\right]\\}_{w,v\in\Sigma^{*}}$
are independent of $t$.

The concept of ZMWSII is an extension of wide-sense stationarity, if
$\Sigma^{+}$ is viewed as a time axis. More precisely, for any two ZMWSII
processes $\mathbf{r}$ and $\mathbf{b}$ and for sequences $w,v\in\Sigma^{*}$,
define the covariances:

$\Lambda_{w}^{\mathbf{r},\mathbf{b}}=E[\mathbf{r}(t)(\mathbf{z}^{\mathbf{b}}_{w}(t))^{T}],\quad
T_{w,v}^{\mathbf{r},\mathbf{b}}=E[\mathbf{z}^{\mathbf{r}}_{w}(t)(\mathbf{z}^{\mathbf{b}}_{v}(t))^{T}]$
(9)

Then, $T_{w,v}^{\mathbf{r},\mathbf{r}}=\Lambda^{\mathbf{r},\mathbf{r}}_{s}$ if
$w=sv$, and
$T_{w,v}^{\mathbf{r},\mathbf{r}}=(\Lambda^{\mathbf{r},\mathbf{r}}_{s})^{T}$ if
$v=sw$, for some $s\\!\in\Sigma^{*}$, and
$T_{w,v}^{\mathbf{r},\mathbf{r}}\\!\\!=\\!0$ otherwise. I.e., the covariance
$T_{w,v}^{\mathbf{r},\mathbf{r}}$ depends on the difference between $w$ and
$v$.

##  III Stationary LSSs

Below we present the definition of the class of LSSs which is studied in this
paper. To this end, we recall from [28] the notion of a white noise process
w.r.t. $\bm{\theta}$.

######  Definition 2 (White noise w.r.t. $\bm{\theta}$, [28])

A ZMWSII process $\mathbf{r}$ is a white noise w.r.t. $\bm{\theta}$, if for
all $v,w\in\Sigma^{+}$, $T^{\mathbf{r},\mathbf{r}}_{w,v}=0$ if $w\neq v$, and
$T^{\mathbf{r},\mathbf{r}}_{w,w}$ is non-singular.

The notion of a white noise process w.r.t. $\bm{\theta}$ (w.r.t. $\bm{\mu}$ in
the terminology of [28]) is an extension of the usual concept of the white
noise process if $\Sigma^{+}$ is viewed as an additional time axis. In
particular, if $\mathbf{r}$ is a white noise w.r.t. $\bm{\theta}$, the
collection $\\{\mathbf{z}_{w}^{\mathbf{r}}(t)\\}_{w\in\Sigma^{+}}$ is a
sequence of uncorrelated random variables and the covariance of
$\mathbf{z}_{w}^{\mathbf{r}}(t)$ does not depend on $t$ and it depends only on
the first letter of $w$.

Next, we state the assumptions on the input and output.

######  Assumption 1 (Inputs and outputs)

(1) $\mathbf{u}$ is a white noise w.r.t. $\bm{\theta}$ and the covariance
$T^{\mathbf{u},\mathbf{u}}_{\sigma,\sigma}=Q_{\textbf{u}}$ does not depend on
$\sigma\in\Sigma$. (2) The process
$\begin{bmatrix}\mathbf{y}^{T},\\!\\!&\\!\\!\mathbf{u}^{T}\end{bmatrix}^{T}$
is a ZMWSSI.

Now, we are ready to define the class of stationary LSS, which is a special
case of stationary generalized switched linear systems defined in [28].

######  Definition 3 (Stationary LSS)

A _stationary LSS_ (abbreviated sLSS) is a system (1), such that

  * 1.

$\mathbf{w}=\begin{bmatrix}\mathbf{v}^{T},\\!\\!&\\!\\!\textbf{u}^{T}\end{bmatrix}^{T}$
is a white noise process w.r.t. $\bm{\theta}$.

  * 2.

The process
$\begin{bmatrix}\mathbf{x}^{T}\\!\\!,&\\!\\!\mathbf{w}^{T}\end{bmatrix}^{T}$
is a ZMWSSI, and $T^{\mathbf{x},\mathbf{w}}_{\sigma,\sigma}=0$,
$\Lambda^{\mathbf{x},\mathbf{w}}_{w}=0$ for all $\sigma\in\Sigma$,
$w\in\Sigma^{+}$.

  * 3.

The eigenvalues of the matrix
$\sum_{\sigma\in\Sigma}p_{\sigma}{A}_{\sigma}\otimes{A}_{\sigma}$ are inside
the open unit circle.

If $B_{\sigma}=0$, $\sigma\in\Sigma$, and $D=0$ the we call (1) an _autonomous
stationary_ LSS (asLSS), and in this case we say it is an asLSS realization of
$(\textbf{y},\bm{\theta})$.

In the terminology of [26], an sLSS corresponds to a stationary GBS w.r.t.
inputs $\\{\bm{\mu}_{\sigma}\\}_{\sigma\in\Sigma}$ and with noise
$w=[\mathbf{v}^{T},\textbf{u}^{T}]^{T}$. In the terminology of [28], a sLSS is
a stationary generalized switched system for which the switching process is
i.i.d. Note that the processes $\mathbf{x}$ and $\mathbf{y}$ are ZMWSII, in
particular, they are wide-sense stationary, and that $\mathbf{x}$ is
orthogonal to the future values of the noise process $\mathbf{v}$. We need
stationarity, as even for LTI case stochastic realization theory exists only
for the stationary case [17].

As it was noted [28], the state of an sLSS is uniquely determined by its
matrices and noise and input process, i.e.,

$\mathbf{x}(t)=\sum_{\sigma\in\Sigma,w\in\Sigma^{*}}\sqrt{p_{\sigma
w}}A_{w}\left(K_{\sigma}\mathbf{z}^{\mathbf{v}}_{\sigma
w}(t)+B_{\sigma}\mathbf{z}^{\textbf{u}}_{\sigma w}(t)\right)$ (10)

where the right-hand side is absolutely convergent in the mean-square sense.
This motivates the following notation.

###### Notation 1

We identify a sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$ of the form (1)
with the tuple
$\mathcal{S}=(\\{A_{\sigma},B_{\sigma},K_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,D,F,\mathbf{v})$.

##  IV Minimality of sLSS in innovation form

In this section, we present the main results on existence and uniqueness of
minimal sLSSs in innovation form. To this end, first, we recall realization
theory of deterministic linear switched systems, and then relate it with
realization theory of sLSSs.

###  IV-A Review of deterministic realization theory of LSSs

A _deterministic linear switched system (abbreviated as dLSS)_ , is a system
of the form

$\mathscr{S}\begin{cases}&\mathrm{x}(t+1)=\mathcal{A}_{q(t)}\mathrm{x}(t)+\mathcal{B}_{q(t)}\mathrm{u}(t)\\\
&\mathrm{y}(t)=\mathcal{C}\mathrm{x}(t)+\mathcal{D}\mathrm{u}(t)\end{cases}$
(11)

where
$\\{\mathcal{A}_{\sigma},\mathcal{B}_{\sigma}\\}_{\sigma\in\Sigma},\mathcal{C},\mathcal{D}$
are matrices of suitable dimensions, $q:\mathbb{Z}\rightarrow\Sigma$ is the
switching signal,
$\mathrm{x}:\mathbb{Z}\rightarrow\mathbb{R}^{n_{\mathrm{x}}}$ is the state
trajectory $\mathrm{u}:\mathbb{Z}\rightarrow\mathbb{R}^{n_{\mathrm{u}}}$ is
the input trajectory
$\mathrm{y}:\mathbb{Z}\rightarrow\mathbb{R}^{n_{\mathrm{y}}}$ is the output
trajectory with finite support 111a function
$g:\mathbb{Z}\longrightarrow\mathbb{R}^{p}$ has a finite support, then it
$\exists\;t_{0}\in\mathbb{Z}$, such that $\forall\;t<t_{0}$, $g(t)=0$.. We
identify a dLSS of the form (11) with the tuple

$\mathscr{S}=(\\{\mathcal{A}_{i},\mathcal{B}_{i}\\}_{i=1}^{n_{\mu}},\mathcal{C},\mathcal{D})$
(12)

We refer to [23, 21] for a detailed definition input-output behavior of dLSSs,
their realization theory, minimality, etc. In particular, let us call any
function $M:\Sigma^{*}\rightarrow\mathbb{R}^{n_{\mathrm{y}}\times
n_{\mathrm{u}}}$ a _Markov function_. The dLSS $\mathscr{S}$ _realizes_ $M$,
if for all $w\in\Sigma^{*}$,

$M(w)=\left\\{\begin{array}[]{ll}\mathcal{CA}_{s}\mathcal{B}_{\sigma},&w=\sigma
s,\,\sigma\in\Sigma,\,s\in\Sigma^{*}\\\
\mathcal{D}.&w=\epsilon\end{array}\right.$ (13)

If $\mathscr{S}$ is a realization of $M$, then $M$ is referred to as the
_Markov function of $\mathscr{S}$_ and it is denoted by _$M_{\mathscr{S}}$_.
The values $\\{M(w)\\}_{w\in\Sigma^{*}}$ of $M_{\mathscr{S}}$ are the _Markov
parameters_ of $\mathscr{S}$. From [23, 21] it then follows that two dLSSs
have the same input-output behavior, if and only if their Markov functions are
equal. For dLSS (11) the integer $n_{x}$ is called the _dimension_ of
$\mathscr{S}$, and we say that a dLSS is _minimal_ , if there exists no other
dLSS of smaller dimension which realizes the same Markov-function. From [23,
21], it follows that a dLSS is minimal if and only if it is span-reachable and
observable, and the latter properties are equivalent to rank conditions of the
extended reachability and observability matrices [21, Definition 23, Theorem
1, Theorem 2]. Furthermore, any dLSS can be transformed to a minimal one with
the same Markov function, using a minimization algorithm [21, Procedure 3
1]222[21, Corollary 1] should be applied with zero initial state. For a more
detailed discussion see [21]. Moreover, any two minimal dLSS which are input-
output equivalent are isomorphic, i.e. they are related by a linear change of
coordinates [21, Theorem 1].

###  IV-B Relationship between sLSSs and dLSSs

The idea behind relating sLSSs and dLSSs is to express the covariances of
outputs of sLSSs as Markov parameters of dLSSs. To this end, we need to recall
[28] the decomposition of the output y into deterministic and stochastic
parts, and the notion of orthogonal projection from [28].

######  Notation 2 ($E_{l}$)

Recall from [4] that the set $\mathcal{H}_{1}$ of real valued square
integrable random variables is a Hilbert-space with the scalar product
$\langle\mathbf{z}_{1},\mathbf{z}_{2}\rangle=E[\mathbf{z}_{1}\mathbf{z}_{2}]$.
If $M$ is a closed subspace of $\mathcal{H}_{1}$, then denote by
$E_{l}[\mathbf{h}\\!\\!\mid\\!\\!M]$ the orthogonal projection, in the usual
sense for Hilbert-spaces, of $\mathbf{h}\in\mathcal{H}_{1}$ onto $M$. Let
$\mathbf{z}=(\mathbf{z}_{1},\ldots,\mathbf{z}_{k})^{T}$ be a $k$-dimensional
random variable such that $\mathbf{z}_{i}$ belongs to $\mathcal{H}_{1}$ for
all $i=1,\ldots,k$. The orthogonal projection of $\mathbf{z}$ onto $M$,
_denoted by $E_{l}[\mathbf{z}\\!\\!\mid\\!\\!M]$_, is defined as
$k$-dimensional random variable
$(E_{l}[\mathbf{z}_{1}\\!\\!\mid\\!\\!M],E_{l}[\mathbf{z}_{2}\\!\\!\mid\\!\\!M],\ldots,E_{l}[\mathbf{z}_{k}\\!\\!\\!\mid\\!\\!M])^{T}$.
If $\mathfrak{S}$ is a subset of vector valued random variables, coordinates
of which all belong to $\mathcal{H}_{1}$, and $M$ is generated by the
coordinates of the elements of $\mathfrak{S}$, then instead of
$E_{l}[\mathbf{z}\mid M]$ we use $E_{l}[\mathbf{z}\mid\mathfrak{S}]$.

Intuitively, $E_{l}[\mathbf{z}\mid\mathfrak{S}]$ is _minimal variance linear
prediction_ of $\mathbf{z}$ based on the elements of $\mathfrak{S}$.

The _deterministic component_ $\mathbf{y}^{d}$ and the _stochastic component_
$\mathbf{y}^{s}$ of $\mathbf{y}$ are defined as

$\begin{split}&{\mathbf{y}}^{d}(t)=E_{l}[\mathbf{y}(t)\mid\\{\mathbf{z}_{w}^{\mathbf{u}}(t)\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{u}(t)\\}],\\\
&\mathbf{y}^{s}(t)=\mathbf{y}(t)-\mathbf{y}^{d}(t).\end{split}$ (14)

Intuitively, $\textbf{y}^{d}$ is the best linear prediction of y based on the
present and past values of u multiplied by indicator functions of past
discrete modes. In fact, by [28, Theorem 1], $\textbf{y}^{d}$ (resp.
$\textbf{y}^{s}$) is the output of the asLSS obtained from (1), by setting
$K_{\sigma}=0$ (resp. $B_{\sigma}=0$), for all $\sigma\in\Sigma$

Define the Markov function
$M_{\mathbf{y},\mathbf{u}}:\Sigma^{*}\rightarrow\mathbb{R}^{n_{y}\times(n_{y}+n_{u})}$
by

$M_{\mathbf{y},\mathbf{u}}(w)=\begin{cases}\begin{bmatrix}\Lambda^{\textbf{y}^{d},\textbf{u}}_{w}Q_{\textbf{u}}^{-1},&\Lambda_{w}^{\textbf{y}^{s}}\end{bmatrix}&w\neq\epsilon\vspace{0.2cm}\\\
\begin{bmatrix}\Lambda^{\textbf{y}^{d},\textbf{u}}_{\epsilon}Q_{\textbf{u}}^{-1},&I_{n_{y}}\end{bmatrix}&w=\epsilon\end{cases}$
(15)

It can be shown that the first components of $M_{\mathbf{y},\textbf{u}}$ can
be expressed as Markov parameters of a suitably defined dLSS. Since, by [28],
$\textbf{y}^{s}$ is the output of an asLSS, and hence of a GBS in terminology
of [26], then by [26, Lemma 4] $\Lambda_{w}^{\textbf{y}^{s}}$ can be shown to
be the Markov function of a suitable dLSS. That is,
$M_{\mathbf{y},\mathbf{u}}$ has a dLSS realization.

Formally, define the process
$\mathbf{x}^{s}(t)=\textbf{x}(t)-E_{l}[\textbf{x}(t)\mid\\{\mathbf{z}_{w}^{\mathbf{u}}(t)\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{u}(t)\\}]$
and the matrices

$\begin{split}&G_{\sigma}=\sqrt{p_{\sigma}}(A_{\sigma}T^{\mathbf{x}^{s},\mathbf{x}^{s}}_{\sigma,\sigma}C^{T}+K_{\sigma}T^{\mathbf{v},\mathbf{v}}_{\sigma,\sigma}F^{T})\\\
\end{split}$ (16)

Then define the _dLSS associated with sLSS_ as

$\mathscr{S}_{\mathcal{S}}=(\\{\sqrt{p_{\sigma}}A_{\sigma},\begin{bmatrix}\sqrt{p_{\sigma}}B_{\sigma}&G_{\sigma}\end{bmatrix}\\}_{\sigma=1}^{n_{\mu}},C,\begin{bmatrix}D&I_{n_{y}}\end{bmatrix}),$

Note that by [28, proof of Theorem 1] $\mathbf{x}^{s}(t)$ is the state of the
asLSS obtained from $\mathcal{S}$ by considering $B_{\sigma}=0$, and hence
$\mathbf{x}^{s}$ is a ZMWSII process and
$T^{\mathbf{x}^{s},\mathbf{x}^{s}}_{\sigma,\sigma}$ is well-defined.

###### Lemma 1

If $\mathcal{S}$ is a sLSS realization of
$(\mathbf{y},\mathbf{u},\bm{\theta})$, then the associated dLSS
$\mathscr{S}_{\mathcal{S}}$ is a realization of $M_{\mathbf{y},\mathbf{u}}$.

The proof follows from [26, Lemma 4], [28, Theorem 2], it is presented in
[27].

######  Remark 2 (Computing $G_{\sigma}$)

In order to compute $G_{\sigma}$, we can use that by [28, proof Theorem 1]
$\mathbf{x}^{s}$ is the state of the asLSS obtained from (1) by setting
$B_{\sigma}\\!\\!=\\!\\!0$, $\sigma\in\Sigma$. Hence, by [26, Lemma 5], the
covariance of $\mathbf{x}^{s}$ satisfies
$p_{\sigma}T^{\mathbf{x}^{s},\mathbf{x}^{s}}_{\sigma,\sigma}=\lim_{N\rightarrow\infty}P_{\sigma}^{N}$,
where $P_{\sigma}^{0}=0$ and
$P_{\sigma}^{N+1}=p_{\sigma}\sum_{\sigma_{1}\in\Sigma}(A_{\sigma_{1}}P_{\sigma_{1}}^{N}A_{\sigma_{1}}^{T}+p_{\sigma_{1}}K_{\sigma_{1}}T^{\mathbf{v},\mathbf{v}}_{\sigma_{1},\sigma_{1}}K_{\sigma_{1}}^{T})$.

Conversely, we can associate with any dLSS realization of the Markov function
$M_{\textbf{y},\textbf{u}}$ a sLSS realization of
$(\textbf{y},\textbf{u},\bm{\theta})$. In order to define the latter, we need
to specify its noise process, which happens to be the _innovation noise_
$\textbf{e}^{s}$ of $\textbf{y}^{s}$ as defined in [26, eq. (16)]. By [28,
Theorem 2],

$\begin{split}&\mathbf{e}^{s}(t)=\mathbf{y}(t)-\hat{\mathbf{y}}(t)\\\
&\hat{\mathbf{y}}(t)=E_{l}[\mathbf{y}(t)\mid\\{\mathbf{z}^{\mathbf{y}}_{w}(t),\mathbf{z}^{\mathbf{u}}_{w}(t)\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{u}(t)\\}]\end{split}$
(17)

That is, $\mathbf{e}^{s}(t)$ is the prediction error of the best linear
predictor $\hat{\textbf{y}}(t)$ of $\textbf{y}(t)$ given the products of past
outputs, inputs and discrete modes, i.e., $\textbf{e}^{s}$ is direct extension
of the classical innovation noise. We say that $\mathbf{y}$ is _full rank_ ,
if for all $\sigma\in\Sigma$, the covariance
$T^{\mathbf{e}^{s},\mathbf{e}^{s}}_{\sigma,\sigma}$ is invertable. This is a
direct extension of the classical notion of a full rank process. If
$\mathbf{y}$ is full rank, for an observable dLSS

$\mathscr{S}=(\\{\hat{A}_{\sigma},\begin{bmatrix}\hat{B}_{\sigma}&\hat{G}_{\sigma}\end{bmatrix}\\}_{\sigma=1}^{n_{\mu}},\hat{C},\begin{bmatrix}D&I_{n_{y}}\end{bmatrix})$

for which $\sum_{\sigma=1}^{n_{\mu}}\hat{A}_{\sigma}\otimes\hat{A}_{\sigma}$
is a Schur matrix333all its eigenvalues are inside the unit disk, define the
_sLSS $\mathcal{S}_{\mathscr{S}}$ associated with $\mathscr{S}$ as _

$\mathcal{S}_{\mathscr{S}}=(\\{\frac{1}{\sqrt{p_{i}}}\hat{A}_{\sigma},\frac{1}{\sqrt{p_{\sigma}}}\hat{B}_{\sigma},\hat{K}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\hat{C},\hat{D},I_{n_{y}},\mathbf{e}^{s}),$

where
$\hat{K}_{\sigma}=\lim_{\mathcal{I}\rightarrow\infty}\hat{K}_{\sigma}^{\mathcal{I}}$,
and
$\\{\hat{K}_{\sigma}^{\mathcal{I}}\\}_{\sigma\in\Sigma,\mathcal{I}\in\mathbb{N}}$
satisfies

$\begin{split}&\hat{P}^{\mathcal{I}+1}_{\sigma}\\!\\!=\\!\\!p_{\sigma}\\!\\!\sum\limits_{\sigma_{1}\in\Sigma}\frac{1}{p_{\sigma_{1}}}\left(\hat{A}_{\sigma_{1}}\hat{P}^{\mathcal{I}}_{\sigma_{1}}\hat{A}_{\sigma_{1}}^{T}+\hat{K}_{\sigma_{1}}^{\mathcal{I}}\hat{Q}^{\mathcal{I}}_{\sigma_{1}}(\hat{K}^{\mathcal{I}}_{\sigma_{1}})^{T}\right)\\\
&\hat{Q}^{\mathcal{I}}_{\sigma}=p_{\sigma}T^{\textbf{y}^{s},\textbf{y}^{s}}_{\sigma,\sigma}-\hat{C}\hat{P}^{\mathcal{I}}_{\sigma}(\hat{C})^{T}\\\
&\hat{K}^{\mathcal{I}}_{\sigma}=\left(\hat{G}_{\sigma}\sqrt{p_{\sigma}}-\frac{1}{\sqrt{p_{\sigma}}}\hat{A}_{\sigma}\hat{P}^{\mathcal{I}}_{\sigma}(\hat{C})^{T}\right)\left(\hat{Q}^{\mathcal{I}}_{\sigma}\right)^{-1}\end{split}$
(18)

with $\hat{P}^{0}_{\sigma}=0$. Note that the noise process of
$\mathcal{S}_{\mathscr{S}}$ is the innovation noise, and its noise and state
covariances satisfy

$\begin{split}p_{\sigma}T^{\mathbf{e}^{s},\mathbf{e}^{s}}_{\sigma,\sigma}=\lim_{\mathcal{I}\rightarrow\infty}\hat{Q}_{\sigma}^{\mathcal{I}},~{}\quad
p_{\sigma}T^{\hat{\mathbf{x}},\hat{\mathbf{x}}}_{\sigma,\sigma}=\lim_{\mathcal{I}\rightarrow\infty}\hat{P}_{\sigma}^{\mathcal{I}}\end{split}$
(19)

where $\hat{\mathbf{x}}$ is the unique state process of
$\mathcal{S}_{\mathscr{S}}$. The convergence of (18) and (19) follow from the
proof of [26, Theorem 3].

###### Lemma 2

If $\mathbf{y}$ is full rank and $(\mathbf{y},\mathbf{u},\bm{\theta})$ has a
realization by sLSS, and $\mathscr{S}$ is a minimal dLSS realization of
$M_{\mathbf{y},\mathbf{u}}$, then the associated sLSS
$\mathcal{S}_{\mathscr{S}}$ is a sLSS realization of
$(\mathbf{y},\mathbf{u},\bm{\theta})$.

The proof of Lemma 2 is presented in [27], it relies on [28, Theorem 2] and
[26, Theorem 3].

###  IV-C Main result on minimal sLSSs in innovation form

A sLSS of the form (1) is said to be in _innovation form_ , if its noise
process $\mathbf{v}$ equals $\mathbf{e}^{s}$ from (17) and $F=I_{n_{y}}$. Note
that the sLSS associated with a dLSS is in innovation form. The sLSS (1) in
innovation form is a predictor

$\begin{split}&\mathbf{x}(t\\!+\\!1)\\!\\!=\\!\\!(A_{\bm{\theta}(t)}\\!-\\!K_{\bm{\theta}(t)}C)\mathbf{x}(t)+B_{\bm{\theta}(t)}\mathbf{u}(t)+K_{\bm{\theta}(t)}\textbf{y}_{u}(t)\\\
&\hat{\textbf{y}}(t)\\!=\\!C\mathbf{x}(t)+D\mathbf{u}(t),~{}\textbf{y}_{u}(t)=\textbf{y}(t)-D\textbf{u}(t)\end{split}$

which generates the best linear prediction $\hat{\textbf{y}}(t)$ of the output
$\textbf{y}(t)$, see (17), while being driven by past outputs and inputs.

We say that a sLSS realization of $(\textbf{y},\textbf{u},\bm{\theta})$ is
_minimal_ , if it has the smallest dimension among all sLSS realizations of
$(\textbf{y},\textbf{u},\bm{\theta})$. In order to study minimality, we need
the concepts of reachability and observability. We call a sLSS $\mathcal{S}$
_reachable_ (resp. _observable_), if the associated dLSS
$\mathscr{S}_{\mathcal{S}}$ is span-reachable, (resp. observable) according to
the definition of [21, Definition 19], applied to zero initial state.

In order to investigate uniqueness of minmal sLSS in innovation form, we need
the concept of isomorphism Let $\mathcal{S}$ and $\widetilde{\mathcal{S}}$ be
sLSSs realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$ in innovation form
such that $\mathcal{S}$ is of the form (1) and
$\widetilde{\mathcal{S}}=(\\{\tilde{A}_{\sigma},\tilde{B}_{\sigma},\tilde{K}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\tilde{C},\tilde{D},I_{n_{y}},\mathbf{e}^{s})$.
We say that $\mathcal{S}$ and $\widetilde{S}$ are _isomorphic_ , if there
exists a nonsingular matrix $T$ such that

$\begin{split}&\tilde{A}_{\sigma}=TA_{\sigma}T^{-1},\tilde{K}_{\sigma}=TK_{\sigma},~{}\tilde{B}_{\sigma}=TB_{\sigma},\quad\sigma\in\Sigma\\\
&\tilde{C}=CT^{-1},D=\tilde{D}\end{split}$ (20)

######  Theorem 1 (Main result: minimal innovation form)

Assume that $(\mathbf{y},\mathbf{u},\bm{\theta})$ has a sLSS realization and
that $\mathbf{y}$ is full rank w.r.t. u and $\bm{\theta}$. Then the following
holds.

  1. 1.

A sLSS realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$ is minimal if and
only if it is reachable and observable.

  2. 2.

If a dLSS $\mathscr{S}_{m}$ is a minimal realization of
$M_{\mathbf{y},\mathbf{u}}$, then the associated sLSS
$\mathcal{S}_{\mathscr{S}_{m}}$ is a minimal sLSS realization of
$(\mathbf{y},\mathbf{u},\bm{\theta})$ in innovation form.

  3. 3.

There exists a minimal sLSS realization of
$(\textbf{y},\textbf{u},\bm{\theta})$ in innovation form.

  4. 4.

Any two minimal sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$ in innovation
form are isomorphic.

The proof is presented in [27], it relies on the fact that any dLSS can be
transformed to a minimal one, that minimal input-output dLSS are isomorphic
and on Lemma 1-2.

Note that observability and reachability of the associated dLSS can be checked
using simple rank conditions of suitable matrices [21]. That is, our
conditions for minimality can be checked numerically. Moreover, a sLSS can be
transformed effectively to a minimal one in innovation form as follows: first
we compute the associated dLSS, we minimize it using [21, Procedure 3] to
obtain a minimal dLSS realization of $M_{\textbf{y},\textbf{u}}$, and then we
compute the sLSS associted with the latter minimal dLSS.

######  Remark 3 (Relationship with [28])

For a sLSS (1), the minimality condition of [28] corresponds to reachability
and observability of the dLSS which is obtained from the dLSS (11) associated
with (1) by deleting certain columns of $\mathcal{B}_{\sigma}$. The latter is
sufficient, but not necessary for the reachability and observability of the
dLSS associated with (1). Likewise, [28] shows isomorphism between sLSSs in
innovation form which satisfy the above sufficient condition for minimality,
and for which the image of $B_{\sigma}$ belongs to the image of $K_{\sigma}$.
In contrast, Theorem 1 establishes isomorphism for a much wider class of sLSSs
in innovation form.

##  V Minimial covariance realization algorithm

In this section we present a Ho-Kalman-like algorithm for computing a minimal
sLSS realization innovation form from $M_{\textbf{y},\textbf{u}}$. Ot this
end, we first we recall the Ho-Kalman realization algorithm for dLSS.

###  V-A Reduced basis Ho-Kalman algorithm for dLSS

Below we recall from [8] an adaptation of the Ho-Kalman-like algorithm. Define
a _$(n,n_{\mathrm{y}},n_{\mathrm{u}})$ -selection (selection for short)_ as a
pair of word-index sets $\left(\alpha,\beta\right)$ such that,

$\begin{split}&\alpha=\\{(u_{i},k_{i})\\}_{i=1}^{n},~{}\beta=\\{(\sigma_{j},v_{j},l_{j})\\}_{j=1}^{n},\end{split}$
(21)

for some $u_{i}\in\Sigma^{+}$, $|u_{i}|\leq n$,
$k_{i}\in\\{1,2,\cdots,n_{\mathrm{y}}\\}$, $\sigma_{j}\in\Sigma$,
$v_{j}\in\Sigma^{+}$, $|v_{j}|\leq n$,
$l_{j}\in\\{1,2,\cdots,n_{\mathrm{u}}\\}$, $i,j\in\\{1,\ldots,n\\}$
Intuitively, the components of $\alpha,\beta$ which belong to
$\Sigma^{+}\cup\Sigma$ determine the choice of Markov parameters, while the
other components determine a choice of row and column indices of the chosen
Markov parameters, see [20] for an example. Formally, let
$M:\Sigma^{*}\rightarrow\mathbb{R}^{n_{\mathrm{y}}\times n_{\mathrm{u}}}$ be a
Markov function. Define the Hankel matrix
$\mathcal{H}_{\alpha,\beta}^{M}\in\mathbb{R}^{n\times n}$ and the matrices
$\mathcal{H}_{\sigma,\alpha,\beta}^{M}\in\mathbb{R}^{n\times n}$,
$\mathcal{H}_{\alpha,\sigma}^{M}\in\mathbb{R}^{n\times n_{\mathrm{u}}}$ and
$\mathcal{H}^{M}_{\beta}\in\mathbb{R}^{n_{\mathrm{y}}\times n}$ as follows as
follows:

$\displaystyle\left[\mathcal{H}_{\alpha,\beta}^{M}\right]_{i,j}\\!=\\!\left[M(\sigma_{j}v_{j}u_{i})\right]_{k_{i},l_{j}},\quad
i,j=1,\ldots,n$ (22)
$\displaystyle\left[\mathcal{H}_{\sigma,\alpha,\beta}^{M}\right]_{i,j}=\left[M(\sigma_{j}v_{j}\sigma
u_{i})\right]_{k_{i},l_{j}},~{}i,j=1,\ldots,n$ (23)
$\displaystyle\left[\mathcal{H}^{M}_{\alpha,\sigma}\right]_{i,j}\\!=\\!\left[M(\sigma
u_{i})\right]_{k_{i},j},\ j\\!=\\!1,\ldots,n_{\mathrm{u}},i\\!=\\!1,\ldots,n$
(24)
$\displaystyle\left[\mathcal{H}^{M}_{\beta}\right]_{i,j}\\!=\\!\left[M(\sigma_{j}v_{j})\right]_{i,l_{j}},\
i=1,\ldots,n_{\mathrm{y}},j=1,\ldots n$ (25)

where
$\left(u_{i},k_{i}\right)\in\alpha,\left(\sigma_{j},v_{j},l_{j}\right)\in\beta$
are as in the ordering in (21). Finally, let $\mathcal{L}_{\alpha,\beta}$ be
the set of all words $w\in\Sigma^{*}$ such that $M(w)$ occurs in one of the
matrices, (22) – (23), i.e.,

$\mathcal{L}_{\alpha,\beta}=\\{u_{i},\sigma_{j}v_{j},\sigma_{j}v_{j}u_{i},\sigma_{j}v_{j}\sigma
u_{i},\sigma u_{i}\mid\sigma\in\Sigma\\}_{i,j=1}^{n}$

The promised algorithm is presented in Algorithm 1.

Algorithm 1 Ho-Kalman for dLSSs

Input: $(n,n_{\mathrm{y}},n_{\mathrm{u}})$-selection
$\left(\alpha,\beta\right)$, $\\{M(w)\\}_{w\in\mathcal{L}_{\alpha,\beta}}$,
$M(\epsilon)$ Construct the matrices $\mathcal{H}^{M}_{\alpha,\beta}$,
$\mathcal{H}^{M}_{\sigma,\alpha,\beta}$ $\mathcal{H}_{\alpha,\sigma}^{M}$ and
$\mathcal{H}_{\beta}^{M}$, and set

$\displaystyle\hat{A}_{\sigma}=(\mathcal{H}_{\alpha,\beta}^{M})^{-1}\mathcal{H}_{\sigma,\alpha,\beta}^{M},~{}\hat{B}_{\sigma}=(\mathcal{H}_{\alpha,\beta}^{M})^{-1}\mathcal{H}^{M}_{\alpha,\sigma},~{}\hat{C}=\mathcal{H}^{M}_{\beta}.$

Output: dLSS
$(\\{\hat{A}_{\sigma},\hat{B}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\hat{C},M(\epsilon))$

######  Lemma 3 ([8])

Assume that there exists a minimal dLSS realization of $M$ of dimension $n$.
Then there exists an $(n,n_{\mathrm{y}},n_{\mathrm{u}})$-selection
$(\alpha,\beta)$ such that $\text{rank}(\mathcal{H}_{\alpha,\beta}^{M})=n$.
For any $(n,n_{\mathrm{y}},n_{\mathrm{u}})$-selection $(\alpha,\beta)$ for
which $\text{rank}(\mathcal{H}_{\alpha,\beta}^{M})=n$, Algorithm 1 returns a
minimal dLSS realization of $M$.

###  V-B Covariance realization algorithm

Theorem 1, together with Algorithm 1 and Lemma 3 suggest that in order to
compute a sLSS realization of $(\textbf{y},\textbf{u},\bm{\theta})$, one could
apply Algorithm 1 to Hankel-matrices corresponding to
$M_{\textbf{y},\textbf{u}}$. However, the definition of
$M_{\textbf{y},\textbf{u}}$ uses the covariances of the processes
$\textbf{y}^{d}$ and $\textbf{y}^{s}$, which are not directly available. Below
we show how to compute $M_{\textbf{y},\textbf{u}}$ using only the covariances
of y and u.

To this end, define the Markov function $\Psi_{\mathbf{u},\mathbf{y}}$ such
that $\Psi_{\mathbf{u},\mathbf{y}}(w)$ is formed by the first $n_{u}$ columns
of $M_{\textbf{y},\textbf{u}}(w)$, i.e.
$\Psi_{\mathbf{u},\mathbf{y}}(w)=\Lambda_{w}^{\textbf{y}^{d},\textbf{u}}Q_{u}^{-1}$.
Then $\Psi_{\mathbf{u},\mathbf{y}}$ has a realization by a dLSS: by Lemma 1
$(\\{\sqrt{p_{\sigma}}A_{\sigma},\sqrt{p_{\sigma}}B_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,D)$
is a dLSS realization of $\Psi_{\mathbf{u},\mathbf{y}}$.

###### Lemma 4

If there exists a sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$. Then

$\begin{split}&\Lambda_{w}^{\textbf{y}^{d},\textbf{u}}\\!\\!=\\!\\!\Lambda^{\textbf{y},\textbf{u}}_{w},~{}\Lambda_{\sigma
w}^{\textbf{y}^{s},\textbf{y}^{s}}\\!\\!=\\!\\!\Lambda^{\textbf{y},\textbf{y}}_{\sigma
w}-\Lambda^{\textbf{y}^{d},\textbf{y}^{d}}_{\sigma w},\\\
&T^{\textbf{y}^{s},\textbf{y}^{s}}_{\sigma,\sigma}\\!\\!=\\!\\!T_{\sigma,\sigma}^{\textbf{y},\textbf{y}}\\!\\!-T_{\sigma,\sigma}^{\textbf{y}^{d},\textbf{y}^{d}}\end{split}$
(26)

for all $w\in\Sigma^{*}$, $\sigma\in\Sigma$. Moreover, if
$(\\{\tilde{A}_{\sigma}^{d},\tilde{B}_{\sigma}^{d}\\}_{\sigma=1}^{n_{\mu}},\tilde{C}^{d},\tilde{D}^{d})$
is a minimal dLSS realization of $\Psi_{\mathbf{u},\mathbf{y}}$, then

$\begin{split}&\Lambda^{\textbf{y}^{d},\textbf{y}^{d}}_{\sigma
w}=\frac{1}{p_{\sigma
w}}\tilde{C}^{d}\tilde{A}_{w}^{d}(\tilde{A}^{d}_{\sigma}\tilde{P_{\sigma}}(\tilde{C}^{d})^{T}+\tilde{B}^{d}_{\sigma}Q_{u}(\tilde{D}^{d})^{T})\\\
&T_{\sigma,\sigma}^{\textbf{y}^{d},\textbf{y}^{d}}=\frac{1}{p_{\sigma}}(\tilde{C}^{d}\tilde{P_{\sigma}}(\tilde{C}^{d})^{T}+\tilde{D}^{d}Q_{u}(\tilde{D}^{d})^{T})\end{split}$
(27)

where
$\tilde{P}_{\sigma}=\lim\limits_{\mathcal{I}\rightarrow\infty}\tilde{P}_{\sigma}^{\mathcal{I}}$,
and $\tilde{P}_{\sigma}^{0}=0$ and
$\tilde{P}_{\sigma}^{\mathcal{I}+1}=p_{\sigma}\sum_{\sigma_{1}\in\Sigma}\left(\frac{1}{p_{\sigma_{1}}}\tilde{A}_{\sigma_{1}}^{d}\tilde{P}_{\sigma_{1}}^{\mathcal{I}}(\tilde{A}_{\sigma_{1}}^{d})^{T}+\tilde{B}_{\sigma_{1}}^{d}Q_{u}(\tilde{B}_{\sigma_{1}}^{d})^{T}\right)$.

The proof of Lemma is presented in [27]. The first part of the lemma relies on
orthogonality of $\textbf{y}^{s}(t)$ and
$\\{\mathbf{z}_{w}^{\textbf{u}}(t)\\}_{w\in\Sigma^{*}}$ established in [28].
The second part follows by identifying dLSS realizations of
$\Psi_{\mathbf{u},\mathbf{y}}$ with asLSS realizations of $\textbf{y}^{d}$
whose noise is u, and using the equations in [26, Lemma 4] for the covariances
of $\textbf{y}^{d}$.

We can then use Lemma 4 to compute the necessary values of
$M_{\textbf{y},\textbf{u}}$ as follows. First, we compute a minimal dLSS
realization of $\Psi_{\mathbf{u},\mathbf{y}}$ using Algorithm 1, and then use
(26) – (27) to compute those values of
$\Lambda_{w}^{\textbf{y}^{s},\textbf{y}^{s}}$, and hence of
$M_{\mathbf{y},\mathbf{u}}$, which are necessary for applying Algorithm 1 to
$M_{\mathbf{y},\mathbf{u}}$. This idea is formalized in Algorithm 2.

Algorithm 2 Minimal covariance realization algorithm

Input: $(n_{x},n_{y},n_{u}\\!\\!+\\!n_{y})$-selection
$\left(\alpha,\beta\right)$; $(\bar{n},n_{y},n_{u})$-selection
$\left(\bar{\alpha},\bar{\beta}\right)$; covariances
$\\{\Lambda^{\textbf{y},\textbf{u}}_{w}\\}_{w\in\mathcal{L}_{\alpha,\beta}\cup\mathcal{L}_{\bar{\alpha},\bar{\beta}}}$,
$\\{\Lambda^{\textbf{y},\textbf{y}}_{w}\\}_{w\in\mathcal{L}_{\alpha,\beta}}$,
$\Lambda_{\epsilon}^{\textbf{y},\textbf{u}}$,
$\\{T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}\\}_{\sigma\in\Sigma}$; integer
$\mathcal{I}>0$.

  1. 1.

Use (26) to compute
$\\{\Psi_{\mathbf{u},\mathbf{y}}(w)\\}_{w\in\mathcal{L}_{\bar{\alpha},\bar{\beta}}}$
and $\Psi_{\mathbf{u},\mathbf{y}}(\epsilon)$.

  2. 2.

Run Algorithm 1 with $M=\Psi_{\mathbf{u},\mathbf{y}}$ and selection
$(\bar{\alpha},\bar{\beta})$ and denote the result by
$\mathscr{S}_{d}=(\\{\tilde{A}_{i},\tilde{B}_{i}\\}_{i=1}^{n_{\mu}},\tilde{C},\tilde{D})$.

  3. 3.

Compute
$\\{\Lambda^{\textbf{y}^{s},\textbf{y}^{s}}_{w},\Lambda_{w}^{\textbf{y}^{d},\textbf{u}}\\}_{w\in\mathcal{L}_{\alpha,\beta}}$,
using (26), (27) and
$\\{\Lambda^{\textbf{y},\textbf{y}^{s}}_{w}\\}_{w\in\mathcal{L}_{\alpha,\beta}}$.

  4. 4.

Compute $M_{\textbf{y},\textbf{u}}(w)$ from
$\\{\Lambda^{\textbf{y}^{s},\textbf{y}^{s}}_{w},\Lambda_{w}^{\textbf{y}^{d},\textbf{u}}\\}$
for $w\in\mathcal{L}_{\alpha,\beta}$.

  5. 5.

Run Algorithm 1 with $M=M_{\mathbf{y},\mathbf{u}}$ and selection
$(\alpha,\beta)$, and denote by
$\mathscr{S}=(\\{\hat{A}_{i},\left[\hat{B}_{i}\
\hat{G}_{i}\right]\\}_{i=1}^{n_{\mu}},\hat{C},\hat{D})$ the result.

  6. 6.

From $\\{T_{\sigma,\sigma}^{\textbf{y},\textbf{y}}\\}_{\sigma\in\Sigma}$
compute
$\\{T_{\sigma,\sigma}^{\textbf{y}^{s},\textbf{y}^{s}}\\}_{\sigma\in\Sigma}$
using (26) and (27). Let $\hat{K}^{\mathcal{I}}_{\sigma}$,
$\hat{Q}^{\mathcal{I}}_{\sigma}$ as in (18).

Output: Matrices
$\\{\frac{\hat{A}_{\sigma}}{\sqrt{p_{\sigma}}},\frac{\hat{B}_{\sigma}}{\sqrt{p_{\sigma}}},\hat{K}^{\mathcal{I}}_{\sigma},\hat{Q}^{\mathcal{I}}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\hat{C},\hat{D}$.

###### Corollary 1

Assume that y is full rank and there exists a minimal sLSS realization of
$(\mathbf{y},\mathbf{u},\bm{\theta})$ of dimension $n_{x}$, and a minimal dLSS
realization of $\Psi_{\textbf{y},\textbf{u}}$ of dimension $\bar{n}$. If the
selections $(\alpha,\beta)$ and $(\bar{\alpha},\bar{\beta})$ satisfy

$\mathrm{rank}H^{M_{\mathbf{y},\mathbf{u}}}_{\alpha,\beta}\\!\\!=\\!\\!n_{x},\quad\mathrm{rank}H^{\Psi_{\mathbf{u},\mathbf{y}}}_{\bar{\alpha},\bar{\beta}}\\!\\!=\\!\\!\bar{n}.$
(28)

then Algorithm 2 returns matrices such that the sLSS
$\tilde{S}=(\\{\hat{A}_{\sigma}/\sqrt{p_{\sigma}},\hat{B}_{\sigma}/\sqrt{p_{\sigma}},\hat{K}_{\sigma},\\}_{\sigma=1}^{n_{\mu}},\hat{C},\hat{D},\mathbf{e}^{s})$
is a minimal realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$ in
innovation form, where
$\hat{K}_{\sigma}=\lim_{\mathcal{I}\rightarrow\infty}\hat{K}_{\sigma}^{\mathcal{I}}$
and
$T^{\textbf{e}^{s},\textbf{e}^{s}}_{\sigma,\sigma}p_{\sigma}=\lim_{\mathcal{I}\rightarrow+\infty}\hat{Q}_{\sigma}^{\mathcal{I}}$,
$\sigma\in\Sigma$. Moreover, there exist an
$(n_{x},n_{y},n_{u}+n_{y})$-selection $(\alpha,\beta)$ and
$(\bar{n},n_{y},n_{u})$-selection $(\bar{\alpha},\bar{\beta})$ which satisfy
(28).

The proof of Corollary 1 is presented in [27], it uses Lemma 3, Theorem 1 and
the notion of sLSSs associated with dLSSs.

That is, Algorithm 2 returns a minimal sLSS in innovation form based on the
input and output covariances, if the selections $(\alpha,\beta)$,
$(\bar{\alpha},\bar{\beta})$ give Hankel-matrices of a correct rank, and there
always exists such selections.

That is, by finding a minimal sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$ in
innovation form, Algorithm 2 finds a sLSS which has the same deterministic
behavior as the true system, i.e. the same output response as the true system
for any inputs, noise and switching signals, if the true system is assumed to
be minimal in innovation form.

##  VI Identification algorithm

We formulate an identification algorithm based on Algorithm 2, by using
empirical covariances instead of the true ones
$\Lambda_{w}^{\textbf{y},\textbf{u}}$, $\Lambda_{w}^{\textbf{y},\textbf{y}}$,
$T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}$ when applying Algorithm 2. To this
end, we make the following assumptions.

###### Assumption 2

(1) The $(n_{x},n_{y},n_{u}+n_{y})$-selection $\left(\alpha,\beta\right)$ and
the $(\bar{n},n_{y},n_{u})$-selection $(\bar{\alpha},\bar{\beta})$ satisfy
(28), y is full rank, and $n_{x}$ and $\bar{n}$ satisfy the hypothesis of
Corollary 1.

(2) The process $(\mathbf{y},\mathbf{u},\bm{\theta})$ is ergodic, and the
observed sample paths $y:\mathbb{Z}\rightarrow\mathbb{R}^{n_{y}}$,
$u:\mathbb{Z}\rightarrow\mathbb{R}^{n_{u}}$ and
$q:\mathbb{Z}\rightarrow\Sigma$ of $\mathbf{y}$, $\mathbf{u}$ and
$\bm{\theta}$ respectively satisfy the following. For all
$w,v\in\mathcal{L}_{\alpha,\beta}\cup\mathcal{L}_{\bar{\alpha},\bar{\beta}}\cup\Sigma\cup\\{\epsilon\\}$
define the _empirical covariances_

$T^{\textbf{y},\mathbf{b}}_{v,w,N}=\frac{\sum_{t=N_{0}}^{N}z^{y}_{v}(t)(z_{w}^{b}(t))^{T}}{N-N_{0}},$
(29)

where $b=\begin{cases}y&\mathbf{b}=\textbf{y}\\\
u&\mathbf{b}=\textbf{u}\end{cases}$, and for all
$\mu_{\sigma}(t)=\chi(q(t)=\sigma)$, $\sigma\in\Sigma$, and for all
$w=\sigma_{1}\sigma_{2}\ldots\sigma_{r}\in\Sigma^{+}$, $r>0$,
$\sigma_{1},\ldots,\sigma_{r}\in\Sigma$, $b\in\\{y,u\\}$

$\begin{split}&\mu_{w}(t)=\mu_{\sigma_{1}}(t-k+1)\mu_{\sigma_{2}}(t-k+2)\cdots\mu_{\sigma_{r}}(t)\\\
&z^{b}_{w}(t)=b(t-r)\mu_{w}(t-1)\frac{1}{\sqrt{p_{w}}},\quad
z^{b}_{\epsilon}(t)=b(t),\\\ \end{split}$

and $N_{0}$ is an upper bound on the length of words in
$\mathcal{L}_{\alpha,\beta}\cup\mathcal{L}_{\bar{\alpha},\bar{\beta}}\cup\Sigma$.
Then we assume that for all $\mathbf{b}\in\\{\textbf{y},\textbf{u}\\}$,

$\Lambda^{\mathbf{y},\mathbf{u}}_{w}=\lim_{N\rightarrow\infty}T^{\mathbf{y},\mathbf{b}}_{\epsilon,w,N},\quad
T^{\mathbf{y},\mathbf{y}}_{\sigma,\sigma}=\lim_{N\rightarrow\infty}T^{\mathbf{y},\mathbf{y}}_{\sigma,\sigma,N}$
(30)

The first assumption is not restrictive, such selections always exist, and
they can be found by an exhaustive search through all the possible selections.
The assumption (30) says that the observed sample $(y,u,q)$ satisfies the law
of large numbers; ergodicity, which is a standard assumption in
identification, implies that almost any sample satisfies (30).

Algorithm 3 Identification sLSS

Input: Data $\\{{y}(t),u(t),q(t)\\}_{t=1}^{N}$,
$(n_{x},n_{y},n_{u}+n_{y})$-selection $\left(\alpha,\beta\right)$ and
$(\bar{n},n_{y},n_{u})$-selection $\left(\bar{\alpha},\bar{\beta}\right)$;
integer $\mathcal{I}>0$.

  1. 1.

Run Algorithm 2 with the covariances $\Lambda^{\textbf{y},\mathbf{b}}_{w}$,
$T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}$ being replaced by the empirical
covariances $T^{\textbf{y},\mathbf{b}}_{\epsilon,w,N}$,
$T^{\textbf{y},\textbf{y}}_{\sigma,\sigma,N}$ respectively for
$\mathbf{b}\in\\{\textbf{y},\textbf{u}\\}$ and
$w\in\mathcal{L}_{\alpha,\beta}\cup\mathcal{L}_{\bar{\alpha},\bar{\beta}}$,
$\sigma\in\Sigma$.

Output: The matrices
$\\{\tilde{A}_{\sigma}^{N},\tilde{B}^{N}_{\sigma},\tilde{K}^{N,\mathcal{I}}_{\sigma},\tilde{Q}^{N,\mathcal{I}}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\tilde{C}^{N},\tilde{D}^{N}$
returned by Algorithm 2.

######  Lemma 5 (Consistency)

Under Assumption 2 the matrices returned by Algorithm 3 satisfy the following:

$\displaystyle\tilde{K}_{\sigma}=\lim_{\mathcal{I}\rightarrow\infty}\lim_{N\rightarrow\infty}\tilde{K}^{N,\mathcal{I}}_{\sigma},~{}~{}p_{\sigma}T^{\textbf{e}^{s},\textbf{e}^{s}}_{\sigma,\sigma}=\lim_{\mathcal{I}\rightarrow\infty}\lim_{N\rightarrow\infty}\tilde{Q}^{N,\mathcal{I}}_{\sigma}$
$\displaystyle[\tilde{A}_{\sigma},\tilde{B}_{\sigma}]=\lim_{N\rightarrow\infty}[\tilde{A}_{\sigma}^{N},\tilde{B}_{\sigma}^{N}],~{}[\tilde{C},\tilde{D}]=\lim_{N\rightarrow\infty}[\tilde{C}^{N},\tilde{D}^{N}]$

and
$\mathcal{S}=(\\{\tilde{A}_{\sigma},\tilde{B}_{\sigma},\tilde{K}_{\sigma},\\}_{\sigma=1}^{n_{\mu}},\tilde{C},\tilde{D},\hat{\mathbf{x}},\mathbf{e}^{s})$
is a minimal sLSS realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$ in
innovation form.

That is, Algorithm 3 is a statistically consistent. Moreover, if the true
system is a minimal sLSS in innovation form, which, by Theorem 1 we can assume
w.l.g, then the sLSS returned by Algorithm 3 will be isomorphic to the true
system, as $N\rightarrow\infty$. In particular, in the limit, the identified
system has _the same deterministic behavior_ as the true system. That is,
while the data used for identification had to be sampled from certain
distributions, the identified model recreates the behavior of the true one for
any switching signal and input.

Algorithm 3 can be improved as follows.

######  Remark 4 (Computing empirical covariances)

Using (29) directly for computing empirical covariances
$T^{\textbf{y},\mathbf{b}}_{\epsilon,w,N}$,
$\mathbf{b}\in\\{\textbf{y},\textbf{u}\\}$ results in slow convergence.
Instead, we propose to compute the empirical covariances by solving a linear
regression problem. More precisely, assume that
$\mathcal{L}_{\alpha,\beta}\cup\mathcal{L}_{\bar{\alpha},\bar{\beta}}=\\{w_{1},\ldots,w_{k}\\}$
and $\mathcal{L}_{\alpha,\beta}=\\{w_{1},\ldots,w_{r}\\}$ for some $k,r>0$.
Let us then define the following matrices

$R=\begin{bmatrix}y(N_{0})\\\ \vdots\\\
y(N)\end{bmatrix},\quad\Phi_{\mathbf{b}}=\begin{bmatrix}\mathbf{z}^{y}_{w_{1}}(N_{0})&\cdots&\mathbf{z}^{\mathbf{b}}_{w_{l(\mathbf{b})}}(N_{0})\\\
\vdots&&\vdots\\\
\mathbf{z}^{\mathbf{b}}_{w_{1}}(N)&\cdots&\mathbf{z}^{\mathbf{b}}_{w_{l(\mathbf{b})}}(N)\end{bmatrix}$

where for $\mathbf{b}=\textbf{y}$, $l(\mathbf{b})=r$ and $b=y$, and for
$\mathbf{b}=\textbf{u}$, $l(\mathbf{b})=k$ and $b=u$. By the well-known
formula,
$\hat{\Theta}^{\mathbf{b}}=(\Phi^{T}_{\mathbf{b}}\Phi_{\mathbf{b}})^{-1}\Phi_{\mathbf{b}}^{T}R$
is the least squares solution of the equation
$R=\Phi_{\mathbf{b}}\hat{\Theta}^{\mathbf{b}}$. Hence,
$\frac{1}{N-N_{0}}(\Phi^{T}_{\mathbf{b}}\Phi_{\mathbf{b}})\hat{\Theta}^{\mathbf{b}}=\frac{1}{N-N_{0}}\Phi^{T}_{\mathbf{b}}R$,
and the latter contains all covariances
$T_{\epsilon,w,N}^{\textbf{y},\mathbf{b}}$,
$\mathbf{b}\in\\{\textbf{u},\textbf{y}\\}$ required for Algorithm 3. In turn,
$\hat{\Theta}^{\mathbf{b}}$ can be computed using standard linear regression
tools.

######  Remark 5 (Refinement using gradient descend)

In order to enhance the performance of Algorithm 3, inspired by [9], we
propose to use the sLSS returned by Algorithm 3 as initial value for the
Gradient-Based (GB) algorithm of [9, Algorithm 7.1]. Note that [9] uses zero
matrices as initial values for the noise gain matrices, whereas Algorithm 3
returns a non-zero estimate of those matrices.

##  VII Numerical example

In this section, we illustrate Algorithm 3 on a numerical example. All
computations are carried out on an i7 2.11-GHz Intel core processor with 32GB
of RAM running MATLAB R2023b. For data generation we use the following
randomly generatated sLSS (1) with $\Sigma=\\{1,2\\}$

$\begin{split}&A_{1}=\begin{bmatrix}0.1039&0.0255&0.5598\\\
0.4338&0.0067&0.0078\\\
0.3435&0.0412&0.0776\end{bmatrix},B_{1}=\begin{bmatrix}1.6143\\\ 5.9383\\\
7.3671\end{bmatrix},\\\ &A_{2}=\begin{bmatrix}0.1834&0.2456&0.0511\\\
0.0572&0.2445&0.0642\\\
0.1395&0.6413&0.5598\end{bmatrix},B_{2}=\begin{bmatrix}6.0624\\\ 4.9800\\\
3.1372\end{bmatrix},\\\ &K_{1}\\!\\!=\\!\\!\left[0.4942\ 0.2827\
0.8098\right]^{T},\\\ &K_{2}\\!\\!=\\!\\!\left[0.6215\ 0.1561\
0.7780\right]^{T}\\\
&C=\begin{bmatrix}0.1144&0.7623&0.0020\end{bmatrix},D=1,F=1.\end{split}$

Training and validation data of length $N$ and $N_{\mathrm{val}}$,
respectively, are generated using the data generator sLSS with white-noise
input process $\mathbf{u}$ with uniform distribution $\mathcal{U}(-1,1)$, an
i.i.d. process $\bm{\theta}$ sucht that $\mathcal{P}(\bm{\theta}(t)=q)=0.5$,
$q=1,2$, and a Gaussian white noise $\mathbf{v}$ with variance
$\sigma^{2}_{\mathbf{v}}$. The corresponding _Signal-to-Noise Ratio_
$\mathrm{SNR}$ are shown in Table I. We run the version of Algorithm 3 using
the Least-Square method from Remark 4, with
$(\alpha,\beta)=(\bar{\alpha},\bar{\beta})$,

$\alpha\\!\\!=\\!\\!\\{(11,1),(1,1),(\epsilon,1)\\},~{}~{}\beta\\!\\!=\\!\\!\\{(2,\epsilon,1),(1,2,1),(1,1,1)\\},$

and the GB refinement step from Remark 5. For the latter we used the LPVcore
toolbox [11].

For validation, the true output minus the measurement noise $Fv(t)$, denoted
by $y(t)$, was compared with the output $\hat{y}(t)$ predicted by the
estimated model in innovation form using past inputs and outputs, as explained
in Section IV-C. The quality of the match is evaluated via _Best Fit Rate_
criterion
$\mathrm{BFR}\\!\\!=\\!\\!\max\left\\{1\\!\\!-\\!\\!\sqrt{\frac{\sum_{t=1}^{N_{\mathrm{val}}}\left(y(t)-\hat{y}(t)\right)^{2}}{\sum_{t=1}^{N_{\mathrm{val}}}\left(y(t)-\bar{y}\right)^{2}}},0\right\\}\times
100\%$, where $\bar{y}$ denotes the sample mean of the output in the
validation set.

TABLE I: BFR on a noise-free validation data ($N_{\mathrm{val}}=500$) Method | $N=5000$ | $N=10000$
---|---|---
$\mathrm{SNR}=6.1\ \mathrm{dB}$, $\sigma_{\mathbf{v}}=1.5$
BFR[%] | time[s] | BFR[%] | time[s]
GB + zero noise gain | 83.13 | 197 | 82.42 | 361
Algorithm 3 | 85.67 | 2.60 | 90.86 | 2.03
Algorithm 3 \+ GB | 90.5 | 256 | 91.71 | 323
|  $\mathrm{SNR}=0.5\ \mathrm{dB}$, $\sigma_{\mathbf{v}}=3$
GB + zero noise gain | 63.25 | 188 | 66.11 | 316
Algorithm 3 | 76.97 | 1.94 | 87.29 | 1.90
Algorithm 3 \+ GB | 84.17 | 236 | 88.03 | 376

The results are reported in Table I. We compare Algorithm 3 with using only
the GB search algorithm from [9] where the initial value of the noise gain is
zero, while the other matrices are initialized by the outcome of Algorithm 3.
This is then equivalent with combining the CRA algorithm of [8] with GB.
Algorithm 3 appears to perform better than using only GB search, especially
for noisy data and a larger number of data points. Moreover, Algorithm 3 is
faster than GB search. If combined with GB search, the performance of
Algorithm 3 improves further, but at the expense of computational time.

##  VIII Conclusion

In this paper, we a characterization of minimality and uniquenss of LSSs in
innovation form, and we presented a realization algorithm for computing
minimal LSS in innovation form. Using this realization algorithm, we
formulated a system identification algorithm proven to be statistically
consistent. The latter algorithm was evaluated on a numerical example and
demonstrated promising performance, both in terms of runtime complexity and
estimation accuracy.

## References

  * [1] A. R. P. Andriën and D. J. Antunes.  Near-optimal map estimation for markov jump linear systems using relaxed dynamic programming.  IEEE L-CSS, 4(4):815–820, 2020.
  * [2] L. Bako, G. Mercère, and S. Lecoeuche.  On-line structured subspace identification with application to switched linear systems.  International Journal of Control, 82(8):1496–1515, 2009.
  * [3] M. P. Balenzuela, A. G. Wills, C. Renton, and B. Ninness.  Parameter estimation for jump markov linear systems.  Automatica, 135:109949, 2022.
  * [4] P. Bilingsley.  Probability and measure.  Wiley, 1986.
  * [5] A. Chiuso and G. Picci.  Consistency analysis of some closed-loop subspace identification methods.  Automatica, 41(3):377–391, 2005.
  * [6] E. Cinquemani, R. Porreca, G. Ferrari-Trecate, and J. Lygeros.  A general framework for the identification of jump markov linear systems.  In IEEE CDC, 2007.
  * [7] O.L.V. Costa, M.D. Fragoso, and R.P. Marques.  Discrete-Time Markov Jump Linear Systems.  Springer Verlag, 2005.
  * [8] P. Cox, M. Petreczky, and R. Tóth.  Towards efficient maximum likelihood estimation of LPV-SS models.  Automatica, 97(9):392–403, 2018.
  * [9] P. B. Cox.  Towards efficient identification of linear parameter-varying state-space models.  PhD thesis, Eindhoven Univ. of Technology, 2018.
  * [10] P. B. Cox and R. Tóth.  Linear parameter-varying subspace identification: A unified framework.  Automatica, 123:109296, 2021.
  * [11] P. den Boef, P. B. Cox, and R. Tóth.  LPVcore: MATLAB toolbox for LPV modelling, identification and control.  IFAC SYSID, 2021.
  * [12] A. Garulli, S. Paoletti, and A. Vicino.  A survey on switched and piecewise affine system identification.  In IFAC SYSID, 2012.
  * [13] E. J. Hannan and M. Deistler.  The Statistical Theory of Linear Systems.  Classics in Applied Mathematics. SIAM, 1988.
  * [14] B. Hanzon.  Identifiability, recursive identification and spaces of linear dynamical systems, volume 63,64 of CWI Tract.  Stichting Mathematische Centrum, 1989.
  * [15] T. Katayama.  Subspace Methods for System Identification.  Springer-Verlag, 2005.
  * [16] F. Lauer and G. Bloch.  Hybrid System Identification: Theory and Algorithms for Learning Switching Models, volume 478 of LNCIS.  Springer, 2019.
  * [17] A. Lindquist and G. Picci.  Linear Stochastic Systems: A Geometric Approach to Modeling, Estimation and Identification.  Springer, 2015.
  * [18] L. Ljung.  System Identification: Theory for the user (2nd Ed.).  PTR Prentice Hall., Upper Saddle River, USA, 1999.
  * [19] M. Mejari and M. Petreczky.  Consistent and computationally efficient estimation for stochastic lpv state-space models: realization based approach.  In IEEE CDC, 2019.
  * [20] M. Mejari and M. Petreczky.  Realization and identification algorithm for stochastic LPV state-space models with exogenous inputs.  In IFAC LPVS, Eindhoven, Netherlands, 2019.
  * [21] M. Petreczky.  Realization theory of linear hybrid systems.  In Hybrid Dynamical Systems: Observation and control, Lecture Notes in Control and Information Sciences. Springer-Verlag, 2015.
  * [22] M. Petreczky and L. Bako.  On the notion of persistence of excitation for linear switched systems.  Nonlinear Analysis: Hybrid Systems, 48:101308, 2023.
  * [23] M. Petreczky, L. Bako, and J.H. van Schuppen.  Realization theory for discrete-time linear switched systems.  Automatica, 49(11):3337–3344, 2013.
  * [24] M. Petreczky, R. Tóth, and G. Mercére.  Realization theory for LPV state-space representations with affine dependence.  IEEE Transactions on Automatic Control, 62(9):4667–4674, 2017.
  * [25] M. Petreczky and R. Vidal.  Realization theory of stochastic jump-markov linear systems.  In IEEE CDC, 2007.
  * [26] M. Petreczky and R. Vidal.  Realizat:ion theory for a class of stochastic bilinear systems.  IEEE TAC, 63(1):69–84, 2018.
  * [27] E. Rouphael, M. Mejari, M. Petreczky, and L. Belkoura.  Minimal covariance realization and system identification algorithm for a class of stochastic linear switched systems with i.i.d. switching, 2024.  ArXiv 2403.14259.
  * [28] E. Rouphael, M. Mejari, M. Petreczky, and L. Belkoura.  Towards stochastic realization theory for generalized linear switched systems with inputs: decomposition into stochastic and deterministic components and existence and uniqueness of innovation form.  Submitted to CSS Control Systems Letters, 2024.  2403.11012.
  * [29] E. Rouphael, M. Petreczky, and L.Belkoura.  On minimal LPV state-space representations in innovation form: an algebraic characterization.  In IEEE CDC, 2022.
  * [30] T. Sarkar, A. Rakhlin, and M. Dahleh.  Nonparametric system identification of stochastic switched linear systems.  In IEEE CDC, 2019.
  * [31] Zh. Sun and Sh. S. Ge.  Switched linear systems : control and design.  Springer, London, 2005.
  * [32] R. Tóth.  Modeling and identification of linear parameter-varying systems.  In LNCIS, Vol. 403, Heidelberg, 2010. Springer.
  * [33] P. van Overschee and B. De Moor.  Subspace Identification for Linear Systems.  Kluwer Academic Publishers, 1996.
  * [34] C. van Putten and J. H. van Schuppen.  Invariance properties of the conditional independence relation.  Ann. Probab., 13(3):934–945, 08 1985.
  * [35] V. Verdult and M. Verhaegen.  Subspace identification of multivariable linear parameter-varying systems.  Automatica, 38(5):805–814, 2002.
  * [36] V. Verdult and M. Verhaegen.  Subspace identification of piecewise linear systems.  In 43rd IEEE CDC, 2004.

###  -A Proof of Lemma 1

In order to present the proof we need some preliminaries definitions,
notations and lemmas.

######  Notation 3 (autonomous sLPSS)

As discuss in Notation 1, a sLPSS is noted as
$\mathcal{S}=(\\{A_{\sigma},B_{\sigma},K_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,D,F,\mathbf{v})$.
However, if $\mathcal{S}$ depend only on the noise, i.e., $B_{\sigma}=0$ and
$D=0$ for all $\sigma\in\Sigma$, then the sLSS is called autonomous (with no
inputs) and abbreviated as asLSS. We will note an asLPSS as
$\mathcal{S}=(\\{A_{\sigma},K_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,F)$ and which
has the following form:

$\mathcal{S}_{as}\left\\{\begin{aligned}
&\mathbf{x}(t+1)=A_{\bm{\theta}(t)}\mathbf{x}(t)+K_{\bm{\theta}(t)}\mathbf{v}(t)\\\
&\textbf{y}(t)=C\mathbf{x}(t)+F\mathbf{v}(t)\end{aligned}\right.$ (31)

where $A_{\sigma}\\!\\!\in\\!\\!\mathbb{R}^{n_{x}\times
n_{x}},K_{\sigma}\\!\in\\!\mathbb{R}^{n_{x}\times n_{n}}$,
$\sigma\\!\in\\!\Sigma=\\{1,\ldots,n_{\mu}\\}$,
$C\\!\in\\!\mathbb{R}^{n_{y}\times n_{x}}$, $F\\!\in\\!\mathbb{R}^{n_{y}\times
n_{n}}$, and $\mathbf{x}$, $\mathbf{v}$, y, $\bm{\theta}$ are the stochastic
state, noise, output and switching processes. The process $\bm{\theta}$ takes
values in the set of discrete states $\Sigma$. We also say that
$\mathcal{S}_{as}$ is a realization of $(\mathbf{y},\bm{\theta})$.

Assume that $\mathcal{S}$ of the form (1) is a sLSS of
$(\mathbf{y},\mathbf{u},\bm{\theta})$444By Assumption of Lemma 15, such a LSS
representation exists.. Recall from Notation 2 the Hilber-space
$\mathcal{H}_{1}$. Denote by $\mathcal{H}_{t,+}^{\mathbf{v}}$ and
$\mathcal{H}_{t}^{\mathbf{v}}$ the closed-subspace of $\mathcal{H}_{1}$
generated by the components of
$\\{\mathbf{z}^{\mathbf{v}}_{w}\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{v}(t)\\}$
and $\\{\mathbf{z}^{\mathbf{v}}_{w}\\}_{w\in\Sigma^{+}}$ respectively.

###### Lemma 6

For all $\sigma\in\Sigma$, $\mathbf{v}(t)$ is orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{u}}$.

###### Proof:

[Proof of Lemma 6] Define
$\mathbf{r}(t):=\begin{bmatrix}\mathbf{v}^{T}(t)&\mathbf{u}^{T}(t)\end{bmatrix}^{T}$.
By the definition of a sLSS, $\mathbf{r}$ is a ZMWSII and it is a white noise
process w.r.t. $\bm{\mu}$. Moreover, $\mathbf{v}(t)$ is the upper $n_{n}$
block of $\mathbf{r}(t)$. Since $\mathbf{r}$ is a white noise w.r.t.
$\bm{\mu}$, $E[\mathbf{r}(t)(\mathbf{z}^{\mathbf{r}}_{w}(t))^{T}]=0$, and
$\frac{1}{\sqrt{p_{\sigma}}}E[\mathbf{v}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]$
is the lower-left block of that latter matrix, and hence it is also zero. From
Definition 3 it follows that $E[\mathbf{v}(t)(\mathbf{u}(t))^{T}]=0$. ∎

###### Lemma 7

For any $w\in\Sigma^{+}$, the components of $\mathbf{z}_{w}^{\mathbf{v}}(t)$
are orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$.

###### Proof:

[Proof of Lemma 7] Since
$\mathbf{r}(t):=\begin{bmatrix}\mathbf{v}(t)^{T}&\mathbf{u}(t)^{T}\end{bmatrix}^{T}$
is a ZMWSII process, from [26, Lemma 7] and because $\mathbf{r}(t)$ is a white
noise, it follows that
$E[\mathbf{z}_{w}^{\mathbf{r}}(t)(\mathbf{z}^{\mathbf{r}}_{v}(t))^{T}]=E[\mathbf{z}_{\sigma}^{\mathbf{r}}(t)(\mathbf{z}^{\mathbf{r}}_{\sigma}(t))^{T}]$
if $v=w=\sigma s$ for all $v,w,s\in\Sigma^{+}$, $\sigma\in\Sigma$, and
$E[\mathbf{z}_{w}^{\mathbf{r}}(t)(\mathbf{z}^{\mathbf{r}}_{v}(t))^{T}]=0$ for
any other case.

Since $E[\mathbf{z}_{w}^{\mathbf{v}}(t)(\mathbf{z}^{\mathbf{u}}_{v}(t))^{T}]$
is the upper right block of
$E[\mathbf{z}_{w}^{\mathbf{r}}(t)(\mathbf{z}^{\mathbf{r}}_{v}(t))^{T}]$, it
follows that
$E[\mathbf{z}_{w}^{\mathbf{v}}(t)(\mathbf{z}^{\mathbf{u}}_{v}(t))^{T}]=0$ if
$v\neq w$ and
$E[\mathbf{z}_{w}^{\mathbf{v}}(t)(\mathbf{z}^{\mathbf{u}}_{w}(t))^{T}]=E[\mathbf{z}_{\sigma}^{\mathbf{v}}(t)(\mathbf{z}^{\mathbf{u}}_{\sigma}(t))^{T}]=\frac{1}{p_{\sigma}}E[\mathbf{u}(t-1)\mathbf{v}(t-1)\bm{\mu}_{\sigma}^{2}(t-1)]$,
where $\sigma$ is the first letter of $w$, and from Definition 3, it follows
that the latter expectation is zero. That is,
$E[\mathbf{z}_{w}^{\mathbf{v}}(t)(\mathbf{z}^{\mathbf{u}}_{v}(t))^{T}]=0$ for
all $v\in\Sigma^{+}$.

Finally, as $\mathbf{r}(t)$ is a white noise process w.r.t. $\bm{\mu}$, it
follows that $E[\mathbf{z}_{w}^{\mathbf{r}}(t)(\mathbf{r}(t))^{T}]=0$, and
since $E[\mathbf{z}_{w}^{\mathbf{v}}(t)(\mathbf{u}(t))^{T}]$ is the upper
right block of $E[\mathbf{z}_{w}^{\mathbf{r}}(t)(\mathbf{r}(t))^{T}]$, it then
follows that $E[\mathbf{z}_{w}^{\mathbf{v}}(t)(\mathbf{u}(t))^{T}]=0$. Since
$\mathbf{z}_{w}^{\mathbf{v}}(t)$ is orthogonal to the components of the random
variables which generate $\mathcal{H}_{t,+}^{\mathbf{u}}$, the statement of
the lemma follows for $k=0$.

∎

Let us denote by $\mathcal{H}_{t}^{\mathbf{u}}$, the closed subspace generated
by the components of
$\\{\mathbf{z}^{\mathbf{u}}_{w}(t)\\}_{w\in\Sigma^{+}}$.It is clear that
$\mathcal{H}_{t}^{\mathbf{u}}\subseteq\mathcal{H}_{t,+}^{\mathbf{u}}$.

###### Lemma 8

The components of $\mathbf{x}^{d}(t)$ belong to $\mathcal{H}_{t}^{\mathbf{u}}$
and

$\mathbf{x}^{d}(t)=\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}A_{w}B_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t),$ (32)

where the right-hand side of converges in the mean square sense.

###### Proof:

[Proof of Lemma 8] It is clear from the definition that the components of
$\mathbf{x}^{d}(t)$ belong to $\mathcal{H}_{t,+}^{\mathbf{u}}$. Since
$\mathbf{x}(t)\\!\\!=\\!\\!\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}A_{w}\left(K_{\sigma}\mathbf{z}^{\mathbf{v}}_{\sigma
w}(t)+B_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)\right)$ and the fact
that the map $z\mapsto E_{l}[z\mid M]$ (where $z\in\mathcal{H}_{1}$) is a
continuous linear operator for any closed subspace $M$, it follows that

$\begin{split}\mathbf{x}^{d}(t)=\sum_{w\in\Sigma^{*},\sigma\in\Sigma}&\sqrt{p_{\sigma
w}}A_{w}\left(K_{\sigma}E_{l}[\mathbf{z}^{\mathbf{v}}_{\sigma w}(t)\mid
H_{t,+}^{\mathbf{u}}]\right.\\\
&\left.+B_{\sigma}E_{l}[\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)\mid
H_{t,+}^{\mathbf{u}}]\right).\end{split}$ (33)

From Lemma 7 it follows that, $E_{l}[\mathbf{z}^{\mathbf{v}}_{\sigma w}(t)\mid
H_{t,+}^{\mathbf{u}}]=0$, and since the components of
$\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)$ belong to
$\mathcal{H}_{t,+}^{\mathbf{u}}$, it follows that
$E_{l}[\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)\mid
H_{t,+}^{\mathbf{u}}]=\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)$, hence (33)
implies (32). Since the components of $\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)$
belong to $\mathcal{H}_{t}^{\mathbf{u}}$, it follows that the components of
the right-hand side of (32) belongs to $\mathcal{H}_{t}^{\mathbf{u}}$ and
hence the components of $\mathbf{x}^{d}(t)$ belong to
$\mathcal{H}_{t}^{\mathbf{u}}$. Note that, the convergence of the right-hand
side of (32) in the mean square sense follows from the convergence of the
series $\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}A_{w}\left(K_{\sigma}\mathbf{z}^{\mathbf{v}}_{\sigma
w}(t)+B_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)\right)$. ∎

###### Lemma 9

The components of $\mathbf{x}^{s}(t)$ belong to
$\mathcal{H}_{t}^{\mathbf{v}}$, they are orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{u}}$, and

$\mathbf{x}^{s}(t)=\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}A_{w}K_{\sigma}\mathbf{z}^{\mathbf{v}}_{\sigma w}(t),$ (34)

where the right-hand side converges in the mean-square sense.

###### Proof:

[Proof of Lemma 9] From (32),
$\mathbf{x}^{s}(t)=\mathbf{x}(t)-\mathbf{x}^{d}(t)$ and
$\mathbf{x}(t)\\!\\!=\\!\\!\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}A_{w}\left(K_{\sigma}\mathbf{z}^{\mathbf{v}}_{\sigma
w}(t)+B_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)\right)$, it follows that
(34) holds and that its right-hand side converges in the mean square sense.
From Lemma 7, it follows that for any $w\in\Sigma^{+}$, the components of
$\mathbf{z}_{w}^{\mathbf{v}}(t)$ are orthogonal to
$\mathcal{H}_{t+k,+}^{\mathbf{u}}$, hence all the summands of the infinite
series of (34) are orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$. ∎

######  Lemma 10 (Decomposition of $\mathbf{y}$)

Assume that there exists a sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$ of
the form (1) and that $(\mathbf{y},\mathbf{u},\bm{\theta})$ satisfy Assumption
1. Define

$\displaystyle\mathbf{x}^{d}(t)=E_{l}[\mathbf{x}(t)\mid\\{\mathbf{z}^{\mathbf{u}}_{w}(t)\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{u}(t)\\}]$
(35) $\displaystyle\mathbf{x}^{s}(t)=\mathbf{x}(t)-\mathbf{x}^{d}(t)$ (36)

Then

$\displaystyle\mathcal{S}_{d}\left\\{\begin{aligned}
&{\mathbf{x}}^{d}(t+1)=\sum_{i=1}^{n_{\mu}}(A_{i}{\mathbf{x}}^{d}(t)\\!+\\!B_{i}{\mathbf{u}}(t))\bm{\mu}_{i}(t),\\\
&{{\mathbf{y}}}^{d}(t)=C{\mathbf{x}}^{d}(t)\\!+\\!D{\mathbf{u}}(t),\end{aligned}\right.$
(37) $\displaystyle\mathcal{S}_{s}\left\\{\begin{aligned}
&{\mathbf{x}}^{s}(t+1)=\sum_{i=1}^{n_{\mu}}(A_{i}{\mathbf{x}}^{s}(t)\\!+\\!K_{i}{\mathbf{v}}(t))\bm{\mu}_{i}(t),\\\
&{{\mathbf{y}}}^{s}(t)=C{\mathbf{x}}^{s}(t)\\!+\\!F{\mathbf{v}}(t),\end{aligned}\right.$
(38)

and $S_{s}$ is an asLSS realization of $(\mathbf{y}^{s},\bm{\theta})$ with the
noise process $\mathbf{v}$, $S_{d}$ is an asLSS realization of
$(\mathbf{y}^{d},\bm{\theta})$ with the noise process $\mathbf{u}$. In
particular,

$\displaystyle{\mathbf{y}}_{d}(t)=\sum_{\sigma\in\Sigma,w\in\Sigma^{*}}\sqrt{p_{\sigma
w}}CA_{w}B_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)+D\mathbf{u}(t)$ (39)
$\displaystyle{\mathbf{y}}_{s}(t)=\sum_{\sigma\in\Sigma,w\in\Sigma^{*}}\sqrt{p_{\sigma
w}}CA_{w}K_{\sigma}\mathbf{z}^{\mathbf{v}}_{\sigma w}(t)+F\mathbf{v}(t)$ (40)

###### Proof:

[Proof of Lemma 10: Decomposition of $\mathbf{y}$] It follows, from the Lemmas
6, 7, 8, and Lemma 9 that,

$\begin{split}&\mathbf{x}^{d}(t+1)=E_{l}[\mathbf{x}(t+1)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]=\\\
&=\sum_{\sigma\in\Sigma}(A_{\sigma}E_{l}[\mathbf{x}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]\\\
&+B_{\sigma}E_{l}[\mathbf{u}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]+K_{\sigma}E_{l}[\mathbf{v}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}])\end{split}$
(41)

Note that,
$\mathbf{u}(t)\bm{\mu}_{\sigma}(t)=\sqrt{p_{\sigma}}\mathbf{z}^{\mathbf{u}}_{\sigma}(t+1)$,
hence the components of $\mathbf{u}(t)\bm{\mu}_{\sigma}(t)$ belong to
$\mathcal{H}_{t+1,+}^{\mathbf{u}}$ and therefore

$E_{l}[\mathbf{u}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]=\mathbf{u}(t)\bm{\mu}_{\sigma}(t)$

We claim that,

$E_{l}[\mathbf{x}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]=\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}.$

Since $\mathbf{x}(t)=\mathbf{x}^{d}(t)+\mathbf{x}^{s}(t)$, it follows that
$\mathbf{x}(t)\bm{\mu}_{\sigma}(t)=\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}(t)+\mathbf{x}^{s}(t)\bm{\mu}_{\sigma}(t)$.

From [26, Lemma 9] and Lemma 8–9, it follows that

$\begin{split}&\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}(t)=\sum_{w\in\Sigma^{*},\sigma^{{}^{\prime}}\in\Sigma}\sqrt{p_{\sigma^{{}^{\prime}}w\sigma}}A_{w}B_{\sigma^{{}^{\prime}}}\mathbf{z}^{\mathbf{u}}_{\sigma^{{}^{\prime}}w\sigma}(t+1)\\\
&\mathbf{x}^{s}(t)\bm{\mu}_{\sigma}(t)=\sum_{w\in\Sigma^{*},\sigma^{{}^{\prime}}\in\Sigma}\sqrt{p_{\sigma^{{}^{\prime}}w\sigma}}A_{w}K_{\sigma^{{}^{\prime}}}\mathbf{z}^{\mathbf{v}}_{\sigma^{{}^{\prime}}w\sigma}(t+1)\\\
\end{split}$ (42)

From Lemma 7, it follows that
$\mathbf{z}^{\mathbf{v}}_{\sigma^{{}^{\prime}}w\sigma}(t+1)$ is orthogonal to
$\mathcal{H}_{t+1,+}^{\mathbf{u}}$ for all $w\in\Sigma^{+}$,
$\sigma^{{}^{\prime}},\sigma\in\Sigma$, and hence
$\mathbf{x}_{s}(t)\bm{\mu}_{\sigma}(t)$ is also orthogonal to
$\mathcal{H}_{t+1,+}^{\mathbf{u}}$. Moreover, since the components of
$\mathbf{z}^{\mathbf{u}}_{\sigma^{{}^{\prime}}w\sigma}(t+1)$ belong to
$\mathcal{H}_{t+1,+}^{\mathbf{u}}$, it follows that
$\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}(t)$ belongs to
$\mathcal{H}_{t+1,+}^{\mathbf{u}}$. Hence,

$\begin{split}&E_{l}[\mathbf{x}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]\\\
&=E_{l}[\mathbf{x}^{s}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]+E_{l}[\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]\\\
&=E_{l}[\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]=\mathbf{x}^{d}(t)\bm{\mu}_{\sigma}(t).\end{split}$

Finally, from Lemma 7, it follows that
$\mathbf{v}(t)\bm{\mu}_{\sigma}(t)=\sqrt{p_{\sigma}}\mathbf{z}_{\sigma}^{\mathbf{v}}(t+1)$
is orthogonal to $\mathcal{H}_{t+1,+}^{\mathbf{u}}$, and hence

$E_{l}[\mathbf{v}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]=0.$

By collecting all these facts, we can show that

$\begin{split}&\mathbf{x}^{d}(t+1)=E_{l}[\mathbf{x}(t+1)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]=\\\
&=\sum_{\sigma\in\Sigma}(A_{\sigma}E_{l}[\mathbf{x}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]+\\\
&B_{\sigma}E_{l}[\mathbf{u}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}]+K_{\sigma}E_{l}[\mathbf{v}(t)\bm{\mu}_{\sigma}(t)\mid\mathcal{H}_{t+1,+}^{\mathbf{u}}])\\\
=&\sum_{\sigma\in\Sigma}(A_{\sigma}\mathbf{x}^{d}(t)+B_{\sigma}\mathbf{u}(t))\end{split}$

That is, the first equation of (37) holds.

As to the second equation of (37), we know from [29], that

$\begin{split}&\mathbf{y}^{d}(t)=E_{l}[\mathbf{y}(t)\mid\mathcal{H}_{t,+}^{\mathbf{u}}]=\\\
&=CE_{l}[\mathbf{x}(t)\mid\mathcal{H}_{t,+}^{\mathbf{u}}]+DE_{l}[\mathbf{u}(t)\mid\mathcal{H}_{t,+}^{\mathbf{u}}]+E_{l}[\mathbf{v}(t)\mid\mathcal{H}_{t,+}^{\mathbf{u}}].\end{split}$

Since the components of $\mathbf{u}(t)$ are among the generators of
$\mathcal{H}_{t,+}^{\mathbf{u}}$, and by Lemma 6, $\mathbf{v}(t)$ is
orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$,
$E_{l}[\mathbf{v}(t)\mid\mathcal{H}_{t,+}^{\mathbf{u}}]=0$ and
$E_{l}[\mathbf{u}(t)\mid\mathcal{H}_{t,+}^{\mathbf{u}}]=\mathbf{u}(t)$, and
hence the second equation of (37) holds.

From $\mathbf{y}^{s}(t)=\mathbf{y}(t)-\mathbf{y}^{d}(t)$,
$\mathbf{x}^{s}(t)=\mathbf{x}(t)-\mathbf{x}^{d}(t)$ and (37), (38) follows.

Finally, notice that as $\sum_{\sigma\in\sigma}p_{\sigma}A_{\sigma}\otimes
A_{\sigma}$ is stable and $\mathbf{u}$ is a white noise w.r.t. $\bm{\mu}$,
$\mathcal{S}_{d}$ is a well-defined asLSS with the noise process $\mathbf{u}$.
Moreover, (37) implies that it is a realization of
$(\mathbf{y}^{d},\bm{\theta})$ with the noise process $\mathbf{u}$. Similarly,
since $\sum_{\sigma\in\sigma}p_{\sigma}A_{\sigma}\otimes A_{\sigma}$ is stable
and $\mathbf{v}$ is a white noise w.r.t. $\bm{\mu}$, it follows that
$\mathcal{S}_{s}$ is as asLSS and from (38) it follows that $\mathcal{S}_{s}$
is a realization of $(\mathbf{y}^{s},\bm{\theta})$.

To conclude, (39) and (40) follow from the fact that $\mathcal{S}_{d}$ is a
realization of $(\mathbf{y}^{d},\bm{\theta})$ and $\mathcal{S}_{s}$ is a
realization of $(\mathbf{y}^{s},\bm{\theta})$, by using [26, Lemma 1].

∎

###### Lemma 11

The components of $\mathbf{y}^{s}(t),\mathbf{z}^{\mathbf{y}^{s}}_{v}(t)$,
$\mathbf{e}^{s}(t)$, $\mathbf{z}^{\mathbf{e}^{s}}_{v}(t)$, $v\in\Sigma^{+}$
belong to $\mathcal{H}_{t,+}^{\mathbf{v}}$.

###### Proof:

[Proof of Lemma 11] Recall (34) from Lemma 9, as
$\mathbf{y}^{s}(t)=C\mathbf{x}^{s}(t)+\mathbf{v}(t)$, the components of
$\mathbf{y}^{s}(t)$ belong to $\mathcal{H}_{t,+}^{\mathbf{v}}$. In particular,
from [26, Lemma 11], it follows that the coordinates of
$\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)$ belong to
$\mathcal{H}_{t,+}^{\mathbf{v}}$ and hence,
$\mathcal{H}_{t}^{\mathbf{y}^{s}}\subseteq\mathcal{H}_{t}^{\mathbf{v}}$. Since
$\mathbf{e}^{s}(t)=\mathbf{y}^{s}(t)-E_{l}[\mathbf{y}^{s}(t)\mid\mathcal{H}_{t}^{\mathbf{y}^{s}}]$,
it follows that the components of $\mathbf{e}^{s}(t)$ belong to
$\mathcal{H}_{t,+}^{\mathbf{v}}$. Since
$\mathbf{z}_{v}^{\mathbf{v}}(t)=\mathbf{z}_{v1}^{\mathbf{v}}(t+1)$,
$\mathbf{v}(t)=\mathbf{z}_{1}^{\mathbf{v}}(t+1)$, it follows that
$\mathcal{H}_{t,+}^{\mathbf{v}}\subseteq\mathcal{H}_{t+1}^{\mathbf{v}}$ and
from [26, Lemma 11] it follows that the components of
$\mathbf{z}_{v}^{\mathbf{e}^{s}}(t)$ belong to
$\mathcal{H}_{t}^{\mathbf{v}}\subseteq\mathcal{H}_{t,+}^{\mathbf{v}}$. ∎

###### Lemma 12

If there exists a sLSS $(\mathbf{y},\mathbf{u},\bm{\theta})$ , then the
components of
$\mathbf{y}^{s}(t),\mathbf{z}^{\mathbf{y}^{s}}_{v}(t),\mathbf{e}^{s}(t),\mathbf{z}^{\mathbf{e}^{s}}_{v}(t)$,
$v\in\Sigma^{+}$ are orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$. i.e., for
all $v,w\in\Sigma^{+}$

###### Proof:

[Proof of Lemma 12] From Lemma 6–7 and by noticing that
$\mathbf{v}(t)=\mathbf{v}(t)\bm{\mu}_{1}(t)$ it follows that the elements of
$\mathcal{H}_{t,+}^{\mathbf{v}}$ are orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{u}}$. Hence, the coordinates of $\mathbf{u}(t)$,
$\mathbf{z}_{w}^{\mathbf{u}}(t)$, $w\in\Sigma^{+}$ are orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{v}}$. Since the coordinates of
$\mathbf{y}^{s}(t),\mathbf{z}^{\mathbf{y}^{s}}_{v}(t),\mathbf{e}^{s}(t),\mathbf{z}^{\mathbf{e}^{s}}_{v}(t)$
belong to $\mathcal{H}_{t,+}^{\mathbf{v}}$, it follows that the coordinates of
$\mathbf{y}^{s}(t),\mathbf{z}^{\mathbf{y}^{s}}_{v}(t),\mathbf{e}^{s}(t),\mathbf{z}^{\mathbf{e}^{s}}_{v}(t)$
are orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$. Since
$\mathcal{H}_{t,+}^{\mathbf{u}}$ is generated by the coordinates of
$\mathbf{u}(t)$, $\mathbf{z}_{w}^{\mathbf{u}}(t)$, $w\in\Sigma^{+}$, the
statement of the lemma follows. ∎

###### Lemma 13

Assume that there exists an sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$.
Then, $(\\{A_{\sigma},B_{\sigma}\\},C,D,\mathbf{u})$ is an asLSS of
$(\mathbf{y}^{d},\bm{\theta})$, if and only if the dLSS
$(\\{A_{\sigma},B_{\sigma}\\}_{\sigma\in\Sigma},C,D)$ is a realization of
$\Psi_{\mathbf{u},\mathbf{y}}$ and $\sum_{i=1}^{n_{\mu}}p_{i}A_{i}\otimes
A_{i}$ is stable.

###### Proof:

[Proof of Lemma 13]

Part(1) Assume that
$(\\{A_{\sigma},B_{\sigma}\\}_{\sigma\in\Sigma},C,D,\mathbf{u})$ is an asLSS
of $(\mathbf{y}^{d},\bm{\theta})$. Then $\sum_{i=1}^{n_{\mu}}p_{i}A_{i}\otimes
A_{i}$ is stable by definition of asLSS. From Lemma 12 it follows that that
the he components of $\mathbf{y}^{s}(t)$ is orthogonal to
$\mathcal{H}^{\mathbf{u}}_{t,+}$, that is,
$E[\mathbf{y}^{s}(t)(\mathbf{z}^{\mathbf{u}}_{w}(t))^{T}]=0$ and
$E[\mathbf{y}^{s}(t)(\mathbf{u}(t))^{T}]=0$. Thus,
$E[\mathbf{y}(t)(\mathbf{z}^{\mathbf{u}}_{w}(t))^{T}]=E[\mathbf{y}^{d}(t)(\mathbf{z}^{\mathbf{u}}_{w}(t))^{T}]$,
$E[\mathbf{y}(t)(\mathbf{u}(t))^{T}]=E[\mathbf{y}^{d}(t)(\mathbf{u}(t))^{T}]$.
Hence, From (32) of Lemma 8 and the fact that
$\mathbf{y}^{d}(t)=C\mathbf{x}^{d}(t)+D\mathbf{u}(t)$ it follows that

$\begin{split}&E[\mathbf{y}^{d}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]=\\\
&\sum_{s\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
s}}CA_{s}B_{\sigma}E[\mathbf{z}^{\mathbf{u}}_{\sigma
s}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]\\!\\!+\\!\\!DE[\mathbf{u}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]\\\
&=\sqrt{p_{\sigma
s}}CA_{s}B_{\sigma}\Lambda_{\mathbf{u}}=\Psi_{\mathbf{y},\mathbf{u}}(\sigma
s)\Lambda_{u}\sqrt{p_{\sigma s}}\end{split}$

This follows, as $\mathbf{u}$ is white noise process,
$E[\mathbf{u}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]=0$ and
$E[\mathbf{z}^{\mathbf{u}}_{\sigma
s}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]=\Lambda_{\mathbf{u}}$ if $\sigma
s=w$, otherwise $E[\mathbf{z}^{\mathbf{u}}_{\sigma
s}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}]=0$. Similarly,
$E[\mathbf{y}^{d}(t)\mathbf{u}(t)]=D\Lambda_{\mathbf{u}}=\Psi_{\mathbf{y},\mathbf{u}}(\epsilon)\Lambda_{\mathbf{u}}$.
Hence, $\Psi_{\mathbf{y},\mathbf{u}}=CA_{\sigma}B_{\sigma}$, i.e.,
$(\\{A_{\sigma},B_{\sigma}\\}_{\sigma\in\Sigma},C,D)$ is a realization of
$\Psi_{\mathbf{y},\mathbf{u}}$.

Part(2) Assume that $\\{(A_{\sigma},B_{\sigma}\\}_{\sigma\in\Sigma},C,D)$ is a
dLSS realization of $\Psi_{\mathbf{y},\mathbf{u}}$ and
$\sum_{i=1}^{n_{\mu}}p_{i}A_{i}\otimes A_{i}$ is stable. Consider the asLSS
$\mathcal{S}=(\\{A_{\sigma},B_{\sigma}\\}_{\sigma\in\Sigma},C,D,\mathbf{u})$.
$\mathcal{S}$ is a well-defined asLSS, as $\mathbf{u}$ is a white noise w.r.t.
$\bm{\mu}$.

Let $\tilde{\mathbf{x}}$ be the unique trajectory of $\mathcal{S}$, and let
$\tilde{\mathbf{y}}$ be the unique output of $\mathcal{S}$. From [26] it
follows that

$\tilde{\mathbf{y}}(t)=\sum_{N=0}^{\infty}\sum_{\tiny\begin{matrix}|w|=N\\\
w\in\Sigma^{*}\end{matrix}}\sum_{\sigma\in\Sigma}\sqrt{p_{\sigma
w}}CA_{w}B_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t)+D\mathbf{u}(t)$

using $\Psi_{\mathbf{y},\mathbf{u}}(\sigma s)=CA_{s}B_{\sigma}$, it follows
that

$\tilde{\mathbf{y}}(t)=\sum_{N=0}^{\infty}\sum_{\tiny\begin{matrix}|w|=N\\\
w\in\Sigma^{*}\end{matrix}}\sum_{\sigma\in\Sigma}\sqrt{p_{\sigma
w}}\Psi_{\mathbf{y},\mathbf{u}}(\sigma s)\mathbf{z}^{\mathbf{u}}_{\sigma
w}(t)+\Psi_{\mathbf{y},\mathbf{u}}(\epsilon)\mathbf{u}(t)$ (43)

By assumption, there exists a sLSS
$\mathcal{S}=(\\{A_{\sigma}^{\prime},B_{\sigma}^{\prime}\\}_{\sigma\in\Sigma},C^{\prime},D^{\prime},\mathbf{u})$,
where $\mathcal{S}$ is a realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$.
By Lemma 10,
$\mathcal{S}_{d}=(\\{A_{\sigma}^{\prime},B_{\sigma}^{\prime}\\}_{\sigma\in\Sigma},C^{\prime},D^{\prime},\mathbf{u})$
is an asLSS realization of $(\mathbf{y}^{d},\bm{\theta})$. Hence, by Part(1)
of the lemma,
$(\\{A_{\sigma}^{\prime},B_{\sigma}^{\prime}\\}_{\sigma\in\Sigma},C^{\prime},D^{\prime})$
is a dLSS realization of $\Psi_{\mathbf{y},\mathbf{u}}$, where
$\Psi_{\mathbf{y},\mathbf{u}}(\sigma
s)=C^{\prime}A_{s}^{\prime}B_{\sigma}^{\prime}$ and
$\Psi_{\mathbf{y},\mathbf{u}}(\epsilon)=D^{\prime}$.

But from [26], it follows that

$\mathbf{y}^{d}(t)=\sum_{N=0}^{\infty}\sum_{\tiny\begin{matrix}|w|=N\\\
w\in\Sigma^{*}\end{matrix}}\sum_{\sigma\in\Sigma}\sqrt{p_{\sigma
w}}C^{\prime}A_{w}^{\prime}B_{\sigma}^{\prime}\mathbf{z}^{\mathbf{u}}_{\sigma
w}(t)+D^{\prime}\mathbf{u}(t)$
$\mathbf{y}^{d}(t)=\sum_{\tiny{N=0}}^{\infty}\sum_{\tiny\begin{matrix}|w|=N\\\
w\in\Sigma^{*}\end{matrix}}\sum_{\sigma\in\Sigma}\sqrt{p_{\sigma
w}}\Psi_{\mathbf{y},\mathbf{u}}(\sigma s)\mathbf{z}^{\mathbf{u}}_{\sigma
w}(t)+\Psi_{\mathbf{y},\mathbf{u}}(\epsilon)\mathbf{u}(t)$ (44)

Hence, by combining (43) and (44) it follows that
$\tilde{\mathbf{y}}(t)=\mathbf{y}^{d}(t)$. That is,
$\mathcal{S}=(\\{A_{\sigma},B_{\sigma}\\}_{\sigma\in\Sigma},C,D,\mathbf{u})$
is a realization of $(\mathbf{y},\bm{\theta})$. ∎

###### Proof:

[Proof of Lemma 1] Assume the sLSS of the form (1) is a realization of
$(\mathbf{y},\mathbf{u},\bm{\theta})$. From Lemma 10, it follows that
$\mathcal{S}_{s}$ defined in (38) is an asLSS realization of
$(\mathbf{y}^{s},\bm{\theta})$, and $\mathcal{S}_{d}$ is an asLSS realization
of $(\mathbf{y}^{d},\bm{\theta})$ as defined in (37). Consider the dLSS
$\mathscr{S}_{s}$ as defined in (11). From [26, Lemma 4] it follows that, in
the terminology of [26], the $\mathcal{R}=(\\{\sqrt{p_{i}}A_{i}\\},[G_{i}\dots
G_{n}],C)$ is a recognizable representation of the formal power series

$s\mapsto\begin{bmatrix}\Psi_{\mathbf{y}^{s}}(1s)\dots\Psi_{\mathbf{y}^{s}}(n_{\mu}s)\end{bmatrix}$
(45)

Note that $\mathcal{R}$ corresponds to Hence by [26, Lemma 4],

$\Psi_{\mathbf{y}^{s}}(\sigma s)=\sqrt{p_{w}}CA_{s}G_{\sigma}$ (46)

where $w=\sigma s\in\Sigma^{+}$, and $\Psi_{\mathbf{y}^{s}}(w)=I$ for
$w=\epsilon$. From Lemma 13 it follows that
$(\\{A_{\sigma},B_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,D)$ is a dLSS realization
of $\Psi_{\mathbf{y},\mathbf{u}}$. Hence

$\Psi_{\mathbf{y},\mathbf{u}}=\left\\{\begin{array}[]{ll}CA_{s}B_{\sigma}&w=\sigma
s,\,\sigma\in\Sigma,\,s\in\Sigma^{*}\\\ D&w=\epsilon\end{array}\right.$ (47)

Combining (46) and (47) results in having

$\displaystyle M_{\mathbf{y},\mathbf{u}}(\sigma s)$
$\displaystyle=\begin{bmatrix}\sqrt{p_{\sigma
s}}\Psi_{\mathbf{y},\mathbf{u}}(\sigma s)&\Psi_{\mathbf{y}^{s}}(\sigma
s)\end{bmatrix}$ (48) $\displaystyle=\sqrt{p_{\sigma
s}}CA_{s}\begin{bmatrix}B_{\sigma}&G_{\sigma}\end{bmatrix}$ $\displaystyle
M_{\mathbf{y},\mathbf{u}}(\epsilon)$
$\displaystyle=\begin{bmatrix}\sqrt{p_{\sigma
s}}\Psi_{\mathbf{y},\mathbf{u}}(\epsilon)&\Psi_{\mathbf{y}^{s}}(\epsilon)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}D&I\end{bmatrix}$

That is, $\mathscr{S}_{s}$ is a realization of $M_{\mathbf{y},\mathbf{u}}$. ∎

###  -B Proof of Lemma 2

Assume that $\mathcal{S}$ of the form (1) is a sLSS of
$(\mathbf{y},\mathbf{u},\bm{\theta})$ 555By Assumption of Lemma 15, such a LSS
representation exists.. Recall from Notation 2 the Hilber-space
$\mathcal{H}_{1}$. Denote by $\mathcal{H}_{t,+}^{\mathbf{v}}$ and
$\mathcal{H}_{t}^{\mathbf{v}}$ the closed-subspace of $\mathcal{H}_{1}$
generated by the components of
$\\{\mathbf{z}^{\mathbf{v}}_{w}\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{v}(t)\\}$
and $\\{\mathbf{z}^{\mathbf{v}}_{w}\\}_{w\in\Sigma^{+}}$ respectively.

###### Lemma 14

$\mathbf{r}=\begin{bmatrix}(\mathbf{e}^{s})^{T}&\mathbf{u}^{T}\end{bmatrix}^{T}$
is a white noise process w.r.t. $\bm{\mu}$ and
$E[\mathbf{e}^{s}(t)\mathbf{u}^{T}(t)\bm{\mu}_{\sigma}^{2}(t)]=0$ for all
$\sigma\in\Sigma$.

###### Proof:

[Proof of Lemma 14] In order to prove the statement of the lemma, we will
first show that $\mathbf{r}$ is a ZMWSII, by showing that $\mathbf{r}$
satisfies the conditions of Definition 1 one by one. First, we show that the
processes $\mathbf{r}(t),\mathbf{z}_{w}^{\mathbf{r}}(t),w\in\Sigma^{+}$ is
zero mean, square integrable.

By assumption $\mathbf{u}$ is a white noise process w.r.t. $\bm{\mu}$. From
the fact that $\hat{\mathcal{S}}_{s}$ is an asLSS of
$(\mathbf{y}^{s},\bm{\theta})$ it follows that $\mathbf{e}^{s}$ is also a
white noise process w.r.t. $\bm{\mu}$. In particular, $\mathbf{u}$, $\bm{\mu}$
are both also ZWMSII and thus
$\mathbf{e}^{s}(t),\mathbf{u}(t),\mathbf{z}_{w}^{\mathbf{e}^{s}}(t),\mathbf{z}_{w}^{\mathbf{u}}(t)$,
$w\in\Sigma^{+}$ is zero mean, square integrable. From this it follows that
$\mathbf{r}(t)$ and $\mathbf{z}_{w}^{\mathbf{r}}(t)$ are zero mean and square
integrable.

From Lemma 11 it follows that the components $\mathbf{e}^{s}(t)$ belongs to
$\mathcal{H}_{t,+}^{\mathbf{v}}(t)$, where $\mathbf{v}$ is a noise process of
an asLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$. From the definition of a
sLSS it follows that
$\mathbf{w}=\begin{bmatrix}\mathbf{v}^{T}&\mathbf{u}^{T}\end{bmatrix}^{T}$ is
ZMWSII. Hence, with the notation of Definition 1, the $\sigma$-algebras
$\mathcal{F}_{t}^{\mathbf{w}}$ and $\mathcal{F}_{t}^{\bm{\mu},+}$ are
conditionally independent w.r.t. $\mathcal{F}_{t}^{\bm{\mu},-}$. From the fact
that $\mathbf{e}^{s}(t)$ belongs to $\mathcal{H}_{t,+}^{\mathbf{v}}$ it
follows that $\mathbf{e}^{s}(t)$ is measurable with respect to the
$\sigma$-algebra generated by
$\\{\mathbf{v}(t)\\}\cup\\{\mathbf{z}_{v}^{\mathbf{v}}(t)\\}_{v\in\Sigma^{+}}$
and the latter $\sigma$-algebra is a subset of
$\mathcal{F}^{\mathbf{w}}_{t}\lor\mathcal{F}^{\bm{\mu},-}_{t}$, where for two
$\sigma$-algebras $\mathcal{F}_{i}$, $i=1,2$,
$\mathcal{F}_{1}\lor\mathcal{F}_{2}$ denotes the smallest $\sigma$-algebra
generated by the $\sigma$-algebras $\mathcal{F}_{1},\mathcal{F}_{2}$. That is,
$\mathbf{e}^{s}(t)$ is measurable w.r.t. the $\sigma$ algebra
$\mathcal{F}^{\mathbf{w}}_{t}\lor\mathcal{F}^{\bm{\mu},-}_{t}$. Since
$\mathcal{F}^{\mathbf{w}}_{t}$ and $\mathcal{F}^{\bm{\mu},+}$ are
conditionally independent w.r.t. $\mathcal{F}^{\bm{\mu},-}_{t}$, from [34,
Proposition 2.4] it follows that
$\mathcal{F}^{\mathbf{w}}_{t}\lor\mathcal{F}^{\bm{\mu},-}_{t}$ and
$\mathcal{F}^{\bm{\mu},+}_{t}$ are conditionally independent w.r.t.
$\mathcal{F}^{\bm{\mu},-}_{t}$, and as
$\mathcal{F}^{\mathbf{r}}_{t}\subseteq\mathcal{F}^{\mathbf{w}}_{t}\lor\mathcal{F}^{\bm{\mu},-}_{t}$,
it follows that $\mathcal{F}^{\mathbf{r}}_{t}$ and $\mathcal{F}^{\bm{\mu},+}$
are conditionally independent w.r.t. $\mathcal{F}^{\bm{\mu},-}_{t}$.

Finally, we show that
$\mathbf{r}(t),\mathbf{z}_{w}^{\mathbf{r}}(t),w\in\Sigma^{+}$ are jointly
wide-sense stationary, i.e., for all $s,t,\in\mathbb{Z}$, $s\leq t$, $v,w\in
\Sigma^{+}$,

$\displaystyle
E\left[\mathbf{r}(t)(\mathbf{z}^{\mathbf{r}}_{w}(s))^{T}\right]$
$\displaystyle=E\left[\mathbf{r}(t-s)(\mathbf{z}^{\mathbf{r}}_{w}(0))^{T}\right],$
$\displaystyle E\left[\mathbf{r}(t)(\mathbf{r}(s))^{T}\right]$
$\displaystyle=E\left[\mathbf{r}(t-s)(\mathbf{r}(0))^{T}\right],$
$\displaystyle
E\left[\mathbf{z}^{\mathbf{r}}_{w}(t)(\mathbf{z}^{\mathbf{r}}_{v}(s))^{T}\right]$
$\displaystyle=E\left[\mathbf{z}^{\mathbf{r}}_{w}(t-s)(\mathbf{z}^{\mathbf{r}}_{v}(0))^{T}\right].$

We will show only the last equality, the proofs of the first two are
analogous. Indeed, from Lemma 14 and from the fact that $\mathbf{e}^{s}$,
$\mathbf{u}$ are ZMWSII it follows the processes
$\mathbf{e}^{s}(t),\mathbf{z}_{w}^{\mathbf{e}^{s}}(t),w\in\Sigma^{+}$ are
jointly wide-sense stationary and the processes
$\mathbf{u}(t),\mathbf{z}_{w}^{\mathbf{u}}(t),w\in\Sigma^{+}$ are also jointly
wide-sense stationary. From Lemma 14 it follows that
$E\left[\mathbf{z}^{\mathbf{e}^{s}}_{w}(t+k)(\mathbf{z}_{v}^{\mathbf{u}}(s+k))^{T}\right]$,
and hence

$\displaystyle
E\left[\mathbf{z}^{\mathbf{r}}_{w}(t)(\mathbf{z}^{\mathbf{r}}_{v}(s))^{T}\right]=$
$\displaystyle=\mathrm{diag}(E\left[\mathbf{z}^{\mathbf{e}^{s}}_{w}(t)(\mathbf{z}_{v}^{\mathbf{e}^{s}}(s))^{T}\right],E\left[\mathbf{z}^{\mathbf{u}}_{w}(t)(\mathbf{z}_{v}^{\mathbf{u}}(s))^{T}\right])$
$\displaystyle=\mathrm{diag}(E\left[\mathbf{z}^{\mathbf{e}^{s}}_{w}(t-s)(\mathbf{z}_{v}^{\mathbf{e}^{s}}(0))^{T}\right],E\left[\mathbf{z}^{\mathbf{u}}_{w}(t-s)(\mathbf{z}_{v}^{\mathbf{u}}(0))^{T}\right])$
$\displaystyle=E\left[\mathbf{z}^{\mathbf{r}}_{w}(t-s)(\mathbf{z}^{\mathbf{r}}_{v}(0))^{T}\right].$

That is, we have shown that $\mathbf{r}$ satisfies all the conditions of
Definition 1.

Next we show that $\mathbf{r}$ is a white noise process w.r.t. $\bm{\mu}$,
i.e., $E[\mathbf{r}(t)(\mathbf{z}^{\mathbf{r}}_{w}(t))^{T}]=0$ for all
$w\in\Sigma^{+}$. From Lemma 14 it follows that

$\begin{split}&E\left[\mathbf{r}(t)(\mathbf{z}^{\mathbf{r}}_{w}(t))^{T}\right]=\\\
&\mathrm{diag}(E\left[\mathbf{e}^{s}(t)(\mathbf{z}_{w}^{\mathbf{e}^{s}}(t))^{T}\right],E\left[\mathbf{u}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}\right])\end{split}$

Notice $\mathbf{e}_{s}$ is a white noise process w.r.t. $\bm{\mu}$, since it
is the noise process of $\hat{\mathcal{S}}_{s}$, and the latter is an asLSS of
$(\mathbf{y}^{s},\bm{\theta})$, and hence
$E\left[\mathbf{e}_{s}(t)(\mathbf{z}_{w}^{\mathbf{e}_{s}}(t)\right]=0$.
Furthermore, $\mathbf{u}$ is a white noise process w.r.t. $\bm{\mu}$ by
assumption, so
$E\left[\mathbf{u}(t)(\mathbf{z}_{w}^{\mathbf{u}}(t))^{T}\right]=0$. Hence,
$E\left[\mathbf{r}(t)(\mathbf{z}^{\mathbf{r}}_{w}(t))^{T}\right]=0$.

It is left to show that
$E[\mathbf{e}^{s}(t)\mathbf{u}^{T}(t)\bm{\mu}_{\sigma}^{2}(t)]=0$ for all
$\sigma\in\Sigma$. Notice that
$E[\mathbf{e}^{s}(t)\mathbf{u}^{T}(t)\bm{\mu}_{\sigma}^{2}(t)]=E[\mathbf{z}^{\mathbf{e}^{s}}_{\sigma}(t+1)(\mathbf{z}^{\mathbf{u}}_{\sigma}(t+1))^{T}]p_{\sigma}$
by definition, and from Lemma 14 it follows that
$E[\mathbf{z}^{\mathbf{e}^{s}}_{\sigma}(t+1)(\mathbf{z}^{\mathbf{u}}_{\sigma}(t+1))^{T}]=0$.
∎

###### Lemma 15

Assume that there exists a sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$ and
that the following holds:

  * •

$\hat{\mathcal{S}}_{d}=(\\{\hat{A}_{i},\hat{B}_{i}\\}_{i=1}^{n_{\mu}},\hat{C},\hat{D},\mathbf{u})$
is a asLSS of $(\mathbf{y}^{d},\bm{\theta})$ 666Note that the input process of
$\mathcal{S}_{d}$ is $\mathbf{u}$.,

  * •

$\hat{\mathcal{S}}_{s}=(\\{\hat{A}_{i},\hat{K}_{i}\\}_{i=1}^{n_{\mu}},\hat{C},I_{n_{y}},\mathbf{e}^{s})$
is asLSS of $(\mathbf{y}^{s},\bm{\theta})$ in _forward innovation form_ ,
i.e., the $\mathbf{e}^{s}$ is the innovation process of $\mathbf{y}^{s}$.

Then
$\hat{\mathcal{S}}=(\\{\hat{A}_{i},\hat{K}_{i},\hat{B}_{i}\\}_{i=1}^{n_{\mu}},\hat{C},\hat{D},\mathbf{e}^{s})$
is a sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$. Moreover, the innovation
process $\mathbf{e}^{s}$ satisfies

$\mathbf{e}^{s}(t)=\mathbf{y}(t)-E_{l}[\mathbf{y}(t)\mid\\{\mathbf{z}^{\mathbf{y}}_{w}(t),\mathbf{z}^{\mathbf{u}}_{w}(t)\\}_{w\in\Sigma^{+}}\cup\\{\mathbf{u}(t)\\}]$
(49)

###### Proof:

[Proof of Lemma 15] From Lemma 14 it follows that the noise process
$\mathbf{e}^{s}$ and the input $\mathbf{u}$ satisfy the condition of
$E[\mathbf{e}^{s}(t)(\mathbf{u}(t))^{T}\bm{\mu}_{\sigma}^{2}(t)]=0$,
$\sigma\in\Sigma$. Since $\hat{\mathcal{S}}_{s}$ and $\hat{\mathcal{S}}_{d}$
are both asLSS, it follows that
$\sum_{i=1}^{n_{\mu}}p_{i}\hat{A}_{i}\otimes\hat{A}_{i}$ is stable. Hence
$\hat{\mathcal{S}}$ satisfies the conditions of a sLSS and it has a unique
state process $\hat{\mathbf{x}}$. Finally, let $\hat{\mathbf{x}}^{s}$ and
$\hat{\mathbf{x}}^{d}$ be the unique state processes of
$\hat{\mathcal{S}}_{s}$ and $\hat{\mathcal{S}}_{d}$ respectively. We claim
that $\hat{\mathbf{x}}(t)=\hat{\mathbf{x}}^{d}(t)+\hat{\mathbf{x}}^{s}(t)$.
Indeed, from (10), it follows that

$\begin{split}&\hat{\mathbf{x}}^{d}(t)=\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}\hat{A}_{w}\hat{B}_{\sigma}\mathbf{z}^{\mathbf{u}}_{\sigma w}(t),\\\
&\hat{\mathbf{x}}^{s}(t)=\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}\hat{A}_{w}\hat{K}_{\sigma}\mathbf{z}^{\mathbf{e}^{s}}_{\sigma
w}(t),\end{split}$

from which it follows that

$\hat{\mathbf{x}}^{d}(t)+\hat{\mathbf{x}}^{s}(t)=\sum_{w\in\Sigma^{*},\sigma\in\Sigma}\sqrt{p_{\sigma
w}}\hat{A}^{d}_{w}\begin{bmatrix}\hat{K}_{\sigma}&\hat{B}_{\sigma}\end{bmatrix}\mathbf{z}^{\mathbf{r}}_{\sigma
w}(t),$ (50)

with
$\mathbf{r}(t)=\begin{bmatrix}(\mathbf{e}^{s}(t))^{T}&(\mathbf{u}(t))^{T}\end{bmatrix}^{T}$.
Then (10) applied to $\mathbf{v}=\mathbf{r}$ means that the right-hand side of
(50) equals $\hat{\mathbf{x}}$. Finally, from
$\hat{\mathbf{x}}(t)=\hat{\mathbf{x}}^{s}(t)+\hat{\mathbf{x}}^{d}(t)$ and the
fact that
$\mathbf{y}^{d}(t)=\hat{C}\hat{\mathbf{x}}^{d}(t)+\hat{D}\mathbf{u}(t)$ (as
$\hat{\mathcal{S}}_{d}$ is an asLSS of $(\mathbf{y}^{d},\bm{\theta})$) and
$\mathbf{y}^{s}(t)=\hat{C}\hat{\mathbf{x}}^{s}(t)+\mathbf{e}^{s}(t)$ (as
$\hat{\mathcal{S}}_{s}$ is an asLSS of $(\mathbf{y}^{s},\bm{\theta})$), it
follows that
$\mathbf{y}(t)=\hat{C}\hat{\mathbf{x}}(t)+\hat{D}\mathbf{u}(t)+\mathbf{e}^{s}(t)$,
i.e., $\hat{\mathcal{S}}$ is a sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$.
∎

###### Proof:

[Proof of Lemma 2] Using the terminology of [26], consider the recognizable
representation
$\mathcal{R}=(n_{x},\\{A_{\sigma}\\}_{\sigma\in\Sigma},\begin{bmatrix}G_{1}\dots
G_{n_{\mu}}\end{bmatrix},C)$. $\mathcal{R}$ is the representation of the
formal power series defined in (45). $\mathcal{R}$ is stable and observable
since the observability of the representations is equivalent to the
observability of the dLSS
$(\\{A_{i},\begin{bmatrix}B_{i}&G_{i}\end{bmatrix}\\}_{i=1}^{n_{\mu}},C,D)$.
The the existence of the limit $K_{i}=\lim_{I\rightarrow\infty}K_{i}^{I}$
follows from [26, Lemma 21], by noticing that the proof of [26, Lemma 21]
requires only the observability of the representation $\mathcal{R}$. Moreover,
from [26, Lemma 21], it follows that the asLSS
$(\\{A_{i},K_{i}\\}_{i=1}^{n_{\mu}},C,I,\mathbf{e}^{s})$ is a realization of
$(\mathbf{y}^{s},\bm{\theta})$. From Lemma 13 it follows that the asLSS
$(\\{A_{i},B_{i}\\}_{i=1}^{n_{\mu}},C,D,\mathbf{u})$ is a realization of
$(\mathbf{y}^{d},\bm{\theta})$. hence by Lemma 15 it follows that the sLSS
$(\\{A_{i},B_{i},K_{i}\\}_{i=1}^{n_{\mu}},C,D,I,\mathbf{e}^{s})$ is a
realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$. ∎

###  -C Proof of Theorem 1

###### Lemma 16

If $(\mathbf{y},\mathbf{u},\bm{\theta})$ has an sLSS realization, and
$\mathscr{S}=(\\{\hat{A}_{\sigma},\hat{B}_{\sigma}\\}_{\sigma\in\Sigma},\hat{C},\hat{D})$
is a minimal dLSS realization of $M_{\mathbf{y},\mathbf{u}}$ then
$\mathscr{S}$ is observable and
$\sum_{i=1}^{n_{\mu}}p_{i}\hat{A}_{i}\otimes\hat{A}_{i}$ is stable.

###### Proof:

[Proof of Lemma 16] Let
$\mathscr{S}=(\\{\hat{A}_{\sigma},\hat{B}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\hat{C},\hat{D},\mathbf{u})$
be any dLSS realization of $M_{\mathbf{y},\mathbf{y}}$. Consider the formal
series
$\Psi:s\mapsto\begin{bmatrix}M_{\mathbf{y},\mathbf{u}}(1s)&\dots&M_{\mathbf{y},\mathbf{u}}(n_{\mu}s)\end{bmatrix}$,
then
$R_{\mathscr{S}^{\prime}}=(\\{\hat{A}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\begin{bmatrix}\begin{bmatrix}\hat{B}_{1}&\hat{G}_{1}\end{bmatrix}&\dots&\begin{bmatrix}\hat{B}_{n_{\mu}}&\hat{G}_{n_{\mu}}\end{bmatrix}\end{bmatrix},\hat{C})$
is a recognisable representation of $\Psi$ if and only if
$\mathscr{S}^{\prime}$ is a realization of $M_{\mathbf{y},\mathbf{u}}$. It is
easy to see that $R_{\mathscr{S}}$ is reachable (observable), if and only if
$\mathscr{S}^{\prime}$ satisfies the reachability and observability rank
conditions of [24]. Hence, $\mathscr{S}$ is minimal, if and only if
$R_{\mathscr{S}}$ is minimal.

We will proceed to show that $R_{\mathscr{S}}$ is stable in the sence of [26],
i.e.,
$\sum_{\sigma=1}^{n_{\mu}}p_{\sigma}\hat{A}_{\sigma}\otimes\hat{A}_{\sigma}$
is stable. To this end, let
$\mathcal{S}=(\\{{A}_{\sigma},{B}_{\sigma},K_{\sigma}\\}_{\sigma=1}^{n_{\mu}},{C},{D},F,\mathbf{v})$
be an sLSS realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$ of the form of
(1). Then by Definition 3,
$\sum_{\sigma=1}^{n_{\mu}}p_{\sigma}{A}_{\sigma}\otimes{A}_{\sigma}$ is
stable. Consider the dLSS $\mathscr{S}_{\mathcal{S}}$ associated with
$\mathcal{S}$. By Lemma 1, $\mathscr{S}_{\mathcal{S}}$ is a realization of
$M_{\mathbf{y},\mathbf{u}}$. Let us consider the formal series $\Psi$ defined
above and let us consider the recognisable representation
$R_{\mathscr{S}_{\mathcal{S}}}=(\\{\sqrt{p_{\sigma}}A_{\sigma}\\}_{\sigma\in\Sigma},\tilde{G},{C})$
where
$\tilde{G}=\begin{bmatrix}\begin{bmatrix}\sqrt{p_{i}}{B}_{1}&{G}_{1}\end{bmatrix}&\dots&\begin{bmatrix}\sqrt{p_{n_{\mu}}}{B}_{n_{\mu}}&{G}_{n_{\mu}}\end{bmatrix}\end{bmatrix}$.
With the same argument as above, it is easy ti see that
$R_{\mathscr{S}_{\mathcal{S}}}$ is a representation of $\Psi$. Since
$R_{\mathscr{S}_{\mathcal{S}}}$ is stable in the term of [26] (as
$\sum_{i=1}^{n_{\mu}}\sqrt{p_{\sigma}}{A}_{\sigma}\otimes\sqrt{p_{\sigma}}{A}_{\sigma}=\sum_{i=1}^{n_{\mu}}p_{\sigma}{A}_{\sigma}\otimes{A}_{\sigma}$
is stable), then by [26, Theorem 6], $\Psi$ is square summable, i.e.,

$\sum_{N=0}^{\infty}\sum_{\tiny\begin{matrix}|w|=N\\\
w\in\Sigma^{*}\end{matrix}}\|\Psi(w)\|_{2}^{2}<+\infty$

From [26, Theorem 6] it follows that any minimal representation of $\Psi$ is
stable. In particular, as $\mathscr{S}$ is minimal, hence $R_{\mathscr{S}}$ is
minimal, therefore, $R_{\mathscr{S}}$ is stable, i.e.,
$\sum_{\sigma=1}^{n_{\mu}}p_{\sigma}\hat{A}_{\sigma}\otimes\hat{A}_{\sigma}$
is stable. The observability of $\mathscr{S}$ follows from its minimality. ∎

That is, finding an asLSS of $(\mathbf{y}^{d},\bm{\theta})$ boils down to
finding a dLSS realization of $\Psi_{\mathbf{u},\mathbf{y}}$.

More precisely, consider sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$ of the
form (1) and consider the associated asLSS $\mathcal{S}_{s}$ of
$(\textbf{y}^{s},\bm{\theta})$ as defined in Lemma 10, (38).

######  Lemma 17 (Lemma 4 from [26])

The dLSS

$(\\{\sqrt{p_{\sigma}}A_{\sigma},G_{\sigma}\\}_{\sigma\in\Sigma},C,I)$

is a realization of $\Psi_{\mathbf{y}}$.

###### Proof:

[Proof of Theorem 1] Part 1. Assume that $\mathcal{S}$ is span-reachable and
observable sLSS of $(\mathbf{y},\mathbf{u},\bm{\theta})$, then by definition
the dLSS $\mathscr{S}_{\mathcal{S}}$ is also span-reachable and observable,
and hence it is a minimal realization of $M_{\mathbf{y};\mathbf{u}}$ by [24].
Let $\mathcal{S}^{{}^{\prime}}$ be another sLSS of
$(\mathbf{y},\mathbf{u},\bm{\theta})$. Then by Lemma 1 the dLSS
$\mathscr{S}_{\mathcal{S}^{{}^{\prime}}}$ associated with
$\mathcal{S}^{{}^{\prime}}$ has the same sub-Markov parameters. Hence, since
$\mathscr{S}_{\mathcal{S}}$ is minimal dimensional, the dimension of
$\mathscr{S}_{\mathcal{S}}$ cannot exceed that of
$\mathscr{S}_{\mathcal{S}^{{}^{\prime}}}$, and since the dimension of a sLSS
is the same as that of the dLSS associated with it, it follows that the
dimension of $\mathcal{S}$ cannot exceed that of $\mathcal{S}^{{}^{\prime}}$.

Part 2. To this end, notice that the dLSS associated with $\mathcal{S}_{m}$ is
$\mathscr{S}_{m}$, and since $\mathscr{S}_{m}$ is minimal, it is span-
reachable and observable, hence $\mathcal{S}_{m}$ is span-reachable and
observable, and hence minimal. The rest of the statement follows from Lemma 1.

Part 3 Let Let
$\mathcal{S}=(\\{A_{\sigma},B_{\sigma},K_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,D,F,\mathbf{v})$
be a sLSS realization of $(\mathbf{y},\mathbf{u},\bm{\theta})$. From Lemma 1,
we define
$\mathscr{S}_{\mathcal{S}}=(\\{\sqrt{p_{\sigma}}A_{\sigma},\begin{bmatrix}\sqrt{p_{\sigma}}B_{\sigma}&G_{\sigma}\end{bmatrix}\\}_{\sigma=1}^{n_{\mu}},C,\begin{bmatrix}D&I_{n_{y}}\end{bmatrix}),$
the associated dLSS, which is a realization of $M_{\mathbf{y},\mathbf{u}}$.
From $\mathscr{S}_{\mathcal{S}}$ as an input of Algorithm 1 and from Lemma 3,
we can get a minimal dLSS
$\hat{\mathscr{S}}=(\\{\hat{A}_{\sigma},\hat{B}_{\sigma}\\}_{\sigma\in\Sigma},\hat{C},\hat{D})$
realization $M_{\mathbf{y},\mathbf{u}}$. We know, from Lemma 16, that
$\sum_{i=1}^{n_{\mu}}p_{i}\hat{A}_{i}\otimes\hat{A}_{i}$ is stable. It
follows, from part 2 of Theorem 1, that the associated sLSS
$\hat{\mathcal{S}}_{\mathscr{S}}$ is in innovation form. What remains is to
prove that the latter sLSS is minimal. Note, from equations (16), (18) and
(19), that the associated dLSS
$\hat{\mathscr{S}}_{\hat{\mathcal{S}}_{\hat{\mathscr{S}}}}$ and the minimal
dLSS $\hat{\mathscr{S}}$ are the same when $N\rightarrow\infty$. It follows
that $\hat{\mathcal{S}}_{\hat{\mathscr{S}}}$ is minimal because his associated
dLSS is minimal. Therefore, if $(\mathbf{y},\mathbf{u},\bm{\theta})$ has a
sLSS realization, then there exists a minimal sLSS realization in innovation
form.

Part 4. Let
$\mathcal{S}=(\\{A_{\sigma},B_{\sigma},K_{\sigma}\\}_{\sigma=1}^{n_{\mu}},C,D,F,\mathbf{v})$
and let
$\widetilde{\mathcal{S}}=(\\{\tilde{A}_{\sigma},\tilde{B}_{\sigma},\tilde{K}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\tilde{C},\tilde{D},\tilde{F},\mathbf{v})$
be of the form (1), and assume that $\mathcal{S}$ and
$\widetilde{\mathcal{S}}$ are minimal sLSS of
$(\mathbf{y},\mathbf{u},\bm{\mu})$ in forward innovation form. Let
$\mathscr{S}_{\mathcal{S}}=(\\{\sqrt{p_{i}}A_{i},\begin{bmatrix}G_{i},\sqrt{p_{i}}B_{i}\end{bmatrix}\\}_{i=0}^{n_{\mu}},C,D)$
and
$\mathscr{S}_{\widetilde{\mathcal{S}}}=(\\{\sqrt{p_{i}}\tilde{A}_{i},\begin{bmatrix}\tilde{G}_{i}&\sqrt{p_{i}}\tilde{B}_{i}\end{bmatrix}\\}_{i=0}^{n_{\mu}},\tilde{C},\tilde{D})$
be the corresponding dLSSs. By Lemma 1, $\mathscr{S}_{\mathcal{S}}$ and
$\mathscr{S}_{\widetilde{\mathcal{S}}}$ are realizations of the same sub-
Markov function, they are both span-reachable and observable. Hence,
$\tilde{D}=D$, and by [24] there exists a non-singular matrix $T$ such that
(20) holds, except for $\tilde{K}_{i}Q_{i}=TK_{i}$, $i=1,\ldots,n_{\mu}$. In
order to show the latter, notice that $\tilde{G}_{i}=TG_{i}$,
$i=1,\ldots,n_{\mu}$ holds, and use the the proof of [26, Part (ii), Theorem
2], by applying it to the sLSS
$\mathcal{S}_{as}=(\\{A_{i},K_{i}\\}_{i=1}^{n_{\mu}},C,\mathbf{e}^{s})$ and
$\widetilde{\mathcal{S}}=(\\{\tilde{A}_{i},\tilde{K}_{i},\\}_{i=1}^{n_{\mu}},\tilde{C},I,\mathbf{e}^{s})$.
More precisely, $T$ satisfies the properties of the matrix $T$ defined in the
proof of [26, Part (ii), Theorem 2]. Then, the rest of the proof of [26, Part
(ii), Theorem 2] can be repeated verbatim. ∎

###  -D Proof of Lemma 4

###### Proof:

By definition [28], we know that
$\mathbf{y}(t)=\mathbf{y}^{s}(t)+\mathbf{y}^{d}(t)$. From that, we have
$\mathbf{z}^{\mathbf{y}}_{w}(t)=\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)+\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)$.
From [26, Lemma 11], we know that the entries of $\mathbf{y}^{d}(t)$ and the
entries of $\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)$ are in
$\mathcal{H}_{t,+}^{\mathbf{u}}$. From Lemma 12, it follows that
$\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)$ is orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{u}}$ and hence to
$\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)$. That is,
$T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}=E\left[\mathbf{y}(t)\mathbf{z}^{\mathbf{y}}_{w}(t)\right]=E\left[\mathbf{y}^{s}(t)\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)\right]+E\left[\mathbf{y}^{s}(t)\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)\right]+E\left[\mathbf{y}^{d}(t)\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)\right]+E\left[\mathbf{y}^{d}(t)\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)\right]$.
And since $\mathbf{y}^{s}(t)$ is orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{u}}$ and the entries of
$\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)$ belong to
$\mathcal{H}_{t,+}^{\mathbf{u}}$, then
$E\left[\mathbf{y}^{s}(t)\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)\right]=0$.
Similary, since the components of $\mathbf{y}^{d}(t)$ are in
$\mathcal{H}_{t,+}^{\mathbf{u}}$ and $\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)$ is
orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$ by Lemma 12, then
$E\left[\mathbf{y}^{d}(t)\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)\right]=0$. Then
$\Lambda_{w}^{\textbf{y},\textbf{y}}=E\left[\mathbf{y}(t)\mathbf{z}^{\mathbf{y}}_{w}(t)\right]=E\left[\mathbf{y}^{s}(t)\mathbf{z}^{\mathbf{y}^{s}}_{w}(t)\right]+E\left[\mathbf{y}^{d}(t)\mathbf{z}^{\mathbf{y}^{d}}_{w}(t)\right]=\Lambda_{w}^{\textbf{y}^{s},\textbf{y}^{s}}+\Lambda_{w}^{\textbf{y}^{d},\textbf{y}^{d}}$.

Also, note that
$\Lambda_{w}^{\mathbf{y}^{d},\mathbf{u}}=E\left[\mathbf{y}^{d}(t)\mathbf{z}^{\mathbf{u}}_{w}(t)\right]=E\left[(\mathbf{y}(t)-\mathbf{y}^{s}(t))\mathbf{z}^{\mathbf{u}}_{w}(t)\right]=E\left[\mathbf{y}(t)\mathbf{z}^{\mathbf{u}}_{w}(t)\right]-E\left[\mathbf{y}^{s}(t)\mathbf{z}^{\mathbf{u}}_{w}(t)\right]=E\left[\mathbf{y}(t)\mathbf{z}^{\mathbf{u}}_{w}(t)\right]$
since $\mathbf{y}^{s}(t)$ is orthogonal to $\mathcal{H}_{t,+}^{\mathbf{u}}$
and hence to $\mathbf{z}^{\mathbf{u}}_{w}(t)$. Then
$\Lambda_{w}^{\mathbf{y}^{d},\mathbf{u}}=\Lambda_{w}^{\mathbf{y},\mathbf{u}}$.

Finally, note that
$T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}=E\left[\mathbf{z}^{\mathbf{y}}_{\sigma}(t)(\mathbf{z}^{\mathbf{y}}_{\sigma}(t))^{T}\right]=E\left[\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t)(\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t))^{T}\right]+E\left[\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t)(\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t))^{T}\right]+E\left[\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t)(\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t))^{T}\right]+E\left[\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t)(\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t))^{T}\right]$.
By [26, Lemma 11], the components of $\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t)$
belong to $\mathcal{H}_{t,+}^{\mathbf{u}}$ and
$\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t)$ is orthogonal to
$\mathcal{H}_{t,+}^{\mathbf{u}}$ hence
$E\left[\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t)(\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t))^{T}\right]=E\left[\mathbf{z}^{\textbf{y}^{d}}_{\sigma}(t)(\mathbf{z}^{\textbf{y}^{s}}_{\sigma}(t))^{T}\right]=0$.
Subsequently,
$T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}=T^{\textbf{y}^{d},\textbf{y}^{d}}_{\sigma,\sigma}+T^{\textbf{y}^{s},\textbf{y}^{s}}_{\sigma,\sigma}$.
Then equation (26) of Lemma 4 holds. Equation (27) of Lemma 4 follows from
[26, Lemma 4]. ∎

###  -E Proof of Corollary 1

###### Proof:

Let us recall the equation (15).

$M_{\mathbf{y},\mathbf{u}}(w)=\begin{cases}\begin{bmatrix}\Lambda^{\textbf{y}^{d},\textbf{u}}_{w}Q_{\textbf{u}}^{-1},&\Lambda_{w}^{\textbf{y}^{s}}\end{bmatrix}&w\neq\epsilon\vspace{0.2cm}\\\
\begin{bmatrix}\Lambda^{\textbf{y}^{d},\textbf{u}}_{\epsilon}Q_{\textbf{u}}^{-1},&I_{n_{y}}\end{bmatrix}&w=\epsilon\end{cases}$

From Lemma 3, it follows that
$\mathscr{S}_{d}=(\\{\tilde{A}_{i},\tilde{B}_{i}\\}_{i=1}^{n_{\mu}},\tilde{C},\tilde{D})$
is a minimal dLSS realization of the covariance sequence
$\Psi=\Lambda^{\textbf{y}^{d},\textbf{u}}_{\epsilon}Q_{\textbf{u}}^{-1}$. Then
from Lemma 4, it follows that (27) holds, and hence, step 4. and step 4. of
Algorithm 2 result in computing
$\left\\{M_{\mathbf{y},\mathbf{u}}(w)\right\\}_{w\in\mathcal{L}_{\alpha,\beta}}$.
Then by Lemma 3, $\mathscr{S}=(\\{\hat{A}_{i},\left[\hat{B}_{i}\
\hat{G}_{i}\right]\\}_{i=1}^{n_{\mu}},\hat{C},\hat{D})$ is a minimal dLSS
realization of $M_{\mathbf{y},\mathbf{u}}$. From part 2 of Theorem 1, it
follows that the LSS $\tilde{\mathcal{S}}$ is a minimal sLSS realization of
$(\mathbf{y},\mathbf{u},\bm{\theta})$ in innovation form. The last statement
of the Corollary 1 follows from Lemma 3. ∎

###  -F Proof of Lemma 5

###### Proof:

The matrices of the sLSS returned by Algorithm 3 are continuous functions of
the entries of the Hankel matrices $\mathcal{H}^{M_{\alpha,\beta},N}$,
$\mathcal{H}^{M_{\sigma,\alpha,\beta},N}$,$\mathcal{H}_{\alpha,\sigma}^{M,N}$
and $\mathcal{H}_{\beta}^{M,N}$. As $N$ goes to infinity, the empirical
covariances
$T^{\textbf{y},\mathbf{u}}_{\epsilon,w,N}$,$T^{\textbf{y},\mathbf{y}}_{\epsilon,w,N}$
and $T^{\textbf{y},\textbf{y}}_{\sigma,\sigma,N}$ go, respectively, to
$\Lambda^{\textbf{y},\mathbf{u}}_{w}$,$\Lambda^{\textbf{y},\mathbf{y}}_{w}$
and $T^{\textbf{y},\textbf{y}}_{\sigma,\sigma}$. In other words, the empirical
covariances are equal to the true covariances when $N\rightarrow+\infty$. In
this case, the Hankel matrices computed from the empiraqual covariances are
equal to the true Hankel matrices $\mathcal{H}^{M_{\alpha,\beta}}$,
$\mathcal{H}^{M_{\sigma,\alpha,\beta}}$,$\mathcal{H}_{\alpha,\sigma}^{M}$ and
$\mathcal{H}_{\beta}^{M}$. And because of the continuous relationship in
Algorithm 1, the matrices
$\\{\tilde{A}_{\sigma}^{N},\tilde{B}^{N}_{\sigma},\tilde{K}^{N,\mathcal{I}}_{\sigma},\tilde{Q}^{N,\mathcal{I}}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\tilde{C}^{N},\tilde{D}^{N}$
returned by Algorithm 3 are equal to true matrices
$\\{\tilde{A}_{\sigma},\tilde{B}_{\sigma},\tilde{K}_{\sigma},\tilde{Q}_{\sigma}\\}_{\sigma=1}^{n_{\mu}},\tilde{C},\tilde{D}$.
Then, note also that the returned sLSS is minimal beacause the dLSS is
returned by Algorithm 1 so the dLSS is minimal, hence, the associated sLSS is
also minimal by Lemma 2. ∎