# Convergence of Recursive Least Squares Based Input/Output System
Identification with Model Order Mismatch

Brian Lai and Dennis S. Bernstein  Brian Lai and Dennis S. Bernstein are with
the Department of Aerospace Engineering, University of Michigan, Ann Arbor,
MI, USA. {brianlai<EMAIL_ADDRESS>This work was supported by the NSF
Graduate Research Fellowship under Grant No. DGE 1841052.

###### Abstract

Discrete-time input/output models, also called infinite impulse response (IIR)
models or autoregressive moving average (ARMA) models, are useful for online
identification as they can be efficiently updated using recursive least
squares (RLS) as new data is collected. Several works have studied the
convergence of the input/output model coefficients identified using RLS under
the assumption that the order of the identified model is the same as that of
the true system. However, the case of model order mismatch is not as well
addressed. This work begins by introducing the notion of equivalence of
input/output models of different orders. Next, this work analyzes online
identification of input/output models in the case where the order of the
identified model is higher than that of the true system. It is shown that,
given persistently exciting data, the higher-order identified model converges
to the model equivalent to the true system that minimizes the regularization
term of RLS.

##  I Introduction

Least squares based methods are fundamental and widely used in identification,
signal processing, and control [1, 2]. One useful application is online
identification of a linear model for adaptive control [3, ch. 3]. A particular
model structure that lends itself to online identification is a discrete-time
input/output model [4], also called an infinite-impulse-response (IIR) model
[5] or autoregressive moving-average (ARMA) model [3, p. 32]. An advantage of
discrete-time input/output models is they can be efficiently updated in real
time as new data is collected [3, ch. 3.2]. Note that in the single-input-
single-output (SISO) case, the coefficients of a discrete-time input/output
model directly give the discrete-time transfer function. However, the multi-
input-multi-output (MIMO) case is considerably more complex [4, 6] and
converting between input/output models and other linear model structures is
nontrivial [7, 8]. As such, it may be beneficial to directly study the online
identification of MIMO input/output models without converting to another model
structure.

This paper focuses on the online identification of input/output models using
recursive least squares (RLS), which has been used in adaptive model
predictive control [9] and retrospective cost adaptive control [10] with
various applications [11, 12, 13]. While related works have discussed
convergence of model coefficients when identifying input/output models using
RLS [3, ch. 3.4], [14], these results assume the order of the true model is
known. A natural question is whether similar guarantees can be made if the
order of the identified model and true system do not match. This work will
show that if the order of the identified model is higher than order of the
true model, then the regressor of RLS is not persistently exciting, and hence
standard convergence guarantees of RLS [15, 16, 3] do not apply. The main
contribution of this work is developing new analysis of the case where the
order of the identified input/output model is higher than that of the true
input/output system.

This paper is organized as follows. Section II introduces discrete-time
input/output models and a useful output transition equation. Next, Section III
introduces the notion of equivalence of input/output models as models giving
the same outputs under the same inputs and initial conditions. It is shown
that a necessary and sufficient condition for equivalence can be written as a
linear equation of the model coefficients. This section also introduces the
notion of reducibility as the existence of a lower-order, equivalent
input/output model. Finally, section IV discusses the online identification of
input/output models using RLS. It is first shown that, in the case where the
order of the identified model is the same as that of the true system,
persistent excitation conditions guarantee global asymptotic stability of the
coefficient estimation error. Next, in the case where the order of the
identified model is higher than that of the true system, conditions are given
under which the identified model converges to the higher-order model
equivalent to the true system that minimizes the regularization term of RLS.

##  II Input/Output Modeling

Let $k_{0}\in{\mathbb{N}}$ be the initial time step and let $n\geq 0$ be the
model order. Consider the input/output model where, for all $k\geq k_{0}$,
$u_{k}\in{\mathbb{R}}^{m}$ is the input,
$y_{k_{0}},\ldots,y_{k_{0}+n-1}\in{\mathbb{R}}^{p}$ are the initial conditions
and, for all $k\geq k_{0}$, the output $y_{k+n}\in{\mathbb{R}}^{p}$ is given
by

$\displaystyle
y_{k+n}=-\sum_{i=1}^{n}F_{i}y_{k+n-i}+\sum_{i=0}^{n}G_{i}u_{k+n-i},$ (1)

where $F_{1},\ldots,F_{n}\in{\mathbb{R}}^{p\times p}$, and
$G_{0},\ldots,G_{n}\in{\mathbb{R}}^{p\times m}$ are the input/output model
coefficients. It follows that, for all $k\geq k_{0}$,

$\displaystyle
y_{k+n}=-{\mathcal{F}}_{n}{\mathcal{Y}}_{k,n}+{\mathcal{G}}_{n}{\mathcal{U}}_{k,n},$
(2)

where ${\mathcal{F}}_{n}\in{\mathbb{R}}^{p\times pn}$,
${\mathcal{Y}}_{k,n}\in{\mathbb{R}}^{pn}$,
${\mathcal{G}}_{n}\in{\mathbb{R}}^{p\times m(n+1)}$, and
${\mathcal{U}}_{k,n}\in{\mathbb{R}}^{m(n+1)}$ are defined as

$\displaystyle{\mathcal{F}}_{n}$
$\displaystyle\triangleq\begin{bmatrix}F_{1}&\cdots&F_{n}\end{bmatrix},\quad{\mathcal{Y}}_{k,n}\triangleq\begin{bmatrix}y_{k+n-1}\\\
\vdots\\\ y_{k}\end{bmatrix},$ (3) $\displaystyle{\mathcal{G}}_{n}$
$\displaystyle\triangleq\begin{bmatrix}G_{0}&\cdots&G_{n}\end{bmatrix},\quad{\mathcal{U}}_{k,n}\triangleq\begin{bmatrix}u_{k+n}\\\
\vdots\\\ u_{k}\end{bmatrix}.$ (4)

Proposition 1 shows that, for all $k\geq k_{0}$ and $j\geq 0$, $y_{k+n+j}$ can
be written as a linear combination of the inputs $u_{k},\ldots,u_{k+n+j-1}$
and the $n$ outputs $y_{k},\ldots,y_{k+n-1}$. We call this the output
transition equation.

######  Proposition 1.

Let $k_{0}\in{\mathbb{N}}$. For all $k\geq k_{0}$, let
$u_{k}\in{\mathbb{R}}^{m}$, let
$y_{k_{0}},\ldots,y_{k_{0}+n-1}\in{\mathbb{R}}^{p}$, and, for all $k\geq
k_{0}$, let $y_{k+n}\in{\mathbb{R}}^{p}$ be given by (1). Then, for all $k\geq
k_{0}$ and $j\geq 0$,

$\displaystyle
y_{k+n+j}=-{\mathcal{F}}_{n,j}{\mathcal{Y}}_{k,n}+{\mathcal{G}}_{n,j}{\mathcal{U}}_{k,n+j},$
(5)

where ${\mathcal{F}}_{n,0}\triangleq{\mathcal{F}}_{n}$,
${\mathcal{G}}_{n,0}\triangleq{\mathcal{G}}_{n}$, and, for all $j\geq 1$,
${\mathcal{F}}_{n,j}\in{\mathbb{R}}^{p\times pn}$ and
${\mathcal{G}}_{n,j}\in{\mathbb{R}}^{p\times m(n+1+j)}$ are defined

$\displaystyle{\mathcal{F}}_{n,j}$
$\displaystyle\triangleq\mathcal{S}({\mathcal{F}}_{n,0},j)-\sum_{i=1}^{\mathclap{\min\\{j,n\\}}}F_{i}{\mathcal{F}}_{n,j-i},$
(6) $\displaystyle{\mathcal{G}}_{n,j}$
$\displaystyle\triangleq\begin{bmatrix}{\mathcal{G}}_{n,0}&0_{p\times
jm}\end{bmatrix}-\sum_{i=1}^{\mathclap{\min\\{j,n\\}}}F_{i}\begin{bmatrix}0_{p\times
im}&{\mathcal{G}}_{n,j-i}\end{bmatrix},$ (7)

and where $\mathcal{S}({\mathcal{F}}_{n,0},j)\in{\mathbb{R}}^{p\times pn}$ is
the $j$ step shift of ${\mathcal{F}}_{n,0}$, defined as

$\mathcal{S}({\mathcal{F}}_{n,0},j)\triangleq\begin{cases}\begin{bmatrix}F_{j+1}&\cdots&F_{n}&0_{p\times
jp}\end{bmatrix}&j\leq n-1,\\\ 0_{p\times np}&j\geq n.\end{cases}$ (8)

###### Proof.

Proof follows by strong induction on $j\geq 0$. Note that for all $k\geq
k_{0}$ and $j=0$, (5) simplifies to (2). Next, let $k\geq k_{0}$, let $j\geq
1$ and suppose that, for all $\hat{j}\leq j-1$, (5) holds. Note that by (1),
$y_{k+n+j}$ can be written as

$y_{k+n+j}=-\sum_{i=1}^{n}F_{i}y_{k+n+j-i}+\sum_{i=0}^{n}G_{i}u_{k+n+j-i}.$

Next, for all $1\leq i\leq\min\\{j,n\\}$, it follows that $0\leq j-i\leq j-1$
and by inductive hypothesis, $y_{k+n+j-i}$ can be written as

$\displaystyle y_{k+n+j-i}$
$\displaystyle=-{\mathcal{F}}_{n,j-i}{\mathcal{Y}}_{k,n}+{\mathcal{G}}_{n,j-i}{\mathcal{U}}_{k,n+j-i}$
$\displaystyle=-{\mathcal{F}}_{n,j-i}{\mathcal{Y}}_{k,n}+\begin{bmatrix}0_{p\times
im}&{\mathcal{G}}_{n,j-i}\end{bmatrix}{\mathcal{U}}_{k,n+j}.$

Furthermore, note that

$\displaystyle\sum_{i=0}^{n}G_{i}u_{k+n+j-i}=\begin{bmatrix}{\mathcal{G}}_{n,0}&0_{p\times
jm}\end{bmatrix}{\mathcal{U}}_{k,n+j}.$

Hence, $y_{k+n+j}$ can be written as

$\displaystyle y_{k+n-j}=$
$\displaystyle\sum_{i=1}^{\mathclap{\min\\{j,n\\}}}F_{i}\left({\mathcal{F}}_{n,j-i}{\mathcal{Y}}_{k,n}-\begin{bmatrix}0_{p\times
im}&{\mathcal{G}}_{n,j-i}\end{bmatrix}{\mathcal{U}}_{k,n+j}\right)$
$\displaystyle-\hskip 5.0pt\sum_{\mathclap{i=\min\\{j,n\\}+1}}^{n}\hskip
5.0ptF_{i}y_{k+n+j-i}+\begin{bmatrix}{\mathcal{G}}_{n,0}&0_{p\times
jm}\end{bmatrix}{\mathcal{U}}_{k,n+j}.$

Noting that
$\sum_{i=\min\\{j,n\\}+1}^{n}F_{i}y_{k+n+j-i}=\mathcal{S}({\mathcal{F}}_{n,0},j){\mathcal{Y}}_{k,n}$
and combining terms yields (5). ∎

##  III Equivalence and Reducibility of Input/Output Models

Consider an input/output model of order $\hat{n}\geq n$ where, for all $k\geq
k_{0}$, $u_{k}\in{\mathbb{R}}^{m}$ is the input,
$\hat{y}_{k_{0}},\ldots,\hat{y}_{k_{0}+\hat{n}-1}\in{\mathbb{R}}^{p}$ are the
initial conditions and, for all $k\geq k_{0}$, the output
$\hat{y}_{k+\hat{n}}\in{\mathbb{R}}^{p}$ is given by

$\displaystyle\hat{y}_{k+\hat{n}}=-\sum_{i=1}^{\hat{n}}\hat{F}_{i}\hat{y}_{k+\hat{n}-i}+\sum_{i=0}^{\hat{n}}\hat{G}_{i}u_{k+\hat{n}-i},$
(9)

where $\hat{F}_{1},\ldots,\hat{F}_{\hat{n}}\in{\mathbb{R}}^{p\times p}$, and
$\hat{G}_{0},\ldots,\hat{G}_{\hat{n}}\in{\mathbb{R}}^{p\times m}$ are the
input/output model coefficients. Definition 1 defines models (1) and (9) as
equivalent if they give the same outputs under the same inputs and initial
conditions.

######  Definition 1.

Let $k_{0}\in{\mathbb{N}}$. Consider input/output model (1) with order $n$ and
and input/output Model (9) with order $\hat{n}\geq n$. For all $k\geq k_{0}$,
let $u_{k}\in{\mathbb{R}}^{m}$ be arbitrary. For all $k_{0}\leq k\leq
k_{0}+n-1$, let $y_{k}\in{\mathbb{R}}^{p}$ be arbitrary and, for all $k\geq
k_{0}+n$, let $y_{k}\in{\mathbb{R}}^{p}$ be given by (1). Next, for all
$k_{0}\leq k\leq k_{0}+\hat{n}-1$, let $\hat{y}_{k}=y_{k}$ and, for all $k\geq
k_{0}+\hat{n}$, let $\hat{y}_{k}\in{\mathbb{R}}^{p}$ be given by (9). Models
(1) and (9) are equivalent if, for all $k\geq k_{0}+\hat{n}$,
$\hat{y}_{k}=y_{k}$.

Proposition 2 shows that two input/output models of the same order are
equivalent if and only if they have the same model coefficients.

######  Proposition 2.

Consider input/output models (1) and (9) with the same order $\hat{n}=n$.
Models (1) and (9) are equivalent if and only if $\hat{G}_{0}=G_{0}$ and, for
all $1\leq i\leq n$, $\hat{F}_{i}=F_{i}$ and $\hat{G}_{i}=G_{i}$.

###### Proof.

Proof of necessity follow immediately. To prove sufficiency, let
$k_{0}\in{\mathbb{N}}$. First consider that there exists $0\leq i\leq n$ such
that $\hat{G}_{i}\neq G_{i}$. Then, there exists $u\in{\mathbb{R}}^{m}$ such
that $\hat{G}_{i}u\neq G_{i}u$. Next, consider
$y_{k_{0}}=\cdots=y_{k_{0}+n-1}=0$, for all $k\geq k_{0}$ such that $k\neq
k_{0}+n-i$, $u_{k}=0$, and $u_{k_{0}+n-i}=u$. Then,
$\hat{y}_{k_{0}+n}=\hat{G}_{i}u$, $y_{k_{0}+n}=G_{i}u$, and
$\hat{y}_{k_{0}+n}\neq y_{k_{0}+n}$.

Next, consider that there exists $1\leq i\leq n$ such that $\hat{F}_{i}\neq
F_{i}$. Similarly, there exists $y\in{\mathbb{R}}^{p}$ such that
$\hat{F}_{i}y\neq F_{i}y$. Hence, if, for all $k_{0}\leq k\leq k_{0}+n-1$,
$k\neq k_{0}+n-i$, $y_{k}=0$, $y_{k_{0}+n-i}=y$, and, for all $k\geq k_{0}$,
$u_{k}=0$, then $\hat{y}_{k_{0}+n}=\hat{F}_{i}y$, $y_{k_{0}+n}=F_{i}y$, and
$\hat{y}_{k_{0}+n}\neq y_{k_{0}+n}$. Thus, (1) and (9) are not equivalent and
sufficiency is proven. ∎

We next consider the equivalence of input/output models of different orders.
Note that, for all $k\geq k_{0}$,

$\displaystyle\hat{y}_{k+\hat{n}}=-\hat{{\mathcal{F}}}_{\hat{n}}\hat{{\mathcal{Y}}}_{k,\hat{n}}+\hat{{\mathcal{G}}}_{\hat{n}}{\mathcal{U}}_{k,\hat{n}},$
(10)

where ${\mathcal{U}}_{k,\hat{n}}\in{\mathbb{R}}^{m(\hat{n}+1)}$ is defined in
(4) and $\hat{{\mathcal{F}}}_{\hat{n}}\in{\mathbb{R}}^{p\times p\hat{n}}$,
$\hat{{\mathcal{Y}}}_{k,\hat{n}}\in{\mathbb{R}}^{p\hat{n}}$, and
$\hat{{\mathcal{G}}}_{\hat{n}}\in{\mathbb{R}}^{p\times m(\hat{n}+1)}$ are
defined as

$\displaystyle\hat{{\mathcal{F}}}_{\hat{n}}$
$\displaystyle\triangleq\begin{bmatrix}\hat{F}_{1}&\cdots&\hat{F}_{\hat{n}}\end{bmatrix},\quad\hat{{\mathcal{Y}}}_{k,\hat{n}}\triangleq\begin{bmatrix}\hat{y}_{k+\hat{n}-1}\\\
\vdots\\\ \hat{y}_{k}\end{bmatrix},$ (11)
$\displaystyle\hat{{\mathcal{G}}}_{\hat{n}}$
$\displaystyle\triangleq\begin{bmatrix}\hat{G}_{0}&\cdots&\hat{G}_{\hat{n}}\end{bmatrix}.$
(12)

Theorem 1 gives necessary and sufficient conditions for the equivalence of
input/output models of different orders. We begin with two useful Lemmas.

######  Lemma 1.

Let $k_{0}\in{\mathbb{N}}$. Consider input/output model (1) with order $n$ and
and input/output Model (9) with order $\hat{n}>n$. For all $k\geq k_{0}$, let
$u_{k}\in{\mathbb{R}}^{m}$, for all $k_{0}\leq k\leq k_{0}+n-1$, let
$y_{k}\in{\mathbb{R}}^{p}$, and, for all $k\geq k_{0}+n$, let
$y_{k}\in{\mathbb{R}}^{p}$ be given by (1). Let $k^{*}\geq k_{0}$ and, for all
$k_{0}\leq k\leq k^{*}+\hat{n}-1$, let $\hat{y}_{k}=y_{k}$. Finally, let
$\hat{y}_{k^{*}+\hat{n}}\in{\mathbb{R}}^{p}$ be given by (9). Then,
$\hat{y}_{k^{*}+\hat{n}}$ can be expressed as

$\displaystyle\hat{y}_{k^{*}+\hat{n}}=-\hat{{\mathcal{F}}}_{n,\hat{n}-n}{\mathcal{Y}}_{k^{*},n}+\hat{{\mathcal{G}}}_{n,\hat{n}-n}{\mathcal{U}}_{k^{*},\hat{n}},$
(13)

where $\hat{{\mathcal{F}}}_{n,\hat{n}-n}\in{\mathbb{R}}^{p\times pn}$ and
$\hat{{\mathcal{G}}}_{n,\hat{n}-n}\in{\mathbb{R}}^{p\times m(\hat{n}+1)}$ are
defined

$\displaystyle\hat{{\mathcal{F}}}_{n,\hat{n}-n}$
$\displaystyle\triangleq\begin{bmatrix}\hat{F}_{\hat{n}-n+1}&\cdots&\hat{F}_{\hat{n}}\end{bmatrix}-\sum_{i=1}^{\hat{n}-n}\hat{F}_{i}{\mathcal{F}}_{n,\hat{n}-n-i},$
(14) $\displaystyle\hat{{\mathcal{G}}}_{n,\hat{n}-n}$
$\displaystyle\triangleq\hat{{\mathcal{G}}}_{\hat{n}}-\sum_{i=1}^{\hat{n}-n}\hat{F}_{i}\begin{bmatrix}0_{p\times
im}&{\mathcal{G}}_{n,\hat{n}-n-i}\end{bmatrix}.$ (15)

###### Proof.

Let $k_{0}\in{\mathbb{N}}$ and let $k^{*}\geq k_{0}$. By (9),
$\hat{y}_{k^{*}+\hat{n}}$ can be written as

$\hat{y}_{k^{*}+\hat{n}}=-\sum_{i=1}^{\hat{n}-n}\hat{F}_{i}y_{k^{*}+\hat{n}-i}-\sum_{\mathclap{i=\hat{n}-n+1}}^{\hat{n}}\hat{F}_{i}y_{k+\hat{n}-i}+\hat{{\mathcal{G}}}_{\hat{n}}{\mathcal{U}}_{k^{*},\hat{n}}.$
(16)

Note that the second term can be written as

$\displaystyle\sum_{i=\hat{n}-n+1}^{\hat{n}}\hat{F}_{i}y_{k^{*}+\hat{n}-i}=\begin{bmatrix}\hat{F}_{\hat{n}-n+1}&\cdots&\hat{F}_{\hat{n}}\end{bmatrix}{\mathcal{Y}}_{k^{*},n}.$
(17)

Next, for all $1\leq i\leq\hat{n}-n$, note that $\hat{n}-n-i\geq 0$ and
Proposition 1 (with $k=k^{*}$ and $j=\hat{n}-n-i$) implies that

$\displaystyle
y_{k^{*}+\hat{n}-i}=-{\mathcal{F}}_{n,\hat{n}-n-i}{\mathcal{Y}}_{k^{*},n}+{\mathcal{G}}_{n,\hat{n}-n-i}{\mathcal{U}}_{k^{*},\hat{n}-i}.$
(18)

Substituting (17) and (18) into (16), it follows that

$\displaystyle\hat{y}_{k^{*}+\hat{n}}=$
$\displaystyle-\sum_{i=1}^{\hat{n}-n}\hat{F}_{i}(-{\mathcal{F}}_{n,\hat{n}-n-i}{\mathcal{Y}}_{k^{*},n}+{\mathcal{G}}_{n,\hat{n}-n-i}{\mathcal{U}}_{k^{*},\hat{n}-i})$
$\displaystyle-\begin{bmatrix}\hat{F}_{\hat{n}-n+1}&\cdots&\hat{F}_{\hat{n}}\end{bmatrix}{\mathcal{Y}}_{k^{*},n}+\hat{{\mathcal{G}}}_{\hat{n}}{\mathcal{U}}_{k^{*},\hat{n}}.$
(19)

Finally, note that, for all $1\leq i\leq\hat{n}-n$,

$\displaystyle{\mathcal{G}}_{n,\hat{n}-n-i}{\mathcal{U}}_{k^{*},\hat{n}-i}=\begin{bmatrix}0_{p\times
im}&{\mathcal{G}}_{n,\hat{n}-n-i}\end{bmatrix}{\mathcal{U}}_{k^{*},\hat{n}}.$
(20)

Substituting (19) into (20) and simplifying yields (13). ∎

######  Lemma 2.

For all $\hat{n}>n$,

$\displaystyle\begin{bmatrix}-\hat{{\mathcal{F}}}_{n,\hat{n}-n}&\hat{{\mathcal{G}}}_{n,\hat{n}-n}\end{bmatrix}=\begin{bmatrix}-\hat{{\mathcal{F}}}_{\hat{n}}&\hat{{\mathcal{G}}}_{\hat{n}}\end{bmatrix}M_{n,\hat{n}},$
(21)

where $M_{n,\hat{n}}\in{\mathbb{R}}^{p\hat{n}+m(\hat{n}+1)\times
pn+m(\hat{n}+1)}$ is defined

$M_{n,\hat{n}}\triangleq\begin{bmatrix}M_{n,\hat{n}}^{1}&M_{n,\hat{n}}^{2}\\\
I_{pn}&0_{pn\times m(\hat{n}+1)}\\\ 0_{m(\hat{n}+1)\times
pn}&I_{m(\hat{n}+1)}\end{bmatrix}=\begin{bmatrix}\begin{bmatrix}M_{n,\hat{n}}^{1}&M_{n,\hat{n}}^{2}\end{bmatrix}\\\
I_{pn+m(\hat{n}+1)}\end{bmatrix},$ (22)

where $M_{n,\hat{n}}^{1}\in{\mathbb{R}}^{p(\hat{n}-n)\times pn}$ and
$M_{n,\hat{n}}^{2}\in{\mathbb{R}}^{p(\hat{n}-n)\times m(\hat{n}+1)}$ are
defined

$\displaystyle
M_{n,\hat{n}}^{1}\triangleq\begin{bmatrix}-{\mathcal{F}}_{n,\hat{n}-n-1}\\\
-{\mathcal{F}}_{n,\hat{n}-n-2}\\\ \vdots\\\ -{\mathcal{F}}_{n,1}\\\
-{\mathcal{F}}_{n,0}\end{bmatrix},M_{n,\hat{n}}^{2}\triangleq\begin{bmatrix}\begin{bmatrix}0_{p\times
m}&{\mathcal{G}}_{n,\hat{n}-n-1}\end{bmatrix}\\\ \begin{bmatrix}0_{p\times
2m}&{\mathcal{G}}_{n,\hat{n}-n-2}\end{bmatrix}\\\ \vdots\\\
\begin{bmatrix}0_{p\times(\hat{n}-n-1)m}&{\mathcal{G}}_{n,1}\end{bmatrix}\\\
\begin{bmatrix}0_{p\times(\hat{n}-n)m}&{\mathcal{G}}_{n,0}\end{bmatrix}\end{bmatrix}$
(23)

###### Proof.

It follows from (14) that

$\displaystyle\hat{{\mathcal{F}}}_{n,\hat{n}-n}=\begin{bmatrix}\hat{F}_{\hat{n}-n+1}&\cdots&\hat{F}_{\hat{n}}\end{bmatrix}-\begin{bmatrix}\hat{F}_{1}&\cdots&\hat{F}_{\hat{n}-n}\end{bmatrix}M_{n,\hat{n}}^{1}.$

Furthermore, it follows from (15) that

$\displaystyle\hat{{\mathcal{G}}}_{n,\hat{n}-n}=\hat{{\mathcal{G}}}_{\hat{n}}-\begin{bmatrix}\hat{F}_{1}&\cdots&\hat{F}_{\hat{n}-n}\end{bmatrix}M_{n,\hat{n}}^{2}.$

Combining these two expressions can yields (21). ∎

######  Theorem 1.

Consider input/output model (1) with order $n$ and input/output model (9) with
order $\hat{n}>n$. Models (1) and (9) are equivalent if and only if

$\displaystyle\hat{{\mathcal{F}}}_{n,\hat{n}-n}={\mathcal{F}}_{n,\hat{n}-n},\quad\hat{{\mathcal{G}}}_{n,\hat{n}-n}={\mathcal{G}}_{n,\hat{n}-n},$
(24)

which holds if and only if

$\displaystyle\begin{bmatrix}-\hat{{\mathcal{F}}}_{\hat{n}}&\hat{{\mathcal{G}}}_{\hat{n}}\end{bmatrix}M_{n,\hat{n}}=\begin{bmatrix}-{{\mathcal{F}}}_{n,\hat{n}-n}&{{\mathcal{G}}}_{n,\hat{n}-n}\end{bmatrix}.$
(25)

###### Proof.

It follows from Lemma 2 that (24) and (25) are equivalent. Hence, it suffices
to show that Models (1) and (9) are equivalent if and only if (24) holds. To
prove sufficiency, assume models (1) and (9) are equivalent and let
$k_{0}\in{\mathbb{N}}$. Then, it follows from Definition 1 that, for all
${\mathcal{Y}}_{k_{0},n}\in{\mathbb{R}}^{pn}$ and
${\mathcal{U}}_{k_{0},\hat{n}}\in{\mathbb{R}}^{m(\hat{n}+1)}$,
$y_{k_{0}+\hat{n}}=\hat{y}_{k_{0}+\hat{n}}$ holds, where, for all $k_{0}+n\leq
k\leq k_{0}+\hat{n}$, $y_{k}\in{\mathbb{R}}^{p}$ is given by (1), for all
$k_{0}\leq k\leq k_{0}+\hat{n}-1$, $\hat{y}_{k}=y_{k}$, and where
$\hat{y}_{k+\hat{n}}\in{\mathbb{R}}^{p}$ is given by (9). It follows from
Proposition 1 and Lemma 1 that

$\displaystyle y_{k+\hat{n}}$
$\displaystyle=-{{\mathcal{F}}}_{n,\hat{n}-n}{\mathcal{Y}}_{k,n}+{{\mathcal{G}}}_{n,\hat{n}-n}{\mathcal{U}}_{k,n},$
$\displaystyle\hat{y}_{k+\hat{n}}$
$\displaystyle=-\hat{{\mathcal{F}}}_{n,\hat{n}-n}{\mathcal{Y}}_{k,n}+\hat{{\mathcal{G}}}_{n,\hat{n}-n}{\mathcal{U}}_{k,n},$

Since ${\mathcal{Y}}_{k,n}$ and ${\mathcal{U}}_{k,\hat{n}}$ are chosen
arbitrarily and $y_{k+\hat{n}}=\hat{y}_{k+\hat{n}}$, (24) follows.

To prove necessity, assume that (25) holds, let $k_{0}\in{\mathbb{N}}$. For
all $k\geq k_{0}$, let $u_{k}\in{\mathbb{R}}^{m}$ be arbitrary, for all
$k_{0}\leq k\leq k_{0}+n-1$, let $y_{k}\in{\mathbb{R}}^{p}$ be arbitrary and,
for all $k\geq k_{0}+n$, let $y_{k}\in{\mathbb{R}}^{p}$ be given by (1).
Furthermore, for all $k_{0}\leq k\leq k_{0}+\hat{n}-1$, let
$\hat{y}_{k}=y_{k}$ and, for all $k\geq k_{0}+\hat{n}$, let
$\hat{y}_{k}\in{\mathbb{R}}^{p}$ be given by (9). We now show by strong
induction that, for all $k^{*}\geq k_{0}$,
$\hat{y}_{k^{*}+\hat{n}}=y_{k^{*}+\hat{n}}$. First, consider the base case
$k^{*}=k_{0}$. It follows from (5) of Proposition 1 (with $k=k_{0}$ and
$j=\hat{n}-n$) that
$y_{k_{0}+\hat{n}}=-{\mathcal{F}}_{n,\hat{n}-n}{\mathcal{Y}}_{k_{0},n}+{\mathcal{G}}_{n,\hat{n}-n}{\mathcal{U}}_{k_{0},\hat{n}}$.
Moreover, since by assumption, for all $k_{0}\leq k\leq k_{0}+\hat{n}-1$,
$\hat{y}_{k}=y_{k}$, it follows from (13) of Lemma 1 (with $k^{*}=k_{0}$) that
$\hat{y}_{k_{0}+\hat{n}}=-\hat{{\mathcal{F}}}_{n,\hat{n}-n}{\mathcal{Y}}_{k_{0},n}+\hat{{\mathcal{G}}}_{n,\hat{n}-n}{\mathcal{U}}_{k_{0},\hat{n}}$.
Finally, (24) implies that $y_{k_{0}+\hat{n}}=\hat{y}_{k_{0}+\hat{n}}$.

Next, let $k^{*}\geq k_{0}+1$ and assume for inductive hypothesis that, for
all $k_{0}\leq k\leq k^{*}-1$, $\hat{y}_{k+\hat{n}}=y_{k+\hat{n}}$. It follows
from (5) of Proposition 1 (with $k=k^{*}$ and $j=\hat{n}-n$) that
$y_{k^{*}+\hat{n}}=-{\mathcal{F}}_{n,\hat{n}-n}{\mathcal{Y}}_{k^{*},n}+{\mathcal{G}}_{n,\hat{n}-n}{\mathcal{U}}_{k^{*},\hat{n}}$.
Moreover, it follows from inductive hypothesis and (13) of Lemma 1 that
$\hat{y}_{k^{*}+\hat{n}}=-\hat{{\mathcal{F}}}_{n,\hat{n}-n}{\mathcal{Y}}_{k^{*},n}+\hat{{\mathcal{G}}}_{n,\hat{n}-n}{\mathcal{U}}_{k^{*},\hat{n}}$.
Finally, (24) implies that $y_{k^{*}+\hat{n}}=\hat{y}_{k^{*}+\hat{n}}$. Thus,
by strong induction, for all $k^{*}\geq k_{0}$,
$\hat{y}_{k^{*}+\hat{n}}=y_{k^{*}+\hat{n}}$, and models (1) and (9) are
equivalent. ∎

Note that the matrix
$M_{n,\hat{n}}\in{\mathbb{R}}^{p\hat{n}+m(\hat{n}+1)\times pn+m(\hat{n}+1)}$
will be of importance in the later discussion on online identification.

Example 1.  To better illustrate the result of Theorem 1, consider the case
$m=p=1$, $n=1$, and $\hat{n}=2$. It follows from Theorem 1 that models (1) and
(9) are equivalent if and only if

$\displaystyle\begin{bmatrix}-\hat{F}_{1}&-\hat{F}_{2}&\hat{G}_{0}&\hat{G}_{1}&\hat{G}_{2}\end{bmatrix}\begin{bmatrix}-F_{1}&0&G_{0}&G_{1}\\\
1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{bmatrix}$
$\displaystyle=\begin{bmatrix}F_{1}^{2}&G_{0}&G_{1}-F_{1}G_{0}&-F_{1}G_{1}\end{bmatrix}.$
(26)

As a sanity check, note that the trivial case $\hat{F}_{1}=F_{1}$,
$\hat{G}_{0}=G_{0}$, $\hat{G}_{1}=G_{1}$ and $\hat{F}_{2}=\hat{G}_{2}=0$
satisfies (26). $\diamond$

Definition 2 defines an input/output model as reducible if there exists an
equivalent input/output model of lower-order, and irreducible otherwise.
Theorem 2 provides necessary and sufficient conditions for reducibility of
input/output models.

######  Definition 2.

Consider input/output model (9) with order $\hat{n}$. The input/output model
(9) is reducible if there exists an input/output model (1) with order
$n\leq\hat{n}-1$ such that $\eqref{eqn: IO Model}$ and (9) are equivalent.
Otherwise, input/output model (9) is irreducible.

######  Theorem 2.

The input/output model (9) is reducible if and only if there exists
$F_{1}\in{\mathbb{R}}^{p\times p}$ such that

$\displaystyle(\hat{F}_{1}-F_{1})F_{\hat{n}-1}$
$\displaystyle=\hat{F}_{\hat{n}},$ (27)
$\displaystyle(\hat{F}_{1}-F_{1})G_{\hat{n}-1}$
$\displaystyle=\hat{G}_{\hat{n}},$ (28)

where $G_{0}\triangleq\hat{G}_{0}$ and, for all $2\leq i\leq\hat{n}-1$ and
$1\leq j\leq\hat{n}-1$,

$\displaystyle F_{i}\triangleq$
$\displaystyle=\hat{F}_{i}-(\hat{F}_{1}-F_{1})F_{i-1},$ (29) $\displaystyle
G_{j}\triangleq$ $\displaystyle=\hat{G}_{j}-(\hat{F}_{1}-F_{1})G_{j-1}.$ (30)

Moreover, if there exists $F_{1}\in{\mathbb{R}}^{p\times p}$ satisfying (27)
and (28), then input/output model (1) with coefficients
$F_{1},\ldots,F_{\hat{n}-1}$ and $G_{0},\ldots,G_{\hat{n}-1}$ defined by (29)
and (30) is equivalent to input/output model (9).

###### Proof.

To begin, if input/output model (1) with order $n<\hat{n}-1$ is equivalent to
input/output model (9), then there exists an input/output model with order
$\hat{n}-1$ that is equivalent to (9), namely a model with the coefficients
$F_{1},\ldots,F_{n}$, $G_{0},\ldots,G_{n}$, and $F_{i}=0_{p\times p}$ and
$G_{i}=0_{p\times m}$ for all $n+1\leq i\leq\hat{n}-1$. Hence, input/output
model (9), with order $\hat{n}$ is reducible if and only if there exists an
equivalent input/output model (1) with order $n=\hat{n}-1$.

Next, it follows from Theorem 1 that model (1) with order $n=\hat{n}-1$ and
model (9) with order $\hat{n}$ are equivalent if and only if
$\hat{{\mathcal{F}}}_{\hat{n}-1,1}={\mathcal{F}}_{\hat{n}-1,1}$ and
$\hat{{\mathcal{G}}}_{\hat{n}-1,1}={\mathcal{G}}_{\hat{n}-1,1}$. Moreover, it
follows from (6), (14), (7), and (15) that

$\displaystyle\hat{{\mathcal{F}}}_{\hat{n}-1,1}$
$\displaystyle=\begin{bmatrix}\hat{F}_{2}&\hat{F}_{3}&\cdots&\hat{F}_{\hat{n}}\end{bmatrix}-\hat{F}_{1}{\mathcal{F}}_{\hat{n}-1},$
$\displaystyle{\mathcal{F}}_{\hat{n}-1,1}$
$\displaystyle=-F_{1}{\mathcal{F}}_{\hat{n}-1}+\begin{bmatrix}\hat{F}_{2}&\hat{F}_{3}&\cdots&\hat{F}_{\hat{n}-1}&0_{p\times
p}\end{bmatrix},$ $\displaystyle\hat{{\mathcal{G}}}_{\hat{n}-1,1}$
$\displaystyle=\hat{{\mathcal{G}}}_{\hat{n}}-\hat{F}_{1}\begin{bmatrix}0_{p\times
m}&{\mathcal{G}}_{\hat{n}-1}\end{bmatrix},$
$\displaystyle{\mathcal{G}}_{\hat{n}-1,1}$
$\displaystyle=-F_{1}\begin{bmatrix}0_{p\times
m}&{\mathcal{G}}_{\hat{n}-1}\end{bmatrix}+\begin{bmatrix}{\mathcal{G}}_{\hat{n}-1}&0_{p\times
m}\end{bmatrix}.$

Rearranging terms, it follows that
$\hat{{\mathcal{F}}}_{\hat{n}-1,1}={\mathcal{F}}_{\hat{n}-1,1}$ and
$\hat{{\mathcal{G}}}_{\hat{n}-1,1}={\mathcal{G}}_{\hat{n}-1,1}$ hold if and
only if

$\displaystyle(\hat{F}_{1}-F_{1}){\mathcal{F}}_{\hat{n}-1}=\begin{bmatrix}\hat{F}_{2}-F_{2}&\cdots&\hat{F}_{\hat{n}-1}-F_{\hat{n}-1}&\hat{F}_{\hat{n}}\end{bmatrix},$
$\displaystyle(\hat{F}_{1}-F_{1})\begin{bmatrix}0_{p\times
m}&{\mathcal{G}}_{\hat{n}-1}\end{bmatrix}$
$\displaystyle\hphantom{(\hat{F}_{1}-F_{1}){\mathcal{F}}_{\hat{n}-1}}=\begin{bmatrix}\hat{G}_{0}-G_{0}&\cdots&\hat{G}_{\hat{n}-1}-G_{\hat{n}-1}&\hat{G}_{\hat{n}}\end{bmatrix},$

which can be expanded as, for all $2\leq i\leq\hat{n}-1$ and $1\leq
j\leq\hat{n}-1$,

$\displaystyle(\hat{F}_{1}-F_{1})F_{i-1}$
$\displaystyle=\hat{F}_{i}-F_{i},\quad,$ (31)
$\displaystyle(\hat{F}_{1}-F_{1})F_{\hat{n}-1}$
$\displaystyle=\hat{F}_{\hat{n}},$ (32) $\displaystyle 0_{p\times m}$
$\displaystyle=\hat{G}_{0}-G_{0}.$ (33)
$\displaystyle(\hat{F}_{1}-F_{1})G_{j-1}$ $\displaystyle=\hat{G}_{j}-G_{j},$
(34) $\displaystyle(\hat{F}_{1}-F_{1})G_{\hat{n}-1}$
$\displaystyle=\hat{G}_{\hat{n}}.$ (35)

Finally, note that, for all $2\leq i\leq\hat{n}-1$, (31) holds if and only if
(29), for all $1\leq j\leq\hat{n}-1$, (34) holds if and only if (30), and (33)
holds if and only if $G_{0}=\hat{G}_{0}$. Hence, model (1) with order
$n=\hat{n}-1$ and model (9) with order $\hat{n}$ are equivalent if and only if
$F_{1}$ satisfies (32) and (35). ∎

##  IV Online Identification of Input/Output Models using Recursive Least
Squares

Next, we discuss the online identification of input/output models using
recursive least squares. We consider input/output model (1) of order $n$ to be
the true system. We define $\theta_{n,{\rm true}}\in{\mathbb{R}}^{p\times
pn+m(n+1)}$ as

$\theta_{n,{\rm
true}}\triangleq\begin{bmatrix}F_{1}&\cdots&F_{n}&G_{0}&\cdots&G_{n}\end{bmatrix}=\begin{bmatrix}{\mathcal{F}}_{n}&{\mathcal{G}}_{n}\end{bmatrix}.$
(36)

It follows from (2) that, for all $k\geq 0$, $y_{k}\in{\mathbb{R}}^{p}$ is
given by

$\displaystyle y_{k}=\theta_{n,{\rm true}}\phi_{n,k},$ (37)

where, for all $k\geq 0$ and $n\geq 0$,
$\phi_{n,k}\in{\mathbb{R}}^{pn+m(n+1)}$ is defined as

$\displaystyle\phi_{n,k}\triangleq\begin{bmatrix}-y_{k-1}\\\ \vdots\\\
-y_{k-n}\\\ u_{k}\\\ \vdots\\\
u_{k-n}\end{bmatrix}=\begin{bmatrix}{\mathcal{Y}}_{k-n,n}\\\
{\mathcal{U}}_{k-n,n}\end{bmatrix}.$ (38)

The objective of online identification is to identify the coefficients an
input/output model (9) of order $\hat{n}$ using measurements of the inputs
$u_{k}$ and outputs $y_{k}$ generated from (1). This can be accomplished by
minimizing the cost function $J_{\hat{n},k}\colon{\mathbb{R}}^{p\times
p\hat{n}+m(\hat{n}+1)}\rightarrow{\mathbb{R}}$, defined as

$\displaystyle J_{\hat{n},k}(\hat{\theta}_{\hat{n}})=$
$\displaystyle\sum_{i=0}^{k}z_{\hat{n},i}^{\rm
T}(\hat{\theta}_{\hat{n}})z_{\hat{n},i}(\hat{\theta}_{\hat{n}})$
$\displaystyle+\operatorname{tr}\left[(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0}){P}_{\hat{n},0}^{-1}(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0})^{\rm
T}\right],$ (39)

