# SIFt-RLS: Subspace of Information Forgetting Recursive Least Squares

Brian Lai<EMAIL_ADDRESS>Dennis S. Bernstein<EMAIL_ADDRESS>Department
of Aerospace Engineering, The University of Michigan, Ann Arbor, Michigan
48109, United States

###### Abstract

This paper presents subspace of information forgetting recursive least squares
(SIFt-RLS), a directional forgetting algorithm which, at each step, forgets
only in row space of the regressor matrix, or the information subspace. As a
result, SIFt-RLS tracks parameters that are in excited directions while not
changing parameter estimation in unexcited directions. It is shown that SIFt-
RLS guarantees an upper and lower bound of the covariance matrix, without
assumptions of persistent excitation, and explicit bounds are given.
Furthermore, sufficient conditions are given for the uniform Lyapunov
stability and global uniform exponential stability of parameter estimation
error in SIFt-RLS when estimating fixed parameters without noise. SIFt-RLS is
compared to other RLS algorithms from the literature in a numerical example
without persistently exciting data.

###### keywords:

System Identification; Recursive Identification; Parameter Estimation;
Adaptive Systems; Directional Forgetting

and

##  1 Introduction

Recursive least squares (RLS) is a fundamental algorithm in systems and
control theory for the online identification of fixed parameters [21, 1]. An
important property of RLS is that the eigenvalues of the covariance matrix are
monotonically decreasing and may become arbitrarily small [30, subsection
2.3.2], [10], resulting in eventual slow adaptation and inability to track
time-varying parameters [25, 29, 19]. A classical extension of RLS used to
track time-varying parameters is exponential forgetting [15, 14], which uses a
forgetting factor to put exponentially lower weights on older terms in the
least squares cost function. While this allows for continued adaptation of
parameter estimation, a critical issue that arises is, without persistent
excitation, at least one of the eigenvalues the covariance matrix may become
arbitrarily large [15, 10], a phenomenon known as covariance blow up [22] or
covariance windup [1, p. 473]. This results in significant sensitivity to
measurement noise and poor parameter estimation [10].

As such, a well-established heuristic for RLS extensions is that the
eigenvalues of the covariance matrix should have an upper bound and positive
lower bound [29]. Later works have shown that conditions related to the
boundedness of the covariance matrix are sufficient to guarantee stability of
the parameter estimation error [28, 18, 31]. Common approaches to bound the
covariance matrix and further improve tracking of time-varying parameters
include variable-rate forgetting, in which a time-varying forgetting factor is
used [4, 8, 7, 26, 20, 23], and resetting strategies, in which the covariance
matrix is periodically reset to a desired value [11] or slowly converges back
to a desired value when there is little excitation [29, 32, 17]. These methods
address the fact that there may be periods of rich excitation, in which
forgetting old data can more effectively adapt parameter estimates, and
periods of poor excitation, in which it is preferable to rely on old data for
parameter estimation.

While variable-rate forgetting and resetting strategies address periods of
rich and poor excitation, these methods do not address when excitation is
nonuniform. Nonuniform excitation may result in sufficient excitation to
quickly adapt parameters in particular directions (that is, particular linear
combinations of the parameters), while parameters in other directions can only
be slowly adapted or not adapted at all [34, 16, 29]. If it is known a priori
how quickly parameters will vary in different directions and which directions
will be excited, techniques such as multiple forgetting may be suitable, where
different forgetting factors are chosen for different directions [34, 9].
However, a more challenging problem is forgetting when such information is not
known a priori. To tackle this problem, various directional forgetting
techniques have been developed which analyze the regressor and/or the
covariance matrix to gauge which directions are being excited and which are
not [5, 16, 3, 35, 10].

This work presents a new directional forgetting algorithm called subspace of
information forgetting (SIFt) RLS. We begin by presenting a subspace
decomposition of a positive definite matrix into the sum of two positive
semidefinite matrices, one parallel to the subspace and one orthogonal to the
subspace. This decomposition reduces to the decomposition used in [5] when the
subspace is of dimension $1$. We give a thorough analysis of this
decomposition, including the main properties of the decomposition, the
uniqueness of this decomposition, and a duality between the parallel and
orthogonal components.

Next, we develop the SIFt-RLS algorithm, where, at each step, we call the row
space of the regressor the information subspace. At each step, the inverse
covariance matrix (also called the information matrix) is decomposed into the
components parallel and and orthogonal to the information subspace, and
forgetting is applied only to the parallel component. This approach is
developed for vector measurements and specializes to the method in [5] in the
case of scalar measurements. Forgetting techniques for parameter estimation
with vector measurements are useful, for example, in adaptive control of
multiple-input, multiple-output (MIMO) systems [24, 14].

Finally, we give explicit upper and lower bounds for the eigenvalues of the
covariance matrix in SIFt-RLS that are guaranteed without persistent
excitation. This goes beyond the analysis of [5] which only shows the
existence of bounds. Moreover, we show a striking similarity between the
eigenvalue bounds of exponential forgetting that are guaranteed with
persistent excitation and the eigenvalue bounds of SIFt. This shows that
forgetting in the information subspace yields analogous bounds to uniform
forgetting when all directions are excited. Furthermore, a counterexample
shows that [35], a different vector measurement extension of [5], does not
guarantee an upper bound on the eigenvalues of the covariance matrix as SIFt
does. Finally, we provide sufficient conditions for the uniform Lyapunov
stability and global uniform exponential stability of the estimation error
dynamics of SIFt-RLS.

###  1.1 Notation and Terminology

$I_{n}$ denotes the $n\times n$ identity matrix, and $0_{m\times n}$ denotes
the $m\times n$ zero matrix. For $B\in{\mathbb{R}}^{m\times n}$,
$\bm{\sigma_{\rm max}}(B)$ denotes the largest singular value of $B$, and
$\bm{\sigma_{\rm min}}(B)$ denotes the smallest singular value of $B$. For
symmetric $A\in{\mathbb{R}}^{n\times n}$, let the $n$ real eigenvalues of $A$
be denoted by $\bm{\lambda_{\rm
min}}(A)\triangleq\bm{\lambda_{n}}(A)\leq\cdots\leq\bm{\lambda_{\rm
max}}(A)\triangleq\bm{\lambda_{1}}(A)$. Additionally, the spectral radius of
$A$, $\rho(A)$, is defined as

$\displaystyle\rho(A)\triangleq\max\\{|\bm{\lambda_{1}}(A)|,\cdots,|\bm{\lambda_{n}}(A)|\\}.$
(1)

Furthermore, if A is positive definite, the singular values of $A$ are
equivalent to the eigenvalues of $A$ and the condition number of A,
$\kappa(A)$, can be expressed as

$\displaystyle\kappa(A)\triangleq\frac{\bm{\sigma_{\rm
max}}(A)}{\bm{\sigma_{\rm min}}(A)}=\frac{\bm{\lambda_{\rm
max}}(A)}{\bm{\lambda_{\rm min}}(A)}.$ (2)

If $A$ is positive semidefinite but not positive definite, then
$\kappa(A)\triangleq\infty.$

For $x\in{\mathbb{R}}^{n}$, $\|x\|$ denotes the Euclidean norm of $x$. For
$B\in{\mathbb{R}}^{m\times n}$, $B^{+}$ denotes the Moore-Penrose inverse of
$B$. $\mathcal{R}(B)$ and $\mathcal{N}(B)$ denote the column space and
nullspace of $B$, respectively. For positive-semidefinite
$R\in{\mathbb{R}}^{n\times n}$ and $x\in{\mathbb{R}}^{n}$,
$\|x\|_{R}\triangleq\sqrt{x^{\rm T}Rx}$. Let
$(a_{k})_{k=0}^{\infty}\subset{\mathbb{R}}^{m\times n}$ denote that, for all
$k\geq 0$, $a_{k}\in{\mathbb{R}}^{m\times n}$. For
$P,Q\in{\mathbb{R}}^{n\times n}$, let $P\prec Q$ (respectively $P\preceq Q$)
denote that $Q-P$ is positive definite (respectively positive semidefinite).

######  Definition 1.

A sequence $(\phi_{k})_{k=0}^{\infty}\subset{\mathbb{R}}^{p\times n}$ is
persistently exciting if there exist $N\geq 1$ and $\alpha>0$ such that, for
all $k\geq 0$,

$\displaystyle\alpha I_{n}\preceq\sum_{i=k}^{k+N}\phi_{i}^{\rm T}\phi_{i}.$
(3)

Furthermore, $\alpha$ and $N$ are, respectively, the lower bound and
persistency window of $(\phi_{k})_{k=0}^{\infty}$.

######  Definition 2.

A sequence $(\phi_{k})_{k=0}^{\infty}\subset{\mathbb{R}}^{p\times n}$ is
bounded if there exist $\beta>0$ such that, for all $k\geq 0$,

$\displaystyle\phi_{k}^{\rm T}\phi_{k}\preceq\beta I_{n}.$ (4)

Furthermore, $\beta$ is the upper bound of $(\phi_{k})_{k=0}^{\infty}$.

##  2 RLS with Exponential Forgetting

To begin, we introduce RLS with exponential forgetting in Proposition 3, which
gives a recursive way to compute the global minimizer of a least squares cost
with exponentially smaller weighting on older terms. This background will be
useful for later comparison with SIFt-RLS.

######  Proposition 3.

For all $k\geq 0$, let $\phi_{k}\in{\mathbb{R}}^{p\times n}$ and
$y_{k}\in{\mathbb{R}}^{p}$. Furthermore, let $\theta_{0}\in{\mathbb{R}}^{n}$,
let $R_{0}\in{\mathbb{R}}^{n\times n}$ be positive definite, and let
$\lambda\in(0,1)$. For all $k\geq 0$, define the function
$J_{k}\colon{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ by

$\displaystyle
J_{k}(\hat{\theta})\triangleq\lambda^{k+1}\|\hat{\theta}-\theta_{0}\|_{R_{0}}^{2}+\sum_{i=0}^{k}\lambda^{k-i}\|y_{i}-\phi_{i}\hat{\theta}\|_{2}.$
(5)

Then, $J_{k}$ has a unique global minimizer, denoted

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

which, for all $k\geq 0$, is given recursively by

$\displaystyle R_{k+1}$ $\displaystyle=\lambda R_{k}+\phi_{k}^{\rm
T}\phi_{k},$ (7) $\displaystyle\theta_{k+1}$
$\displaystyle=\theta_{k}+P_{k+1}\phi_{k}^{\rm T}(y_{k}-\phi_{k}\theta_{k}),$
(8)

where, for all $k\geq 0$, $R_{k}\in{\mathbb{R}}^{n\times n}$ is positive
definite and $P_{k}\triangleq R_{k}^{-1}\in{\mathbb{R}}^{n\times n}$.
Moreover, for all $k\geq 0$, $P_{k+1}$ is given recursively by

$\displaystyle
P_{k+1}=\frac{1}{\lambda}P_{k}-\frac{1}{\lambda}P_{k}\phi_{k}^{\rm T}(\lambda
I_{p}+\phi_{k}P_{k}\phi_{k}^{\rm T})^{-1}\phi_{k}P_{k}.$ (9)

######  Proof 2.1.

See Theorem 1 of [14].

For all $k\geq 0$, We call $y_{k}\in{\mathbb{R}}^{p}$ the measurement,
$\phi_{k}\in{\mathbb{R}}^{p\times n}$ the regressor, and
$\theta_{k}\in{\mathbb{R}}^{n}$ the parameter estimate. Moreover, we call
$R_{k}\in{\mathbb{R}}^{n\times n}$ is the information matrix, and
$P_{k}\in{\mathbb{R}}^{n\times n}$ the covariance matrix. Finally, we call
$\lambda\in(0,1)$ the forgetting factor.

Note that RLS with exponential forgetting may experience covariance windup,
where some of the eigenvalues of the covariance matrix $P_{k}$ may become
unbounded as $k\rightarrow\infty$ (e.g. see example 3 of [10]). However, if
the sequence of regressors $(\phi_{k})_{k=0}^{\infty}$ is persistently
exciting and bounded, then $P_{k}$ has guaranteed upper and lower bounds [10].
Proposition 4 gives an expression for these bounds in the special case where
the persistency window is $N=1$. For bounds in the case $N>1$, see Proposition
4 of [10].

######  Proposition 4.

Let $\lambda\in(0,1)$, let $\theta_{0}\in{\mathbb{R}}^{n}$, and let
$R_{0}\in{\mathbb{R}}^{n\times n}$ be positive definite. For all $k\geq 0$,
let $y_{k}\in{\mathbb{R}}^{p}$, and $\phi_{k}\in{\mathbb{R}}^{p\times n}$.
Finally, for all $k\geq 0$, let $R_{k}\in{\mathbb{R}}^{n\times n}$ and
$\theta_{k}\in{\mathbb{R}}^{n}$ be recursively updated by (7) and (8) and
$P_{k}\triangleq R_{k}^{-1}$. Then the following statements hold:

  1. 1.

If $\left(\phi_{k}\right)_{k=0}^{\infty}$ is persistently exciting with lower
bound $\alpha>0$ and persistency window $N=1$, then, for all $k\geq 0$,

$\displaystyle\bm{\lambda_{\rm min}}(R_{k})$
$\displaystyle\geq\min\\{\frac{\alpha}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\},$ (10) $\displaystyle\bm{\lambda_{\rm max}}(P_{k})$
$\displaystyle\leq\max\\{\frac{1-\lambda}{\alpha},\bm{\lambda_{\rm
max}}(P_{0})\\}.$ (11)

  2. 2.

If $\left(\phi_{k}\right)_{k=0}^{\infty}$ is bounded with upper bound
$\beta\in(0,\infty)$, then, for all $k\geq 0$,

$\displaystyle\bm{\lambda_{\rm
max}}(R_{k})\leq\max\\{\frac{\beta}{1-\lambda},\bm{\lambda_{\rm
max}}(R_{0})\\},$ (12) $\displaystyle\bm{\lambda_{\rm
min}}(P_{k})\geq\min\\{\frac{1-\lambda}{\beta},\bm{\lambda_{\rm
min}}(P_{0})\\}.$ (13)

######  Proof 2.2.

We first prove (1) by induction. For brevity, let
$a\triangleq\min\\{\frac{\alpha}{1-\lambda},\bm{\lambda_{\rm min}}(R_{0})\\}$.
For the base case, note that $\bm{\lambda_{\rm min}}(R_{0})\geq a$ immediately
holds. Next, assume for inductive hypothesis that $\bm{\lambda_{\rm
min}}(R_{k})\geq a$. It follows from (7), Lemma 3, and persistent excitation
of $\left(\phi_{k}\right)_{k=0}^{\infty}$ that $\bm{\lambda_{\rm
min}}(R_{k+1})\geq\lambda a+\alpha$. Substituting
$a=\min\\{\frac{\alpha}{1-\lambda},\bm{\lambda_{\rm min}}(R_{0})\\}$ yields
$\bm{\lambda_{\rm
min}}(R_{k+1})\geq\min\\{\frac{\alpha}{1-\lambda},\lambda\bm{\lambda_{\rm
min}}(R_{0})+\alpha\\}I_{n}$.

In the case where $\bm{\lambda_{\rm min}}(R_{0})\geq\frac{\alpha}{1-\lambda}$,
it follows that $\lambda\bm{\lambda_{\rm
min}}(R_{0})+\alpha\geq\lambda(\frac{\alpha}{1-\lambda})+\alpha=\frac{\alpha}{1-\lambda}\geq
a$. In the case where $\bm{\lambda_{\rm
min}}(R_{0})<\frac{\alpha}{1-\lambda}$, it follows that
$\lambda\bm{\lambda_{\rm min}}(R_{0})+\alpha\geq\bm{\lambda_{\rm
min}}(R_{0})\geq a$. Hence, $R_{k+1}\succeq aI_{n}$, and (10) holds by
mathematical induction. Lastly (11) follows directly from (10) since, for all
$k\geq 0$, $P_{k}=R_{k}^{-1}$. Statement (2) can be proven using similar
reasoning.

##  3 Subspace Decomposition of a Positive-Definite Matrix

This section presents a novel decomposition of a positive-definite matrix
$A\in{\mathbb{R}}^{n\times n}$ into the sum of two positive-semidefinite
matrices based on the choice of a subspace $S\subset{\mathbb{R}}^{n}$. This
decomposition will be the main tool used in SIFt-RLS. Note that this
decomposition reduces to the decomposition proposed in [5] when subspace $S$
is dimension $1$. To begin, Definition 5 defines the proposed matrix
decomposition.

######  Definition 5.

Let $S\subset{\mathbb{R}}^{n}$ be a subspace of dimension $p\leq n$ and let
$A\in{\mathbb{R}}^{n\times n}$ be positive definite. Let
$v_{1},\ldots,v_{p}\in{\mathbb{R}}^{n}$ be a basis for $S$ and
$v\triangleq\begin{bmatrix}v_{1}&\cdots&v_{p}\end{bmatrix}\in{\mathbb{R}}^{n\times
p}$. Then, define the operators $\parallel$ and $\perp$ as

$\displaystyle A^{\parallel S}$ $\displaystyle\triangleq
Av(v^{T}Av)^{-1}v^{T}A\in{\mathbb{R}}^{n\times n},$ (14) $\displaystyle
A^{\perp S}$ $\displaystyle\triangleq A-A^{\parallel
S}\in{\mathbb{R}}^{n\times n},$ (15)

where, by Lemma 7, $v^{\rm T}Av\in{\mathbb{R}}^{p\times p}$ is nonsingular.

We call $A^{\parallel S}$ “$A$ parallel to $S$” and $A^{\perp S}$ “$A$
orthogonal to $S$”. We call the equality $A=A^{\parallel S}+A^{\perp S}$ the
“$S$ subspace decomposition of $A$”. Next, Proposition 6 shows that the
matrices $A^{\parallel S}$ and $A^{\perp S}$ do not depend on the choice of
basis for $S$.

######  Proposition 6.

Let $S\subset{\mathbb{R}}^{n}$ be a subspace of dimension $p\leq n$ and let
$A\in{\mathbb{R}}^{n\times n}$ be positive definite. Let
$v_{1},\cdots,v_{p}\in{\mathbb{R}}^{n}$ and
$w_{1},\cdots,w_{p}\in{\mathbb{R}}^{n}$ be a bases for $S$ and
$v\triangleq\begin{bmatrix}v_{1}&\cdots&v_{p}\end{bmatrix}\in{\mathbb{R}}^{n\times
p}$,
$w\triangleq\begin{bmatrix}w_{1}&\cdots&w_{p}\end{bmatrix}\in{\mathbb{R}}^{n\times
p}$. Then,

$\displaystyle Av(v^{\rm T}Av)^{-1}v^{\rm T}A=Aw(w^{\rm T}Aw)^{-1}w^{\rm T}A.$
(16)

######  Proof 3.1.

Since $v$ and $w$ are both bases for $S$, there exists invertible
$P\in{\mathbb{R}}^{p\times p}$ such that $v=wP$. Then, (16) follows from
substituting $v=wP$ in $Av(v^{\rm T}Av)^{-1}v^{\rm T}A$.

###  3.1 Properties

Theorem 1 now gives the main properties of the matrices $A^{\parallel S}$ and
$A^{\perp S}$ in the $S$ subspace decomposition of $A$.

######  Theorem 1 (Properties of $A^{\parallel S}$ and $A^{\perp S}$).

Let $S\subset{\mathbb{R}}^{n}$ be a subspace of dimension $p\leq n$ and let
$A\in{\mathbb{R}}^{n\times n}$ be positive definite. Then, $A$ can be
decomposed into

$\displaystyle A=A^{\parallel S}+A^{\perp S},$ (17)

where $A^{\parallel S}\in{\mathbb{R}}^{n\times n}$, given by (14), satisfies
the properties:

  1. (1a)

$A^{\parallel S}$ is positive semidefinite,

  2. (2a)

$\operatorname{rank}(A^{\parallel S})=p$,

  3. (3a)

For all $x\in S$, $A^{\parallel S}x=Ax$.

and $A^{\perp S}\in{\mathbb{R}}^{n\times n}$, given by (15), satisfies the
properties:

  1. (1b)

$A^{\perp S}$ is positive semidefinite,

  2. (2b)

$\operatorname{rank}(A^{\perp S})=n-p$,

  3. (3b)

For all $x\in S$, $A^{\perp S}x=0$.

######  Proof 3.2.

See Appendix Section B.

Note that properties 2a) and 3a) imply that $\mathcal{R}(A^{\parallel S})=AS$
and properties 2b) and 3b) imply that $\mathcal{N}(A^{\perp S})=S$.

Next, Theorem 2 shows that $A^{\parallel S}$ is the unique matrix satisfying
properties (1a*), (2a), and (3a) of Theorem 2. Note that since property (1a)
of Theorem 1 implies property (1a*), $A^{\parallel S}$ is also the unique
matrix satisfying properties (1a), (2a), and (3a) of Theorem 1.

######  Theorem 2 (Uniqueness of $A^{\parallel S}$).

Let $S\subset{\mathbb{R}}^{n}$ be a subspace of dimension $p\leq n$ and
$A\in{\mathbb{R}}^{n\times n}$ be positive definite. If
$\tilde{A}\in{\mathbb{R}}^{n\times n}$ satisfies the properties

  1. (1a*)

$\tilde{A}$ is symmetric,

  2. (2a)

$\operatorname{rank}(\tilde{A})=p$,

  3. (3a)

For all $x\in S$, $\tilde{A}x=Ax$,

then $\tilde{A}=A^{\parallel S}$.

######  Proof 3.3.

See Appendix Section B.

Next, Definition 7 defines the $\langle\cdot,\cdot\rangle_{A}$ inner product
for positive-definite matrix $A$ and Definition 8 defines $S^{\perp_{A}}$, the
orthogonal complement of subspace $S$ under this inner product. Finally,
Proposition 9 shows a duality between the $\parallel$ and $\perp$ operators
and the subspaces $S$ and $S^{\perp_{A}}$.

######  Definition 7.

Let $A\in{\mathbb{R}}^{n\times n}$ be positive definite. Define the inner
product
$\langle\cdot,\cdot\rangle_{A}\colon{\mathbb{R}}^{n}\times{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$
as

$\displaystyle\langle x,y\rangle_{A}\triangleq x^{\rm T}Ay.$ (18)

######  Definition 8.

Let $S\subset{\mathbb{R}}^{n}$ be a subspace and let
$A\in{\mathbb{R}}^{n\times n}$ be positive definite. Define the orthogonal
complement of $S$ under the inner product $\langle\cdot,\cdot\rangle_{A}$ as

$\displaystyle
S^{\perp_{A}}\triangleq\left\\{x\in{\mathbb{R}}^{m}:\textnormal{for all $y\in
S$, }\langle x,y\rangle_{A}=0\right\\}.$ (19)

######  Proposition 9 (Duality).

Let $S\subset{\mathbb{R}}^{n}$ be a subspace of dimension $p\leq n$ and let
$A\in{\mathbb{R}}^{n\times n}$ be positive definite. Then,

$\displaystyle A^{\parallel S}$ $\displaystyle=A^{\perp(S^{\perp_{A}})},$ (20)
$\displaystyle A^{\perp S}$ $\displaystyle=A^{\parallel(S^{\perp_{A}})}.$ (21)

######  Proof 3.4.

See Appendix Section B.

##  4 SIFt-RLS

To motivate this algorithm, suppose there exists true parameters
$\theta\in{\mathbb{R}}^{n}$ such that, for all $k\geq 0$,
$y_{k}=\phi_{k}\theta$. Then, at any $k\geq 0$, knowledge of the regressor
$\phi_{k}\in{\mathbb{R}}^{p\times n}$ and measurement
$y_{k}\in{\mathbb{R}}^{p}$ only provide information about the true parameters
in the row space of $\phi_{k}$. For example, a regressor $\phi_{k}=[1\ 1\ 0]$
only informs about the sum of the first two parameters of
$\theta\in{\mathbb{R}}^{3}$. We call the row space of $\phi_{k}$, i.e.
$\mathcal{R}({\phi}_{k}^{\rm T})$, the information subspace.

Note that in (7), $R_{k}$ is multiplied by $\lambda\in(0,1)$, which can be
interpreted as forgetting uniformly over all directions. Covariance windup in
exponential forgetting RLS occurs when the information subspace does not
contain particular directions over a large number of time steps, while
forgetting is uniform. As a result, persistent excitation conditions are often
used to guarantee excitation in all directions.

We propose subspace of information forgetting recursive least squares, or
SIFt-RLS, a directional forgetting algorithm which, at each step $k\geq 0$,
only forgets in the information subspace of that step. To summarize the
algorithm, at each step $k\geq 0$, SIFt-RLS involves three parts:

  1. 1.

Information Filtering: First, we take a compact singular value decomposition
(SVD) of the regressor $\phi_{k}\in{\mathbb{R}}^{p\times n}$ to truncate any
singular values smaller than a desired threshold. This gives the filtered
regressor $\bar{\phi}_{k}$ and filtered measurement $\bar{y}_{k}$. This step
is critical to ensure the algorithm is numerically stable.

  2. 2.

Subspace of Information Forgetting (SIFTing): Next, we decompose the
information matrix $R_{k}$ using the subspace decomposition presented in
section 3 with the information subspace $\mathcal{R}(\bar{\phi}_{k}^{\rm T})$.
Forgetting is applied only to the component of $R_{k}$ parallel to the
information subspace.

  3. 3.

Update: Lastly, we compute the updated information matrix $R_{k+1}$ and
parameter estimate $\theta_{k+1}$ using the filtered regressor and filtered
measurement.

Furthermore, we also provide a way to directly update the covariance matrix
$P_{k}\triangleq R_{k}^{-1}$ in steps 2 and 3 using the matrix inversion
Lemma, which is more computationally efficient when $p\ll n$. The next three
subsections provide details on the three parts of SIFt-RLS. The algorithm is
initialized with forgetting factor $\lambda\in(0,1)$, tuning parameter
$\varepsilon>0$, initial estimate of parameters
$\theta_{0}\in{\mathbb{R}}^{n}$, initial positive-definite information matrix
$R_{0}\in{\mathbb{R}}^{n\times n}$, and initial covariance matrix
$P_{0}^{-1}$.

###  4.1 Information Filtering

To begin, let $\varepsilon>0$ be a tuning parameter which, for all $k\geq 0$,
will be used to truncate small singular values of $\phi_{k}$. Next, let
$\phi_{k}=U_{k}\Sigma_{k}V_{k}^{\rm T}$ be the compact SVD of $\phi_{k}$ with
the singular values on the diagonal of $\Sigma_{k}$ in descending order.111If
$p\leq n$, then $U_{k}\in{\mathbb{R}}^{p\times p}$,
$\Sigma_{k}\in{\mathbb{R}}^{p\times p}$, and $V_{k}\in{\mathbb{R}}^{n\times
p}$. If $p>n$, then $U_{k}\in{\mathbb{R}}^{p\times n}$,
$\Sigma_{k}\in{\mathbb{R}}^{n\times n}$, and $V_{k}\in{\mathbb{R}}^{n\times
n}$.222This is more computationally efficient than computing the full SVD of
$\phi_{k}$. The compact SVD can, for example, be computed in MATLAB as [U,S,V]
= svd(phi,"econ").333Note that, for computational efficiency, the right
singular vectors $V_{k}$ do not need to be computed. Let $q_{k}$ be the number
of singular values of $\phi_{k}$ greater or equal to $\sqrt{\varepsilon}$ and
define $\bar{U}_{k}\in{\mathbb{R}}^{p\times q_{k}}$ as the first $q_{k}$
columns of $U_{k}$. Then, define the filtered regressor,
$\bar{\phi}_{k}\in{\mathbb{R}}^{q_{k}\times n}$, and filtered measurement
$\bar{y}_{k}\in{\mathbb{R}}^{q_{k}}$ by

$\displaystyle\bar{\phi}_{k}\triangleq\bar{U}_{k}^{\rm T}\phi_{k},$ (22)
$\displaystyle\bar{y}_{k}\triangleq\bar{U}_{k}^{\rm T}y_{k}.$ (23)

Note that, by construction, all singular values of $\bar{\phi}_{k}$ are
greater or equal to $\sqrt{\varepsilon}$.

###  4.2 Subspace of Information Forgetting (SIFting)

For all $k\geq 0$, define $R_{k}^{\parallel}\in{\mathbb{R}}^{n\times n}$ and
$R_{k}^{\perp}\in{\mathbb{R}}^{n\times n}$ as

$\displaystyle R_{k}^{\parallel}$ $\displaystyle\triangleq
R_{k}^{\parallel\mathcal{R}(\bar{\phi}_{k}^{\rm T})}=R_{k}\bar{\phi}_{k}^{\rm
T}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})^{-1}\bar{\phi}_{k}R_{k},$ (24)
$\displaystyle R_{k}^{\perp}$ $\displaystyle\triangleq
R_{k}^{\perp\mathcal{R}(\bar{\phi}_{k}^{\rm
T})}=R_{k}-R_{k}\bar{\phi}_{k}^{\rm T}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T})^{-1}\bar{\phi}_{k}R_{k},$ (25)