where $\hat{\theta}_{\hat{n}}\in{\mathbb{R}}^{p\times p\hat{n}+m(\hat{n}+1)}$
are the coefficients to be identified, defined as

$\displaystyle\hat{\theta}_{\hat{n}}\triangleq\begin{bmatrix}\hat{F}_{1}&\cdots&\hat{F}_{\hat{n}}&\hat{G}_{0}&\cdots&\hat{G}_{\hat{n}}\end{bmatrix}=\begin{bmatrix}\hat{{\mathcal{F}}}_{\hat{n}}&\hat{{\mathcal{G}}}_{\hat{n}}\end{bmatrix},$
(40)

where the residual error function $z_{\hat{n},k}\colon{\mathbb{R}}^{p\times
p\hat{n}+m(\hat{n}+1)}\rightarrow{\mathbb{R}}^{p}$ is defined as

$\displaystyle z_{\hat{n},k}(\hat{\theta}_{\hat{n}})\triangleq
y_{k}-\hat{\theta}_{\hat{n}}\phi_{\hat{n},k},$ (41)

where $\phi_{\hat{n},k}\in{\mathbb{R}}^{p\hat{n}+m(\hat{n}+1)}$ is defined in
(38), and where $\theta_{\hat{n},0}\in{\mathbb{R}}^{p\times
p\hat{n}+m(\hat{n}+1)}$ is an initial guess of the coefficients and
$\bar{P}_{\hat{n},0}^{-1}\in{\mathbb{R}}^{[p^{2}\hat{n}+pm(\hat{n}+1)]\times[p^{2}\hat{n}+pm(\hat{n}+1)]}$
is the positive-definite regularization matrix. The following algorithm from
[9] uses recursive least squares to minimize $J_{\hat{n},k}$.