where the operators $\parallel$ and $\perp$ are defined in Definition 5 and
$\mathcal{R}(\bar{\phi}_{k}^{\rm T})$ is the information subspace. It will
later be shown in Corollary 12 that the matrix
$\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T}$ is nonsingular and, under mild
conditions, is well-conditioned. Hence, for all $k\geq 0$, the information
subspace decomposition of $R_{k}$ can be expressed as

$\displaystyle R_{k}=R_{k}^{\parallel}+R_{k}^{\perp}.$ (26)

Next, we forget in only the information subspace to get the SIFted information
matrix $\bar{R}_{k}\in{\mathbb{R}}^{n\times n}$, defined as

$\displaystyle\bar{R}_{k}$ $\displaystyle\triangleq\lambda
R_{k}^{\parallel}+R_{k}^{\perp}$
$\displaystyle=R_{k}-(1-\lambda)R_{k}\bar{\phi}_{k}^{\rm
T}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})^{-1}\bar{\phi}_{k}R_{k}.$ (27)

Furthermore, we define the SIFted covariance matrix as
$\bar{P}_{k}\triangleq\bar{R}_{k}^{-1}\in{\mathbb{R}}^{n\times n}$. Note that
it will later be shown in Corollary 11 that $\bar{R}_{k}$ is positive
definite, and hence nonsingular. The matrix inversion lemma (Lemma 1) can also
be used to express $\bar{P}_{k}$ as

$\displaystyle\bar{P}_{k}$
$\displaystyle=P_{k}+\frac{1-\lambda}{\lambda}\bar{\phi}_{k}^{\rm
T}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})^{-1}\bar{\phi}_{k}.$ (28)

###  4.3 Update

Lastly, for all $k\geq 0$, we compute the updated information matrix,
$R_{k+1}\in{\mathbb{R}}^{n\times n}$, and updated parameter vector estimate,
$\theta_{k+1}\in{\mathbb{R}}^{n}$ as

$\displaystyle R_{k+1}$ $\displaystyle=\bar{R}_{k}+\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k},$ (29) $\displaystyle\theta_{k+1}$
$\displaystyle=\theta_{k}+P_{k+1}\bar{\phi}_{k}^{\rm
T}(\bar{y}_{k}-\bar{\phi}_{k}\theta_{k}),$ (30)

where $P_{k+1}\triangleq R_{k+1}^{-1}\in{\mathbb{R}}^{n\times n}$. It will
later be shown in Corollary 11 that $R_{k+1}$ is positive definite, and hence
nonsingular. Furthermore, note that the matrix inversion Lemma (Lemma 1) can
be used to express $P_{k+1}$ as

$\displaystyle P_{k+1}$
$\displaystyle=\bar{P}_{k}-\bar{P}_{k}\bar{\phi}_{k}^{\rm
T}(I_{q_{k}}+\bar{\phi}_{k}\bar{P}_{k}\bar{\phi}_{k}^{\rm
T})^{-1}\bar{\phi}_{k}\bar{P}_{k}.$ (31)

###  4.4 Implementation and Computational Cost

This subsection summarizes some subtleties in implementing SIFt-RLS which
minimize computational cost and ensure numerical stability. We also analyze
the computational complexity of SIFT-RLS and discuss when it is or is not
efficient to use the matrix inversion Lemma to update the covariance matrix.

To begin our discussion on the computational cost of SIFt-RLS, note that, for
all $k\geq 0$, the computational complexity of the compact SVD of $\phi_{k}$
is $\mathcal{O}(\min\\{pn^{2},p^{2}n\\})$ (See Lecture 31 of [33]). Next, note
that $\bar{R}_{k}$, defined in (27), can be computed in
$\mathcal{O}(q_{k}n^{2})$ time complexity, where $q_{k}\leq\min\\{p,n\\}$ be
the number of singular values of $\phi_{k}$ larger than $\sqrt{\varepsilon}$.
This is done by first computing $L_{k}\triangleq\bar{\phi}_{k}R_{k}$, then
computing $\bar{R}_{k}=R_{k}-(1-\lambda)L_{k}^{\rm T}(L_{k}\bar{\phi}_{k}^{\rm
T})^{-1}L_{k}$.444Computing $L_{k}$ is important because standard left to
right multiplication of (27) results in $\mathcal{O}(n^{3})$ time complexity.
A concern in practice is that the calculation of $\bar{R}_{k}$ over many steps
may cause $\bar{R}_{k}$ to drift from symmetric due to round-off errors,
resulting in numerical instability. A simple solution is to recompute
$\bar{R}_{k}\leftarrow\frac{1}{2}(\bar{R}_{k}+\bar{R}_{k}^{\rm T})$ at each
step.

Furthermore, note that, for all $k\geq 0$, the updated parameter estimate
$\theta_{k+1}$, given by (30) is most efficiently computed with the ordering
$\theta_{k+1}=\theta_{k}+P_{k+1}[\bar{\phi}_{k}^{\rm
T}(\bar{y}_{k}-\bar{\phi}_{k}\theta_{k})]$. This computation requires the
updated covariance matrix $P_{k+1}$, which can either be computed by first
computing $\bar{P}_{k}$ using (28) then computing $P_{k+1}$ using (31), or by
directly inverting $R_{k+1}$.

Using the matrix inversion lemma, the matrix $\bar{P}_{k}$ can be computed in
$\mathcal{O}(q_{k}n^{2})$ as
$\bar{P}_{k}=P_{k}+\frac{1-\lambda}{\lambda}\bar{\phi}_{k}^{\rm
T}(L_{k}\bar{\phi}_{k}^{\rm T})^{-1}\bar{\phi}_{k}$. Then, $P_{k+1}$ can be
computed in $\mathcal{O}(q_{k}n^{2})$ by first computing
$M_{k}\triangleq\bar{\phi}_{k}\bar{P}_{k}$, then computing
$P_{k+1}=\bar{P}_{k}-M_{k}^{\rm T}(I_{q_{k}}+M_{k}\bar{\phi}_{k}^{\rm
T})^{-1}M_{k}$.555First computing $M_{k}$ is important because standard left
to right matrix multiplication of (31) results in $\mathcal{O}(n^{3})$ time
complexity. Similarly, $P_{k+1}$ may drift from symmetric when computed using
the matrix inversion Lemma due to round-off errors. A solution is to recompute
$P_{k+1}\leftarrow\frac{1}{2}(P_{k+1}+P_{k+1}^{\rm T})$ at each step. In
contrast, the computational complexity to compute $P_{k+1}$ by directly
inverting $R_{k+1}$ is $\mathcal{O}(n^{3})$.

In practice, however, it is only faster to compute $P_{k+1}$ using the matrix
inversion lemma via (28) and (31) if $q_{k}\ll n$. Note that
$q_{k}\in\\{0,1,\ldots,\min\\{p,n\\}\\}$ may change at each step but $n$
remains constant. Hence, we suggest to select $q_{\rm
max}\in\\{1,2,\ldots,\min\\{p,n\\}\\}$ such that if $q_{k}\leq q_{\rm max}$,
$P_{k+1}$ is computed using (28) and (31), otherwise $P_{k+1}$ is computed by
directly inverting $R_{k+1}$. Figure 1 gives data on which method is faster
for various values of $q_{k}$ and $n$ as well as suggest values of $q_{\rm
max}$ as a function of $n$. It is important to note that the choice of $q_{\rm
max}$ only affects computational cost, not the algorithm itself.
Alternatively, for simpler implementation, one can select $q_{\rm max}=0$ to
always perform direct inversion or $q_{\rm max}=p$ to always use the matrix
inversion lemma.

Figure 1: Comparison of computation time to compute $P_{k+1}$ in SIFt-RLS,
tested in MATLAB on an i7-6600U processor with 16 GB of RAM. Blue x indicates
that, for the given values of $q_{k}$ and $n$, it is faster, on average, to
compute $P_{k+1}\in{\mathbb{R}}^{n\times n}$ using the matrix inversion lemma
via (28) and (31) than by direct inversion of $R_{k+1}$. However, further
testing has shown that these results may differ greatly between different
machines.

To summarize, the algorithm SIFt-RLS can be performed in
$\max\\{\min\\{pn^{2},p^{2}n\\},q_{k}n^{2}\\}$ computational complexity per
step. While no assumptions are made whether $p<n$ or $p\geq n$, SIFt-RLS is
best used when $p<n$. In the case where $p<n$, the computational complexity of
SIFt-RLS is $\max\\{p^{2}n,q_{k}n^{2}\\}$ per step. Note that if $p\geq n$
and, at step $k\geq 0$, all singular values of $\phi_{k}$ are greater or equal
to $\sqrt{\varepsilon}$, then the information subspace is all of
${\mathbb{R}}^{n}$ and SIFt-RLS simplifies to exponential forgetting RLS, as
shown in Proposition 10. However, SIFt-RLS can still be still be useful in the
case $p\geq n$ if it is expected that $\phi_{k}$ will have one or more
singular values smaller than $\sqrt{\varepsilon}$.

######  Proposition 10.

Let $k\geq 0$, let $\phi_{k}\in{\mathbb{R}}^{p\times n}$,
$y_{k}\in{\mathbb{R}}^{p}$, $\theta_{k}\in{\mathbb{R}}^{n}$, and let
$R_{k}\in{\mathbb{R}}^{n\times n}$ be positive definite. Also let
$\varepsilon>0$. Let $\theta_{k+1}\in{\mathbb{R}}^{n}$ and
$R_{k+1}\in{\mathbb{R}}^{n\times n}$ be computed using (22), (23), (27), (29),
and (30). If $p\geq n$ and all singular values of $\phi_{k}$ are greater or
equal to $\sqrt{\varepsilon}$, then

$\displaystyle R_{k+1}$ $\displaystyle=\lambda R_{k}+\phi_{k}^{\rm
T}\phi_{k},$ (32) $\displaystyle\theta_{k+1}$
$\displaystyle=\theta_{k}+P_{k+1}\phi_{k}^{\rm T}(y_{k}-\phi_{k}\theta_{k}).$
(33)

######  Proof 4.1.

Let $\phi_{k}=U_{k}\Sigma_{k}V_{k}^{\rm T}$ be the compact SVD of $\phi_{k}$,
where $U_{k}\in{\mathbb{R}}^{p\times n}$, $\Sigma_{k}\in{\mathbb{R}}^{n\times
n}$, and $V_{k}\in{\mathbb{R}}^{n\times n}$. Since $p\geq n$ and all singular
values of $\phi_{k}$ are greater or equal to $\sqrt{\varepsilon}$, it follows
that $q_{k}=n$ and $\bar{U}_{k}=U_{k}$. Hence, $\bar{\phi}_{k}=U_{k}^{\rm
T}\phi_{k}\in{\mathbb{R}}^{n\times n}$ and $\bar{y}_{k}=U_{k}^{\rm
T}y_{k}\in{\mathbb{R}}^{n}$. Moreover, since $U_{k}$ is semi-orthogonal,
$\operatorname{rank}(\bar{\phi}_{k})=n$, hence $\bar{\phi}_{k}$ is
nonsingular. Therefore, it follows that
$(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})^{-1}=\bar{\phi}_{k}^{-{\rm
T}}P_{k}\bar{\phi}_{k}^{-1}$. Substituting this equality into (27), it follows
that $\bar{R}_{k}=\lambda R_{k}$. Furthermore, since $U_{k}$ is semi-
orthogonal, it follows that $\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}=\phi_{k}^{\rm T}\phi_{k}$ and $\bar{\phi}_{k}^{\rm
T}\bar{y}_{k}=\phi_{k}^{\rm T}y_{k}$. Substituting into (29) and (30), (32)
and (33) follow.

The implementation details discussed in this subsection are summarized in
Algorithm 1. Some recommendations for tuning parameters $\lambda\in(0,1)$,
$\varepsilon>0$, $\theta_{0}\in{\mathbb{R}}^{n}$, and positive-definite
$P_{0}\in{\mathbb{R}}^{n\times n}$ are as follows. $\theta_{0}$ and $P_{0}$
are a prior belief of the mean and covariance, respectively, of the parameters
being estimated and can be tuned similarly as they would in other extensions
of RLS. $\varepsilon$ can be determined based on the noise level of the data
but should be small to avoid overly truncating the data. Finally, while a
forgetting factor close to $1$ is traditionally recommended to avoid
covariance windup [4, 27, 26], we have found $\lambda\in(0,1)$ can be tuned
more aggressively (more small) in SIFt-RLS to track quickly changing
parameters since forgetting only occurs in the information subspace. This is
particularly useful if there is ample excitation in certain directions,
allowing for identification of a subspace of parameters, while there is little
excitation in other directions.

Algorithm 1 Subspace of Information Forgetting Recursive Least Squares (SIFt-
RLS)

1:$\lambda\in(0,1)$, $\varepsilon>0$, $\theta_{0}\in{\mathbb{R}}^{n}$,
positive-definite $R_{0}\in{\mathbb{R}}^{n\times n}$ and $P_{0}\triangleq
R_{0}^{-1}$.

2:$q_{\rm max}\in[1,\min\\{p,n\\}]$.

3:for all $k\geq 0$ do

4: 1\. Information Filtering:

5: Compute the compact SVD $\phi_{k}=U_{k}\Sigma_{k}V_{k}^{\rm T}$ with the
singular values on the diagonal of $\Sigma_{k}$ in descending order. Let
$q_{k}$ be the number of singular values of $\phi_{k}$ greater or equal to
$\sqrt{\varepsilon}$.

6: if $q_{k}=0$ then

7: $R_{k+1}\leftarrow R_{k}$, $\theta_{k+1}\leftarrow\theta_{k}$, skip to step
$k+1$.

8: Let $\bar{U}_{k}$ be the first $q_{k}$ columns of $U_{k}$.

9: $\bar{\phi}_{k}\in{\mathbb{R}}^{q_{k}\times n}\leftarrow\bar{U}_{k}^{\rm
T}\phi_{k}$

10: $\bar{y}_{k}\in{\mathbb{R}}^{q_{k}}\leftarrow\bar{U}_{k}^{\rm T}y_{k}$

11: 2\. SIFting:

12: $L_{k}\leftarrow\bar{\phi}_{k}R_{k}$

13: $\bar{R}_{k}\leftarrow R_{k}-(1-\lambda)L_{k}^{\rm
T}(L_{k}\bar{\phi}_{k}^{\rm T})^{-1}L_{k}$

14: $\bar{R}_{k}\leftarrow\frac{1}{2}(\bar{R}_{k}+\bar{R}_{k}^{\rm T})$

15: if $q_{k}\leq q_{\rm max}$ then

16: $\bar{P}_{k}\leftarrow P_{k}+\frac{1-\lambda}{\lambda}\bar{\phi}_{k}^{\rm
T}(L_{k}\bar{\phi}_{k}^{\rm T})^{-1}\bar{\phi}_{k}.$

17: 3\. Update:

18: $R_{k+1}\leftarrow\bar{R}_{k}+\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k}$

19: if $q_{k}\leq q_{\rm max}$ then

20: $M_{k}\leftarrow\bar{\phi}_{k}\bar{P}_{k}$

21: $P_{k+1}\leftarrow\bar{P}_{k}-M_{k}^{\rm
T}(I_{q_{k}}+M_{k}\bar{\phi}_{k}^{\rm T})^{-1}M_{k}$

22: $P_{k+1}\leftarrow\frac{1}{2}(P_{k+1}+P_{k+1}^{\rm T})$

23: else

24: $P_{k+1}\leftarrow R_{k+1}^{-1}$

25: $\theta_{k+1}\leftarrow\theta_{k}+P_{k+1}[\bar{\phi}_{k}^{\rm
T}(\bar{y}_{k}-\bar{\phi}_{k}\theta_{k})]$

##  5 Covariance Bounds and Stability of SIFt-RLS

This section discusses the theoretical guarantees of SIFt-RLS including bounds
on the covariance matrix and estimation error stability assuming estimation of
fixed parameters without noise.

###  5.1 Covariance Bounds

To begin, we show that, without any assumptions of persistent excitation, the
eigenvalues of the information matrix $R_{k}$ in SIFt-RLS are lower bounded.
Furthermore, we show that if the sequence of regressors
$(\phi_{k})_{k=0}^{\infty}$ is upper bounded, then the eigenvalues of the
information matrix $R_{k}$ in SIFt-RLS are also upper bounded. This result
also immediately implies that the reciprocal expressions are bounds for the
covariance matrix $P_{k}=R_{k}^{-1}$. These results are given in Theorem 3.
Note that explicit bounds are given which improves upon the works of [5] and
[35] which only state the existence of bounds. Moreover, the bounds of Theorem
3 are stronger than those of [35], see Appendix D for details.

######  Theorem 3.

Let $\lambda\in(0,1)$, let $\varepsilon>0$, and let
$R_{0}\in{\mathbb{R}}^{n\times n}$ be positive definite. For all $k\geq 0$,
let $\phi_{k}\in{\mathbb{R}}^{p\times n}$, let
$\bar{\phi}_{k}\in{\mathbb{R}}^{q_{k}\times n}$ be defined by (22), let
$\bar{R}_{k}\in{\mathbb{R}}^{n\times n}$ be defined by (27), and let
$R_{k+1}\in{\mathbb{R}}^{n\times n}$ be defined by (29). Then the following
statements hold:

  1. 1.

For all $k\geq 0$,

$\displaystyle\bm{\lambda_{\rm min}}(R_{k})$
$\displaystyle\geq\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\},$ (34) $\displaystyle\bm{\lambda_{\rm max}}(P_{k})$
$\displaystyle\leq\max\\{\frac{1-\lambda}{\varepsilon},\bm{\lambda_{\rm
max}}(P_{0})\\}.$ (35)

  2. 2.

If $(\phi_{k})_{k=0}^{\infty}$ is bounded with upper bound
$\beta\in(0,\infty)$, then, for all $k\geq 0$,

$\displaystyle\bm{\lambda_{\rm max}}(R_{k})$
$\displaystyle\leq\max\\{\frac{\beta}{1-\lambda},\bm{\lambda_{\rm
max}}(R_{0})\\},$ (36) $\displaystyle\bm{\lambda_{\rm min}}(P_{k})$
$\displaystyle\geq\min\\{\frac{1-\lambda}{\beta},\bm{\lambda_{\rm
min}}(P_{0})\\}.$ (37)

######  Proof 5.1.

See Appendix section C for a proof of (34) and (36). Bounds (35) and (37)
follow directly from (34) and (36) respectively since, for all $k\geq 0$,
$P_{k}=R_{k}^{-1}$.

Note that the bounds of Theorem 3 are strikingly analogous to the bounds of
RLS with exponential forgetting in Proposition 4, where
$(\phi_{k})_{k=0}^{\infty}$ is persistently exciting with persistency window
$N=1$. This is a result of the information filtering step of SIFt-RLS
truncating the singular values of $\phi_{k}$ smaller than
$\sqrt{\varepsilon}$, and the SIFting step of SIFt-RLS forgetting only in the
information subspace, $\mathcal{R}({\phi}_{k}^{\rm T})$.

Next, Corollary 11 shows that, for all $k\geq 0$, $R_{k}$ and $\bar{R}_{k}$
are positive definite. Furthermore, Corollary 12 shows that, for all $k\geq
0$, the matrix $\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T}$ is nonsingular and,
assuming bounded regressors, has a bounded condition number. This is ensures
that computing $(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})^{-1}$ in the
SIFting step is well-conditioned.

######  Corollary 11.

Consider the notation of Theorem 3. For all $k\geq 0$, $R_{k}$ and
$\bar{R}_{k}$ are positive definite.

######  Proof 5.2.

Since $\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\}>0$, it follows from (34) that, for all $k\geq 0$, $R_{k}\succ
0$. Next, note that, for all $k\geq 0$, $\bar{R}_{k}$, defined in (27), can be
written as $\bar{R}_{k}=\lambda R_{k}+(1-\lambda)R_{k}^{\perp}$. It follows
from Theorem 1 that $R_{k}^{\perp}$ is positive semidefinite, and hence
$\bar{R}_{k}\succeq\lambda R_{k}\succ 0$.

######  Corollary 12.

Consider the notation of Theorem 3. For all $k\geq 0$,
$\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T}$ is nonsingular. Moreover, if
$(\phi_{k})_{k=0}^{\infty}$ is bounded with upper bound $\beta\in(0,\infty)$,
then, for all $k\geq 0$,

$\displaystyle\kappa(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T})\leq\frac{\beta\max\\{\frac{\beta}{1-\lambda},\bm{\lambda_{\rm
max}}(R_{0})\\}}{\varepsilon\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\}}.$ (38)

######  Proof 5.3.

It follows from Corollary 11 that $R_{k}$ is positive definite. Next, since
$\operatorname{rank}(\bar{\phi}_{k})=q_{k}$ by construction, it follows from
Lemma 7 that $\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T}$ is positive definite,
hence nonsingular.

Next, suppose $(\phi_{k})_{k=0}^{\infty}$ is bounded with upper bound
$\beta\in(0,\infty)$. Since $\bm{\sigma_{\rm max}}(\cdot)$ is
submultiplicative, it follows that $\bm{\sigma_{\rm
max}}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})\leq\bm{\sigma_{\rm
max}}(\bar{\phi}_{k})\bm{\sigma_{\rm max}}(R_{k})\bm{\sigma_{\rm
max}}(\bar{\phi}_{k}^{\rm T})$. Furthermore, since $(\phi_{k})_{k=0}^{\infty}$
is bounded with upper bound $\beta\in(0,\infty)$,
$(\bar{\phi}_{k})_{k=0}^{\infty}$ is also bounded with upper bound
$\beta\in(0,\infty)$. Therefore, $\bm{\sigma_{\rm
max}}(\bar{\phi}_{k})\leq\sqrt{\beta}$. This combined with (36) imply that
$\bm{\sigma_{\rm max}}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T})\leq\beta\max\\{\frac{\beta}{1-\lambda},\bm{\lambda_{\rm max}}(R_{0})\\}$.

Next, as a consequence of the min-max theorem given in Lemma 2, note that

$\displaystyle\bm{\sigma_{\rm min}}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T})=\min_{x\in{\mathbb{R}}^{q_{k}},x\neq
0}\frac{\|\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T}x\|}{\|x\|}.$

Since $\bar{\phi}_{k}^{\rm T}$ has full column rank, $x\neq 0$ implies that
$\bar{\phi}_{k}^{\rm T}x\neq 0$. Therefore, we can write

$\displaystyle\min_{x\in{\mathbb{R}}^{q_{k}},x\neq 0}$
$\displaystyle\frac{\|\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T}x\|}{\|x\|}=\min_{x\in{\mathbb{R}}^{q_{k}},x\neq
0}\frac{\|\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T}x\|}{\|\bar{\phi}_{k}^{\rm
T}x\|}\frac{\|\bar{\phi}_{k}^{\rm T}x\|}{\|x\|}$
$\displaystyle\geq\min_{y\in{\mathbb{R}}^{n},y\neq
0}\frac{\|\bar{\phi}_{k}R_{k}y\|}{\|y\|}\min_{x\in{\mathbb{R}}^{q_{k}},x\neq
0}\frac{\|\bar{\phi}_{k}^{\rm T}x\|}{\|x\|}$ $\displaystyle=\bm{\sigma_{\rm
min}}(\bar{\phi}_{k}R_{k})\bm{\sigma_{\rm min}}(\bar{\phi}_{k}^{\rm T}).$

Furthermore, since $\bar{\phi}_{k}$ has full row rank, it can be shown by
similar reasoning that $\bm{\sigma_{\rm
min}}(\bar{\phi}_{k}R_{k})\geq\bm{\sigma_{\rm
min}}(\bar{\phi}_{k})\bm{\sigma_{\rm min}}(R_{k})$. By construction of
$\bar{\phi}_{k}$, $\bm{\sigma_{\rm min}}(\bar{\phi}_{k})=\bm{\sigma_{\rm
min}}(\bar{\phi}_{k}^{\rm T})\geq\sqrt{\varepsilon}$. Combined with (34), it
follows that $\bm{\sigma_{\rm min}}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T})\geq\varepsilon\bm{\sigma_{\rm
min}}(R_{k})\geq\varepsilon\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\}$.

Substituting the upper bound of $\bm{\sigma_{\rm
max}}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})$ and lower bound of
$\bm{\sigma_{\rm min}}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm T})$ into
definition (2) yields (38).

###  5.2 Stability

Next, for the analysis of this section, we make the assumption that there
exist fixed parameters $\theta\in{\mathbb{R}}^{n}$ such that, for all $k\geq
0$,

$\displaystyle y_{k}=\phi_{k}\theta.$ (39)

Furthermore, for all $k\geq 0$, we define the parameter estimation error
$\tilde{\theta}_{k}\in{\mathbb{R}}^{n}$ by

$\displaystyle\tilde{\theta}_{k}\triangleq\theta_{k}-\theta.$ (40)

Substituting (40) into (30), it then follows that, for all $k\geq 0$,

$\displaystyle\tilde{\theta}_{k+1}=(I_{n}-P_{k+1}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k})\tilde{\theta}_{k}.$ (41)

Note that (41) is a linear time-varying system with an equilibrium point
$\tilde{\theta}_{k}\equiv 0$. Thus, we can study the stability of the
estimation error equilibrium point $\tilde{\theta}_{k}\equiv 0$. Theorem 4
uses the results of [18] to show that this the equilibrium point
$\tilde{\theta}_{k}\equiv 0$ is uniformly asymptotically stable without
further assumptions and globally uniformly exponentially stable under
persistent excitation. For definitions of uniform asymptotic stability and
global uniform exponential stability, see Definition 13.7 in [12, pp. 783,
784].

######  Theorem 4.

Let $\lambda\in(0,1)$, let $\varepsilon>0$, let $R_{0}\in{\mathbb{R}}^{n\times
n}$ be positive definite, and let $\theta_{0}\in{\mathbb{R}}^{n}$. For all
$k\geq 0$, let $\phi_{k}\in{\mathbb{R}}^{p\times n}$, let
$\bar{\phi}_{k}\in{\mathbb{R}}^{q_{k}\times n}$ be defined by (22), let
$\bar{R}_{k}\in{\mathbb{R}}^{n\times n}$ be defined by (27), let
$R_{k+1}\in{\mathbb{R}}^{n\times n}$ be defined by (29), and let
$\theta_{k+1}\in{\mathbb{R}}^{n}$ be defined by (30). Finally, assume there
exists $\theta\in{\mathbb{R}}^{n}$ such that, for all $k\geq 0$, (39) holds.
Then, the following two statements hold:

  1. 1.

The equilibrium $\tilde{\theta}_{k}\equiv 0$ of (41) is uniformly Lyapunov
stable.

  2. 2.

If $\\{\bar{\phi}_{k}\\}_{k=0}^{\infty}$ is persistently exciting, then the
equilibrium $\tilde{\theta}_{k}\equiv 0$ of (41) is globally uniformly
exponentially stable.

######  Proof 5.4.

This result is based on Theorem 2 of [18]. Note that, for all $k\geq 0$, (29)
can be written as

$\displaystyle R_{k+1}=R_{k}-F_{k}+\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k},$

where $F_{k}\triangleq(1-\lambda)R_{k}^{\parallel}$. Note that, for all $k\geq
0$, $1-\lambda>0$ and that by Theorem 1, $R_{k}^{\parallel}\succeq 0$, hence
$F_{k}\succeq 0$. Therefore, condition A1) of [18] is satisfied.

Next, note that, for all $k\geq 0$, $R_{k}-F_{k}=\lambda
R_{k}^{\parallel}+R_{k}^{\perp}$. Then, since $R_{k}^{\perp}\succeq 0$ by
Theorem 1, it follows that

$\displaystyle R_{k}-F_{k}\succeq\lambda R_{k}^{\parallel}+\lambda
R_{k}^{\perp}=\lambda R_{k}.$

Furthermore, it follows from (34) of Theorem 3 that, for all $k\geq 0$,