######  Proposition 3.

For all $k\geq-\hat{n}$, let $u_{k}\in{\mathbb{R}}^{m}$,
$y_{k}\in{\mathbb{R}}^{p}$. Furthermore, let
$\theta_{\hat{n},0}\in{\mathbb{R}}^{p\times p\hat{n}+m(\hat{n}+1)}$ and let
${P}_{\hat{n},0}\in{\mathbb{R}}^{[p\hat{n}+m(\hat{n}+1)]\times[p\hat{n}+m(\hat{n}+1)]}$
be positive definite. Then, for all $k\geq 0$, $J_{\hat{n},k}$, defined in
(IV), has a unique global minimizer, denoted

$\displaystyle\theta_{\hat{n},k+1}\triangleq\operatorname*{arg\,min}_{\hat{\theta}_{\hat{n}}\in{\mathbb{R}}^{p\times\hat{n}(m+p)+m}}J_{k}(\hat{\theta}_{\hat{n}}).$
(42)

which, for all $k\geq 1$, is given by

$\displaystyle\theta_{\hat{n},k}=({\mathcal{Y}}_{0,k}{\Phi}_{\hat{n},k}^{\rm
T}+\theta_{\hat{n},0}{P}_{\hat{n},0}^{-1})({\Phi}_{\hat{n},k}{\Phi}_{\hat{n},k}^{\rm
T}+{P}_{\hat{n},0}^{-1})^{-1},$ (43)

and where ${\Phi}_{\hat{n},k}\in{\mathbb{R}}^{p\hat{n}+m(\hat{n}+1)\times k}$
is defined

$\displaystyle{\Phi}_{\hat{n},k}\triangleq\begin{bmatrix}\phi_{\hat{n},k-1}&\cdots&\phi_{\hat{n},0}\end{bmatrix}.$
(44)

Moreover, for all $k\geq 0$, $\bar{\theta}_{\hat{n},k+1}$ is given recursively
as

$\displaystyle{P}_{\hat{n},k+1}$
$\displaystyle={P}_{\hat{n},k}-\frac{{P}_{\hat{n},k}{\phi}_{\hat{n},k}{\phi}_{\hat{n},k}^{\rm
T}{{P}_{\hat{n},k}}}{1+{\phi}_{\hat{n},k}^{\rm
T}{P}_{\hat{n},k}{\phi}_{\hat{n},k}},$ (45)
$\displaystyle{\theta}_{\hat{n},k+1}$
$\displaystyle={\theta}_{\hat{n},k}+(y_{k}-{\theta}_{\hat{n},k}{\phi}_{\hat{n},k}){\phi}_{\hat{n},k}^{\rm
T}{P}_{\hat{n},k+1}.$ (46)

###### Proof.