$\displaystyle
R_{k}-F_{k}\succeq\lambda\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\}I_{n},$

and hence

$\displaystyle(R_{k}-F_{k})^{-1}\preceq\frac{1}{\lambda}\max\\{\frac{1-\lambda}{\varepsilon},\bm{\lambda_{\rm
max}}(P_{0})\\}I_{n}.$

Therefore, condition A2) of [18] is satisfied. Finally, (36) of Theorem 3
implies that, for all $k\geq 0$,

$\displaystyle\min\\{\frac{1-\lambda}{\beta},\bm{\lambda_{\rm
min}}(P_{0})\\}I_{n}\preceq P_{k}.$

Hence, condition A2) of [18] is satisfied. Thus, by statement 2) of Theorem 2
of [18], the equilibrium $\tilde{\theta}_{k}\equiv 0$ of (41) is uniformly
Lyapunov stable.

Moreover, if $\\{\bar{\phi}_{k}\\}_{k=0}^{\infty}$ is persistently exciting,
then condition A4) of [18] is satisfied. It then follows from statement 4) of
Theorem 2 of [18], the equilibrium $\tilde{\theta}_{k}\equiv 0$ of (41) is
globally uniformly exponentially stable.

##  6 Numerical Example

We consider the follow example of identifying $n=4$ parameters with $p=2$
measurements at each step. For all $0\leq k\leq 1200$, consider the true
parameters $\theta_{{\rm true},k}\in{\mathbb{R}}^{4}$, defined

$\displaystyle\theta_{{\rm true},k}$
$\displaystyle\triangleq\begin{bmatrix}\theta^{1}_{{\rm
true},k}&\theta^{2}_{{\rm true},k}&\theta^{3}_{{\rm true},k}&\theta^{4}_{{\rm
true},k}\end{bmatrix}^{\rm T}$
$\displaystyle=\begin{bmatrix}\sin(\frac{\pi}{60}k)&\cos(\frac{k}{60})&\sin(\frac{k}{225})&\cos(\frac{k}{225})\end{bmatrix}^{\rm
T}.$ (42)

For all $0\leq k<400$, let both rows of $\phi_{k}\in{\mathbb{R}}^{2\times 4}$
be i.i.d. sampled from
$\mathcal{N}(0,\operatorname{diag}(1,1,10^{-4},10^{-4}))$ and, for all
$400\leq k<800$, let both rows of $\phi_{k}\in{\mathbb{R}}^{2\times 4}$ be
i.i.d. sampled from $\mathcal{N}(0,\operatorname{diag}(10^{-4},10^{-4},1,1))$.
Lastly, for all $800\leq k\leq 1200$, let $\phi_{k}=\sigma_{k}[0\ 2\ 1\
0]+\nu_{k}$ where $\sigma_{k}$ is i.i.d. sampled from $\mathcal{N}(0,I_{2})$
and both rows of $\sigma_{k}\in{\mathbb{R}}^{2\times 4}$ are i.i.d. sampled
from $\mathcal{N}(0,10^{-4}I_{4})$. Furthermore, for all $0\leq k<1200$, let
$y_{k}=(\phi_{k}+v_{k})\theta_{{\rm true},k}+w_{k}$, where both rows of
$v_{k}\in{\mathbb{R}}^{2\times 4}$ are i.i.d. sampled from
$\mathcal{N}(0,\frac{1}{100}I_{4})$ and $w_{k}$ is i.i.d. sampled from
$\mathcal{N}(0,\frac{1}{100}I_{2})$, i.e. regressor noise and measurement
noise.

The result of this sampled data is, between $0\leq k<400$, excitation is
sufficient to identify $\theta^{1}_{{\rm true},k}$ and $\theta^{2}_{{\rm
true},k}$, which form a basis for the excited subspace
$S^{12}\triangleq\\{[x_{1}\ x_{2}\ 0\ 0]\colon x_{1},x_{2}\in{\mathbb{R}}\\}$,
but insufficient to identify $\theta^{3}_{{\rm true},k}$ and $\theta^{4}_{{\rm
true},k}$, which form a basis for the unexcited subspace
$(S^{12})^{\perp}=S^{34}\triangleq\\{[0\ 0\ x_{3}\ x_{4}]\colon
x_{3},x_{4}\in{\mathbb{R}}\\}$. Then, the reverse is the case between $400\leq
k<800$. Finally, between $800\leq k\leq 1200$, excitation is sufficient to
identify $\theta^{\parallel}_{{\rm true},k}\in{\mathbb{R}}$, defined as

$\theta^{\parallel}_{{\rm true},k}\triangleq\frac{2}{3}\theta^{2}_{{\rm
true},k}+\frac{1}{3}\theta^{3}_{{\rm true},k},$ (43)

which forms a basis for the excited subspace $S^{\parallel}\triangleq\\{[0\
2x\ x\ 0]\colon x\in{\mathbb{R}}\\}$. However, excitation is insufficient to
identify $\theta^{1}_{{\rm true},k}$, $\theta^{4}_{{\rm true},k}$, and
$\theta^{\perp}_{{\rm true},k}\in{\mathbb{R}}$, defined as

$\displaystyle\theta^{\perp}_{{\rm
true},k}\triangleq\frac{1}{3}\theta^{2}_{{\rm
true},k}-\frac{2}{3}\theta^{3}_{{\rm true},k},$ (44)

which form a basis for the unexcited subspace $S^{\perp}\triangleq\\{[x_{1}\
x\ -2x\ x_{4}]\colon x_{1},x,x_{4}\in{\mathbb{R}}\\}$.

We now consider the performance of SIFt-RLS in identifying $\theta_{{\rm
true},k}$. We initialize $P_{0}=I_{4}$, $\theta_{0}=0_{4\times 1}$ and let
$\lambda=0.5$ and $\varepsilon=10^{-4}$.666We also select $q_{\rm max}=1$
which only affects computation time. The parameter tracking of SIFT-RLS is
shown in Figure 2, where, for all $k\geq 0$, $\theta^{i}_{k}$ is the $i^{\rm
th}$ element of $\theta_{k}$. Between $0\leq k<400$, SIFt-RLS tracks
$\theta^{1}_{{\rm true},k}$ and $\theta^{2}_{{\rm true},k}$ with little change
to its estimate of the $\theta^{3}_{{\rm true},k}$ and $\theta^{4}_{{\rm
true},k}$ and vice versa for $400\leq k<800$. Similarly, between $800\leq
k\leq 1200$, SIFt-RLS tracks $\theta^{\parallel}_{{\rm true},k}$ with little
change to its estimate of $\theta^{1}_{{\rm true},k}$, $\theta^{4}_{{\rm
true},k}$, and $\theta^{\perp}_{{\rm true},k}$.

Figure 2: Estimated parameters $\theta^{1}_{k}$, $\theta^{2}_{k}$,
$\theta^{3}_{k}$, $\theta^{4}_{k}$, $\theta^{\parallel}_{k}$, and
$\theta^{\perp}_{k}$ using SIFt-RLS (blue) and true parameters
$\theta^{1}_{{\rm true},k}$, $\theta^{2}_{{\rm true},k}$, $\theta^{3}_{{\rm
true},k}$, $\theta^{4}_{{\rm true},k}$, $\theta^{\parallel}_{{\rm true},k}$,
and $\theta^{\perp}_{{\rm true},k}$ (black).

Next, we compare SIFt-RLS to RLS with no forgetting (NF), RLS with exponential
forgetting (EF), and three other directional forgetting algorithms from the
literature: variable direction forgetting (VD) [10], directional forgetting
(DF) [3], and multiple forgetting (MF) [34, 9]. EF and VD are tuned with a
conservative $\lambda=0.95$ to delay covariance windup. DF is tuned with the
same $\lambda=0.5$ of SIFt. MF is tuned with $\Lambda\triangleq[\lambda_{1}\
\lambda_{2}\ \lambda_{3}\ \lambda_{4}]=[0.9\ 0.9\ 0.95\ 0.95]$ to forget more
agressively in the first and second parameters. Finally, we test MF with a
priori knowledge of which subspaces will be excited (MF a priori), where time-
varying forgetting factor $\Lambda$ is tuned to only forget in the excited
subspace. Tuning parameters are summarized in Table 1.

Table 1: RLS Algorithms Tuning Parameters Algorithm | Tuning Parameters
---|---
SIFt |  $\lambda=0.5$, $\varepsilon=10^{-4}$
NF | —
EF | $\lambda=0.95$
VD |  $\lambda=0.95$, $\varepsilon=10^{-4}$
DF | $\lambda=0.5$
MF | $\Lambda\triangleq[\lambda_{1}\ \lambda_{2}\ \lambda_{3}\ \lambda_{4}]=[0.9\ 0.9\ 0.95\ 0.95]$
MF a priori | $\Lambda=\begin{cases}[0.5\ 0.5\ 1\ 1]&0\leq k<400,\\\ [1\ 1\ 0.5\ 0.5]&400\leq k<800,\\\ [1\ 0.6\ 0.85\ 1]&800\leq k\leq 1200,\\\ \end{cases}$

To more easily compare the performance of these seven different algorithms in
Figure 3, we show, over $0\leq k\leq 800$, the error in the $S^{12}$ subspace,
$e^{12}_{k}\in{\mathbb{R}}$, and the error in the $S^{34}$ subspace,
$e^{34}_{k}\in{\mathbb{R}}$, defined as

$\displaystyle e^{12}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{1}_{k}-\theta^{1}_{{\rm
true},k})^{2}+(\theta^{2}_{k}-\theta^{2}_{{\rm true},k})^{2}},$ (45)
$\displaystyle e^{34}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{3}_{k}-\theta^{3}_{{\rm
true},k})^{2}+(\theta^{4}_{k}-\theta^{4}_{{\rm true},k})^{2}}.$ (46)

Furthermore, Figure 3 also shows, between $800\leq k\leq 1200$, the error in
the $S^{\parallel}$ subspace, $e^{\parallel}_{k}\in{\mathbb{R}}$, and the
error in the $S^{\perp}$ subspace, $e^{\perp}_{k}\in{\mathbb{R}}$, defined as

$\displaystyle e^{\parallel}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{\parallel}_{k}-\theta^{\parallel}_{{\rm
true},k})^{2}},$ $\displaystyle e^{\perp}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{1}_{k}-\theta^{1}_{{\rm
true},k})^{2}+(\theta^{4}_{k}-\theta^{4}_{{\rm
true},k})^{2}+(\theta^{\perp}_{k}-\theta^{\perp}_{{\rm true},k})^{2}}.$

Note that NF is unable to track changing parameters and results in the largest
errors in the excited subspace. On the contrary, while EF, VD, DF, and MF are
able to track the true parameters in the excited subspaces, they all result in
large error in the unexcited subspaces due to covariance windup. DF performs
the best of these methods, particularly between $0\leq k\leq 800$, but still
suffers from covariance windup between $800\leq k\leq 1200$. While an
aggressive $\lambda=0.5$ is used for DF, slower windup still occurs with a
more conservative $\lambda$. Finally, MF a priori achieved very comparable
performance to SIFt, with tracking in the excited subspace and little change
in estimates in the unexcited subspace. However, this required careful tuning
and a priori knowledge of which subspaces would be excited.

Figure 3: Over $0\leq k\leq 800$, $e_{k}^{12}$ and $e_{k}^{34}$ show the
parameter estimation error in the subspaces $S^{34}\triangleq\\{[x_{1}\ x_{2}\
0\ 0]^{\rm T}\colon x_{1},x_{2}\in{\mathbb{R}}\\}$ and $S_{34}\triangleq\\{[0\
0\ x_{3}\ x_{4}]^{\rm T}\colon x_{3},x_{4}\in{\mathbb{R}}\\}$, respectively.
Subspace $S^{12}$ is excited over $0\leq k<400$ while $S^{34}$ is not, and
vice versa over $400\leq k<800$. Next, over $800\leq k\leq 1200$,
$e_{k}^{\parallel}$ and $e_{k}^{\perp}$ show the parameter estimation error in
the subspaces $S^{\parallel}\triangleq\\{[0\ 2x\ x\ 0]\colon
x\in{\mathbb{R}}\\}$ and $S^{\perp}\triangleq\\{[x_{1}\ x\ -2x\ x_{4}]\colon
x_{1},x,x_{4}\in{\mathbb{R}}\\}$, respectively. Subspace $S^{\parallel}$ is
excited over $800\leq k\leq 1200$ while $S^{\perp}$ is not.

As another useful metric, we define $\Delta^{12}_{k}\in{\mathbb{R}}$,
$\Delta^{34}_{k}\in{\mathbb{R}}$, and $\Delta^{\perp}_{k}\in{\mathbb{R}}$ over
$k\in[1,400]$, $k\in[401,800]$, and $k\in[801,1200]$, respectively, as

$\displaystyle\Delta^{12}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{1}_{k}-\theta^{1}_{0})^{2}+(\theta^{2}_{k}-\theta^{2}_{0})^{2}},$
$\displaystyle\Delta^{34}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{3}_{k}-\theta^{3}_{400})^{2}+(\theta^{4}_{k}-\theta^{4}_{400})^{2}},$
$\displaystyle\Delta^{\perp}_{k}$
$\displaystyle\triangleq\sqrt{(\theta^{1}_{k}-\theta^{1}_{800})^{2}+(\theta^{4}_{k}-\theta^{4}_{800})^{2}+(\theta^{\perp}_{k}-\theta^{\perp}_{800})^{2}}.$

These quantities show how much parameter estimates change in the unexcited
subspaces. Figure 4 shows that NF, SIFt, and MF a priori makes only small
changes to parameter estimates in the unexcited subspaces, while EF, VD, DF,
and MF significantly update estimates of parameters in the unexcited subspace
despite lack of useful new information in these directions.

Figure 4: $\Delta_{k}^{12}$, $\Delta_{k}^{34}$, and $\Delta_{k}^{\perp}$ show
the magnitude of the change in parameter estimates in the unexcited subspace
over $0\leq k<400$, $400\leq k<800$, and $800\leq k\leq 1200$, respectively.

As a final metric, Figure 5 shows the spectral radius of the covariance matrix
$P_{k}$ for the various RLS algorithms. The spectral radius $\rho(P_{k})$
becomes very small in NF, indicating parameter estimates is no longer
changing. In EF, VD, DF, and MF, the spectral radius becomes very large,
indicating covariance windup and sensitivity to noise. SIFt and MF a priori
both maintain a spectral radius close to $1$.

Figure 5: Spectral radius of the covariance matrix at step $k$.

##  7 Conclusion

This work develops SIFt-RLS, a directional forgetting algorithm which, at each
step, forgets only in the information subspace. The key tool used in SIFt-RLS
is a subspace decomposition of a positive-definite matrix, which was developed
and analyzed in Section 3. The properties of this decomposition are used to
derive explicit covariance bounds for SIFt-RLS and to develop sufficient
conditions for the stability of the parameter estimation error dynamics.
Moreover, an interesting parallel is made between the covariance bounds of
SIFt-RLS and the covariance bounds of exponential forgetting RLS under
persistent excitation with persistency window $1$. A numerical example show
the benefits of SIFt-RLS when the data collected is not persistently exciting.

We have presented a simple version of SIFt-RLS, in which forgetting in the
information subspace is uniform and constant-rate, and no forgetting is
applied in the orthogonal complement of the information subspace. However, a
natural area of future interest is combining SIFt-RLS with other forgetting
algorithms. One idea is to apply nonuniform forgetting and/or variable-rate
forgetting to the information subspace. Another idea is to apply a separate
forgetting method, for example resetting [17], to the orthogonal complement of
the information subspace. While some other forgetting methods require
persistent excitation to guarantee bounds on the covariance matrix [7, 3, 10],
a question of interest is whether SIFt-RLS combined with these methods can
guarantee similar bounds without persistent excitation, as was shown in this
work for exponential forgetting.

This work was supported by the NSF Graduate Research Fellowship under Grant
DGE 1841052.

## References

  * [1] Karl J Åström and Björn Wittenmark.  Adaptive control.  Courier Corporation, 2013.
  * [2] Dennis S Bernstein.  Matrix mathematics: theory, facts, and formulas.  Princeton university press, 2009.
  * [3] Sergio Bittanti, Paolo Bolzern, and M Campi.  Convergence and exponential convergence of identification algorithms with directional forgetting factor.  Automatica, 26(5):929–932, 1990.
  * [4] Adam L Bruce, Ankit Goel, and Dennis S Bernstein.  Convergence and consistency of recursive least squares with variable-rate forgetting.  Automatica, 119:109052, 2020.
  * [5] Liyu Cao and Howard Schwartz.  A directional forgetting algorithm based on the decomposition of the information matrix.  Automatica, 36(11):1725–1731, 2000.
  * [6] Moody T. Chu, R. E. Funderlic, and Gene H. Golub.  Rank modifications of semidefinite matrices associated with a secant update formula.  SIAM Journal on Matrix Analysis and Applications, 20(2):428–436, 1998.
  * [7] S. Dasgupta and Yih-Fang Huang.  Asymptotically convergent modified recursive least-squares with data-dependent updating and forgetting factor for systems with bounded noise.  IEEE Transactions on Information Theory, 33(3):383–392, 1987.
  * [8] TR Fortescue, Lester S Kershenbaum, and B Erik Ydstie.  Implementation of self-tuning regulators with variable forgetting factors.  Automatica, 17(6):831–835, 1981.
  * [9] Francesco Fraccaroli, Andrea Peruffo, and Mattia Zorzi.  A new recursive least squares method with multiple forgetting schemes.  In 2015 54th IEEE conference on decision and control (CDC), pages 3367–3372. IEEE, 2015.
  * [10] Ankit Goel, Adam L Bruce, and Dennis S Bernstein.  Recursive least squares with variable-direction forgetting: Compensating for the loss of persistency [lecture notes].  IEEE Control Systems Magazine, 40(4):80–102, 2020.
  * [11] GC Goodwin, EK Teoh, and H Elliott.  Deterministic convergence of a self-tuning regulator with covariance resetting.  In IEEE Proceedings D-Control Theory and Applications, volume 130, pages 6–8, 1983.
  * [12] W. M. Haddad and V. Chellaboina.  Nonlinear Dynamical Systems and Control: A Lyapunov-based Approach.  Princeton University Press, 2008.
  * [13] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [14] Syed Aseem Ul Islam and Dennis S Bernstein.  Recursive least squares for real-time implementation [lecture notes].  IEEE Control Systems Magazine, 39(3):82–85, 2019.
  * [15] Richard M Johnstone, C Richard Johnson Jr, Robert R Bitmead, and Brian DO Anderson.  Exponential convergence of recursive least squares with exponential forgetting factor.  Systems & Control Letters, 2(2):77–82, 1982.
  * [16] R Kulhavỳ and M Kárnỳ.  Tracking of slowly varying parameters by directional forgetting.  IFAC Proceedings Volumes, 17(2):687–692, 1984.
  * [17] Brian Lai and Dennis S. Bernstein.  Exponential resetting and cyclic resetting recursive least squares.  IEEE Control Systems Letters, 7:985–990, 2023.
  * [18] Brian Lai and Dennis S Bernstein.  Generalized forgetting recursive least squares: Stability and robustness guarantees.  arXiv preprint arXiv:2308.04259, 2023.
  * [19] Brian Lai, Syed Aseem Ul Islam, and Dennis S Bernstein.  Regularization-induced bias and consistency in recursive least squares.  In 2021 American Control Conference (ACC), pages 3987–3992. IEEE, 2021.
  * [20] Shu-Hung Leung and C.F. So.  Gradient-based variable forgetting factor rls algorithm in time-varying environments.  IEEE Transactions on Signal Processing, 53(8):3141–3150, 2005.
  * [21] Lennart Ljung and Torsten Söderström.  Theory and practice of recursive identification.  MIT press, 1983.
  * [22] OP Malik, GS Hope, and SJ Cheng.  Some issues on the practical use of recursive least squares identification in self-tuning control.  International Journal of Control, 53(5):1021–1033, 1991.
  * [23] Nima Mohseni and Dennis S Bernstein.  Recursive least squares with variable-rate forgetting based on the f-test.  In 2022 American Control Conference (ACC), pages 3937–3942. IEEE, 2022.
  * [24] Tam W Nguyen, Syed Aseem Ul Islam, Dennis S Bernstein, and Ilya V Kolmanovsky.  Predictive cost adaptive control: A numerical investigation of persistency, consistency, and exigency.  IEEE Control Systems Magazine, 41(6):64–96, 2021.
  * [25] Romeo Ortega, Vladimir Nikiforov, and Dmitry Gerasimov.  On modified parameter estimators for identification and adaptive control. a unified framework and some new schemes.  Annual Reviews in Control, 50:278–293, 2020.
  * [26] Constantin Paleologu, Jacob Benesty, and Silviu Ciochina.  A robust variable forgetting factor recursive least-squares algorithm for system identification.  IEEE Signal Processing Letters, 15:597–600, 2008.
  * [27] Constantin Paleologu, Jacob Benesty, and Silviu Ciochină.  A practical variable forgetting factor recursive least-squares algorithm.  In 2014 11th International symposium on electronics and telecommunications (ISETC), pages 1–4. IEEE, 2014.
  * [28] JE Parkum, Niels Kjølstad Poulsen, and Jan Holst.  Recursive forgetting algorithms.  International Journal of Control, 55(1):109–128, 1992.
  * [29] Mario E. Salgado, Graham C. Goodwin, and Richard H. Middleton.  Modified least squares algorithm incorporating exponential resetting and forgetting.  International Journal of Control, 47(2):477–491, 1988.
  * [30] Shankar Sastry, Marc Bodson, and James F Bartram.  Adaptive control: stability, convergence, and robustness, 1990.
  * [31] Vitaly Shaferman, Michael Schwegel, Tobias Glück, and Andreas Kugi.  Continuous-time least-squares forgetting algorithms for indirect adaptive control.  European Journal of Control, 62:105–112, 2021.
  * [32] Hyo-Sang Shin and Hae-In Lee.  A new exponential forgetting algorithm for recursive least-squares parameter estimation.  arXiv preprint arXiv:2004.03910, 2020.
  * [33] Lloyd N Trefethen and David Bau.  Numerical linear algebra, volume 181.  Siam, 2022.
  * [34] A. Vahidi, A. Stefanopoulou, and H. Peng.  Recursive least squares with forgetting for online estimation of vehicle mass and road grade: theory and experiments.  Vehicle System Dynamics, 43(1):31–55, 2005.
  * [35] Kun Zhu, Chengpu Yu, and Yiming Wan.  Recursive least squares identification with variable-direction forgetting via oblique projection decomposition.  IEEE/CAA Journal of Automatica Sinica, 9(3):547–555, 2021.

##  Appendix A Useful Matrix Lemmas

######  Lemma 1 (Matrix Inversion Lemma).

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

######  Proof A.1.

See Corollary 3.9.8 of [2].

######  Lemma 2 (min-max theorem).

Let $A\in{\mathbb{R}}^{n\times n}$ be symmetric. Then, for all $k=1,\ldots,n$,

$\displaystyle\bm{\lambda_{k}}(A)$
$\displaystyle=\max_{\begin{subarray}{c}S\subset{\mathbb{R}}^{n}\\\
\dim(S)=k\end{subarray}}\min_{\begin{subarray}{c}x\in S\\\
\|x\|=1\end{subarray}}x^{\rm T}Ax.$

######  Proof A.2.

See Theorem 4.2.6 of [13].

######  Lemma 3.

Let $A\in{\mathbb{R}}^{n\times n}$ and $B\in{\mathbb{R}}^{n\times n}$ be
symmetric. Then,

$\displaystyle\bm{\lambda_{k}}(A)+\bm{\lambda_{\rm
min}}(B)\leq\bm{\lambda_{k}}(A+B)\leq\bm{\lambda_{k}}(A)+\bm{\lambda_{\rm
max}}(B).$

######  Proof A.3.

See Theorem 10.4.11 of [2].

######  Lemma 4.

Let $A\in{\mathbb{R}}^{n\times n}$ and $B\in{\mathbb{R}}^{n\times n}$. Then,
the eigenvalues of $AB\in{\mathbb{R}}^{n\times n}$ are the eigenvalues of
$BA\in{\mathbb{R}}^{n\times n}$

######  Proof A.4.

See Theorem 1.3.22 of [13].

######  Lemma 5.

Let $H\in{\mathbb{R}}^{n\times n}$ and $M\in{\mathbb{R}}^{n\times n}$ by
symmetric matrices. Then,
$\operatorname{rank}(H-M)=\operatorname{rank}(H)-\operatorname{rank}(M)$ if
and only if there exists $S\in{\mathbb{R}}^{n\times p}$ such that $M=HS(S^{\rm
T}HS)^{-1}S^{\rm T}H$.

######  Proof A.5.

See Lemma 2.4 in [6].

######  Lemma 6.

Let $H,M\in{\mathbb{R}}^{n\times n}$, where $H$ is positive definite and $M$
is positive semidefinite. Then, $H-M\succeq 0$ (respectively $H-M\succ 0$) if
and only if $\rho(H^{-1}M)\leq 1$ (respectively $\rho(H^{-1}M)<1$).

######  Proof A.6.

See Theorem 7.7.3 in [13].

######  Lemma 7.

Let $A\in{\mathbb{R}}^{n\times n}$ be positive definite and
$b\in{\mathbb{R}}^{n\times p}$. Then, $b^{\rm T}Ab\in{\mathbb{R}}^{p\times p}$
is positive semidefinite, $\operatorname{rank}(b^{\rm
T}Rb)=\operatorname{rank}(b)$, and $b^{\rm T}Ab$ is positive definite if and
only if $\operatorname{rank}(b)=p$.

######  Proof A.7.

See Observation 7.1.8 in [13].

##  Appendix B Proofs in the Subspace Decomposition of a Positive-Definite
Matrix

######  Proof B.1 (Proof of Theorem 1).

By Lemma 7, $v^{\rm T}Av$ is positive definite. Hence, $A^{\parallel S}$ and
$A^{\perp S}$ are well defined.

Proof of (1a), (1b): Since $v^{\rm T}Av$ is positive definite, $(v^{\rm
T}Av)^{-1}$ is also positive definite. Furthermore, Lemma 7 implies that
$A^{\parallel S}=(Av)(v^{\rm T}Av)^{-1}(Av)^{\rm T}$ is positive semidefinite.
Next, note that by Lemma 6, $A^{\perp S}=A-A^{\parallel S}$ is positive
semidefinite if and only if $\rho(A^{-1}A^{\parallel S})\leq 1$. Notice that

$\displaystyle(A^{-1}A^{\parallel S})^{2}$ $\displaystyle=\left[v(v^{\rm
T}Av)^{-1}v^{\rm T}A\right]^{2},$ $\displaystyle=v(v^{\rm T}Av)^{-1}v^{\rm
T}Av(v^{\rm T}Av)^{-1}v^{\rm T}A,$ $\displaystyle=v(v^{\rm T}Av)^{-1}v^{\rm
T}A,=A^{-1}A^{\parallel S}.$

Therefore, $A^{-1}A^{\parallel S}$ is idempotent implying each of its $n$
eigenvalues are either $0$ or $1$. Hence, $\rho(A^{-1}A^{\parallel S})\leq 1$
implying that $A^{\perp S}$ is positive semidefinite.

Proof of (2a), (2b): Define $B\triangleq(v^{\rm
T}Av)^{\nicefrac{{1}}{{2}}}\in{\mathbb{R}}^{p\times p}$. It follows that

$\displaystyle A^{\parallel S}=Av(BB^{\rm T})^{-1}v^{\rm T}A=(AvB^{-1})^{\rm
T}(AvB^{-1}).$

Thus, $\operatorname{rank}(A^{\parallel S})=\operatorname{rank}(AvB^{-1})$.
Since $A$ and $B^{-1}$ are positive definite, it follows that
$\operatorname{rank}(AvB^{-1})=\operatorname{rank}(v)$. Hence,
$\operatorname{rank}(A^{\parallel S})=\operatorname{rank}(v)=p$. Next, Lemma 5
implies that $\operatorname{rank}(A^{\perp
S})=\operatorname{rank}(A)-\operatorname{rank}(A^{\parallel S})=n-p$.

Proof of (3a), (3b): Let $x\in S$. Since $v_{1},\ldots,v_{p}$ is a basis for
$S$, it follows that there exists $c\in{\mathbb{R}}^{p\times 1}$ such that
$x=vc$. Hence,

$\displaystyle A^{\parallel S}x=Av(v^{\rm T}Av)v^{\rm T}Avc=Avc=Ax,$