See [9] and [17]. ∎

In practice, the recursive formulation (46) is used to update the coefficient
identification in real time as new measurements are obtained. We’ve included
the batch formulation (43) to aid in subsequent analysis. It will also be
beneficial for analysis to note that using Lemma A.1, for all $k\geq 0$, (45)
can be rewritten as

$\displaystyle{P}_{\hat{n},k+1}^{-1}$
$\displaystyle={P}_{\hat{n},k}^{-1}+{\phi}_{\hat{n},k}{\phi}_{\hat{n},k}^{\rm
T}.$ (47)

###  IV-A Convergence with Correct Model Order

We begin by considering the case $\hat{n}=n$, where the correct model order is
known. In this case, the identified coefficients ${\theta}_{n,k}$ and true
model coefficients ${\theta}_{n,{\rm true}}$ are the same dimension, and it is
natural to define the estimation error
$\tilde{\theta}_{n,k}\in{\mathbb{R}}^{p\times pn+m(n+1)}$ as

$\displaystyle\tilde{\theta}_{n,k}\triangleq{\theta}_{n,k}-{\theta}_{n,{\rm
true}}.$ (48)

It then follows from (37), (46), and (47) that, for all $k\geq 0$, the
estimation error dynamics can be written as

$\displaystyle\tilde{\theta}_{{n},k+1}=\tilde{\theta}_{{n},k}{P}_{\hat{n},k}^{-1}{P}_{\hat{n},k+1}.$
(49)

It then follows from (47) that, for all $k\geq 0$,

$\displaystyle\tilde{\theta}_{{n},k}=\tilde{\theta}_{{n},0}{P}_{{n},0}^{-1}{P}_{{n},k}=\tilde{\theta}_{{n},0}{P}_{{n},0}^{-1}({\Phi}_{{n},k-1}{\Phi}_{{n},k-1}^{\rm
T}+{P}_{{n},0}^{-1})^{-1}.$ (50)

We now define the notions of weak persistent excitation and persistent
excitation. Note that persistent excitation implies weak persistent
excitation.

######  Definition 3.

$(\phi_{k})_{k=0}^{\infty}\subset{\mathbb{R}}^{p\times n}$ is weakly
persistently exciting if

$\displaystyle\lim_{k\rightarrow\infty}\bm{\lambda_{\rm
min}}\left[\sum_{i=0}^{k}\phi_{i}^{\rm T}\phi_{i}\right]=\infty.$ (51)

$(\phi_{k})_{k=0}^{\infty}\subset{\mathbb{R}}^{p\times n}$ is persistently
exciting if

$\displaystyle
C\triangleq\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=0}^{k-1}\phi_{i}^{\rm
T}\phi_{i}$ (52)

exists and is positive definite.

Theorem 3 shows that weak persistent excitation is necessary and sufficient
conditions for the global asymptotic stability (GAS) of the error dynamics
(49). For definition of GAS and further discussion on weak persistent
excitation, see [15]. Moreover, Theorem 3 shows that persistent excitation
implies that the convergence of $\tilde{\theta}_{n,k}$ to zero is
asymptotically proportional to $\nicefrac{{1}}{{k}}$.