and $A^{\perp S}x=(A-A^{\parallel S})x=Ax-Ax=0$.

######  Proof B.2 (Proof of Theorem 2).

Let $v_{1},\cdots,v_{p}\in{\mathbb{R}}^{n}$ be a basis for $S$ and
$v\triangleq\begin{bmatrix}v_{1}&\cdots&v_{p}\end{bmatrix}\in{\mathbb{R}}^{n\times
p}$. Begin by writing $\tilde{A}=AXA$, where $X\triangleq
A^{-1}\tilde{A}A^{-1}\in{\mathbb{R}}^{n\times n}$ and define $P\triangleq
v(v^{\rm T}v)^{-1}v^{\rm T}\in{\mathbb{R}}^{n\times n}$. Since
$\tilde{A}v=Av$, it follows that

$\displaystyle XAP=A^{-1}\tilde{A}v(v^{\rm T}v)^{-1}v^{\rm T}=A^{-1}Av(v^{\rm
T}v)^{-1}v^{\rm T}=P.$

Since $XAP=P$, it follows that the column space of $P$ is a subset of the
column space of $X$. However, note that
$\operatorname{rank}(P)=\operatorname{rank}(X)=p$. Therefore, $X$ and $P$ have
the same column space.

Hence, for all $x\in{\mathbb{R}}^{n}$, there exists $y\in{\mathbb{R}}^{n}$
such that $Xx=Py$. Moreover, since $P^{2}=P$, it follows that, for all
$x\in{\mathbb{R}}^{n}$, there exists $y\in{\mathbb{R}}^{n}$ such that
$PXx=PPy=Py=Xx$. Hence, $PX=X$. Moreover, since $P$, $X$, and $PX=X$ are
symmetric, it follows that $P$ and $X$ commute. Therefore,

$\displaystyle PX=XP=X.$

Next, define $Q\triangleq PAP$. Note that $XQ=XPAP=XAP=P$. Moreover, since
$X$, $Q$, and $XQ=P$ are symmetric, it follows that $X$ and $Q$ commute.
Therefore,

$\displaystyle XQ=QX=P.$

Thus, it follows that $X$ and $Q$ satisfy the four Moore-Penrose Conditions:

  1. 1.

$XQX=XP=X$,

  2. 2.

$QXQ=QP=PAPP=PAP=Q$,

  3. 3.

$XQ=P=P^{\rm T}=(XQ)^{\rm T}$,

  4. 4.

$QX=P=P^{\rm T}=(QX)^{\rm T}$.

Therefore, $X=Q^{+}$ and $\tilde{A}=AQ^{+}A$. Finally, define $G\triangleq
v(v^{\rm T}Av)^{-1}v^{\rm T}\in{\mathbb{R}}^{n\times n}$. It can be easily
verified that $Q=v(v^{\rm T}v)^{-1}v^{\rm T}Av(v^{\rm T}v)^{-1}v^{\rm T}$ and
$G$ satisfy the four Moore-Penrose Conditions $GQG=G$, $QGQ=Q$, $GQ=(GQ)^{\rm
T}$, and $QG=(QG)^{\rm T}$. Hence, $X=Q^{+}=(G^{+})^{+}=G$, and
$\tilde{A}=AGA=Av(v^{\rm T}Av)^{-1}v^{\rm T}A=A^{\parallel S}$.

######  Proof B.3 (Proof of Proposition 9).

Note that since $\langle\cdot,\cdot\rangle_{A}$ is an inner product, it
follows that $\dim(S^{\perp_{A}})=n-\dim(S)=n-p$. Let
$w_{1},\ldots,w_{n-p}\in{\mathbb{R}}^{n}$ be a basis for $S^{\perp_{A}}$ and
let $w\triangleq[w_{1}\ \cdots\ w_{n-p}]\in{\mathbb{R}}^{n\times n-p}$. Then,
$A^{\perp(S^{\perp_{A}})}$ can be written as

$\displaystyle A^{\perp(S^{\perp_{A}})}=A-Aw(w^{\rm T}Aw)^{-1}w^{\rm T}A.$

Note that $A^{\perp(AS)^{\perp}}$ is the difference of two symmetric matrices,
$A$ and $Aw(w^{\rm T}Aw)^{-1}w^{\rm T}A$, hence is symmetric. Next, since
$\operatorname{rank}(w)=n-p$, it follows that $\operatorname{rank}(Aw(w^{\rm
T}Aw)^{-1}w^{\rm T}A)=n-p$. Furthermore, it follows from Lemma 5 that
$\operatorname{rank}(A^{\perp(AS)^{\perp}})=\operatorname{rank}(A)-\operatorname{rank}(Aw(w^{\rm
T}Aw)^{-1}w^{\rm T}A)=n-(n-p)=p$. Finally, since the columns of $w$ are
elements of $S^{\perp_{A}}$, it follows that, for all $x\in S$, $w^{\rm
T}Ax=0_{n-p\times 1}$. Hence, for all $x\in S$,

$\displaystyle A^{\perp(S^{\perp_{A}})}x=Ax-Aw(w^{\rm T}Aw)^{-1}w^{\rm
T}Ax=Ax.$

Thus, the three properties of Theorem 2 are satisfied and $A^{\parallel
S}=A^{\perp(S^{\perp_{A}})}$ holds, proving (20).

Next, it follows from definition (15) that
$A^{\perp(S^{\perp_{A}})}=A-A^{\parallel(S^{\perp_{A}})}$ which can be
rewritten as $A-A^{\perp(S^{\perp_{A}})}=A^{\parallel(S^{\perp_{A}})}$. It
then follows from (20) that $A-A^{\parallel S}=A^{\parallel(S^{\perp_{A}})}$.
Finally, by definition (15), it follows that $A^{\perp
S}=A^{\parallel(S^{\perp_{A}})}$, proving (21).

##  Appendix C Proof of Theorem 3

We begin the proof of Theorem 3 with a useful Lemma.

######  Lemma 13.

For all $k\geq 0$, the $n-q_{k}$ nonzero eigenvalues of $R_{k}^{\perp}$ are
bounded below by $\bm{\lambda_{\rm min}}(R_{k})$ and bounded above by
$\bm{\lambda_{\rm max}}(R_{k})$.

Proof. Let $k\geq 0$. To begin, note that by Theorem 1,
$\operatorname{rank}(R_{k}^{\perp})=n-q_{k}$. Therefore, $R_{k}^{\perp}$ has
$n-q_{k}$ nonzero eigenvalues.

First, we show the upper bound. Since $R_{k}=R_{k}^{\parallel}+R_{k}^{\perp}$,
it follows from Lemma 3 that $\bm{\lambda_{\rm
min}}(R_{k}^{\parallel})+\bm{\lambda_{\rm
max}}(R_{k}^{\perp})\leq\bm{\lambda_{\rm max}}(R_{k})$. Next, Theorem 1
implies that $R_{k}^{\parallel}$ is positive semidefinite, thus
$0\leq\bm{\lambda_{\rm min}}(R_{k}^{\parallel})$. It then follows that
$\bm{\lambda_{\rm max}}(R_{k}^{\perp})\leq\bm{\lambda_{\rm max}}(R_{k})$.

Second, to show the lower bound, first let
$R_{k}^{\nicefrac{{1}}{{2}}}\in{\mathbb{R}}^{n}$ be the unique positive-
definite matrix such that
$R_{k}=R_{k}^{\nicefrac{{1}}{{2}}}R_{k}^{\nicefrac{{1}}{{2}}}$. Furthermore,
define $\Omega_{k}\in{\mathbb{R}}^{n\times n}$ as

$\displaystyle\Omega_{k}\triangleq
I_{n}-R_{k}^{\nicefrac{{1}}{{2}}}\bar{\phi}_{k}^{\rm
T}(\bar{\phi}_{k}R_{k}\bar{\phi}_{k}^{\rm
T})^{-1}\bar{\phi}_{k}R_{k}^{\nicefrac{{1}}{{2}}}.$

It then follows that
$R_{k}^{\perp}=R_{k}^{\nicefrac{{1}}{{2}}}\Omega_{k}R_{k}^{\frac{1}{2}}$. It
can also be easily verified that $\Omega_{k}^{2}=\Omega_{k}$, hence
$R_{k}^{\perp}=(R_{k}^{\frac{1}{2}}\Omega_{k})(\Omega_{k}R_{k}^{\frac{1}{2}})$.
Then, it follows from Lemma 4 that the eigenvalues of $R_{k}^{\perp}$ are the
same as the eigenvalues of
$(\Omega_{k}R_{k}^{\frac{1}{2}})(R_{k}^{\frac{1}{2}}\Omega_{k})=\Omega_{k}R_{k}\Omega_{k}$.

Next, since $R_{k}^{\perp}$ has $n-q_{k}$ nonzero eigenvalues, it suffices to
show that $\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})\geq\bm{\lambda_{\rm
min}}(R_{k})$. Furthermore, by the previous result, it holds that
$\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})=\bm{\lambda_{n-q_{k}}}(\Omega_{k}R_{k}\Omega_{k})$.
It then follows from Lemma 2 that

$\displaystyle\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})=\max_{\begin{subarray}{c}S\subset{\mathbb{R}}^{n}\\\
\dim(S)=n-q_{k}\end{subarray}}\min_{\begin{subarray}{c}x\in S\\\
\|x\|=1\end{subarray}}x^{\rm T}\Omega_{k}R_{k}\Omega_{k}x.$

Furthermore, since
$\Omega_{k}=R_{k}^{-\nicefrac{{1}}{{2}}}R_{k}^{\perp}R_{k}^{-\nicefrac{{1}}{{2}}}$
and $R^{-\nicefrac{{1}}{{2}}}$ is positive definite, it follows that
$\operatorname{rank}(\Omega_{k})=n-q_{k}$. Hence,
$\dim(\mathcal{R}(\Omega_{k}))=n-q_{k}$. Therefore,

$\displaystyle\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})\geq\min_{x\in\mathcal{R}(\Omega_{k}),\
\|x\|=1}x^{\rm T}\Omega_{k}R_{k}\Omega_{k}x.$

Next, since $\Omega_{k}^{2}=\Omega_{k}$, it follows that, for all
$x\in\mathcal{R}(\Omega_{k})$, $\Omega_{k}x=x$. Hence,

$\displaystyle\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})\geq\min_{x\in\mathcal{R}(\Omega_{k}),\
\|x\|=1}x^{\rm T}R_{k}x.$

Finally, note that

$\displaystyle\min_{x\in\mathcal{R}(\Omega_{k}),\ \|x\|=1}x^{\rm
T}R_{k}x\geq\min_{\|x\|=1}x^{\rm T}R_{k}x=\bm{\lambda_{\rm min}}(R_{k}).$
$\blacksquare$

We now present the proof of Theorem 3.

######  Proof C.1 (Proof of Theorem 3).

Proof follows by induction on $k\geq 0$. First, consider the base case $k=0$.
Note that $R_{0}\succeq\bm{\lambda_{\rm min}}(R_{0})I_{n}$ implying (34) and
that $R_{0}\preceq\bm{\lambda_{\rm max}}(R_{0})I_{n}$ implying (36).

Next, let $k\geq 0$. Let $\phi_{k}=U_{k}\Sigma_{k}V_{k}^{\rm T}$ be the full
SVD of $\phi_{k}$, where $U_{k}\in{\mathbb{R}}^{p\times p}$ is orthogonal,
$\Sigma_{k}\in{\mathbb{R}}^{p\times n}$ is rectangular diagonal with diagonal
in descending order, and $V_{k}\in{\mathbb{R}}^{n\times n}$ is orthogonal.
Moreover, denote the singular of $\phi_{k}$ as
$\sigma_{1,k},\sigma_{2,k},\ldots,\sigma_{\min\\{p,n\\},k}$. Finally, since
$q_{k}\leq\min\\{p,n\\}$, we can partition the columns of $U_{k}$ and rows of
$V_{k}$ as

$\displaystyle U_{k}=\begin{bmatrix}U_{1,k}&U_{2,k}\end{bmatrix},\quad
V_{k}=\begin{bmatrix}V_{1,k}&V_{2,k}\end{bmatrix},$ (47)

where $U_{1,k}\in{\mathbb{R}}^{p\times q_{k}}$ and
$V_{1,k}\in{\mathbb{R}}^{n\times q_{k}}$ are the first $q_{k}$ columns of
$U_{k}$ and $V_{k}$ respectively, and
$U_{2,k}\in{\mathbb{R}}^{p\times(p-q_{k})}$ and
$V_{2,k}\in{\mathbb{R}}^{n\times(n-q_{k})}$ are the remaining columns of
$U_{k}$ and $V_{k}$ respectively. Note that
$\bar{\phi}_{k}\in{\mathbb{R}}^{q_{k}\times n}$, defined in (22), can be
expressed as

$\displaystyle\bar{\phi}_{k}=U_{1,k}^{\rm T}\phi_{k}.$ (48)

Moreover, the columns of $V_{1,k}$ form an orthonormal basis for
$\mathcal{R}(\bar{\phi}_{k}^{\rm T})$.

Next, it follows from (27) and (29) that $R_{k+1}=\lambda
R_{k}^{\parallel}+R_{k}^{\perp}+\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k}$. It then
follows from (26) that

$\displaystyle R_{k+1}=\lambda
R_{k}+(1-\lambda)R_{k}^{\perp}+\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k}.$ (49)

Pre-multiplying by $V_{k}^{\rm T}$ and post-multiplying by $V_{k}$, it follows
that

$\displaystyle V_{k}^{\rm T}R_{k+1}V_{k}=V_{k}^{\rm T}[\lambda
R_{k}+(1-\lambda)R_{k}^{\perp}+\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k}]V_{k}.$
(50)

Since the columns of $V_{1,k}$ form an orthonormal basis for
$\mathcal{R}(\bar{\phi}_{k}^{\rm T})$, it follows from Theorem 1 that
$R_{k}^{\perp}V_{1,k}=0_{n\times q_{k}}$. It then follows that

$\displaystyle V_{k}^{\rm T}R_{k}^{\perp}V_{k}=\begin{bmatrix}0_{q_{k}\times
q_{k}}&0_{q_{k}\times(n-q_{k})}\\\ 0_{(n-q_{k})\times q_{k}}&V_{2,k}^{\rm
T}R_{k}^{\perp}V_{2,k}\end{bmatrix}.$ (51)