######  Theorem 3.

Consider the assumptions and notation of Proposition 3. (49) is GAS if and
only of $(\phi_{n,k}^{\rm T})_{k=0}^{\infty}$ is weakly persistently exciting.
Moreover, if $(\phi_{n,k}^{\rm T})_{k=0}^{\infty}$ is persistently exciting,
then

$\displaystyle\lim_{k\rightarrow\infty}k\tilde{\theta}_{n,k}=\tilde{\theta}_{{n},0}{P}_{{n},0}^{-1}C_{n}^{-1},$
(53)

where
$C_{n}\triangleq\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{i=0}^{N-1}{\phi}_{{n},k-1}{\phi}_{{n},k-1}^{\rm
T}$.

Proof. Note that, for all $1\leq i\leq p$,

$\displaystyle(\tilde{\theta}_{\hat{n},k+1}^{i})^{\rm
T}={P}_{\hat{n},k+1}{P}_{\hat{n},k}^{-1}(\tilde{\theta}_{\hat{n},k}^{i})^{\rm
T},$ (54)

where $\tilde{\theta}_{\hat{n},k}^{i}\in{\mathbb{R}}^{1\times pn+m(n+1)}$ is
the $i^{\rm th}$ row of $\tilde{\theta}_{\hat{n},k}$. It follows from Theorem
3 of [15] that (54) is GAS if and only of $(\phi_{n,k}^{\rm
T})_{k=0}^{\infty}$ is weakly persistently exciting. Hence, (49) is GAS if and
only of $(\phi_{n,k}^{\rm T})_{k=0}^{\infty}$ is weakly persistently exciting.
Next, if $(\phi_{n,k}^{\rm T})_{k=0}^{\infty}$ is persistently exciting, it
follows from (50) that

$\displaystyle\lim_{k\rightarrow\infty}k\tilde{\theta}_{{n},k}$
$\displaystyle=\lim_{k\rightarrow\infty}\tilde{\theta}_{{n},0}{P}_{{n},0}^{-1}(\frac{1}{k}{\Phi}_{{n},k-1}{\Phi}_{{n},k-1}^{\rm
T}+\frac{1}{k}{P}_{{n},0}^{-1})^{-1}$
$\displaystyle=\tilde{\theta}_{{n},0}{P}_{{n},0}^{-1}C_{n}^{-1}.$ $\square$

Proposition 4 show that for $(\phi_{n,k}^{\rm T})_{k=0}^{\infty}$ to be weakly
persistently exciting, it is necessary that (1) be irreducible.

######  Proposition 4.

If (1) is reducible, then $(\phi_{n,k}^{\rm T})_{k=0}^{\infty}$ is not weakly
persistently exciting.

###### Proof.

If (1) is reducible, then there exists an equivalent input/output model of
order $n_{\rm r}<n$. Lemma 3 implies that

$\displaystyle\phi_{n,k}=M_{n_{\rm
r},n}\begin{bmatrix}{\mathcal{Y}}_{k-n,n_{\rm r}}\\\
{\mathcal{U}}_{k-n,n}\end{bmatrix}.$

Hence, for all $N\geq 0$,

$\displaystyle\operatorname{rank}(\sum_{k=0}^{N}\phi_{n,k}\phi_{n,k}^{\rm
T})\leq pn_{\rm r}+m(n+1).$

but $\sum_{k=0}^{N}\phi_{n,k}\phi_{n,k}^{\rm
T}\in{\mathbb{R}}^{pn+m(n+1)\times pn+m(n+1)}$. Therefore, for all $N\geq 0$,
$\bm{\lambda_{\rm min}}\left[\sum_{k=0}^{N}\phi_{n,k}\phi_{n,k}^{\rm
T}\right]=0$. ∎

Note that if (1) is reducible, then there exists an equivalent input/output
model of a lower-order which is irreducible. In other words, (1) being
reducible can be viewed as the order of the identified model being higher than
the order of the true model. This case is addressed in the following
subsection.

###  IV-B Convergence with Higher Model Order

Next, we address the case $\hat{n}>n$, where the identified model order is
higher than the model order of the true system. To begin, note that a model of
order $\hat{n}$ which is equivalent to (1) is given by the coefficients111The
trivial equivalent model (55) is chosen because it can be written in terms of
only the true model coefficients.

$\displaystyle\theta_{\hat{n},{\rm
true}}=\begin{bmatrix}{\mathcal{F}}_{n}&0_{p\times
p(\hat{n}-n)}&{\mathcal{G}}_{n}&0_{p\times m(\hat{n}-n)}\end{bmatrix}.$ (55)

In particular, it holds that, for all $k\geq 0$,

$\displaystyle y_{k}=\theta_{\hat{n},{\rm true}}\phi_{\hat{n},k}.$ (56)

Since $\hat{n}>n$, it follows from Proposition 4 that $(\phi_{\hat{n},k}^{\rm
T})_{k=0}^{\infty}$ is not weakly persistently exciting. However, it is
possible that $(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is weakly
persistently exciting, where, for all $k\geq 0$,
$\phi_{n,\hat{n},k}\in{\mathbb{R}}^{pn+m(\hat{n}+1)}$ is defined

$\displaystyle\phi_{n,\hat{n},k}\triangleq\begin{bmatrix}-y_{k-\hat{n}+n-1}\\\
\vdots\\\ -y_{k-\hat{n}}\\\ u_{k}\\\ \vdots\\\
u_{k-\hat{n}}\end{bmatrix}=\begin{bmatrix}{\mathcal{Y}}_{k-\hat{n},n}\\\
{\mathcal{U}}_{k-\hat{n},\hat{n}}\end{bmatrix}.$ (57)

By similar reasoning to Proposition 4, for $(\phi_{n,\hat{n},k}^{\rm
T})_{k=0}^{\infty}$ to be weakly persistently exciting, it is necessary that
(1) be irreducible. Lemma 3 shows that
$\phi_{\hat{n},k}=M_{n,\hat{n}}\phi_{n,\hat{n},k}$ where $M_{n,\hat{n}}$ is
defined in (22).

######  Lemma 3.

For all $k\geq 0$ and $\hat{n}>n$,

$\displaystyle\phi_{\hat{n},k}$
$\displaystyle=M_{n,\hat{n}}\phi_{n,\hat{n},k}.$ (58)

###### Proof.

Note that $\phi_{\hat{n},k}$ can be written as

$\displaystyle\phi_{\hat{n},k}=\begin{bmatrix}{\mathcal{Y}}_{k-\hat{n},\hat{n}}\\\
{\mathcal{Y}}_{k-\hat{n},\hat{n}}\end{bmatrix}=\begin{bmatrix}{\mathcal{Y}}_{k-\hat{n}+n,\hat{n}-n}\\\
{\mathcal{Y}}_{k-\hat{n},n}\\\ {\mathcal{U}}_{k-\hat{n},\hat{n}}\end{bmatrix}$

For all $1\leq i\leq\hat{n}-n$, note that $k-i=(k-\hat{n})+n+(\hat{n}-n-i)$
and it follows from Proposition 1 that

$\displaystyle
y_{k-i}=-{\mathcal{F}}_{n,\hat{n}-n-i}{\mathcal{Y}}_{k-\hat{n},n}+{\mathcal{G}}_{n,\hat{n}-n-i}{\mathcal{U}}_{k-\hat{n},\hat{n}-i}$
$\displaystyle\ \
=-{\mathcal{F}}_{n,\hat{n}-n-i}{\mathcal{Y}}_{k-\hat{n},n}+\begin{bmatrix}0_{p\times
im}&{\mathcal{G}}_{n,\hat{n}-n-i}\end{bmatrix}{\mathcal{U}}_{k-\hat{n},\hat{n}-i}.$

Hence,

$\displaystyle{\mathcal{Y}}_{k-\hat{n}+n,\hat{n}-n}=\begin{bmatrix}M_{n,\hat{n}}^{1}&M_{n,\hat{n}}^{2}\end{bmatrix}\begin{bmatrix}{\mathcal{Y}}_{k-\hat{n},n}\\\
{\mathcal{U}}_{k-\hat{n},\hat{n}}\end{bmatrix},$

and (58) follows from (22). ∎

Proposition 5 shows that input/output model (9) with coefficients
$\hat{\theta}_{\hat{n}}$ is equivalent to (1) if and only if (59) holds. Next,
Proposition 6 give an explicit formulation for the equivalent model of order
$\hat{n}$ which minimizes the regularization term
$\operatorname{tr}\left[(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0}){P}_{\hat{n},0}^{-1}(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0})^{\rm
T}\right]$ of the of cost function $J_{\hat{n},k}$, defined in (IV).

######  Proposition 5.

Input/Output models (1) and (9) are equivalent if and only if

$\displaystyle(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},{\rm
true}})M_{n,\hat{n}}=0_{p\times pn+m(\hat{n}+1)}.$ (59)

###### Proof.

Note that an input/output model of order $\hat{n}$ with coefficients
${\theta}_{\hat{n},{\rm true}}$ is trivially equivalent to (1). Hence, by
Theorem 1, ${\theta}_{\hat{n},{\rm
true}}M_{n,\hat{n}}=\begin{bmatrix}-{{\mathcal{F}}}_{n,\hat{n}-n}&{{\mathcal{G}}}_{n,\hat{n}-n}\end{bmatrix}$.
Then, it also follows from Theorem 1 that (9) is equivalent to (1) if and only
of
$\hat{\theta}_{\hat{n}}M_{n,\hat{n}}=\begin{bmatrix}-{{\mathcal{F}}}_{n,\hat{n}-n}&{{\mathcal{G}}}_{n,\hat{n}-n}\end{bmatrix}={\theta}_{\hat{n},{\rm
true}}M_{n,\hat{n}}$. ∎

######  Proposition 6.

The constrained optimization problem

$\displaystyle\min_{\hat{\theta}_{\hat{n}}\in{\mathbb{R}}^{p\times\hat{n}(m+p)+m}}$
$\displaystyle\operatorname{tr}\left[(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0})P_{\hat{n},0}^{-1}(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0})^{\rm
T}\right],$ (60) such that
$\displaystyle(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},{\rm
true}})M_{n,\hat{n}}=0_{p\times pn+m(\hat{n}+1)},$

has the unique solution

$\displaystyle\theta^{*}_{\hat{n}}\triangleq{\theta}_{\hat{n},0}+({\theta}_{\hat{n},{\rm
true}}-{\theta}_{\hat{n},0})H_{\hat{n}},$ (61)

where hat matrix $H_{\hat{n}}\in{\mathbb{R}}^{p\hat{n}+m(\hat{n}+1)\times
p\hat{n}+m(\hat{n}+1)}$ is defined

$\displaystyle H_{\hat{n}}\triangleq M_{n,\hat{n}}(M_{n,\hat{n}}^{\rm
T}P_{\hat{n},0}M_{n,\hat{n}})^{-1}M_{n,\hat{n}}^{\rm T}P_{\hat{n},0}.$ (62)

###### Proof.

Note that

$\displaystyle\operatorname{tr}\big{[}(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0})$
$\displaystyle
P_{\hat{n},0}^{-1}(\hat{\theta}_{\hat{n}}-{\theta}_{\hat{n},0})^{\rm
T}\big{]}$
$\displaystyle=\sum_{i=1}^{p}(\hat{\theta}_{\hat{n},i}-{\theta}_{\hat{n},0,i})P_{\hat{n},0}^{-1}(\hat{\theta}_{\hat{n},i}-{\theta}_{\hat{n},0,i})^{\rm
T},$

where, for all $1\leq i\leq p$,
$\hat{\theta}_{\hat{n},i}\in{\mathbb{R}}^{1\times\hat{n}(m+p)+m}$ and
${\theta}_{\hat{n},0,i}\in{\mathbb{R}}^{1\times\hat{n}(m+p)+m}$ are the
$i^{\rm th}$ row of $\hat{\theta}_{\hat{n}}$ and ${\theta}_{\hat{n},0}$,
respectively. It then follows that (60) can be written as $p$ separate
optimization problems given by, for all $1\leq i\leq p$,

$\displaystyle\min_{\hat{\theta}_{\hat{n},i}\in{\mathbb{R}}^{1\times\hat{n}(m+p)+m}}$
$\displaystyle(\hat{\theta}_{\hat{n},i}-{\theta}_{\hat{n},0,i})P_{\hat{n},0}^{-1}(\hat{\theta}_{\hat{n},i}-{\theta}_{\hat{n},0,i})^{\rm
T},$ (63) such that $\displaystyle M_{n,\hat{n}}^{\rm
T}\hat{\theta}_{\hat{n},i}^{\rm T}=M_{n,\hat{n}}^{\rm T}{\theta}_{\hat{n},{\rm
true},i}^{\rm T},$

where, for all $1\leq i\leq p$, ${\theta}_{\hat{n},{\rm
true},i}\in{\mathbb{R}}^{1\times\hat{n}(m+p)+m}$ is the $i^{\rm th}$ row of
${\theta}_{\hat{n},{\rm true},i}$. It then follows from Lemma A.2 that, for
all $1\leq i\leq p$, (63) has a unique solution ${\theta}_{\hat{n},i}^{*}$,
given by

$\displaystyle M_{n,\hat{n}}^{\rm T}{\theta_{\hat{n},i}^{*}}^{\rm T}$
$\displaystyle=M_{n,\hat{n}}^{\rm T}\theta_{\hat{n},{\rm true},i}^{\rm T},$
(64) $\displaystyle P_{\hat{n},0}^{-1}{\theta_{\hat{n},i}^{*}}^{\rm
T}+M_{n,\hat{n}}{\nu_{i}^{*}}^{\rm T}$
$\displaystyle=P_{\hat{n},0}^{-1}\theta_{\hat{n},0,i}^{\rm T}.$ (65)

It follows from (65) that

$\displaystyle{\theta_{\hat{n},i}^{*}}^{\rm T}=\theta_{\hat{n},0,i}^{\rm
T}-P_{\hat{n},0}M_{n,\hat{n}}{\nu_{i}^{*}}^{\rm T}.$ (66)

Substituting (66) into (64), it follows that

$\displaystyle M_{n,\hat{n}}^{\rm T}(\theta_{\hat{n},0,i}^{\rm
T}-P_{\hat{n},0}M_{n,\hat{n}}{\nu_{i}^{*}}^{\rm T})=M_{n,\hat{n}}^{\rm
T}\theta_{\hat{n},{\rm true},i}^{\rm T}.$ (67)

Hence, ${\nu_{i}^{*}}^{\rm T}$ is given as

$\displaystyle{\nu_{i}^{*}}^{\rm T}=(M_{n,\hat{n}}^{\rm
T}P_{\hat{n},0}M_{n,\hat{n}})^{-1}M_{n,\hat{n}}^{\rm
T}(\theta_{\hat{n},0,i}^{\rm T}-\theta_{\hat{n},{\rm true},i}^{\rm T}).$ (68)

Substituting (68) into (66), it follows that ${\theta_{\hat{n},i}^{*}}^{\rm
T}=\theta_{\hat{n},0,i}^{\rm T}-P_{\hat{n},0}M_{n,\hat{n}}(M_{n,\hat{n}}^{\rm
T}P_{\hat{n},0}M_{n,\hat{n}})^{-1}M_{n,\hat{n}}^{\rm
T}(\theta_{\hat{n},0,i}^{\rm T}-\theta_{\hat{n},{\rm true},i}^{\rm T}).$
Finally, taking the transpose and noting that ${\theta_{\hat{n},i}^{*}}$ is
the $i^{\rm th}$ row of $\theta_{\hat{n}}^{*}$ yields (61). ∎

As mentioned previously, the input/output model (9) with coefficients given by
$\theta_{\hat{n}}^{*}$ minimizes the regularization term of $J_{\hat{n},k}$
over the set of input/output models of order $\hat{n}$ equivalent to (1).
Theorem 4 show that if $(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is weakly
persistently exciting, then $\theta_{\hat{n},k}$ converges to
$\theta_{\hat{n}}^{*}$. Moreover, if $(\phi_{n,\hat{n},k}^{\rm
T})_{k=0}^{\infty}$ is persistently exciting, then the convergence of
$\theta_{\hat{n},k}-\theta_{\hat{n}}^{*}$ to zero is asymptotically
proportional to $\nicefrac{{1}}{{k}}$.

######  Theorem 4.

Consider the assumptions and notation of Proposition 3. If
$(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is weakly persistently exciting,
then

$\displaystyle\lim_{k\rightarrow\infty}\theta_{\hat{n},k}=\theta_{\hat{n}}^{*},$
(69)

where $\theta_{\hat{n}}^{*}$ is defined in (61). If, additionally,
$(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is persistently exciting, then

$\displaystyle\lim_{k\rightarrow\infty}k(\theta_{\hat{n},k}-\theta_{\hat{n}}^{*})$
$\displaystyle\quad=(\theta_{\hat{n},0}-\theta_{\hat{n},{\rm
true}})M_{n,\hat{n}}W_{n,\hat{n}}^{-1}C_{n,\hat{n}}^{-1}W_{n,\hat{n}}^{-1}M_{n,\hat{n}}^{\rm
T}P_{\hat{n},0},$ (70)

where
$C_{n,\hat{n}}\triangleq\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{k=0}^{k-1}\phi_{n,\hat{n},i}\phi_{n,\hat{n},i}^{\rm
T}$ and $W_{n,\hat{n}}\triangleq M_{n,\hat{n}}^{\rm
T}P_{\hat{n},0}M_{n,\hat{n}}$.

###### Proof.

For brevity, denote $P_{0}\triangleq P_{\hat{n},0}$,
$\theta^{*}\triangleq\theta_{\hat{n}}^{*}$,
$\theta_{0}\triangleq\theta_{\hat{n},0}$,
$\theta\triangleq\theta_{\hat{n},{\rm true}}$, $M\triangleq M_{n,\hat{n}}$,
$H=H_{\hat{n}}$, $W\triangleq W_{n,\hat{n}}$, and, for all $k\geq 0$,
$\theta_{k}\triangleq\theta_{\hat{n},k}$,
$\Phi_{k}\triangleq{\Phi}_{\hat{n},k}$ and
$\bar{\Phi}_{k}\triangleq\begin{bmatrix}\phi_{n,\hat{n},k-1}&\cdots&\phi_{n,\hat{n},0}\end{bmatrix}.$
It follows from (43), (56), and Lemma 3 that, for all $k\geq 0$,

$\displaystyle\theta_{k+1}$ $\displaystyle=(\theta\Phi_{k}\Phi_{k}^{\rm
T}+\theta_{0}P_{0}^{-1})(\Phi_{k}\Phi_{k}^{\rm T}+P_{0}^{-1})^{-1}$
$\displaystyle=\theta+(\theta_{0}-\theta)P_{0}^{-1}(\Phi_{k}\Phi_{k}^{\rm
T}+P_{0}^{-1})^{-1}$
$\displaystyle=\theta+(\theta_{0}-\theta)P_{0}^{-1}(M\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T}M^{\rm T}+P_{0}^{-1})^{-1}.$

Subtracting both sides by $\theta^{*}$ and substituting (61) yields

$\displaystyle\theta_{k+1}-\theta^{*}$ (71)
$\displaystyle\quad=(\theta_{0}-\theta)\big{[}-I+P_{0}^{-1}(M\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T}M^{\rm T}+P_{0}^{-1})^{-1}+H\big{]}.$

Since $(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is weakly persistently
exciting, there exists $N$ such that, for all $k\geq N$,
$\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm T}$ is nonsingular. Then, it follows from
Lemma A.1 that, for all $k\geq N$,

$\displaystyle(M\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm T}M^{\rm T}$
$\displaystyle+P^{-1})^{-1}$
$\displaystyle=P_{0}-P_{0}M[(\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T})^{-1}+W]^{-1}M^{\rm T}P_{0},$

and hence