Moreover, note that the columns of $V_{2,k}$ are orthogonal to the columns of
$V_{1,k}$, hence are also orthogonal to the rows of $\bar{\phi}_{k}$.
Therefore, $\bar{\phi}_{k}V_{2,k}=0_{q_{k}\times(n-q_{k})}$. Thus it follows
that

$\displaystyle V_{k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{k}=\begin{bmatrix}V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{1,k}&0_{q_{k}\times(n-q_{k})}\\\ 0_{(n-q_{k})\times
q_{k}}&0_{(n-q_{k})\times(n-q_{k})}\end{bmatrix}.$ (52)

Substituting (51) and (52) into (50), it follows that

$\displaystyle V_{k}^{\rm T}R_{k+1}$ $\displaystyle V_{k}=\lambda V_{k}^{\rm
T}R_{k}V_{k}$ $\displaystyle+\begin{bmatrix}V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{1,k}&0_{q_{k}\times(n-q_{k})}\\\ 0_{(n-q_{k})\times
q_{k}}&(1-\lambda)V_{2,k}^{\rm T}R_{k}^{\perp}V_{2,k}\end{bmatrix}.$ (53)

We now prove two claims which will later be useful.

Claim 1: $V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{1,k}=\operatorname{diag}(\sigma_{1,k}^{2},\ldots,\sigma_{q_{k},k}^{2})$.

Proof of Claim 1: Note that $\bar{\phi}_{k}=U_{1,k}^{\rm
T}U_{k}\Sigma_{k}V_{k}^{\rm T}$. Furthermore, note that, $U_{1,k}^{\rm
T}U_{k}=[U_{1,k}^{\rm T}U_{1,k}\ U_{1,k}^{\rm T}U_{2,k}]=[I_{q_{k}}\
0_{q_{k}\times(p-q_{k})}]$. Similarly, we can express $V_{1,k}^{\rm
T}V_{k}=[V_{1,k}^{\rm T}V_{1,k}\ V_{1,k}^{\rm T}V_{2,k}]=[I_{q_{k}}\
0_{q_{k}\times(n-q_{k})}]$. Therefore, $V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{1,k}$ can be written as

$\displaystyle V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k}V_{1,k}$
$\displaystyle=V_{1,k}^{\rm T}V_{k}\Sigma_{k}^{\rm T}U_{k}^{\rm
T}U_{1,k}U_{1,k}^{\rm T}U_{k}\Sigma_{k}V_{k}^{\rm T}V_{1,k}$
$\displaystyle=\begin{bmatrix}I_{q_{k}}&0\end{bmatrix}\Sigma_{k}^{\rm
T}\begin{bmatrix}I_{q_{k}}&0\\\
0&0\end{bmatrix}\Sigma_{k}\begin{bmatrix}I_{q_{k}}\\\ 0\end{bmatrix}$
$\displaystyle=\operatorname{diag}(\sigma_{1,k}^{2},\ldots,\sigma_{q_{k},k}^{2}),$
(54)

with zero matrices of appropriate sizes. $\square$

Claim 2: The $n-q_{k}$ nonzero eigenvalues of $R_{k}^{\perp}$ are the
eigenvalues of $V_{2,k}^{\rm
T}R_{k}^{\perp}V_{2,k}\in{\mathbb{R}}^{(n-q_{k})\times(n-q_{k})}$.

Proof of Claim 2: First, note that, by Theorem 1,
$\operatorname{rank}(R_{k}^{\perp})=n-q_{k}$, hence $R_{k}^{\perp}$ has
$n-q_{k}$ nonzero eigenvalues. Next, it follows from (51) that $V_{k}^{\rm
T}R_{k}^{\perp}V_{k}$ is block diagonal. Therefore, the eigenvalues of
$V_{k}^{\rm T}R_{k}^{\perp}V_{k}$ are $q_{k}$ zeros and the $n-q_{k}$
eigenvalues of $V_{2,k}^{\rm T}R_{k}^{\perp}V_{2,k}$. Finally, since
similarity transformation preserve eigenvalues, it follows that the
eigenvalues of $R_{k}^{\perp}$ are $q_{k}$ zeros and the $n-q_{k}$ eigenvalues
of $V_{2,k}^{\rm T}R_{k}^{\perp}V_{2,k}$. $\square$

We now show the induction step for statement (1) of Theorem 3. First, assume,
for inductive hypothesis, that (34) holds $k\geq 0$. Applying Lemma 3 to (C.1)
yields

$\displaystyle\bm{\lambda_{\rm min}}(V_{k}^{\rm
T}R_{k+1}V_{k})\geq\lambda\bm{\lambda_{\rm min}}(V_{k}^{\rm T}R_{k}V_{k})+$
$\displaystyle\min\\{\bm{\lambda_{\rm min}}(V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{1,k}),(1-\lambda)\bm{\lambda_{\rm min}}(V_{2,k}^{\rm
T}R_{k}^{\perp}V_{2,k})\\}.$ (55)

Since similarity transformations preserve eigenvalues, it then follows that

$\displaystyle\bm{\lambda_{\rm min}}(R_{k+1})\geq\lambda\bm{\lambda_{\rm
min}}(R_{k})+$ $\displaystyle\min\\{\bm{\lambda_{\rm min}}(V_{1,k}^{\rm
T}\bar{\phi}_{k}^{\rm T}\bar{\phi}_{k}V_{1,k}),(1-\lambda)\bm{\lambda_{\rm
min}}(V_{2,k}^{\rm T}R_{k}^{\perp}V_{2,k})\\}.$ (56)

Next, applying the results of Claims 1 and 2, it follows that

$\displaystyle\bm{\lambda_{\rm min}}(R_{k+1})$
$\displaystyle\geq\lambda\bm{\lambda_{\rm min}}(R_{k})$
$\displaystyle+\min\\{\sigma_{q_{k},k}^{2},(1-\lambda)\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})\\}.$
(57)

Note that, by construction of $q_{k}$, it follows that
$\sigma_{q_{k},k}\geq\sqrt{\varepsilon}$. Moreover, by Lemma 13,
$\bm{\lambda_{n-q_{k}}}(R_{k}^{\perp})\geq\bm{\lambda_{\rm min}}(R_{k})$.
Applying these two inequalities to (C.1), it follows that

$\displaystyle\bm{\lambda_{\rm min}}(R$ ${}_{k+1})\geq\lambda\bm{\lambda_{\rm
min}}(R_{k})+\min\\{\varepsilon,(1-\lambda)\bm{\lambda_{\rm min}}(R_{k})\\}$
$\displaystyle=\min\\{\varepsilon+\lambda\bm{\lambda_{\rm
min}}(R_{k}),\bm{\lambda_{\rm min}}(R_{k})\\}.$ (58)

Next, substituting inductive hypothesis (34) into (C.1), it follows that

$\displaystyle\bm{\lambda_{\rm min}}(R_{k+1})\geq\min\Big{\\{}$
$\displaystyle\varepsilon+\lambda(\frac{\varepsilon}{1-\lambda}),\varepsilon+\lambda\bm{\lambda_{\rm
min}}(R_{0}),$ $\displaystyle\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\Big{\\}}.$ (59)

Note that $\varepsilon+\lambda(\frac{\varepsilon}{1-\lambda})$ simplifies to
$\frac{\varepsilon}{1-\lambda}$. Hence, (C.1) can be rewritten as

$\displaystyle\bm{\lambda_{\rm
min}}(R_{k+1})\geq\min\\{\varepsilon+\lambda\bm{\lambda_{\rm
min}}(R_{0}),\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm min}}(R_{0})\\}.$
(60)

In the case where $\bm{\lambda_{\rm
min}}(R_{0})\geq\frac{\varepsilon}{1-\lambda}$, it follows that

$\displaystyle\varepsilon+\lambda\bm{\lambda_{\rm
min}}(R_{0})\geq\varepsilon+\lambda(\frac{\varepsilon}{1-\lambda})=(\frac{\varepsilon}{1-\lambda}).$

In the case where $\bm{\lambda_{\rm
min}}(R_{0})<\frac{\varepsilon}{1-\lambda}$, it follows that
$\varepsilon-(1-\lambda)\bm{\lambda_{\rm min}}(R_{0})>0$, and hence

$\displaystyle\varepsilon+\lambda\bm{\lambda_{\rm min}}(R_{0})$
$\displaystyle=\bm{\lambda_{\rm
min}}(R_{0})+\varepsilon-(1-\lambda)\bm{\lambda_{\rm min}}(R_{0})$
$\displaystyle>\bm{\lambda_{\rm min}}(R_{0}).$

Combining these two cases implies that

$\displaystyle\varepsilon+\lambda\bm{\lambda_{\rm
min}}(R_{0})\geq\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\}.$ (61)

Substituting (61) into (60) yields

$\displaystyle\bm{\lambda_{\rm
min}}(R_{k+1})\geq\min\\{\frac{\varepsilon}{1-\lambda},\bm{\lambda_{\rm
min}}(R_{0})\\}.$ (62)

Therefore, by induction, (34) holds for all $k\geq 0$.

Next, we will show the induction step for statement (2) of Theorem 3. Assume
that $(\phi_{k})_{k=0}^{\infty}$ is bounded with upper bound
$\beta\in(0,\infty)$ and assume, for inductive hypothesis, that (36) holds for
$k\geq 0$. Next, applying Lemma 3 to (C.1), it follows that

$\displaystyle\bm{\lambda_{\rm max}}(V_{k}^{\rm
T}R_{k+1}V_{k})\leq\lambda\bm{\lambda_{\rm max}}(V_{k}^{\rm T}R_{k}V_{k})+$
$\displaystyle\max\\{\bm{\lambda_{\rm max}}(V_{1,k}^{\rm T}\bar{\phi}_{k}^{\rm
T}\bar{\phi}_{k}V_{1,k}),(1-\lambda)\bm{\lambda_{\rm max}}(V_{2,k}^{\rm
T}R_{k}^{\perp}V_{2,k})\\}.$ (63)

By analogous reasoning to that used previously, we use the fact that
similarity transformations preserve eigenvalues, Lemma 13, and Claims 1 and 2
to simplify (C.1) to

$\displaystyle\bm{\lambda_{\rm max}}(R_{k+1})$
$\displaystyle\leq\lambda\bm{\lambda_{\rm max}}(R_{k})$
$\displaystyle+\max\\{\sigma_{1,k}^{2},(1-\lambda)\bm{\lambda_{\rm
max}}(R_{k})\\}.$ (64)

Moreover since $(\phi_{k})_{k=0}^{\infty}$ is bounded with upper bound
$\beta$, it follows from Definition 2 that $\sigma_{1,k}^{2}\leq\beta$. Thus,
it follows from (C.1) that

$\displaystyle\bm{\lambda_{\rm max}}(R_{k+1})$
$\displaystyle\leq\max\\{\beta+\lambda\bm{\lambda_{\rm
max}}(R_{k}),\bm{\lambda_{\rm max}}(R_{k})\\}.$ (65)

Next, substituting inductive hypothesis (36) into (65) yields

$\displaystyle\bm{\lambda_{\rm max}}(R_{k+1})\leq\max\Big{\\{}$
$\displaystyle\beta+\lambda(\frac{\beta}{1-\lambda}),\beta+\lambda\bm{\lambda_{\rm
max}}(R_{0}),$ $\displaystyle\frac{\beta}{1-\lambda},\bm{\lambda_{\rm
max}}(R_{0})\Big{\\}}.$ (66)

Then, by similar reasoning to before, it can be shown that (C.1) simplifies to

$\displaystyle\bm{\lambda_{\rm
max}}(R_{k+1})\leq\max\\{\frac{\beta}{1-\lambda},\bm{\lambda_{\rm
max}}(R_{0})\\}.$ (67)

Therefore, by induction, (36) holds for all $k\geq 0$.

##  Appendix D Comparison to [35]

In [35], a different vector measurement extension of [5] is presented using an
oblique projection decomposition. A tuning parameter $\varepsilon>0$ is chosen
and, for all $k\geq 0$, if $\|\phi_{k}\|_{2}\geq\varepsilon$, then the
information matrix $R_{k}\in{\mathbb{R}}^{n\times n}$ is updated as

$R_{k+1}=R_{k}-(1-\lambda)R_{k}\phi_{k}^{\rm T}(\phi_{k}R_{k}\phi_{k}^{\rm
T})^{+}\phi_{k}R_{k}+\phi_{k}^{\rm T}\phi_{k},$ (68)

and if $\|\phi_{k}\|_{2}<\varepsilon$, then $R_{k+1}=R_{k}+\phi_{k}^{\rm
T}\phi_{k}$. It is shown in Theorem 3 of [35] that, for all $k\geq 0$, $R_{k}$
is positive definite. However, we show that there may not exist $\gamma>0$
such that, for all $k\geq 0$, $\bm{\lambda_{\rm min}}(R_{k})\succeq\gamma$. In
particular, the following example shows that $R_{k}$ may converge to a
positive semidefinite matrix. Hence, Theorem 3 of SIFt-RLS provides stronger
bounds on the eigenvalues of the information matrix than [35] does.

Let $\varepsilon>0$. Let $R_{0}=\operatorname{diag}(\varepsilon^{2},1)$ and,
for all $k\geq 0$, let
$\phi_{k}=\operatorname{diag}(\varepsilon,\lambda^{\frac{k+1}{2}})$. Then, for
all $k\geq 0$, $\|\phi_{k}\|_{2}\geq\varepsilon$. Moreover, for all $k\geq 0$,
$\phi_{k}$ is nonsingular, hence $\eqref{eqn: Rk update zhu 2021}$ simplifies
to

$\displaystyle R_{k+1}=\lambda R_{k}+\phi_{k}^{\rm T}\phi_{k}=\lambda
R_{k}+\begin{bmatrix}\varepsilon^{2}&0\\\ 0&\lambda^{k+1}\end{bmatrix}.$ (69)

Therefore, for all $k\geq 0$,

$\displaystyle
R_{k}=\begin{bmatrix}\varepsilon^{2}\sum_{i=0}^{k}\lambda^{i}&0\\\
0&(k+1)\lambda^{k}\end{bmatrix}.$ (70)

This implies that
$\lim_{k\rightarrow\infty}R_{k}=\operatorname{diag}(\frac{\varepsilon^{2}}{1-\lambda},0)$.
Therefore, there does not exist $\gamma>0$ such that, for all $k\geq 0$,
$\bm{\lambda_{\rm min}}(R_{k})\succeq\beta$.