$\displaystyle-I+P_{0}^{-1}(M\bar{\Phi}_{k}$ $\displaystyle\bar{\Phi}_{k}^{\rm
T}M^{\rm T}+P_{0}^{-1})^{-1}$
$\displaystyle=-M[(\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm T})^{-1}+W]^{-1}M^{\rm
T}P_{0}.$ (72)

Substituting (72) and $H=M(M^{\rm T}P_{0}M)^{-1}M^{\rm T}P_{0}$ into (71)
implies that, for all $k\geq N$,

$\displaystyle\theta_{k+1}$ $\displaystyle-\theta^{*}$
$\displaystyle=(\theta_{0}-\theta)M\left[-[(\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T})^{-1}+W]^{-1}+W^{-1}\right]M^{\rm T}P_{0}.$

Again applying Lemma A.1, it follows that

$-[(\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T})^{-1}+W]^{-1}+W^{-1}=W^{-1}[\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T}-W^{-1}]^{-1}W^{-1}$

which yields

$\theta_{k+1}-\theta^{*}=(\theta_{0}-\theta)MW^{-1}[\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T}-W^{-1}]^{-1}W^{-1}M^{\rm T}P_{0}.$

Since $(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is weakly persistently
exciting, it follows that $\lim_{k\rightarrow\infty}\bm{\lambda_{\rm
min}}\left(\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm T}\right)=\infty$ and
$\lim_{k\rightarrow\infty}\theta_{k+1}-\theta^{*}=0$ and (69) follows. If
additionally, $(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is persistently
exciting, then

$\displaystyle\lim_{k\rightarrow\infty}k(\theta_{k+1}-\theta^{*})$
$\displaystyle=(\theta_{0}-\theta)MW^{-1}[\lim_{k\rightarrow\infty}\frac{1}{k}\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T}-\frac{1}{k}W^{-1}]^{-1}W^{-1}M^{\rm T}P_{0}.$

Since $\lim_{k\rightarrow\infty}\frac{1}{k}\bar{\Phi}_{k}\bar{\Phi}_{k}^{\rm
T}-\frac{1}{k}W^{-1}=C_{n,\hat{n}}$, (4) follows. ∎

Finally, since the input/output model (9) with coefficients given by
$\theta_{\hat{n}}^{*}$ is equivalent to (1) and
$\lim_{k\rightarrow\infty}{\theta}_{\hat{n},k}=\theta_{\hat{n}}^{*}$, an
immediate corollary is that the residual error
$z_{\hat{n},k}({\theta}_{\hat{n},k})$ converges to $0$, where $z_{\hat{n},k}$
is defined in (41).

######  Corollary 1.

Consider the assumptions and notation of Proposition 3. If
$(\phi_{n,\hat{n},k}^{\rm T})_{k=0}^{\infty}$ is weakly persistently exciting,
then

$\displaystyle\lim_{k\rightarrow\infty}z_{\hat{n},k}({\theta}_{\hat{n},k})=0_{p\times
1}.$ (73)

##  V Conclusions

This work shows that when using RLS to identify an input/output model of a
higher-order than that of the true input/output system, the identified
coefficients still converge to predictable values, given weakly persistently
exciting data. In particular, we obtain the very natural result that the
higher-order identified model converges to the model equivalent to the true
system that minimizes the regularization term of RLS.

One outstanding question in our analysis is under what conditions the
persistent excitation condition of Theorem 4 is met. This itself is a deep
question with sufficient conditions developed in [18] and a relaxation of
those conditions presented in [19]. These conditions require that the input be
persistently exciting of a sufficiently high order, see [18] for further
details. One method to guarantee the input is persistently exciting of
arbitrarily high order is to introduce random inputs in, for example, an
$\varepsilon$-greedy control strategy [20]. Designing a suitable input that is
persistently exciting of sufficiently high order relates to the classical
dilemma of exploration and exploitation [21] and is beyond the scope of this
work.

Another issue not addressed explicitly is the case where the order of the
identified input/output model is lower than that of the true input/output
system. One immediate result however, is that if the true system is
irreducible, then the identified model cannot converge to an equivalent model,
as no lower-order equivalent model exists. As a result, the residual error in
the RLS cost will not converge to zero, unlike in the higher-order case (see
Corollary 1).

An important application of this work is the selection of a model order for
online identification. Many criterion rules for model-order selection balance
the trade-off of maximizing goodness of fit of the model (minimizing residual
error in this case) and the simplicity of the model (minimizing model order in
this case) [22]. This work shows how model identification of different orders
perform under idealized conditions, which may help inform model order
selection in more realistic conditions.

## References

  * [1] K. J. Astrom and B. Wittenmark, _Adaptive Control_ , 2nd ed. USA: Addison-Wesley Longman Publishing Co., Inc., 1994.
  * [2] L. Ljung and T. Söderström, _Theory and practice of recursive identification_. MIT press, 1983.
  * [3] G. C. Goodwin and K. S. Sin, _Adaptive filtering prediction and control_. Courier Corporation, 2014.
  * [4] J. C. Willems, “From time series to linear system—part i. finite dimensional linear time invariant systems,” _Automatica_ , vol. 22, no. 5, pp. 561–580, 1986.
  * [5] E. Cuevas, J. Gálvez, S. Hinojosa, O. Avalos, D. Zaldívar, M. Pérez-Cisneros _et al._ , “A comparison of evolutionary computation techniques for iir model identification,” _Journal of Applied Mathematics_ , vol. 2014, 2014.
  * [6] J. C. Willems and J. W. Polderman, _Introduction to mathematical systems theory: a behavioral approach_. Springer Science & Business Media, 1997, vol. 26.
  * [7] L. Shieh and Y. Tsay, “Transformations of a class of multivariable control systems to block companion forms,” _IEEE Transactions on Automatic Control_ , vol. 27, no. 1, pp. 199–203, 1982.
  * [8] N. Al-Muthairi, S. Bingulac, and M. Zribi, “Identification of discrete-time mimo systems using a class of observable canonical-form,” _IEE Proceedings-Control Theory and Applications_ , vol. 149, no. 2, pp. 125–130, 2002.
  * [9] T. W. Nguyen, S. A. U. Islam, D. S. Bernstein, and I. V. Kolmanovsky, “Predictive cost adaptive control: A numerical investigation of persistency, consistency, and exigency,” _IEEE Control Systems Magazine_ , vol. 41, no. 6, pp. 64–96, 2021.
  * [10] S. A. U. Islam, T. W. Nguyen, I. V. Kolmanovsky, and D. S. Bernstein, “Data-driven retrospective cost adaptive control for flight control applications,” _Journal of Guidance, Control, and Dynamics_ , vol. 44, no. 10, pp. 1732–1758, 2021.
  * [11] B. Y. Lai, S. A. U. Islam, S. Nivison, and D. S. Bernstein, “Data-driven retrospective cost adaptive control of a quadrotor uav,” in _AIAA SCITECH 2023 Forum_ , 2023, p. 0694.
  * [12] N. Mohseni, D. S. Bernstein, and M. B. Quadrelli, “Adaptive force control for small celestial body sampling,” in _2022 American Control Conference (ACC)_. IEEE, 2022, pp. 2515–2520.
  * [13] A. Farahmandi and B. Reitz, “Predictive cost adaptive control of a planar missile with unmodeled aerodynamics,” in _AIAA SCITECH 2024 Forum_ , 2024, p. 2218.
  * [14] F. Ding, P. X. Liu, and G. Liu, “Multiinnovation least-squares identification for system modeling,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , vol. 40, no. 3, pp. 767–778, 2009.
  * [15] A. L. Bruce, A. Goel, and D. S. Bernstein, “Necessary and sufficient regressor conditions for the global asymptotic stability of recursive least squares,” _Systems & Control Letters_, vol. 157, p. 105005, 2021.
  * [16] B. Lai, S. A. U. Islam, and D. S. Bernstein, “Regularization-induced bias and consistency in recursive least squares,” in _2021 American Control Conference (ACC)_. IEEE, 2021, pp. 3987–3992.
  * [17] S. A. U. Islam and D. S. Bernstein, “Recursive least squares for real-time implementation [lecture notes],” _IEEE Control Systems Magazine_ , vol. 39, no. 3, pp. 82–85, 2019.
  * [18] J. C. Willems, P. Rapisarda, I. Markovsky, and B. L. De Moor, “A note on persistency of excitation,” _Systems & Control Letters_, vol. 54, no. 4, pp. 325–329, 2005.
  * [19] H. J. Van Waarde, C. De Persis, M. K. Camlibel, and P. Tesi, “Willems’ fundamental lemma for state-space systems and its extension to multiple datasets,” _IEEE Control Systems Letters_ , vol. 4, no. 3, pp. 602–607, 2020.
  * [20] C. J. C. H. Watkins, “Learning from delayed rewards,” 1989.
  * [21] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [22] P. Stoica and Y. Selen, “Model-order selection: a review of information criterion rules,” _IEEE Signal Processing Magazine_ , vol. 21, no. 4, pp. 36–47, 2004.
  * [23] S. P. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.

######  Lemma A.1.

Let $A\in{\mathbb{R}}^{n\times n}$, $U\in{\mathbb{R}}^{n\times p}$,
$C\in{\mathbb{R}}^{p\times p}$, $V\in{\mathbb{R}}^{p\times n}$. Assume $A$,
$C$, and $A+UCV$ are nonsingular. Then,
$(A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}$.

######  Lemma A.2.

Consider the quadratic minimization problem with affine constraints

$\displaystyle\min_{x\in{\mathbb{R}}^{n}}$ $\displaystyle\frac{1}{2}x^{\rm
T}Px+q^{\rm T}x+r,$ (74) such that $\displaystyle Ax=b,$

where $P\in{\mathbb{R}}^{n\times n}$ is positive definite and
$A\in{\mathbb{R}}^{p\times n}$. Then, (74) has a unique solution
$(x^{*},\nu^{*})$ given by the system

$\displaystyle Ax^{*}=b,\quad Px^{*}+A^{\rm T}\nu^{*}=-q.$ (75)

###### Proof.

See section 10.1.1 of [23]. ∎