# Learning to Stabilize Unknown LTI Systems on a Single Trajectory under
Stochastic Noise

Ziyi Zhang111Department of Electrical and Computer Engineering, Carnegie
Mellon University. Email<EMAIL_ADDRESS>Yorie Nakahira222Department
of Electrical and Computer Engineering, Carnegie Mellon University. Email:
<EMAIL_ADDRESS>Guannan Qu333Department of Electrical and Computer
Engineering, Carnegie Mellon University. Email<EMAIL_ADDRESS>
###### Abstract

We study the problem of learning to stabilize unknown noisy Linear Time-
Invariant (LTI) systems on a single trajectory. It is well known in the
literature that the learn-to-stabilize problem suffers from exponential blow-
up in which the state norm blows up in the order of $\Theta(2^{n})$ where $n$
is the state space dimension. This blow-up is due to the open-loop instability
when exploring the $n$-dimensional state space. To address this issue, we
develop a novel algorithm that decouples the unstable subspace of the LTI
system from the stable subspace, based on which the algorithm only explores
and stabilizes the unstable subspace, the dimension of which can be much
smaller than $n$. With a new singular-value-decomposition(SVD)-based
analytical framework, we prove that the system is stabilized before the state
norm reaches $2^{O(k\log n)}$, where $k$ is the dimension of the unstable
subspace. Critically, this bound avoids exponential blow-up in state dimension
in the order of $\Theta(2^{n})$ as in the previous works, and to the best of
our knowledge, this is the first paper to avoid exponential blow-up in
dimension for stabilizing LTI systems with noise.

##  1 Introduction

Driven by the success of machine learning and the practical engineering need
in control, there has been a lot of interests in learning-based control of
unknown dynamical systems Beard et al. [1997]; Li et al. [2022]; Bradtke et
al. [1994]; Krauth et al. [2019]; Dean S. Mania [2020]. However, the existing
methods commonly rely on the strong assumption of having access to a known
stabilizing controller. This motivates the learning-to-stabilize problem, i.e.
learning to stabilize an unknown dynamical system, particularly on a single
trajectory, which has long been a challenging problem both in theory and for
applications such as control of automatic vehicles and unmanned aerial
vehicles (UAV).

Although many classical adaptive control approaches can solve the learn-to-
stabilize problem and achieve asymptotic stability guarantees Pasik-Duncan
[1996]; Petros A. Ioannou [2001], it is well known that the learn-to-stabilize
problem suffers from an issue known as _exponential blow-up_ during
transients. As an example, Abbasi-Yadkori and Szepesvári [2011] and Chen and
Hazan [2020] presented a model-based approach for learning to stabilize an
unknown LTI system $x_{t+1}=Ax_{t}+Bu_{t}$. It first excites the system in
open loop to learn the dynamics matrices $(A,B)$ and then designs the
stabilizer. However, the initial excitation phase needs to run the system in
open loop for at least $n$ steps before learning $(A,B)$ where $n$ is the
dimension of the state space, because it takes at least $n$ samples to fully
explore the $n$ dimensional state space. As a result, the state norm blows up
to the order of $2^{\tilde{O}(n)}$ as the system may be unstable in open loop.
Such an exponential blow-up can be catastrophic and has been observed in
multiple papers Abbasi-Yadkori and Szepesvári [2011]; Chen and Hazan [2020];
Lale et al. [2020]; Perdomo et al. [2021]; Tsiamis and Pappas [2021]. Further,
it has also been shown that all general-purpose control algorithms suffer a
worst-case regret of $2^{\Omega(n)}$ Chen and Hazan [2020].

Despite the exponential blow-up lower bound in Chen and Hazan [2020], it is a
worst-case bound and does not rule out better results for specific systems.
This motivates the following question: _is it possible to exploit instance-
specific properties to learn to stabilize a noisy LTI system without suffering
from the worst-case exponential blow-up in $n$?_ This problem has two
challenges. First, in order to avoid the exponential blow-up, one can only
collect $o(n)$ samples, based on which we can only get partial information on
the dynamics. With only partial information about the system dynamics, it is
difficult to stabilize it. Second, the noise in each step of the system is
amplified by the open loop unstable system, causing strong statistical
dependencies between states, which explode exponentially in a single
trajectory.

To solve the first challenge, we use the framework proposed in Hu et al.
[2022], which gave an algorithm that stabilizes a _deterministic_ LTI system
with only $\tilde{O}(k)$ state samples along a trajectory, where $k<n$ is the
number of unstable eigenvalues of $A$. Therefore, Hu et al. [2022] offered an
algorithm with state norm upper bounded by $2^{\tilde{O}(k)}$, which avoids
the exponential blow-up $2^{\tilde{O}(n)}$ Chen and Hazan [2020]; Tsiamis and
Pappas [2021]. However, Hu et al. [2022] does not solve the second challenge
as it assumes _noiseless and deterministic_ system dynamics. In addition, Hu
et al. [2022] assumes that the control matrix has the same dimension as the
instability index $k$. In other words, the system is _fully actuated_ when
restricted to the unstable subspace. This assumption is also unrealistic in
applications, as the dimension of control input is problem-specific and may
not be equal to $k$. Particularly, many real-world systems are under-actuated,
meaning that the control dimension can be much less than $k$.

To solve the second challenge and address the limitations in Hu et al. [2022],
we need to determine a new method to approximate the unstable part of the
system dynamics under stochastic noise and stabilize it with under-actuated
control inputs. This is nontrivial as, for example, while some previous works
have designed methods to approximate system dynamics from a noisy and blowing-
up trajectorySarkar and Rakhlin [2018]; Simchowitz et al. [2018], these
methods do not study how to separate the unstable part of the dynamics from
the stable part and how to stabilize the system. The goal of this paper is to
overcome these technical challenges and _to learn-to-stabilize an unknown LTI
system without the exponential blow-up state norm in noisy and under-actuated
settings._

Contribution. In this paper, we develop a novel model-based algorithm, LTS0-N,
to stabilize an unknown LTI system. We design a new singular-value-
decomposition(SVD)-based subspace estimation technique to estimate the
“unstable” part of system dynamics under noise perturbations and stabilize it.
Using this new technique, we develop an analytical framework with the Davis-
Kahan Theorem to estimate the error of subspace estimation, based on which we
show the approach stabilizes the unknown dynamical system with state norm
bounded by $2^{O(k\log k+\log(n-k)+m-\log\text{gap})}$, where $m$ is the
dimension of control input, and gap is a constant depending on the spectral
properties of $A$. Note that this bound avoids the worst-case exponential
blow-up in state dimension $\Theta(2^{n})$ and outperforms the state-of-the-
art for stabilizing unknown noisy systems Lale et al. [2020]; Chen and Hazan
[2020]. Further, despite the challenge caused by strong stochastic
dependencies, the aforementioned bound achieves a similar guarantee as the
norm bound in Hu et al. [2022] for noiseless systems. In addition, as an
improvement to Hu et al. [2022], we do not place any requirement on dimensions
of system dynamics matrices and maintain the same complexity for under-
actuated system dynamics.

Related Work. Our work is mostly related to learn-to-control with known
stabilizing controllers and learn-to-stabilize on a single trajectory. In
addition, we will also briefly cover system identification.

Adaptive control. Adaptive control enjoys a long history of study Pasik-Duncan
[1996]; Petros A. Ioannou [2001]; Chen and Astolfi [2021]. Most classical
adaptive control methods focus on asymptotic stability and do not provide
finite sample analysis, and therefore do not study the exponential blow-up
issue explicitly. The more recent work on non-asymptotic sample complexity of
adaptive control has recongnized the exponential blow-up issue when a
stabilizing controller is not known a priori Chen and Hazan [2020]; Faradonbeh
[2017]; Lee et al. [2023]; Tsiamis and Pappas [2021]; Tu and Recht [2018].
Specifically, the most typical strategy to stabilize an unknown dynamic system
is to use past trajectory to estimate the system dynamics and then design the
controller Berberich et al. [2020]; De Persis and Tesi [2020]; Liu et al.
[2023]. Therefore, those works need to run in an open loop for at least $O(n)$
steps before stabilizing, resulting in an exponential blow-up in the order of
the state space dimension. Compared with those works, we can stabilize the
system with fewer samples by identifying and stabilizing only the unstable
subspace, thus avoiding the exponential blow-up.

Learn to control with known controller. There is abundant literature on
stabilizing LTI under stochastic noise Bouazza et al. [2021]; Jiang and Wang
[2002]; Kusii [2018]; Li et al. [2022]. One line of research uses the model-
free approach to learn the optimal controller Fazel et al. [2019]; Jansch-
Porto et al. [2020]; Li et al. [2022]; Wang et al. [2022]; Zhang et al.
[2020]. Those algorithms typically require a known stabilization controller as
an initialization point for policy search. Another line of research utilizes
the model-based approach, which learns the system dynamics before designing
the controller and also requires a known stabilizing controller Cohen et al.
[2019]; Mania et al. [2019]; Plevrakis and Hazan [2020]; Zheng et al. [2020].
Compared with those works, we focus on learn-to-stabilize, and the controller
we obtain can serve as the initialization to existing learning-to-control
works that require a known stabilizing controller.

Learning to stabilize on multiple trajectories. There are also works that do
not assume open-loop stability and learn the full system dynamics before
designing a stabilizing controller while requiring $\widetilde{\Theta}(n)$
complexity Dean S. Mania [2020]; Tu and Recht [2018]; Zheng and Li [2020],
which is larger than $\widetilde{O}(k)$ of our work. Recently, a model-free
approach via the policy gradient method offers a novel perspective with the
same complexity Perdomo et al. [2021]. Those works do not face the same
exponential blow-up issue since they allow multiple trajectories, i.e., the
state can be “reset” to $0$. Compared with their work, we focus on the more
challenging setting of stabilizing on a single trajectory.

Learning to stabilize on a single trajectory. Learning to stabilize for a
linear system in an infinite time horizon is a classic problem in control Lai
[1986]; Chen and Zhang [1989]; Lai and Ying [1991]. There have been algorithms
incurring regret of $2^{O(n)}O(\sqrt{T})$ which relies on assumptions of
observability and strictly stable transition matrices Abbasi-Yadkori and
Szepesvári [2011]; Ibrahimi et al. [2012]. Some studies have improved the
regret to $2^{\tilde{O}(n)}+\tilde{O}(\text{poly}(n)\sqrt{T})$ Chen and Hazan
[2020]; Lale et al. [2020]. Recently, Hu et al. [2022] proposed an algorithm
that requires $\tilde{O}(k)$ samples but has assumptions on the dimension of
$B$ and does not incorporate noise in the system dynamics. In this work, we
propose an algorithm that has the same state norm bound as Hu et al. [2022] in
a noisy and potentially under-actuated LTI system.

System identification. Our work is related to system identification, which
focuses on determining system parameters Oymak and Ozay [2018]; Sarkar and
Rakhlin [2018]; Simchowitz et al. [2018]; Xing et al. [2022]. Our work is
related in that our approach also partially determines the system parameters
before constructing the stabilizing controller. Compared to those works, we
not just conduct the identification but also close the loop by stabilizing the
system.

##  2 Problem Formulation

Notations. In this paper, we use the $L^{2}$-norm as the default norm
$\left\lVert\cdot\right\rVert$. We use $M^{*}$ to represent the conjugate
transpose of $M$, $e_{i}$ to denote the unit vector with $1$ at the $i$-th
entry and $0$ everywhere else, and $\rho(\cdot)$ to denote the spectral radius
of a matrix. We provide an indexing of notations at Appendix H. We consider an
LTI system $x_{t+1}=Ax_{t}+Bu_{t}+\eta_{t}$ where
$x_{t},\eta_{t}\in\mathbb{R}^{n}$ and $u_{t}\in\mathbb{R}^{m}$ are the state,
noise, and control input at time step $t$, respectively. The system dynamics
determined by $A$ and $B$ are _unknown_ to the learner. We further assume
$\mathbb{E}[\eta_{t}]=0$, and there exists constant $C\in\mathbb{R}^{+}$ such
that $\left\lVert\eta_{t}\right\rVert<C$ for all $t\in\mathbb{N}$.444 The
assumption on boundedness of noise can be loosened to sub-Gaussian random
variables at the cost of a slightly more complicated proof. Indeed, in the
simulation in Section 6, we show our algorithm stabilizes an LTI system with
additive Gaussian noise.

The goal of the learning is to stabilize the system with a learned controller,
defined as follows:

######  Definition 2.1 (Stabilizing controller).

Control rule $(u_{t})$ is called a stabilizing controller if and only if the
closed-loop system $x_{t+1}=Ax_{t}+Bu_{t}+\eta_{t}$ is ultimately bounded;
i.e. when $\|\eta_{t}\|\leq C$ for all $t$,
$\lim\sup_{t\rightarrow\infty}\left\lVert x_{t}\right\rVert<C_{n}$ is
guaranteed in the closed-loop system for some $C_{n}\in\mathbb{R}^{+}$.

The learner is allowed to learn the system by interacting with it on a single
trajectory. More specifically, the learner can observe $x_{t}$ and freely
determine $u_{t}$. In this paper, we make the standard assumption that $(A,B)$
is controllable. We also assume $x_{0}=0$ for simplicity of proof. Our proof
can be easily generalized to nonzero initial conditions.

Exponential blow-up. Although there are many existing works in the learn-to-
stabilize problem, including classical adaptive control Petros A. Ioannou
[2001] or more recent learning-based control papers Abbasi-Yadkori and
Szepesvári [2011]; Chen and Hazan [2020]; Ibrahimi et al. [2012]; Lale et al.
[2020], it is widely recognized that any generic learn-to-stabilize algorithm
inevitably causes exponential blow-up in the state norm as shown by the lower
bound in Chen and Hazan [2020] and Tsiamis and Pappas [2021]. This is because
$\Theta(n)$ samples are mandatory to sufficiently explore the $n$-dimensional
state space and estimate the system dynamics before designing a stabilizing
controller is possible. In contrast to these existing approaches that estimate
the full system, our approach breaks the lower-bound by isolating the smaller
unstable subspace from the stable subspace, estimating the system dynamics in
the unstable subspace under stochastic coupling, and showing that by
stabilizing the ”smaller” subspace, we can stabilize the entire state space.
As such, our approach breaks the exponential blow-up lower-bound in the regime
when the unstable subspace is has smaller dimension than $n$.

##  3 Preliminaries

Our approach uses the decomposition of the state space into stable and
unstable subspace (introduced in Hu et al. [2022]), and we only conduct system
identification and stabilization for the unstable subspace. In this section,
we provide a review of these concepts.

###  3.1 Decomposition of the State Space

Consider the open-loop system $x_{t+1}=Ax_{t}$, where $A$ is diagonalizable.
Let $\lambda_{1},\cdots,\lambda_{n}$ denote the eigenvalues of $A$ such that
555In practice, if $A$ does have the same eigenvalues, a slight perturbation
will make $A$ have distinct eigenvalues, to which our method will apply.
Further, a light perturbation will only introduce a $\log$ factor, as our
dependence on the eigenvalue-related “gap” constant is only logarithmic, as
shown in Theorem 4.2.

$|\lambda_{1}|>|\lambda_{2}|>\cdots>|\lambda_{k}|>1>|\lambda_{k+1}|>\cdots>|\lambda_{n}|.$

We define the unstable subspace $E_{u}$ as the invariant subspace
corresponding to the unstable eigenvalues $\lambda_{1},\ldots,\lambda_{k}$ and
the stable subspace $E_{s}$ as the invariant subspace corresponding to the
stable eigenvalues $\lambda_{k+1},\ldots,\lambda_{n}$.

The $E_{u}\oplus E_{u}^{\perp}$-decomposition. Let
$P_{1}\in\mathbb{R}^{n\times k}$ and $P_{2}\in\mathbb{R}^{n\times(n-k)}$
denote the orthonormal bases of the unstable subspace $E_{u}$ and its
orthogonal complement $E_{u}^{\perp}$, respectively, namely,

$E_{u}=\text{col}(P_{1}),\quad E_{u}^{\perp}=\text{col}(P_{2}).$

Let $P=[P_{1},P_{2}]$, which is also orthonormal and thus
$P^{-1}=P^{*}=[P_{1}^{*},P_{2}^{*}]^{*}$. Let $\Pi_{1}:=P_{1}P_{1}^{*}$ and
$\Pi_{2}:=P_{2}P_{2}^{*}$ be the orthogonal projectors onto $E_{u}$ and
$E_{u}^{\perp}$, respectively. With the above decomposition, we can transform
the matrix $A$ into the two subspaces. Since $E_{u}$ is an invariant subspace
with regard to $A$, there exists $M_{1}\in\mathbb{R}^{k\times k}$,
$\Delta\in\mathbb{R}^{k\times(n-k)}$, and
$M_{2}\in\mathbb{R}^{(n-k)\times(n-k)}$, such that

$AP=P\begin{bmatrix}M_{1}&\Delta\\\ &M_{2}\end{bmatrix}\Leftrightarrow
M:=\begin{bmatrix}M_{1}&\Delta\\\ &M_{2}\end{bmatrix}=P^{-1}AP.$

In the above decomposition, the top-left block $M_{1}\in\mathbb{R}^{k\times
k}$ acts on the unstable subspace, while $M_{2}$ acts on the stable subspace.
Consequently, $M_{1}$ inherits all the unstable eigenvalues of $A$, and
$M_{2}$ inherits all the stable eigenvalues.

Finally, we examine the system dynamics after the above transformation. Let
$y=[y_{1}^{*},y_{2}^{*}]^{*}$ represent $x$ in the basis formed by the column
vectors of $P$ after coordinate transformation (i.e. $x=Py$). The system
dynamics after the transformation can be written as

$\begin{bmatrix}y_{1,t+1}\\\
y_{2,t+1}\end{bmatrix}=P^{-1}AP\begin{bmatrix}y_{1,t}\\\
y_{2,t}\end{bmatrix}+P^{-1}Bu_{t}+\begin{bmatrix}P_{1}^{*}\\\
P_{2}^{*}\end{bmatrix}\eta_{t}=\begin{bmatrix}M_{1}&\Delta\\\
&M_{2}\end{bmatrix}\begin{bmatrix}y_{1,t}\\\
y_{2,t}\end{bmatrix}+\begin{bmatrix}P_{1}^{*}B\\\
P_{2}^{*}B\end{bmatrix}u_{t}+\begin{bmatrix}P_{1}^{*}\\\
P_{2}^{*}\end{bmatrix}\eta_{t}.$ (1)

The $E_{u}\oplus E_{s}$-decomposition As $M$ is not block diagonal, signified
by the top-right $\Delta$ block, which represents how much a state shifts from
$E_{u}^{\perp}$ to $E_{u}$ in one step, $E_{u}^{\perp}$ is in general not an
invariant subspace with respect to $A$ in the $E_{u}\oplus
E_{u}^{\perp}$-decomposition. For convenience of analysis, we introduce
another decomposition in the form of $E_{u}\oplus E_{s}$, where both $E_{u}$
and $E_{s}$ are invariant with respect to $A$. We also represent
$E_{u}=\text{col}(Q_{1})$ and $E_{s}=\text{col}(Q_{2})$ by their orthonormal
bases, and define $Q:=[Q_{1}\quad Q_{2}]$. Since $E_{u}$ and $E_{s}$ are
generally not orthogonal, we define $R:=Q^{-1}=[R_{1}^{*},R_{2}^{*}]^{*}$. The
construction detail is further explained in Appendix A.1 of Hu et al. [2022].

###  3.2 $\tau$-hop Control

A $\tau$-hop controller only inputs non-zero control $u_{t}$ for once every
$\tau$ steps, i.e. when $t=s\tau$, $s\in\mathbb{N}$. We inherit the $\tau$-hop
mechanism introduced in Hu et al. [2022] but change the stopping time
mechanism. Let $\tilde{x}_{s}:=x_{s\tau}$ and $\tilde{u}_{s}:=u_{s\tau}$
denote state and control action $\tau$ time steps apart. We can then write the
dynamics of the $\tau$-hop control system as:

$\tilde{x}_{s+1}=A^{\tau}\tilde{x}_{s}+A^{\tau-1}B\tilde{u}_{s}+\sum_{i=0}^{\tau-1}A^{i}\eta_{s\tau+i}.$
(2)

Let $\tilde{y}_{s}$ denote the state under $E_{u}\oplus
E_{u}^{\perp}$-decomposition, i.e. $\tilde{y}_{s}=P^{*}\tilde{x}_{s}$. The
state evolution becomes

$\begin{split}\begin{bmatrix}\tilde{y}_{1,s+1}\\\
\tilde{y}_{2,s+1}\end{bmatrix}=&P^{-1}A^{\tau}P\begin{bmatrix}\tilde{y}_{1,s}\\\
\tilde{y}_{2,s}\end{bmatrix}+P^{-1}A^{\tau-1}B\tilde{u}_{s}+\sum_{i=0}^{\tau-1}P^{-1}A^{i}\eta_{s\tau+i}\\\
=&M^{\tau}\begin{bmatrix}\tilde{y}_{1,s}\\\
\tilde{y}_{2,s}\end{bmatrix}+\begin{bmatrix}P_{1}^{*}A^{\tau-1}B\\\
P_{2}^{*}A^{\tau-1}B\end{bmatrix}\tilde{u}_{s}+\sum_{i=0}^{\tau-1}\begin{bmatrix}P_{1}^{*}A^{i}\\\
P_{2}^{*}A^{i}\end{bmatrix}\eta_{s\tau+i}.\end{split}$ (3)

We shall denote $B_{\tau}:=P_{1}^{*}A^{\tau-1}B$ for simplicity, and

$M^{\tau}=\left(\begin{bmatrix}M_{1}&\\\
&M_{2}\end{bmatrix}+\begin{bmatrix}0&\Delta\\\
&0\end{bmatrix}\right)^{\tau}=\begin{bmatrix}M_{1}^{\tau}&\sum_{i=1}^{\tau-1}M_{1}^{i}\Delta
M_{2}^{\tau-1-i}\\\
&M_{2}^{\tau}\end{bmatrix}:=\begin{bmatrix}M_{1}^{\tau}&\Delta_{\tau}\\\
&M_{2}^{\tau}\end{bmatrix}.$

Now we use a state feedback controller $\tilde{u}_{s}=K_{1}\tilde{y}_{1,s}$ in
the $\tau$-hop control system to stabilize the system by acting on the
unstable component $\tilde{y}_{1,s}$. The closed-loop dynamics can be written
as

$\tilde{y}_{s+1}=\begin{bmatrix}M_{1}^{\tau}+P_{1}^{*}A^{\tau-1}BK_{1}&\Delta_{\tau}\\\
P_{2}^{*}A^{\tau-1}BK_{1}&M_{2}^{\tau}\end{bmatrix}\tilde{y}_{s}+\sum_{i=0}^{\tau-1}P^{-1}A^{i}P\eta_{s\tau+i}.$
(4)

##  4 Main Results

###  4.1 Algorithm

In this section, we propose Learning to Stabilize from Zero with Noise
(LTS0-N). The algorithm is divided into 4 stages: (i) learn an orthonormal
basis $P_{1}$ of the unstable subspace $E_{u}$ (Stage 1); (ii) learn $M_{1}$,
the restriction of $A$ onto the subspace $E_{u}$ (Stage 2); (iii) learn
$B_{\tau}=P_{1}^{*}A^{\tau-1}B$ (Stage 3); and (iv) design a controller that
seeks to stabilize the “unstable” $E_{u}$ subspace (Stage 4). This is formally
described in Algorithm 1. We provide detailed descriptions of the four stages
in LTS0-N.

Algorithm 1 LTS0-N: learning a $\tau$-hop stablilzing controller

1: Stage 1: learning the unstable subspace of $A$.

2: Run the system in open loop for $T$ steps and let
$D\leftarrow[x_{1},\cdots,x_{T}].$

3: Compute the singular value decomposition of $D=U\Sigma V^{*}$. Let
$\hat{P}_{1}\leftarrow U^{(k)}$ be the top $k$ columns of $U$.

4: Calculate $\hat{\Pi}_{1}\leftarrow\hat{P}_{1}\hat{P}_{1}^{*}$.

5: Stage 2: approximate $M_{1}$ on the unstable subspace.

6: Solve the least square problem
$\hat{M}_{1}\leftarrow\arg\min_{M_{1}\in\mathbb{R}^{k\times
k}}\mathcal{L}(M_{1}):=\sum_{t=0}^{T}\left\lVert\hat{P}_{1}^{*}x_{t+1}-M_{1}\hat{P}_{1}^{*}x_{t}\right\rVert^{2}$.

7: Stage 3: restore $B_{\tau}$ for $\tau$-hop control.

8: for $i=1,\cdots,m$ do

9: Let the system run in open loops for $\omega_{i}$ steps until
$\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}<(1-\epsilon)\gamma$ and $\frac{C}{\left\lVert
x_{t_{i}}\right\rVert}<\delta$.

10: Run for $\tau$ more steps with initial $u_{t_{i}}=\alpha\left\lVert
x_{t_{i}}\right\rVert e_{i}$, where
$t_{i}=T+\sum_{j=1}^{i}\omega_{j}+(i-1)\tau$.

11: end for

12: Let $\hat{B}_{\tau}\leftarrow[\hat{b}_{1},\cdots,\hat{b}_{m}]$, where the
$i$-th column $\hat{b}_{i}\leftarrow\frac{1}{\alpha\left\lVert
x_{t_{i}}\right\rVert}\left(\hat{P}_{1}^{*}x_{t_{i}+\tau}-\hat{M}_{1}^{\tau}\hat{P}_{1}^{*}x_{t_{i}}\right).$

13: Stage 4: construct a $\tau$-hop stabilizing controller $K$.

14: Construct the $\tau$-hop stabilizing controller $\hat{K}_{1}$ from
$\hat{M}_{1}^{\tau}$ and $\hat{B}_{\tau}$.

Stage 1: Learning the unstable subspace of $A$. We let the system run in open-
loop (with control input $u_{t}\equiv 0$) for $T$ time steps. Per the
stable/unstable decomposition, the ratio between the norms of the state
components in the unstable and stable subspace increases exponentially, and,
very quickly, the state will lie “almost” in $E_{u}$. Consequently, the
subspace spanned by the $T$ states, i.e. the column space of
$D:=[x_{1},\cdots,x_{T}]$, is very close to $E_{u}$. Thus, we use the top $k$
left singular vectors of $D$ (the top $k$ eigenvectors of $DD^{*}$), denoted
as $U^{(k)}$, as an estimate of the basis of the unstable subspace
$\hat{P}_{1}$. In other words, we set $\hat{P}_{1}=U^{(k)}$ and use it to
construct the orthogonal projector onto $E_{u}$, namely
$\hat{\Pi}_{1}=U^{(k)}(U^{(k)})^{*}$, as an estimation of the projector
$\Pi_{1}=P_{1}P_{1}^{*}$ onto $E_{u}$.

Stage 2: Learn $M_{1}$ on the unstable subspace. Recall that $M_{1}$ is the
system dynamics matrix for the subspace $E_{u}$ under $E_{u}\oplus
E_{u}^{\perp}$-decomposition. Therefore, to estimate $M_{1}$, we first compute
the projection of states $x_{1:T}$ on subspace $E_{u}$, i.e.
$\hat{y}_{1,t}=\hat{P}_{1}^{*}x_{1,t}$ for $t=1,\cdots,T$. Then we use least
squares to estimate $M_{1}$, i.e. find $\hat{M}_{1}$ that minimizes the square
loss:

$\begin{split}\mathcal{L}(\hat{M}_{1})&:=\sum_{t=0}^{T}\left\lVert\hat{y}_{1,t+1}-\hat{M}_{1}\hat{y}_{1,t}\right\rVert^{2}.\end{split}$
(5)

Stage 3: Learn $B_{\tau}$ for $\tau$-hop control. In this stage, we estimate
$B_{\tau}$, which quantifies the effect of control input on states in the
unstable subspace $E_{u}$ (as discussed in Section 3.2). Note that (3) shows

$y_{1,t_{i}+\tau}=M^{\tau}y_{1,t_{i}}+\Delta_{\tau}y_{2,t_{i}}+B_{\tau}u_{t_{i}}+\sum_{j=1}^{\tau-1}M^{\tau-j}\eta_{1,t_{i}+j}+\Delta_{\tau-j}\eta_{2,t_{i}+j}.$
(6)

We estimate the columns of $B_{\tau}$ one by one. Specifically, we use a
scaled unit vector $e_{i}$ as control input at time $t_{i}$, run the system in
open loop for $\tau$ steps, and use (6) but simply ignore the $\Delta_{\tau}$
related terms to estimate $b_{i}$, the $i$-th column of $B_{\tau}$, as

$\hat{b}_{i}=\frac{1}{\left\lVert
u_{t_{i}}\right\rVert}\left(\hat{P}_{1}^{*}x_{t_{i}+\tau}-\hat{M}_{1}^{\tau}\hat{P}_{1}^{*}x_{t_{i}}\right),$
(7)

where $u_{t_{i}}$ is parallel to $e_{i}$ with magnitude $\alpha\left\lVert
x_{t_{i}}\right\rVert$ for normalization. Here, $\alpha$ is an adjustable
constant to guarantee that the $E_{s}$-component does not increase too much to
blur our estimation after injecting $u_{t_{i}}$. Since we ignored the
$\Delta_{\tau}$ related terms in the estimation of $b_{i}$, to ensure that
those terms do not cause much error in our estimation of $B_{\tau}$, we let
the system run in open loop for $\omega_{i}$ time steps before the estimation
of $b_{i}$ starts. Here, $\omega_{i}$ is a stopping time (cf. Line 9 in
Algorithm 1). The purpose of the stepping time is to reduce the estimation
error caused by the $\Delta_{\tau}$. For more details, see Proposition E.5 in
the proof.

Stage 4: Construct a $\tau$-hop stabilizing controller $K$. With the estimated
$M_{1}^{\tau}$ and $B_{\tau}$ from the last stage, denoted as
$\hat{M}_{1}^{\tau}$ and $\hat{B}_{\tau}$, the learner can choose any
stabilization algorithm to find $\hat{K}_{1}$ by stabilizing the linear system

$\hat{\tilde{y}}_{i+1}=\hat{M}_{1}^{\tau}\hat{\tilde{y}}_{i}+\hat{B}_{\tau}\tilde{u}_{i},\qquad\tilde{u}_{i}=\hat{K}_{1}\hat{\tilde{y}}_{i},$

where the tilde in $\hat{\tilde{y}}$ emphasizes the use of $\tau$-hop control
and the hat emphasizes the use of estimated projector $\hat{P}_{1}$, which
introduces an extra estimation error to the final closed-loop dynamics. As
$\hat{K}_{1}$ is chosen by the learner, we denote $\mathcal{K}$ to be a
constant such that $\left\lVert\hat{K}_{1}\right\rVert<\mathcal{K}$.
Furthermore, by Proposition F.1, there exists a positive definite matrix
$\bar{U}$ such that
$\left\lVert\hat{M}_{1}^{\tau}-\hat{B}_{\tau}\hat{K}_{1}\right\rVert_{\bar{U}}:=\mathcal{U}<1$,
where $\left\lVert\cdot\right\rVert_{\bar{U}}$ denotes the weighted norm
induced by $\bar{U}$. These user-defined constants are used in the proof of
Theorem 4.2.

To sum up, Algorithm 1 terminates in $T+\sum_{i=1}^{m}(1+\omega_{i}+\tau)$
time steps, where $\omega_{i}$ is the stopping time for the system to satisfy
$\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}<(1-\epsilon)\gamma$ and $\frac{C}{\left\lVert
x_{t_{i}}\right\rVert}<\delta$.

######  Remark 4.1.

Our algorithm is different from the algorithm proposed in Hu et al. [2022] in
three aspects. Firstly, to account for the noise, we do not directly use the
span of consecutive $k$ vectors as the estimator for the unstable subspace.
Instead, to identify the unstable subspace under noise, we utilize the
singular value decomposition to identify the dominating state space in the
trajectory and use that space as an estimation of $P_{1}$. Such an estimator
requires a much more delicate analysis framework to bound the error based on
Davis-Kahan Theorem, which we elaborate in Appendix A. Secondly, the above
algorithm generalizes the problem to an under-actuated setting, where the
control matrix $B\in\mathbb{R}^{n\times m}$ with $m\neq k$. To achieve this,
unlike Hu et al. [2022] we no longer try to cancel out the unstable matrix
$M_{1}$, but rather allow the learner to choose the stabilization controller.
We show in Section 6 that our algorithm outperforms Hu et al. [2022] in an
under-actuated setting in simulation. Thirdly, we use a stopping time to
monitor the state norm in estimating $B_{\tau}$, so that our algorithm always
terminates at the earliest possible time.

###  4.2 Stability Guarantee

In this section, we formally state the assumptions and show our approach finds
a stabilizing controller without suffering from exponential blow-up in $n$.
Our first assumption is regarding the spectral properties of $A$, which
requires distinct eigenvalues with specified eigengap.

######  Assumption 1 (Spectral Property).

$A$ is diagonalizable with distinct eigenvalues
$\lambda_{1},\ldots,\lambda_{n}$ satisfying
$|\lambda_{1}|>|\lambda_{2}|>\dots>|\lambda_{k}|>1>|\lambda_{k+1}|>\dots>|\lambda_{n}|$.

We assume the learner knows the value of $k$. However, we point out that our
algorithm works as long as the learner picks a value $\hat{k}$ at least as
large as $k$. In order to provide guarantee to the estimation of the open-loop
unstable system dynamics, we also need an assumption on the distribution of
noise $\eta$.

######  Assumption 2 (pdf of $\eta$).

Let $M_{1}:=\bar{P}^{-1}J\bar{P}$ denote the Jordan normal form of $M_{1}$,
and $\bar{P}:=[\bar{P}_{1},\bar{P}_{2},\cdots,\bar{P}_{k}]^{*}$. There exists
$C_{z}\in\mathbb{R}$, such that the supremum of the probability distribution
function (pdf) of
$\left|\bar{P}_{i}^{*}\sum_{j=1}^{t}M_{1}^{-j}P_{1}^{*}\eta_{j}\right|$ is
upper bounded almost everywhere,.i.e.
$\operatorname*{ess\,sup}\text{pdf}\left(\left|\bar{P}_{i}^{*}\sum_{j=1}^{t}M_{1}^{-j}P_{1}^{*}\eta_{j}\right|\right)<C_{z}$,
for all $i\in\\{1,\dots,k\\}$ and $t\in\mathbb{N}$.

2 holds for most common noise distributions, including bounded uniform
distribution and Gaussian distributions(Lemma C.3). We further discuss this
assumption in Appendix B and C.

With the above assumptions, our main result is as follows.

######  Theorem 4.2.

Given a noisy LTI system $x_{t+1}=Ax_{t}+Bu_{t}+\eta_{t}$ subject to 1, 2, and
additionally, $|\lambda_{1}||\lambda_{k+1}|<1$. Further, denote
$\text{gap}:=\left|\prod_{\begin{subarray}{c}m_{1}\neq m_{2},\\\
m_{1},m_{2}\in\\{1,\dots,k\\}\end{subarray}}(\lambda_{m_{1}}^{-1}-\lambda_{m_{2}}^{-1})\right|.$
By running Algorithm 1 with parameters
$\gamma=O(1),\quad\delta=O(m^{-\frac{1}{2}}),\quad\tau=O(1),\quad\alpha=O(1)$,
and $T=O\left(k\log k+\log(n-k)+\log m-\log\text{gap}\right)$, the controller
returned by Algorithm 1 is a stabilizing controller. Further, Algorithm 1
guarantees that

$\left\lVert x_{t}\right\rVert<\exp\left(O\left(k\log
k+\log(n-k)+m-\log\text{gap}\right)\right),$

before termination. Here the big-O notation only shows dependence on $k,m$ and
$n$, while omitting dependence on
$C,C_{z},|\lambda_{1}|,|\lambda_{k}|,|\lambda_{k+1}|,\theta$, $\mathcal{K}$,
and $\mathcal{U}$.

The precise bound given for each constant can be found at (65),(66),(67), and
(68) in the Appendix, and the bound for $T$ is given in Theorem 5.1. Despite
the more challenging setting with noises and potentially underactuated
systems, Theorem 4.2 achieves a similar guarantee as Hu et al. [2022].
Specifically, in the regime of $m=O(k)$,666We note that the regime of $m=O(k)$
is the most interesting regime as it covers the under-actuated setting, which
is known to be more challenging.  the above Theorem shows that LTS0-N finds a
stabilizing controller with an upper bound on state norm at
$2^{\tilde{O}(k)}$, which is better than the state-of-the-art $2^{\Theta(n)}$
complexity in the noisy settings. Therefore, our approach leverages instance
specific properties (the dimension of unstable subspace $k$) to _break the
exponential lower bound Chen and Hazan [2020] and learns to stabilize without
the exponential blow-up in $n$ in noisy and under-actuated settings_.

We also point out that constant gap is also $k$-dependent. In the worst case,
the gap has an order of $2^{O(k^{2})}$. This is still independent of $n$. We
note that Hu et al. [2022] did not show explicit dependence on this constant.
We leave it as future work whether this additional constant is essential or is
an artifact of the proof. Moreover, our assumption that
$|\lambda_{1}||\lambda_{k+1}|<1$ is weaker than the assumption in Hu et al.
[2022], which requires $|\lambda_{1}|^{2}|\lambda_{k+1}|<|\lambda_{k}|$.

We demonstrate the effectiveness of our algorithm in simulation in Section 6,
showing our algorithm’s state norm does not blow-up with $n$ and also
outperforms other benchmarks.

##  5 Proof Outline

In this section, we will give a high-level overview of the key proof ideas for
the main theorem. The full proof details can be found in Appendix F.

Proof Structure. The proof is largely divided into four steps. In Step 1, we
examine how accurately the learner estimates the unstable subspace $E_{u}$ in
Stage 1. We will show that $\Pi_{1},P_{1}$ can be estimated up to an error of
$\epsilon$, $\delta$ respectively within $T=O\left(k\log
k+\log(n-k)-\log\epsilon-\log\text{gap}\right)$ steps, where
$\delta:=\sqrt{2k}\epsilon$. In Step 2, we examine how accurately the learner
estimates $M_{1}$. We show that $M_{1}$ can be estimated up to an error of
$3\left\lVert A\right\rVert\delta$. In Step 3, we examine the estimation error
of $B_{\tau}$ in Stage 3. Lastly, in Step 4, we eventually show that the
$\tau$-hop controller output by Algorithm 1 makes the system stable.

Overview of Step 1. To upper bound the estimation errors in Stage 1, we use
SVD to isolate the unstable subspace and use the Davis-Kahan Theorem to
decouple the system dynamics from the noise perturbation. The bounds on
$\left\lVert\Pi_{1}-\hat{\Pi}_{1}\right\rVert$ is shown in Theorem 5.1.

######  Theorem 5.1.

For a linear dynamic system with noise $x_{t+1}=Ax_{t}+\eta_{t}$ satisfying 1
and 2, let $E_{u}$ be the unstable subspace of $A$, $k=\dim E_{u}$ be the
instability index of the system and $\Pi_{1}$ be the orthogonal projector onto
subspace $E_{u}$. Then for any $\epsilon>0$, by running Stage 1 of Algorithm 1
with an arbitrary initial state for $T$ time steps, where

$T=O\left(k\log k+\log(n-k)-\log\epsilon-\log\text{gap}\right),$

we get an estimation $\hat{\Pi}_{1}=U^{(k)}(U^{(k)})^{*}$ with error
$\left\lVert\hat{\Pi}_{1}-\Pi_{1}\right\rVert<\epsilon$. Here, the big-O
notation only shows dependence on $k,n$ and $\epsilon$, while omitting
dependence on $C,C_{z},|\lambda_{1}|,|\lambda_{k}|,|\lambda_{k+1}|$, and
$\theta$.

The proof of Theorem 5.1 is deferred to Appendix A.

Overview of Step 2. To upper bound the error in Stage 2, We upper bound the
error in
$\arg\min_{M_{1}}\sum_{t=0}^{T}\left\lVert(U^{(k)})^{*}x_{t+1}-M_{1}(U^{(k)})^{*}x_{t}\right\rVert^{2}$
and obtain the following proposition.

######  Proposition 5.2.

Under the premise of Theorem 4.2, we have

$\left\lVert\hat{M}_{1}^{\tau}-M_{1}^{\tau}\right\rVert\leq 3\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta,$

where $\zeta_{\epsilon_{1}}(A)$ is constant for Gelfand’s formula defined in
Lemma G.2, and we recall $\delta$ is the estimation error for $P_{1}$.

The proof in this step and the related lemmas and propositions are deferred to
Appendix D.

Overview of Step 3. To bound the error in Stage 3, we upper bound the error in
each column of $B_{\tau}$. In particular, we show that (7) generates an
estimation of $B_{\tau}$ with an error in the same order as $\delta$. The
detail is left to Proposition E.5 in Appendix E.

Overview of Step 4. To analyze the stability of the closed-loop system, we
shall first write out the closed-loop dynamics under the $\tau$-hop
controller. Recall in Section 3.2, we have defined
$\tilde{u}_{s},\tilde{x}_{s},\tilde{y}_{s}$ to be the control input, state in
$x$-coordinates, and state in $y$-coordinates in the $\tau$-hop control
system, respectively. Using those notations, the learned controller is
obtained from the estimation of $M_{1}^{\tau}$ and $B_{\tau}$ by the learner
with any stabilization algorithm (e.g. LQR, pole-placement).

Therefore, the closed-loop, the closed-loop $\tau$-hop dynamics should be

$\tilde{y}_{s+1}=\hat{L}\begin{bmatrix}\tilde{y}_{1,s}\\\
\tilde{y}_{2,s}\end{bmatrix}+\sum_{i=0}^{\tau-1}P^{-1}A^{i}P\eta_{s\tau+i}:=\hat{L}\tilde{y}_{s}+\sum_{i=0}^{\tau-1}\begin{bmatrix}P_{1}^{*}A^{i}\\\
P_{2}^{*}A^{i}\end{bmatrix}\eta_{s\tau+i},$ (8)

where

$\hat{L}:=\begin{bmatrix}M_{1}^{\tau}+P_{1}^{*}A^{\tau-1}B\hat{K}_{1}\hat{P}_{1}^{*}P_{1}&\Delta_{\tau}+P_{1}^{*}A^{\tau-1}B\hat{K}_{1}\hat{P}_{1}^{*}P_{2}\\\
P_{2}^{*}A^{\tau-1}B\hat{K}_{1}\hat{P}_{1}^{*}P_{1}&M_{2}^{\tau}+P_{2}^{*}A^{\tau-1}B\hat{K}_{1}\hat{P}_{1}^{*}P_{2}\end{bmatrix}:=\begin{bmatrix}\hat{L}_{1,1}&\hat{L}_{1,2}\\\
\hat{L}_{2,1}&\hat{L}_{2,2}\end{bmatrix}.$ (9)

We will show the above system to be ultimately bounded (i.e.
$\rho(\hat{L}_{\tau})<1$). Note that $\hat{L}_{\tau}$ is given by a 2-by-2
block form, and we can utilize the following lemma for the spectral analysis
of block matrices.

######  Lemma 5.3.

For block matrices $A=\begin{bmatrix}A_{1}&0\\\ 0&A_{2}\end{bmatrix}$,
$E=\begin{bmatrix}0&E_{12}\\\ E_{21}&0\end{bmatrix}$, the spectral radii of
$A$ and $A+E$ differ by at most $|\rho(A+E)-\rho(A)|\leq\chi(A+E)\left\lVert
E_{12}\right\rVert\left\lVert E_{21}\right\rVert$, where $\chi(A+E)$ is a
constant.

The proof of the lemma can be found in existing literature such as Nakatsukasa
[2017]. Therefore, we need to ensure the stability of the diagonal blocks of
$\hat{L}$ and upper-bound the norms of the off-diagonal blocks via estimation
of factors appearing in these blocks. Complete proofs can be found in
Appendices F.

##  6 Numerical simulation

Lastly, we include numerical simulations to demonstrate the performance of our
algorithm. We consider an LTI system with additive noise

$x_{t+1}=Ax_{t}+Bu_{t}+\eta_{t},\quad\text{where
}\eta_{t}\sim\mathcal{N}(0,\sigma^{2}I),$

where $\sigma^{2}$ is the variance of the additive Gaussian noise at each
step. Note we use unbounded Gaussian noise here, and noise with bounded
uniform distribution would generate similar results. The dynamics matrix $B$
is generated randomly. Matrix $A$ is generated by $A=V\Lambda V^{-1}$, where
$V$ is a randomly generated matrix, and $\Lambda$ is a diagonal matrix of
eigenvalues generated uniformly at random from the interval that satisfies
$|\lambda_{1}||\lambda_{k+1}|<1$.

In our first experiment, we compare the performance of LTS0-N in different
settings (with different $n,\sigma$). In each setting, we conduct 200 trials
and record the minimal time steps it takes to stabilize the system, and the
results are in Figure 1(a). In our second experiment, we compare our proposed
algorithm to three different algorithms: a classical self-tunning regulator in
Pasik-Duncan [1996], black-box control proposed in Chen and Hazan [2020], and
the LTS0 algorithm proposed in Hu et al. [2022] and the results are in Figure
1(b).

(a) Running steps of LTS0-N

(b) State norm along one trajectory

Figure 1: In (a), the line shows the average steps it takes to stabilize the
system, and the shadow area shows the standard deviation. In (b), the
trajectory of our algorithm, the algorithm in Hu et al. [2022], the black-box
controller in Chen and Hazan [2020] and a self-turning regulator in Pasik-
Duncan [1996] are compared in a randomly generated LTI system with $n=128$,
$k=4$, $m=3$, and $\sigma=0.01$.

Performance difference under different $n$ and $\sigma$. Figure 1(a) shows the
relationship between the number of steps between running LTS0-N and the
dimension of states. It is evident that the increase in the number of steps is
at most linear in $\log(n)$, as proven in Theorem 4.2. As we used the same
randomly generated matrices for each $(n,\sigma)-$pair, all three curves in
Figure 1(a) have a similar trend at each node. This observation verifies that
the number of steps needed for stabilization also depends on the eigenvalue
distribution of the system dynamics matrices, as we showed in the proof.
Moreover, we see that an increase in noise slightly increases the number of
steps for stabilization, as shown in the proof of Theorem 5.1. As expected, an
increase in noise also increases the standard deviation of the number of steps
before stabilization.

Difference in performance in single trajectory Figure 1(b) shows a typical
trajectory of our LTS0-N algorithm. It is evident that our algorithm takes
significantly fewer steps than adaptive control algorithms (self-tuning
regulator and black-box control) and also fewer steps than the LTS0 algorithm
proposed Hu et al. [2022]. This is because the self-tuning regulator and the
black-box control algorithm cannot take stabilzing control actions before the
system runs for at least $n$ steps and learns the system dynamics. Moreover,
due to the stochastic coupling of the system, estimation of system dynamics
becomes much more difficult, and the adaptive control methods need a
relatively large state to overcome the disturbance of noise in system
identification. In comparison to LTS0, note that in this simulation, we chose
$m<k$ to demonstrate the advantage of our algorithm in an under-actuated
system. We see that our algorithm incurred less zig-zagging than LTS0, since
we can stabilize directly on the existing state space, and LTS0 has to
stabilize on a composite state space, the details of which can be seen at
Appendix C of Hu et al. [2022].

## References

  * Abbasi-Yadkori and Szepesvári [2011] Y. Abbasi-Yadkori and C. Szepesvári.  Regret bounds for the adaptive control of linear quadratic systems.  In S. M. Kakade and U. von Luxburg, editors, _Proceedings of the 24th Annual Conference on Learning Theory_ , volume 19 of _Proceedings of Machine Learning Research_ , pages 1–26, Budapest, Hungary, 09–11 Jun 2011. PMLR.
  * Beard et al. [1997] R. W. Beard, G. N. Saridis, and J. T. Wen.  Galerkin approximations of the generalized hamilton-jacobi-bellman equation.  _Automatica_ , 33(12):2159–2177, 1997.  ISSN 0005-1098.  doi: https://doi.org/10.1016/S0005-1098(97)00128-3.
  * Berberich et al. [2020] J. Berberich, J. Köhler, M. Muller, and F. Allgöwer.  Data-driven model predictive control with stability and robustness guarantees.  _IEEE Transactions on Automatic Control_ , PP:1–1, 06 2020.  doi: 10.1109/TAC.2020.3000182.
  * Bouazza et al. [2021] L. Bouazza, B. Mourllion, A. Makhlouf, and A. Birouche.  Controllability and observability of formal perturbed linear time invariant systems.  _International Journal of Dynamics and Control_ , 9, 12 2021.  doi: 10.1007/s40435-021-00786-4.
  * Bradtke et al. [1994] S. Bradtke, B. Ydstie, and A. Barto.  Adaptive linear quadratic control using policy iteration.  _Proceedings of the American Control Conference_ , 3, 09 1994.  doi: 10.1109/ACC.1994.735224.
  * Cao [2021] Y. Cao.  Davis-kahan theorem, 2021.  https://www.citedrive.com/overleaf.
  * Chatzigeorgiou [2013] I. Chatzigeorgiou.  Bounds on the lambert function and their application to the outage analysis of user cooperation.  _Communications Letters, IEEE_ , 17:1505–1508, 08 2013.  doi: 10.1109/LCOMM.2013.070113.130972.
  * Chen and Zhang [1989] H.-F. Chen and J.-F. Zhang.  Convergence rates in stochastic adaptive tracking.  _International Journal of Control_ , 49(6):1915–1935, 1989.  doi: 10.1080/00207178908559752.
  * Chen and Astolfi [2021] K. Chen and A. Astolfi.  Adaptive control for systems with time-varying parameters.  _IEEE Transactions on Automatic Control_ , 66(5):1986–2001, 2021.  doi: 10.1109/TAC.2020.3046141.
  * Chen and Hazan [2020] X. Chen and E. Hazan.  Black-box control for linear dynamical systems.  _CoRR_ , abs/2007.06650, 2020.
  * Cohen et al. [2019] A. Cohen, T. Koren, and Y. Mansour.  Learning linear-quadratic regulators efficiently with only $\sqrt{T}$ regret.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1300–1309. PMLR, 09–15 Jun 2019.
  * De Persis and Tesi [2020] C. De Persis and P. Tesi.  Formulas for data-driven control: Stabilization, optimality, and robustness.  _IEEE Transactions on Automatic Control_ , 65(3):909–924, 2020.  doi: 10.1109/TAC.2019.2959924.
  * Dean S. Mania [2020] N. e. a. Dean S. Mania, H. Matni.  On the sample complexity of the linear quadratic regulator.  _Foundations of Computational Mathematics_ , (20):633–679, 2020.  doi: https://doi.org/10.1007/s10208-019-09426-y.
  * Faradonbeh [2017] M. K. S. Faradonbeh.  _Non-Asymptotic Adaptive Control of Linear-Quadratic Systems_.  PhD thesis, University of Michigan, 2017.
  * Fazel et al. [2019] M. Fazel, R. Ge, S. M. Kakade, and M. Mesbahi.  Global convergence of policy gradient methods for the linear quadratic regulator, 2019.
  * Horn and Johnson [1985] R. A. Horn and C. R. Johnson.  _Matrix Analysis_.  Cambridge University Press, 1985.
  * Horn and Johnson [2012] R. A. Horn and C. R. Johnson.  _Matrix Analysis_.  Cambridge University Press, USA, 2nd edition, 2012.  ISBN 0521548233.
  * Hu et al. [2022] Y. Hu, A. Wierman, and G. Qu.  On the sample complexity of stabilizing lti systems on a single trajectory (extended abstract).  In _2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 1–2, 2022.  doi: 10.1109/Allerton49937.2022.9929403.
  * Ibrahimi et al. [2012] M. Ibrahimi, A. Javanmard, and B. V. Roy.  Efficient reinforcement learning for high dimensional linear quadratic systems.  In _Neural Information Processing Systems_ , 2012.
  * Jansch-Porto et al. [2020] J. P. Jansch-Porto, B. Hu, and G. E. Dullerud.  Policy learning of mdps with mixed continuous/discrete variables: A case study on model-free control of markovian jump systems.  _CoRR_ , abs/2006.03116, 2020.  URL https://arxiv.org/abs/2006.03116.
  * Jiang and Wang [2002] Z.-P. Jiang and Y. Wang.  A converse lyapunov theorem for discrete-time systems with disturbances.  _Systems & Control Letters_, 45(1):49–58, 2002.  ISSN 0167-6911.  doi: https://doi.org/10.1016/S0167-6911(01)00164-5.
  * Krauth et al. [2019] K. Krauth, S. Tu, and B. Recht.  Finite-time analysis of approximate policy iteration for the linear quadratic regulator.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Kusii [2018] S. Kusii.  Stabilization and attenuation of bounded perturbations in discrete control systems.  _Journal of Mathematical Sciences_ , 2018.  doi: https://doi.org/10.1007/s10958-018-3848-3.
  * Lai [1986] T. Lai.  Asymptotically efficient adaptive control in stochastic regression models.  _Advances in Applied Mathematics_ , 7(1):23–45, 1986.  ISSN 0196-8858.  doi: https://doi.org/10.1016/0196-8858(86)90004-7.
  * Lai and Ying [1991] T. L. Lai and Z. Ying.  Parallel recursive algorithms in asymptotically efficient 496 adaptive control of linear stochastic systems.  _SIAM Journal on Control and Optimization_ , 29(5):1091–1127, 1991.
  * Lale et al. [2020] S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar.  Explore more and improve regret in linear quadratic regulators.  _CoRR_ , abs/2007.12291, 2020.  URL https://arxiv.org/abs/2007.12291.
  * Lee et al. [2023] B. D. Lee, A. Rantzer, and N. Matni.  Nonasymptotic regret analysis of adaptive linear quadratic control with model misspecification, 2023.
  * Li et al. [2022] Y. Li, Y. Tang, R. Zhang, and N. Li.  Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach.  _IEEE Transactions on Automatic Control_ , 67(12):6429–6444, 2022.  doi: 10.1109/TAC.2021.3128592.
  * Liu et al. [2023] W. Liu, Y. Li, J. Sun, G. Wang, and J. Chen.  Robust control of unknown switched linear systems from noisy data.  _ArXiv_ , abs/2311.11300, 2023.
  * Mania et al. [2019] H. Mania, S. Tu, and B. Recht.  _Certainty equivalence is efficient for linear quadratic control_.  Curran Associates Inc., Red Hook, NY, USA, 2019.
  * Nakatsukasa [2017] Y. Nakatsukasa.  Off-diagonal perturbation, first-order approximation and quadratic residual bounds for matrix eigenvalue problems.  In T. Sakurai, S.-L. Zhang, T. Imamura, Y. Yamamoto, Y. Kuramashi, and T. Hoshi, editors, _Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing_ , pages 233–249, Cham, 2017. Springer International Publishing.  ISBN 978-3-319-62426-6.
  * Oymak and Ozay [2018] S. Oymak and N. Ozay.  Non-asymptotic identification of lti systems from a single trajectory.  _2019 American Control Conference (ACC)_ , pages 5655–5661, 2018.
  * Pasik-Duncan [1996] B. Pasik-Duncan.  Adaptive control [second edition, by karl j. astrom and bjorn wittenmark, addison wesley (1995)].  _IEEE Control Systems Magazine_ , 16(2):87–, 1996.
  * Perdomo et al. [2021] J. C. Perdomo, J. Umenberger, and M. Simchowitz.  Stabilizing dynamical systems via policy gradient methods.  _ArXiv_ , abs/2110.06418, 2021.
  * Petros A. Ioannou [2001] J. S. Petros A. Ioannou.  Robust adaptive control.  _Autom._ , 37(5):793–795, 2001.
  * Plevrakis and Hazan [2020] O. Plevrakis and E. Hazan.  Geometric exploration for online control.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.  ISBN 9781713829546.
  * Sarkar and Rakhlin [2018] T. Sarkar and A. Rakhlin.  Near optimal finite time identification of arbitrary linear dynamical systems.  In _International Conference on Machine Learning_ , 2018.
  * Simchowitz et al. [2018] M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht.  Learning without mixing: Towards a sharp analysis of linear system identification.  _Annual Conference Computational Learning Theory_ , 2018.
  * Tsiamis and Pappas [2021] A. Tsiamis and G. J. Pappas.  Linear systems can be hard to learn.  In _2021 60th IEEE Conference on Decision and Control (CDC)_ , pages 2903–2910, 2021.  doi: 10.1109/CDC45484.2021.9682778.
  * Tu and Recht [2018] S. Tu and B. Recht.  The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint.  In _Annual Conference Computational Learning Theory_ , 2018.
  * Tucci and Whiting [2011] G. H. Tucci and P. A. Whiting.  Asymptotic results on generalized vandermonde matrices and their extreme eigenvalues.  In _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 1816–1823, 2011.  doi: 10.1109/Allerton.2011.6120389.
  * Wang et al. [2022] W. Wang, X. Xie, and C. Feng.  Model-free finite-horizon optimal tracking control of discrete-time linear systems.  _Appl. Math. Comput._ , 433(C), nov 2022.  ISSN 0096-3003.  doi: 10.1016/j.amc.2022.127400.
  * Xing et al. [2022] Y. Xing, B. Gravell, X. He, K. H. Johansson, and T. H. Summers.  Identification of linear systems with multiplicative noise from multiple trajectory data.  _Automatica_ , 144:110486, 2022.  ISSN 0005-1098.  doi: https://doi.org/10.1016/j.automatica.2022.110486.
  * Zhang et al. [2020] K. Zhang, B. Hu, and T. Basar.  Policy optimization for $\mathcal{H}_{2}$ linear control with $\mathcal{H}_{\infty}$ robustness guarantee: Implicit regularization and global convergence.  In A. M. Bayen, A. Jadbabaie, G. Pappas, P. A. Parrilo, B. Recht, C. Tomlin, and M. Zeilinger, editors, _Proceedings of the 2nd Conference on Learning for Dynamics and Control_ , volume 120 of _Proceedings of Machine Learning Research_ , pages 179–190. PMLR, 10–11 Jun 2020.
  * Zheng and Li [2020] Y. Zheng and N. Li.  Non-asymptotic identification of linear dynamical systems using multiple trajectories.  _IEEE Control Systems Letters_ , PP:1–1, 12 2020.  doi: 10.1109/LCSYS.2020.3042924.
  * Zheng et al. [2020] Y. Zheng, L. Furieri, M. Kamgarpour, and N. Li.  Sample complexity of linear quadratic gaussian (lqg) control for output feedback systems.  _Conference on Learning for Dynamics & Control_, 2020.

##  Appendix A Proof of Theorem 5.1

One of the key innovations of this work is the SVD-based framework we use to
decouple the unstable subspace from the rest of the system. Therefore, we
prove Theorem 5.1 here. After the system runs for time $T$, we record the
state space in a $n\times T$ matrix $D$ whose $t$-th column is defined as:

$D(t)=x_{t}=Ax_{t-1}+\eta_{t}.$

We decompose $A$ based on $E_{u}\oplus E_{s}$-decomposition. Suppose $E_{u}$
and $E_{s}$ are represented by their orthonormal bases
$Q_{1}\in\mathbb{R}^{n\times k}$ and $Q_{2}\in\mathbb{R}^{n\times(n-k)}$,
respectively, i.e. $E_{u}=\text{col}(Q_{1}),E_{s}=\text{col}(Q_{2})$. Let
$Q=[Q_{1},Q_{2}]$ (which is invertible as $A$ is diagonalizable), and let
$R=[R_{1}^{*},R_{2}^{*}]^{*}:=Q^{-1}$. Since $E_{u}$ and $E_{s}$ are both
invariant with regard to $A$, we know there exists
$N_{1}\in\mathbb{R}^{k\times k}$, $N_{2}\in\mathbb{R}^{(n-k)\times(n-k)}$,
s.t.

$AQ=Q\begin{bmatrix}N_{1}&\\\ &N_{2}\end{bmatrix}\Leftrightarrow
N:=\begin{bmatrix}N_{1}&\\\ &N_{2}\end{bmatrix}=RAQ.$

We are now ready to prove Theorem 5.1.

Proof:  Let $D=U\Sigma V^{*}$ denote the compressed singular value
decomposition of $D$ and $\sigma_{1}>\dots>\sigma_{n}$ denote its singular
values. In this case, we have $U\in\mathbb{R}^{n\times\min\\{n,T\\}}$,
$\Sigma\in\mathbb{R}^{\min\\{n,T\\}\times\min\\{n,T\\}}$, and
$V\in\mathbb{R}^{T\times\min\\{n,T\\}}$. Moreover, denote
$U=[u_{1},\dots,u_{n}]$ and $V=[v_{1},\dots,v_{n}]$.

Furthermore, we have the following equalities

$D=QRD=Q\begin{bmatrix}R_{1}D\\\ R_{2}D\end{bmatrix}=Q\begin{bmatrix}D_{1}\\\
D_{2}\end{bmatrix}=\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}\begin{bmatrix}D_{1}\\\
0\end{bmatrix}+\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}\begin{bmatrix}0\\\
D_{2}\end{bmatrix}=Q_{1}D_{1}+Q_{2}D_{2}.$

Let

$\mathcal{D}=\begin{bmatrix}0&(Q_{1}D_{1})^{*}\\\
Q_{1}D_{1}&0\end{bmatrix},\quad J=\begin{bmatrix}0&(Q_{2}D_{2})^{*}\\\
Q_{2}D_{2}&0\end{bmatrix},\quad\mathcal{D}+J=\begin{bmatrix}0&D^{*}\\\
D&0\end{bmatrix}.$

We can decompose $\mathcal{D}+J$ in the following form

$\mathcal{D}+J=\begin{bmatrix}0&V\Sigma U^{*}\\\ U\Sigma
V^{*}&0\end{bmatrix}=\frac{1}{2}\left(\begin{bmatrix}V\\\
U\end{bmatrix}\Sigma\begin{bmatrix}V\\\ U\end{bmatrix}^{*}-\begin{bmatrix}V\\\
-U\end{bmatrix}\Sigma\begin{bmatrix}V\\\ -U\end{bmatrix}^{*}\right).$

Therefore, we see that the eigenvalues of $\mathcal{D}+J$ are exactly
$\\{\pm\sigma_{i}\\}$ with eigenvectors $[v_{i}^{*},\pm u_{i}^{*}]^{*}$,
respectively. Correspondingly, the top $k$ largest eigenvalues of
$\mathcal{D}+J$ are the top $k$ largest singular values of $D$, or the square
root of top $k$ largest eigenvalues of $DD^{*}$.

Similarly, we use compressed singular value composition on
$D_{1}=U_{1}\Sigma_{1}V_{1}^{*}$, where $U_{1}\in\mathbb{R}^{k\times
k},\Sigma_{1}\in\mathbb{R}^{k\times k},V_{1}\in\mathbb{R}^{T\times k}$, and
decompose $\mathcal{D}$ as follows:

$\displaystyle\mathcal{D}=$
$\displaystyle\begin{bmatrix}0&V_{1}\Sigma_{1}U_{1}^{*}Q_{1}^{*}\\\
Q_{1}U_{1}\Sigma_{1}V_{1}^{*}&0\end{bmatrix}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\bigg{(}\begin{bmatrix}V_{1}\Sigma_{1}V_{1}^{*}&V_{1}\Sigma_{1}U_{1}^{*}Q_{1}^{*}\\\
Q_{1}U_{1}\Sigma_{1}V_{1}^{*}&Q_{1}U_{1}\Sigma_{1}U_{1}^{*}Q_{1}^{*}\end{bmatrix}-\begin{bmatrix}V_{1}\Sigma_{1}V_{1}^{*}&-V_{1}\Sigma_{1}U_{1}^{*}Q_{1}^{*}\\\
-Q_{1}U_{1}\Sigma_{1}V_{1}^{*}&Q_{1}U_{1}\Sigma_{1}U^{*}Q_{1}^{*}\end{bmatrix}\bigg{)}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\bigg{(}\begin{bmatrix}V_{1}\Sigma_{1}\\\
Q_{1}U_{1}\Sigma_{1}\end{bmatrix}\begin{bmatrix}V_{1}^{*}&U_{1}^{*}Q_{1}^{*}\end{bmatrix}-\begin{bmatrix}V_{1}\Sigma_{1}\\\
-Q_{1}U_{1}\Sigma_{1}\end{bmatrix}\begin{bmatrix}V_{1}^{*}&-U_{1}^{*}Q_{1}^{*}\end{bmatrix}\bigg{)}$
$\displaystyle=$ $\displaystyle\frac{1}{2}\left(\begin{bmatrix}V_{1}\\\
Q_{1}U_{1}\end{bmatrix}\Sigma_{1}\begin{bmatrix}V_{1}\\\
Q_{1}U_{1}\end{bmatrix}^{*}-\begin{bmatrix}V_{1}\\\
-Q_{1}U_{1}\end{bmatrix}\Sigma_{1}\begin{bmatrix}V_{1}\\\
-Q_{1}U_{1}\end{bmatrix}^{*}\right).$

We see that the top $k$ largest eigenvalues of $\mathcal{D}$ are the top $k$
largest singular values of $D_{1}$, denoted as
$\hat{\sigma}_{1},\dots,\hat{\sigma}_{k}$.

Let $U^{(k)}$ and $V^{(k)}$ denote the submatrices containing the first $k$
columns of $U$ and $V$, respectively. Let $\Pi$ and $\Pi^{\prime}$ denote the
projection onto the eigenspaces of the largest $k$ eigenvectors of
$\mathcal{D}+J$ and $\mathcal{D}$, respectively.

It is clear that

$\displaystyle\Pi$ $\displaystyle=\frac{1}{2}\begin{bmatrix}V^{(k)}\\\
U^{(k)}\end{bmatrix}\begin{bmatrix}(V^{(k)})^{*}&(U^{(k)})^{*}\end{bmatrix}=\frac{1}{2}\begin{bmatrix}V^{(k)}(V^{(k)})^{*}&V^{(k)}(U^{(k)})^{*}\\\
U^{(k)}(V^{(k)})^{*}&U^{(k)}(U^{(k)})^{*}\end{bmatrix},$
$\displaystyle\Pi^{\prime}$ $\displaystyle=\frac{1}{2}\begin{bmatrix}V_{1}\\\
Q_{1}U_{1}\end{bmatrix}\begin{bmatrix}V_{1}^{*}&U_{1}^{*}Q_{1}^{*}\end{bmatrix}=\frac{1}{2}\begin{bmatrix}V_{1}V_{1}^{*}&V_{1}U_{1}^{*}Q_{1}^{*}\\\
Q_{1}U_{1}V_{1}^{*}&Q_{1}U_{1}U_{1}^{*}Q_{1}^{*}\end{bmatrix}=\frac{1}{2}\begin{bmatrix}V_{1}V_{1}^{*}&V_{1}U_{1}^{*}Q_{1}^{*}\\\
Q_{1}U_{1}V_{1}^{*}&Q_{1}Q_{1}^{*}\end{bmatrix}.$

By Davis-Kahan Theorem (see Cao [2021] and Appendix G), we have

$\left\lVert\Pi-\Pi^{\prime}\right\rVert\leq\frac{1}{2}\frac{\sqrt{2k}\left\lVert
J\right\rVert_{2}}{\hat{\sigma}_{k}-\sigma_{k+1}}=\frac{\sqrt{2k}\left\lVert
Q_{2}D_{2}\right\rVert}{\hat{\sigma}_{k}-\sigma_{k+1}}\leq\frac{\sqrt{2k}\left\lVert
Q_{2}\right\rVert\left\lVert
D_{2}\right\rVert}{\hat{\sigma}_{k}-\sigma_{k+1}}=\frac{\sqrt{2k}\left\lVert
D_{2}\right\rVert}{\hat{\sigma}_{k}-\sigma_{k+1}}.$

Since $\widehat{\Pi}_{1}=U^{(k)}(U^{(k)})^{*},\Pi_{1}=Q_{1}Q_{1}^{*}$, we have

$\left\lVert\widehat{\Pi}_{1}-\Pi_{1}\right\rVert\leq\left\lVert\Pi-\Pi^{\prime}\right\rVert\leq\frac{\sqrt{2k}\left\lVert
D_{2}\right\rVert}{\hat{\sigma}_{k}-\sigma_{k+1}}.$

We next show that $\hat{\sigma}_{k}=\Omega(|\lambda_{k}|^{T})$,
$\sigma_{k+1}=O(T)$ and $\|D_{2}\|=O(T)$, based on which
$\left\lVert\widehat{\Pi}_{1}-\Pi_{1}\right\rVert\leq\frac{O(T)}{\Omega(\lambda_{k}^{T}-T)}\rightarrow
0$. More formally, we have the following.

######  Lemma A.1.

If

$T>\Theta\left(\frac{\log
k-2\log\left(\frac{\text{gap}}{k^{\frac{k}{2}+3}}\right)-3\log\theta}{\log|\lambda_{k}|}\right)$
(10)

is satisfied, with probability at least $1-4\theta$,

$D_{1}D_{1}^{*}\succeq\frac{\pi|\lambda_{k}|^{2T}\theta^{2}}{4}\frac{\text{gap}^{2}}{k^{k+6}}\frac{|\lambda_{1}|^{2}}{|\lambda_{1}|^{2}-1},$

where we recall $\text{gap}=\left|\prod_{\begin{subarray}{c}m_{1}\neq
m_{2},\\\
m_{1},m_{2}\in\\{1,\dots,k\\}\end{subarray}}(\lambda_{m_{1}}^{-1}-\lambda_{m_{2}}^{-1})\right|$.

The proof of Lemma A.1 is delayed to Appendix B.

For $D_{2}$, we have the following inequalities

$\left\lVert D_{2}\right\rVert_{2}\leq\sqrt{T}\left\lVert
D_{2}\right\rVert_{1}\leq\sqrt{T}\sum_{i=k+1}^{n}\left(\sum_{j=1}^{T}\lambda_{i}^{j}C\right)\leq\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right).$
(11)

By Lemma A.1 and (11), in order to have
$\left\lVert\widehat{\Pi}_{1}-\Pi_{1}\right\rVert<\epsilon$, we need

$\displaystyle\left\lVert\widehat{\Pi}_{1}-\Pi_{1}\right\rVert<\epsilon$
$\displaystyle\Leftarrow$
$\displaystyle\frac{\sqrt{2k}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\frac{\sqrt{\pi}|\lambda_{k}|^{T}\theta}{2}\frac{\text{gap}}{k^{\frac{k}{2}+3}}\sqrt{\frac{|\lambda_{1}|^{2}}{|\lambda_{1}|^{2}-1}}-2\sqrt{2k}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}<\epsilon$
$\displaystyle\Leftarrow$
$\displaystyle\frac{2\sqrt{2k}k^{\frac{k}{2}+3}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\sqrt{\pi}|\lambda_{k}|^{T}\theta\text{gap}-4\sqrt{2k}k^{\frac{k}{2}+3}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}<\epsilon$
$\displaystyle\Leftarrow$
$\displaystyle\frac{2\sqrt{2}k^{\frac{k+7}{2}}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\frac{1}{2}\sqrt{\pi}|\lambda_{k}|^{T}\theta\text{gap}}<\epsilon$
(12) $\displaystyle\Leftarrow$ $\displaystyle
4\sqrt{2}k^{\frac{k+7}{2}}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)<\sqrt{\pi}|\lambda_{k}|^{T}\theta\text{gap}\epsilon$
$\displaystyle\Leftarrow$ $\displaystyle\frac{1}{2}\log
T+\log\bigg{(}4\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)\bigg{)}<T\log|\lambda_{k}|+\log\big{(}\sqrt{\pi}\theta\text{gap}\epsilon\big{)}$
$\displaystyle\Leftarrow$
$\displaystyle\frac{1}{2}T\log|\lambda_{k}|>\log\bigg{(}\frac{4\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\sqrt{\pi}\theta\text{gap}\epsilon}\bigg{)}$
(13) $\displaystyle\Leftarrow$ $\displaystyle
T>\frac{2\log\bigg{(}\frac{4\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\sqrt{\pi}\theta\text{gap}\epsilon}\bigg{)}}{\log|\lambda_{k}|}$
(14)

where in (12), we require

$\displaystyle
4\sqrt{2k}k^{\frac{k}{2}+3}\sqrt{T}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)<\frac{1}{2}\sqrt{\pi}|\lambda_{k}|^{T}\theta\text{gap}$
$\displaystyle\Leftarrow$ $\displaystyle\frac{1}{2}\log
T+\log\bigg{(}4\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)\bigg{)}<T\log|\lambda_{k}|+\log(\frac{1}{2}\sqrt{\pi}\theta\text{gap})$
$\displaystyle\Leftarrow$
$\displaystyle\frac{1}{2}T\log|\lambda_{k}|>\log\bigg{(}4\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)\bigg{)}-\log(\frac{1}{2}\sqrt{\pi}\theta\text{gap})$
(15) $\displaystyle\Leftarrow$ $\displaystyle
T>\frac{2\log\bigg{(}\frac{8\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\sqrt{\pi}\theta\text{gap}}\bigg{)}}{\log|\lambda_{k}|}$
(16)

where in (13) and (15), we need $T\log|\lambda_{k}|>\log T$. In order to have
$T\log|\lambda_{k}|>\log T$, define

$f(T):=T\log|\lambda_{k}|-\log T.$

When $T>\log|\lambda_{k}|$, we have
$f(T)=\left(\log|\lambda_{k}|\right)^{2}-\log\log|\lambda_{k}|>0$ and
$f^{\prime}(T)=\log|\lambda_{k}|-\frac{1}{T}>0$.

Therefore, when $T>\log|\lambda_{k}|$, we have $T\log|\lambda_{k}|>\log T$.

Combining (14), (16), and $T>\log|\lambda_{k}|$ required above, we get

$\begin{split}T&>\max\Bigg{\\{}\frac{2\log\bigg{(}\frac{8\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\sqrt{\pi}\theta\text{gap}}\bigg{)}}{\log|\lambda_{k}|},\frac{2\log\bigg{(}\frac{4\sqrt{2}k^{\frac{k+7}{2}}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)}{\sqrt{\pi}\theta\text{gap}\epsilon}\bigg{)}}{\log|\lambda_{k}|},\log|\lambda_{k}|\Bigg{\\}}.\end{split}$
(17)

Treating the eigenvalue terms and $\theta$ to be constants as stated in the
theorem, for $\left\lVert\widehat{\Pi}_{1}-\Pi_{1}\right\rVert<\epsilon$ to
hold, we need

$T>\Theta(\left(k\log k+\log(n-k)-\log\epsilon-\log\text{gap}\right).$ (18)

This concludes the proof. $\square$

##  Appendix B Auxillary Lemmas for Step 1

We derive a lower bound on $D_{1}D_{1}^{*}$ from Appendix 11 of Sarkar and
Rakhlin [2018], which requires two additional functions $\phi_{\min}(M_{1},T)$
and $\psi(M_{1},T)$:

For the space $\mathbb{R}^{d}$, define the $a-$outbox, $S_{d}(a)$, as the
following set

$S_{d}(a)=\\{v\in\mathbb{R}^{d}|\min_{1\leq i\leq d}|v(i)|>a\\},$

which is used to quantify the following norm–like quantities of a matrix:

$\phi_{\min}(M_{1},T)=\sqrt{\inf_{v\in
S_{k}(1)}\sigma_{\min}\left(\sum_{i=1}^{T}J^{-i+1}vv^{*}(J^{-i+1})^{*}\right)},$
(19)

where $M_{1}=\bar{P}^{-1}J\bar{P}$ is the Jordan normal form of $M_{1}$. Here,
Since $A$ is diagonalizable (so $M_{1}$ is diagonalizable), $J$ is the
diagonal matrix of $\lambda_{1},\cdots,\lambda_{k}$.

$\psi(M_{1},T)=\frac{1}{2k\sup_{1\leq i\leq k}C_{|\bar{P}_{i}^{*}z_{T}|}},$
(20)

where $C_{X}$ is the essential supremum of the probability distribution
function (pdf) of $X$,
$\bar{P}=[\bar{P}_{1},\bar{P}_{2},\cdots,\bar{P}_{k}]^{*}$, and

$z_{t}:=M_{1}^{-t}P_{1}^{*}x_{t}=\sum_{j=1}^{t}M_{1}^{-j}P_{1}^{*}\eta_{j}.$
(21)

The following lemma is adapted from Appendix 11 of Sarkar and Rakhlin [2018].

######  Lemma B.1.

With probability at least $1-4\theta$,

$D_{1}D_{1}^{*}\succeq\frac{1}{2}\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{2}M_{1}^{T}(M_{1}^{T})^{*},$

whenever

$\begin{split}&\left(4T^{3}\lambda_{k}^{-2(T+1)\upsilon}k+\frac{T^{2}k\sum_{i=1}^{k}\lambda_{i}^{-2(T+1)}}{\theta}\right)\\\
&\leq\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{2}}{2},\end{split}$
(22)

and

$T>\max\left\\{\frac{C}{1-|\lambda_{k+1}|},\frac{C}{|\lambda_{k}|-1}\right\\}.$
(23)

for some $\upsilon$ such that $(T+1)\upsilon=\lfloor\frac{T+1}{2}\rfloor$.

Note that in (22), we select $T$ such that
$\sum_{i=1}^{k}\sum_{t=1}^{T}|\lambda_{i}|^{-t}<kT$, or
$T>\frac{1}{k}\sum_{i=1}^{k}\frac{\lambda_{i}}{\lambda_{i}-1}$.

In Section C, we further prove the bounds on $\phi_{\min}$ and $\psi$ in Lemma
C.2 and Lemma C.4, which, combining with Lemma B.1 leads to the result in
Lemma A.1 directly. It is clear that the bound in (10) under Lemma A.1
satisfies (23) in Lemma B.1 trivially. Therefore, to prove Lemma A.1, we just
need to show that under (10), (22) in Lemma B.1 is satisfied.

Proof: [proof of Lemma A.1] To satisfy (22), we need

$T^{3}\lambda_{k}^{-2(T+1)\upsilon}k\leq\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{2}}{16},$
(24)

and

$\frac{T^{2}k\sum_{i=1}^{k}|\lambda_{i}|^{-2(T+1)}}{\theta}\leq\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{2}}{4}.$
(25)

We then separately evaluate the conditions that would guarantee the
satisfaction of the above inequities.

Condition (24): Taking the $\log$, we have

$\displaystyle 3\log T-2(T+1)\upsilon\log|\lambda_{k}|+\log k\leq
2\log\left(\phi_{\min}(M_{1},T)\psi(M_{1},T)\theta\right)-\log 16$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\Leftarrow}}$ $\displaystyle
3T\upsilon\log|\lambda_{k}|-2(T+1)\upsilon\log|\lambda_{k}|+\log k\leq
2\log\left(\phi_{\min}(M_{1},T)\psi(M_{1},T)\theta\right)-\log 16$
$\displaystyle\Leftarrow$ $\displaystyle-(3T+2)\upsilon\log|\lambda_{k}|\leq
2\log\left(\phi_{\min}(M_{1},T)\psi(M_{1},T)\theta\right)-\log 16-\log k$
$\displaystyle\Leftarrow$ $\displaystyle T\geq\frac{\log 16+\log
k-2\log\left(\phi_{\min}(M_{1},T)\psi(M_{1},T)\theta\right)}{3\upsilon\log|\lambda_{k}|}-2.$

where the step $(a)$ uses the following: $T\upsilon\log|\lambda_{k}|>\log T$,
which we show now. Define

$f(T):=T\log|\lambda_{k}|^{\upsilon}-\log T.$

When $T=\log|\lambda_{k}|^{\upsilon}$, we have
$f(T)=\left(\log|\lambda_{k}|^{\upsilon}\right)^{2}-\log\log|\lambda_{k}|^{\upsilon}>0$.
When $T\geq\log|\lambda_{k}|^{\upsilon}$, we have
$f^{\prime}(T)=\log|\lambda_{k}|^{\upsilon}-\frac{1}{T}>0$.

Therefore, when $T>\log|\lambda_{k}|^{\upsilon}$, we have
$T\upsilon\log|\lambda_{k}|>\log T$.

Condition (25): Since $|\lambda_{1}|>\ldots>|\lambda_{k}|$, to meet (25), it
suffices to show:

$\displaystyle
T^{2}k^{2}|\lambda_{k}|^{-2(T+1)}\leq\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{3}}{4}$
$\displaystyle\Leftarrow$ $\displaystyle
T^{2}|\lambda_{k}|^{-2(T+1)}\leq\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{3}}{4k^{2}}$
$\displaystyle\Leftarrow$ $\displaystyle 2\log
T-2(T+1)\log|\lambda_{k}|\leq\log\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{3}}{4k^{2}}$
$\displaystyle\Leftarrow$ $\displaystyle
T\log|\lambda_{k}|-2(T+1)\log|\lambda_{k}|\leq\log\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{3}}{4k^{2}}$
$\displaystyle\Leftarrow$ $\displaystyle
T\geq-\frac{\log\frac{\phi_{\min}(M_{1},T)^{2}\psi(M_{1},T)^{2}\theta^{3}}{4k^{2}}}{\log|\lambda_{k}|}+2.$

Similar to the derivation of (24), in order to get $T\log|\lambda_{k}|>2\log
T$, we need $T>2\log|\lambda_{k}|$.

Combining the above and applying Lemma C.2 and Lemma C.4, we get the condition
for $T$ as in (10).

This concludes the proof of Lemma A.1. $\square$

The following Corollary directly follows from Theorem 5.1.

######  Corollary B.2.

Under the premise of Theorem 5.1, for any orthonormal basis $\hat{P}_{1}$ of
$\text{col}(\widehat{\Pi}_{1})$ (where $\widehat{\Pi}_{1}$ is obtained by
Algorithm 1), there exists a corresponding orthonormal basis $P_{1}$ of
$\text{col}(\Pi_{1})$, such that

$\left\lVert P_{1}-\hat{P}_{1}\right\rVert<\sqrt{2k}\epsilon:=\delta.$

The proof structure of Corollary B.2 is identical to the proof of Corollary
5.2 of Hu et al. [2022].

##  Appendix C Proof of Auxiliary Lemmas for Appendix B

In this section, we prove a few Lemmas that is used to bound $D_{1}D_{1}^{*}$
in Appendix B.

######  Lemma C.1.

Given a $k\times k$ Vandermonde Matrix $\Lambda$

$\Lambda=\begin{bmatrix}1&\lambda_{1}^{-1}&\cdots&\lambda_{1}^{-k+1}\\\
\vdots&\vdots&\vdots&\vdots\\\
1&\lambda_{k}^{-1}&\cdots&\lambda_{k}^{-k+1}\end{bmatrix},$ (26)

and $\lambda_{1},\ldots,\lambda_{k}\neq 0$, then
$\left\lVert\Lambda^{-1}\right\rVert\leq\frac{k^{\frac{k}{2}+1}}{\text{gap}}$,
where

$\text{gap}=\left|\prod_{m_{1}\neq
m_{2}}(\lambda_{m_{1}}^{-1}-\lambda_{m_{2}}^{-1})\right|.$ (27)

Proof:  From Theorem 1 of Tucci and Whiting [2011], we have

$\Lambda^{-1}(i,j)=\frac{(-1)^{k-i}\sigma^{j}_{k-i}}{\prod_{m_{1}\neq
m_{2}}(\lambda_{m_{1}}^{-1}-\lambda_{m_{2}}^{-1})},$ (28)

where
$\sigma_{k-i}^{j}:=\sum_{\rho_{k-i}^{j}}\prod_{\ell\in\rho_{k-i}^{j}}\lambda_{\ell}^{-1}$
and $\rho_{k-i}^{j}$ goes through all subsets of
$\\{\lambda_{1}^{-1},\ldots,\lambda_{j-1}^{-1},\lambda_{j+1}^{-1},\ldots,\lambda_{k}^{-1}\\}$
with cardinality $k-i$. In the above expression, the quantity
$\sigma_{k-i}^{j}$ can be bounded as:

$\sigma_{k-i}^{j}\leq\binom{k}{k-i}\left(\frac{1}{\lambda_{k}}\right)^{k-i}.$
(29)

Plugging (29) into (28) gives a bound for $|\Lambda^{-1}(i,j)|$ as follows:

$\left\lVert\Lambda^{-1}(i,j)\right\rVert\leq\frac{\binom{k}{k-i}\left(\frac{1}{\lambda_{k}}\right)^{k-i}}{\text{gap}}.$
(30)

Moreover, we have the following well-known inequality (see, for example, Horn
and Johnson [1985])

$\frac{1}{\sqrt{k}}\left\lVert\Lambda^{-1}\right\rVert_{1}\leq\left\lVert\Lambda^{-1}\right\rVert_{2}\leq\sqrt{k}\left\lVert\Lambda^{-1}\right\rVert_{1}.$
(31)

Combining the above, we get

$\left\lVert\Lambda^{-1}\right\rVert\leq\max_{i}\left\\{\sum_{j}\left|\Lambda^{-1}(i,j)\right|\right\\}\leq\frac{k^{\frac{k}{2}+\frac{3}{2}}}{\text{gap}}.$
(32)

where we have used the Sterling’s formula for bounding $\binom{k}{k-i}$ in the
summation. $\square$

######  Lemma C.2.

Under the premise of Theorem 5.1, given $\phi_{\min}$ as defined in (19), we
have

$\phi_{\min}(M_{1},T)\geq\frac{\text{gap}}{k^{\frac{k}{2}+2}}.$

Proof:

Let $h_{i}(v)=\begin{bmatrix}\lambda_{1}^{-i+1}v(1)\\\
\lambda_{2}^{-i+1}v(2)\\\ \vdots\\\
\lambda_{k}^{-i+1}v(k)\end{bmatrix}\in\mathbb{R}^{k}$, and
$H(v)=\begin{pmatrix}h_{1}(v)&h_{2}(v)&\dots&h_{T}(v)\end{pmatrix}$. Then we
have

$\displaystyle\begin{array}[]{rcl}\phi_{\min}(M_{1},T)&=&\sqrt{\inf_{v\in
S_{d}(1)}\sigma_{\min}\left(\sum_{i=1}^{T}h_{i}(v)h_{i}^{*}(v)\right)}\\\
&=&\sqrt{\inf_{v\in S_{d}(1)}\sigma_{\min}\left(H(v)H^{*}(v)\right)}\\\
&=&\sqrt{\inf_{v\in S_{d}(1)}\frac{1}{\left\lVert
H^{-1}(v)\right\rVert^{2}}}\\\ &=&\inf_{v\in S_{d}(1)}\frac{1}{\left\lVert
H^{-1}(v)\right\rVert}\end{array}$

and we can decompose $H(v)$ as follows

$\begin{split}H(v)&=\text{diag}\left(v(1),\dots,v(k)\right)\begin{bmatrix}1&\lambda_{1}^{-1}&\dots&\lambda_{1}^{-T+1}\\\
1&\lambda_{2}^{-1}&\dots&\lambda_{2}^{-T+1}\\\ \vdots&\vdots&\vdots&\vdots\\\
1&\lambda_{k}^{-1}&\dots&\lambda_{k}^{-T+1}\end{bmatrix}\\\
&:=\text{diag}(v)\tilde{H}.\end{split}$

Therefore,

$\left\lVert
H^{-1}(v)\right\rVert=\left\lVert\tilde{H}^{-1}(\text{diag}(v))^{-1}\right\rVert\leq\left\lVert\tilde{H}^{-1}\right\rVert\left\lVert(\text{diag}(v))^{-1}\right\rVert.$
(33)

By Lemma C.1, we get

$\left\lVert\tilde{H}^{-1}\right\rVert\leq\frac{k^{\frac{k}{2}+\frac{3}{2}}}{\text{gap}}.$

Plugging the above inequality into (33) gives

$\left\lVert H^{-1}(v)\right\rVert\leq\frac{k^{\frac{k}{2}+2}}{\text{gap}},$

and

$\phi_{\min}(M_{1},T)\geq\frac{\text{gap}}{k^{\frac{k}{2}+2}}.$

$\square$

We also need a similar bound for $\psi(M_{1},T)$. However, since we do not
have an explicit formula for the pdf of noise $\eta$, it is difficult to
evaluate $\sup_{1\leq i\leq k}C_{|\bar{P}_{i}^{*}z_{T}|}$ in (20) explicitly.
However, it is intuitively clear that $\sup_{1\leq i\leq
k}C_{|\bar{P}_{i}^{*}z_{T}|}$ is upper bounded by a constant, as $z_{T}$ in
(21) converges in distribution as $T\rightarrow\infty$. Therefore, the
probability distribution function of $\bar{P}_{i}^{*}z_{T}$ also converges.

To demonstrate this more concretely, we explicitly compute the bound when
$\eta_{t}\sim N(0,1)$ follows the standard normal distribution:

######  Lemma C.3.

If $\eta_{t}$ follows the standard normal distribution for all $t$, then

$C_{|\bar{P}_{i}^{*}z_{T}|}<\sqrt{\frac{2}{\pi}}\sqrt{\frac{|\lambda_{i}|^{2}-1}{|\lambda_{i}|^{2}}}$

Proof:  The $j$-th entry of $\bar{P}_{i}^{*}z_{T}$ can be represented as

$\bar{P}_{i}^{*}z_{T}(j)=\sum_{t=1}^{T}v_{i}\cdot\left(M_{1}^{-t}P_{1}^{*}\eta_{t}\right)\sim
N\left(0,\sum_{t=1}^{T}\left(|\lambda_{j}|^{-t}\right)^{2}\right)$

so

$\text{pdf}_{\bar{P}_{i}^{*}Z_{T}}(y)=\frac{1}{\sqrt{2\pi\sum_{t=1}^{T}\left(|\lambda_{i}|^{-t}\right)^{2}}}e^{-\frac{y^{2}}{2\sum_{t=1}^{T}\left(|\lambda_{i}|^{-t}\right)^{2}}},\qquad
y\in\mathbb{R}.$

With some algebra, we get

$\text{pdf}_{|\bar{P}_{i}^{*}z_{T}|}(y)=\frac{\sqrt{2}}{\sqrt{\pi\sum_{t=1}^{T}\left(|\lambda_{i}|^{-t}\right)^{2}}}e^{-\frac{y^{2}}{2\sum_{t=1}^{T}\left(|\lambda_{i}|^{-t}\right)^{2}}},\qquad
y\in\mathbb{R}^{+}.$

Therefore,
$C_{|\bar{P}_{i}^{*}z_{T}|}\leq\frac{\sqrt{2}}{\sqrt{\pi\sum_{t=1}^{T}\left(|\lambda_{i}|^{-t}\right)^{2}}}\leq\sqrt{\frac{2}{\pi}}\sqrt{\frac{|\lambda_{i}|^{2}-1}{|\lambda_{i}|^{2}}}$.
$\square$

In the rest of the paper, we will assume $C_{|\bar{P}_{i}^{\prime}z_{T}|}$ is
bounded and take

$C_{|\bar{P}_{i}^{*}z_{T}|}<C_{z},$ (34)

for some constant $C_{z}$, as in 2. Therefore, the following result directly
follows:

######  Lemma C.4.

Under the premise of Theorem 5.1, given $\psi$ as defined in (20), we have

$\psi(M_{1},T)\geq\frac{1}{2kC_{z}}.$

##  Appendix D Solution to the Least Square Problem in Stage 2

Lemma D.1 gives the explicit form for the solution to the least squares
problem in Algorithm 1

######  Lemma D.1.

Given $D:=[x_{0},\cdots,x_{T}]$ and $\hat{\Pi}_{1}=U^{(k)}(U^{(k)})^{*}$, the
solution to

$\hat{M}_{1}=\arg\min_{M_{1}}\sum_{t=0}^{T}\left\lVert(U^{(k)})^{*}x_{t+1}-M_{1}(U^{(k)})^{*}x_{t}\right\rVert^{2}$

is uniquely given by $\hat{M}_{1}=(U^{(k)})^{*}AU^{(k)}+\varpi$, where
$\varpi=\left(\sum_{t}(U^{(k)})^{*}\eta_{t}x_{t}^{*}U^{(k)}\right)((\Sigma^{(k)})^{2})^{-1}$.

Proof:  Sincec $M_{1}$ is a stationary point of $\mathcal{L}$, for any
$\Delta$ in the neighborhood of $O$, we have

$\displaystyle 0\leq$
$\displaystyle\mathcal{L}(M_{1}+\Delta)-\mathcal{L}(M_{1})$ $\displaystyle=$
$\displaystyle\sum_{t}\left\lVert\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t}-\Delta\hat{y}_{1,t}\right\rVert^{2}-\sum_{t}\left\lVert\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t}\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\sum_{t}\langle\Delta\hat{y}_{1,t},\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t}\rangle+O(\left\lVert\Delta\right\rVert^{2})$
$\displaystyle=$
$\displaystyle\sum_{t}\text{tr}\left(\hat{y}_{1,t}^{*}\Delta^{*}(\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t})\right)+O(\left\lVert\Delta\right\rVert^{2})$
$\displaystyle=$
$\displaystyle\sum_{t}\text{tr}\left(\Delta^{*}(\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t})\hat{y}_{1,t}^{*}\right)+O(\left\lVert\Delta\right\rVert^{2})$
$\displaystyle=$
$\displaystyle\text{tr}\left(\Delta^{*}\sum_{t}\left(\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t}\right)\hat{y}_{1,t}^{*}\right)+O(\left\lVert\Delta\right\rVert^{2}).$

Since the above holds for all $\Delta$, we get

$\sum_{t}(\hat{y}_{1,t+1}-M_{1}\hat{y}_{1,t})\hat{y}_{1,t}^{*}\Leftrightarrow
M_{1}\sum_{t}\hat{y}_{1,t}\hat{y}_{1,t}^{*}=\sum_{t}\hat{y}_{1,t+1}\hat{y}_{1,t}^{*}.$

Plugging in $\hat{y}_{1,t}=(U^{(k)})^{*}x_{t}$ and
$\hat{y}_{1,t+1}=(U^{(k)})^{*}(Ax_{t}+\eta_{t})$, we have

$\begin{split}M_{1}(U^{(k)})^{*}DD^{*}U^{(k)}&=M_{1}\sum_{t}(U^{(k)})^{*}x_{t}x_{t}^{*}U^{(k)}\\\
&=\sum_{t}(U^{(k)})^{*}(Ax_{t}+\eta_{t})x_{t}^{*}U^{(k)}\\\
&=(U^{(k)})^{*}ADD^{*}U^{(k)}+\sum_{t}(U^{(k)})^{*}\eta_{t}x_{t}^{*}U^{(k)}.\end{split}$

Since $U^{(k)}$ are the first $k$ singular vectors of $D$, we have the
following equalities:

$(U^{(k)})^{*}DD^{*}U^{(k)}=(U^{(k)})^{*}U\Sigma
V^{*}V\Sigma^{*}U^{*}U^{(k)}=\begin{bmatrix}I^{(k)}&0\end{bmatrix}\Sigma^{2}\begin{bmatrix}I^{(k)}\\\
0\end{bmatrix}=(\Sigma^{(k)})^{2},$ (35)

which is invertible, and $\hat{M}_{1}$ is explicitly given by

$\hat{M}_{1}=\left((U^{(k)})^{*}ADD^{*}U^{(k)}+\sum_{t}(U^{(k)})^{*}\eta_{t}x_{t}^{*}U^{(k)}\right)(\Sigma^{(k)})^{-2}.$
(36)

Moreover, we have

$\displaystyle U^{(k)}(U^{(k)})^{*}DD^{*}U^{(k)}=U^{(k)}(\Sigma^{(k)})^{2}$
$\displaystyle=$
$\displaystyle\begin{bmatrix}U^{(k)}&0\end{bmatrix}\begin{bmatrix}(\Sigma^{(k)})^{2}\\\
0\end{bmatrix}=U\begin{bmatrix}(\Sigma^{(k)})^{2}\\\ 0\end{bmatrix}$
$\displaystyle=$ $\displaystyle U\Sigma^{2}\begin{bmatrix}I^{(k)}\\\
0\end{bmatrix}=U\Sigma^{2}U^{*}U^{(k)}=DD^{*}U^{(k)},$

where the first equality is obtained by using (35). Substituting the above in
(36) yields

$\begin{split}\hat{M}_{1}&=\left((U^{(k)})^{*}A(U^{(k)}(U^{(k)})^{*}DD^{*})U^{(k)}\right)(\Sigma^{(k)})^{-2}+\varpi\\\
&=\left((U^{(k)})^{*}AU^{(k)}(U^{(k)})^{*}\right)\left(DD^{*}U^{(k)}\right)(\Sigma^{(k)})^{-2}+\varpi\\\
&=(U^{(k)})^{*}AU^{(k)}+\varpi,\end{split}$

where
$\varpi=\left(\sum_{t}(U^{(k)})^{*}\eta_{t}x_{t}^{*}U^{(k)}\right)(\Sigma^{(k)})^{-2}$.
$\square$

We want to show $(U^{(k)})^{*}AU^{(k)}$ is the dominating term of the above
expression, as we will bound $\varpi$ in the following lemma.

######  Lemma D.2.

Under the premise of Theorem 5.1,

$\left\lVert M_{1}-\hat{M}_{1}\right\rVert<3\left\lVert A\right\rVert\delta$

for any $\delta>0$ whenever

$T\geq\frac{\log\left(\frac{4C}{\pi\theta^{2}\left\lVert
A\right\rVert\delta}\frac{k^{k+6}}{\text{gap}^{2}}\right)}{\log|\lambda_{k}|}.$

Proof:  First, we prove that $\varpi\leq\delta$. Let
$H=[\eta_{1},\dots,\eta_{T}]$, then we have

$\displaystyle\varpi$
$\displaystyle=(U^{(k)})^{*}HD^{*}U^{(k)}(\Sigma^{(k)})^{-2}$
$\displaystyle=(U^{(k)})^{*}HV\Sigma^{*}U^{*}U^{(k)}(\Sigma^{(k)})^{-2}$
$\displaystyle=(U^{(k)})^{*}HV\Sigma^{*}\begin{bmatrix}I^{(k)}\\\
0\end{bmatrix}(\Sigma^{(k)})^{-2}$
$\displaystyle=(U^{(k)})^{*}HV\begin{bmatrix}\Sigma^{(k)}\\\
0\end{bmatrix}(\Sigma^{(k)})^{-2}$
$\displaystyle=(U^{(k)})^{*}HV\begin{bmatrix}(\Sigma^{(k)})^{-1}\\\
0\end{bmatrix}.$

Therefore,

$\displaystyle\left\lVert\varpi\right\rVert\leq\left\lVert
A\right\rVert\delta$ $\displaystyle\Leftarrow$ $\displaystyle\left\lVert
H\right\rVert\left\lVert(\Sigma^{(k)})^{-1}\right\rVert\leq\left\lVert
A\right\rVert\delta$ $\displaystyle\Leftarrow$
$\displaystyle\sqrt{T}C\frac{2}{\sqrt{\pi}|\lambda_{k}|^{T}\theta}\frac{k^{\frac{k}{2}+3}}{\text{gap}}\sqrt{\frac{|\lambda_{1}|^{2}-1}{|\lambda_{1}|^{2}}}\leq\left\lVert
A\right\rVert\delta$ (37) $\displaystyle\Leftarrow$
$\displaystyle\frac{|\lambda_{k}|^{T}}{\sqrt{T}}\geq\frac{2C}{\sqrt{\pi}\theta\left\lVert
A\right\rVert\delta}\frac{k^{\frac{k}{2}+3}}{\text{gap}}$
$\displaystyle\Leftarrow$ $\displaystyle T\log|\lambda_{k}|-\frac{1}{2}\log
T\geq\log\left(\frac{2C}{\pi\theta\left\lVert
A\right\rVert\delta}\frac{k^{\frac{k}{2}+3}}{\text{gap}}\right)$
$\displaystyle\Leftarrow$
$\displaystyle\frac{1}{2}T\log|\lambda_{k}|\geq\log\left(\frac{2C}{\pi\theta\left\lVert
A\right\rVert\delta}\frac{k^{\frac{k}{2}+3}}{\text{gap}}\right)$ (38)
$\displaystyle\Leftarrow$ $\displaystyle
T\geq\frac{2\log\left(\frac{2C}{\pi\theta\left\lVert
A\right\rVert\delta}\frac{k^{\frac{k}{2}+3}}{\text{gap}}\right)}{\log|\lambda_{k}|},$
(39)

where (37) used Lemma A.1 and that for a $n\times T$ matrix $H$, $\left\lVert
H\right\rVert_{2}\leq\sqrt{T}\left\lVert H\right\rVert_{1}$, and (38) requires
$\log T<T\log|\lambda_{k}|$, which is satisfied when we derived (13) and (15).
We can use Lemma A.1 to bound $\left\lVert(\Sigma^{(k)})^{-1}\right\rVert$ is
a direct result of Cauchy Interlacing Theorem. We further observe that (39)
does not change the criteria obtained in (18).

Recall that $U^{(k)}=\hat{P}_{1}$. We obtain

$\displaystyle\left\lVert M_{1}-\hat{M}_{1}\right\rVert$
$\displaystyle=P_{1}^{*}AP_{1}-\left((U^{(k)})^{*}AU^{(k)}+\varpi\right)$
$\displaystyle\leq\left\lVert
P_{1}^{*}AP_{1}-P_{1}^{*}A\hat{P}_{1}^{*}\right\rVert+\left\lVert
P_{1}^{*}A\hat{P}_{1}-\hat{P}_{1}^{*}A\hat{P}_{1}^{*}\right\rVert+\left\lVert\varpi\right\rVert$
$\displaystyle\leq\left\lVert A\right\rVert\left\lVert
P_{1}-\hat{P}_{1}\right\rVert+\left\lVert A\right\rVert\left\lVert
P_{1}-\hat{P}_{1}\right\rVert+\left\lVert\varpi\right\rVert$
$\displaystyle\leq 3\left\lVert A\right\rVert\delta.$

where in the last inequality, we used Corollary B.2. $\square$

With Lemma D.2, we are ready to prove Proposition 5.2.

Proof: [Proof of Proposition 5.2] By Lemma D.2, we get $\left\lVert
M_{1}-\hat{M}_{1}\right\rVert<3\left\lVert A\right\rVert\delta$. Moreover, by
Gelfand’s formula, we have

$\displaystyle\left\lVert M_{1}^{t}\right\rVert$ $\displaystyle=\left\lVert
P_{1}^{*}A^{t}P_{1}\right\rVert\leq\left\lVert
A^{t}\right\rVert\leq\zeta_{\epsilon_{1}}(A)(|\lambda_{1}|+\epsilon_{1})^{t},$
$\displaystyle\left\lVert\hat{M}_{1}^{t}\right\rVert$
$\displaystyle=\left\lVert\hat{P}_{1}^{*}A^{t}\hat{P}_{1}\right\rVert\leq\left\lVert
A^{t}\right\rVert\leq\zeta_{\epsilon_{1}}(A)(|\lambda_{1}|+\epsilon_{1})^{t},$

Therefore, by telescoping, we get

$\displaystyle\left\lVert M_{1}^{\tau}-\hat{M}_{1}^{\tau}\right\rVert$
$\displaystyle=\left\lVert\sum_{i=1}^{\tau}(M_{1}^{i}\hat{M}_{1}^{\tau-i}-M_{1}^{i-1}\hat{M}_{1}^{\tau-i+1})\right\rVert$
$\displaystyle\leq\left\lVert M_{1}^{i-1}\right\rVert\left\lVert
M_{1}^{\tau-i}\right\rVert\left\lVert M_{1}-\hat{M}_{1}\right\rVert$
$\displaystyle<\tau\cdot\zeta_{\epsilon_{1}}(A)^{2}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\cdot
3\left\lVert A\right\rVert\delta$ $\displaystyle=3\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta.$

$\square$

With Proposition 5.2, the following corollary easily follows:

######  Corollary D.3.

Under the premise of Theorem 4.2, when $\delta<\frac{1}{\tau}$,

$\left\lVert\hat{M}_{1}^{\tau}\right\rVert<\left(\zeta_{\epsilon_{1}}(M_{1})(|\lambda_{1}|+\epsilon_{1})+3\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)\right)(|\lambda_{1}|+\epsilon_{1})^{\tau-1}.$

Proof:  By Gelfand’s formula and Proposition 5.2,

$\displaystyle\left\lVert\hat{M}_{1}^{\tau}\right\rVert$
$\displaystyle\leq\left\lVert
M_{1}^{\tau}\right\rVert+\left\lVert\hat{M}_{1}^{\tau}-M_{1}^{\tau}\right\rVert$
$\displaystyle\leq\zeta_{\epsilon_{1}}(A)(\lambda_{1}+\epsilon_{1})^{\tau}+3\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta$
$\displaystyle<\left(\zeta_{\epsilon_{1}}(M_{1})(|\lambda_{1}|+\epsilon_{1})+3\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)\right)(|\lambda_{1}|+\epsilon_{1})^{\tau-1}.$

where the last inequality requires $\delta<\frac{1}{\tau}$. $\square$

##  Appendix E Bounding $\left\lVert\hat{B}_{\tau}-B_{\tau}\right\rVert$

######  Lemma E.1.

For any $\gamma>\epsilon$, the following implication holds:

$\frac{\left\lVert R_{2}x\right\rVert}{\left\lVert
x\right\rVert}\leq\gamma-\epsilon:=\gamma^{\prime}\quad\Rightarrow\quad\frac{\left\lVert(I-\hat{\Pi}_{1})x\right\rVert}{\left\lVert
x\right\rVert}\leq\gamma$

Proof:

$\displaystyle\frac{\left\lVert(I-\hat{\Pi}_{1})x\right\rVert}{\left\lVert
x\right\rVert}$
$\displaystyle=\frac{\left\lVert(I-\hat{\Pi}_{1}+\Pi_{1}-\Pi_{1})x\right\rVert}{\left\lVert
x\right\rVert}$ $\displaystyle\leq$
$\displaystyle\frac{\left\lVert(I-\Pi_{1})x\right\rVert}{\left\lVert
x\right\rVert}+\frac{\left\lVert\hat{\Pi}_{1}-\Pi_{1}\right\rVert\left\lVert
x\right\rVert}{\left\lVert x\right\rVert}$ $\displaystyle\leq$
$\displaystyle\frac{\left\lVert\Pi_{2}x\right\rVert}{\left\lVert
x\right\rVert}+\epsilon$ $\displaystyle=$
$\displaystyle\frac{\left\lVert\Pi_{2}\Pi_{s}x\right\rVert}{\left\lVert
x\right\rVert}+\epsilon$ (40) $\displaystyle\leq$
$\displaystyle\frac{\left\lVert\Pi_{s}x\right\rVert}{\left\lVert
x\right\rVert}+\epsilon$ $\displaystyle\leq$ $\displaystyle\gamma$ (41)

where (40) holds because $E_{2}$ is orthogonal to $E_{1}$, therefore
$\Pi_{2}\Pi_{u}=0$, as $P_{2}P_{2}^{*}Q_{1}R_{1}=0$ by orthogonality of
$P_{2}$ and $Q_{1}=P_{1}$. $\square$

In the following propositions, we show that the stopping time $\omega_{i}$
defined in Algorithm 1 guarantees a bound on $\left\lVert x_{t}\right\rVert$.

######  Proposition E.2.

Under the premise of Theorem 4.2, for any constant $\gamma>\epsilon$, if in
the open loop system,

$\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t}\right\rVert}{\left\lVert
x_{t}\right\rVert}>\gamma,$

then, exists $C_{\gamma}\in\mathbb{R}^{+}$ such that $\left\lVert
x_{t}\right\rVert<C_{\gamma}$.

Proof:  Since we have that $x_{t}=\sum_{j=0}^{t}A^{t-j}\eta_{j}$, we have

$Rx_{t}=\begin{bmatrix}R_{1}x_{t}\\\
R_{2}x_{t}\end{bmatrix}=\begin{bmatrix}R_{1}\sum_{j=0}^{t}A^{t-j}\eta_{j}\\\
R_{2}\sum_{j=0}^{t}A^{t-j}\eta_{j}\end{bmatrix}=\begin{bmatrix}\sum_{j=0}^{t}N_{1}^{t-j}R_{1}\eta_{j}\\\
\sum_{j=0}^{t}N_{2}^{t-j}R_{2}\eta_{j}\end{bmatrix}$

Therefore, we have that

$\displaystyle\left\lVert R_{2}x\right\rVert$
$\displaystyle\leq\sum_{j=0}^{t}\left\lVert N_{2}^{j}\right\rVert\left\lVert
R_{2}\right\rVert
C\leq\sum_{j=0}^{t}\zeta_{\epsilon_{4}}(N_{2})(\lambda_{k+1}+\epsilon_{4})^{j}\left\lVert
R_{2}\right\rVert C$
$\displaystyle\leq\frac{\zeta_{\epsilon_{4}}(N_{2})C}{1-\xi}\frac{1}{1-(\lambda_{k+1}+\epsilon_{4})}$

where we used Lemma A.1 of Hu et al. [2022]. As $\left\lVert
R_{2}x_{j}\right\rVert$ is bounded above by a constant, so is
$\left\lVert\Pi_{s}x_{t}\right\rVert=\left\lVert Q_{2}R_{2}x_{t}\right\rVert$.

Since $\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t}\right\rVert}{\left\lVert
x_{t}\right\rVert}>\gamma$, by Lemma E.1, $\frac{\left\lVert
R_{2}x_{t}\right\rVert}{\left\lVert x_{t}\right\rVert}>\gamma^{\prime}$.
Correspondingly, we have

$\displaystyle\gamma^{\prime}<\frac{\left\lVert
R_{2}x_{t}\right\rVert}{\left\lVert x_{t}\right\rVert},$

which implies

$\left\lVert
x_{t}\right\rVert<\frac{\zeta_{\epsilon_{4}}(N_{2})C}{\gamma^{\prime}(1-\xi)}\frac{1}{1-(|\lambda_{k+1}|+\epsilon_{4})}:=C_{\gamma}.$
(42)

$\square$

######  Proposition E.3.

Under the premise of Theorem 4.2, for any constant $\gamma>\epsilon$, consider
the initial state $x_{i}$ such that $\frac{\left\lVert
P_{2}^{*}x_{i}\right\rVert}{\left\lVert x_{i}\right\rVert}>\gamma$. Moreover,
$x_{i+1}=Ax_{i}+Bu+\eta_{i}$, i.e. we insert control right after the initial
state and let the system run in open-loop thereafter. If for
$t\in\mathbb{Z}^{+}$ such that

$\frac{\left\lVert(I-\hat{\Pi}_{1})x_{i+t}\right\rVert}{\left\lVert
x_{i+t}\right\rVert}>\gamma,$

then, for all $\alpha<\frac{1}{\left\lVert B\right\rVert}$,

$\left\lVert
x_{i+t}\right\rVert<\frac{1}{\gamma^{\prime}}\left(\frac{2\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}\left\lVert
x_{i}\right\rVert+C_{\gamma}\right).$

Proof:

$\displaystyle\left\lVert R_{2}x_{i+t}\right\rVert\leq$
$\displaystyle\left\lVert
N_{2}^{t}R_{2}x_{i}+N_{2}^{t-1}R_{2}Bu\right\rVert+\sum_{j=0}^{t}\left\lVert
N_{2}^{j}\right\rVert\left\lVert R_{2}\right\rVert C$ $\displaystyle\leq$
$\displaystyle\frac{\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}(|\lambda_{k+1}|+\epsilon_{4})^{t-1}((1+\alpha\left\lVert
B\right\rVert)\left\lVert x_{i}\right\rVert)+C_{\gamma}$ $\displaystyle\leq$
$\displaystyle\frac{2\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}(|\lambda_{k+1}|+\epsilon_{4})^{t-1}\left\lVert
x_{i}\right\rVert+C_{\gamma}.$ (43)

Since $\frac{\left\lVert(I-\hat{\Pi}_{1})x_{i+t}\right\rVert}{\left\lVert
x_{i+t}\right\rVert}>\gamma$, by Lemma E.1, we have that

$\displaystyle\gamma^{\prime}<\frac{\left\lVert
R_{2}x_{i+t}\right\rVert}{\left\lVert x_{i+t}\right\rVert}.$

Substitute the above in (43) finishes the proof. $\square$

######  Proposition E.4.

Under the premise of Theorem 4.2, for any constant $\gamma>\epsilon$ and
stopping time $\omega_{i}$ such that:

$\omega_{i}=\min\left\\{t>t_{i-1}:\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t}\right\rVert}{\left\lVert
x_{t}\right\rVert}\leq\gamma\wedge\left\lVert
x_{t}\right\rVert>\frac{C}{\delta}\right\\},$

where we assume $t_{0}=T$. Then, Algorithm 1 guarantees that

$\frac{\left\lVert P_{2}^{*}x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}<\gamma+\epsilon,\qquad\forall i\in\\{1,\dots,m\\},$

while maintaining

$\left\lVert x_{t_{1}}\right\rVert\leq\max\left\\{\left\lVert
A\right\rVert\frac{C}{\delta}+C,\left\lVert A\right\rVert
C_{\gamma}+C,\left\lVert x_{T}\right\rVert\right\\},$ $\left\lVert
x_{t}\right\rVert<\max\left\\{\left\lVert
A\right\rVert\frac{C}{\delta}+C,\left(\frac{\left\lVert
A\right\rVert}{\gamma^{\prime}}\frac{2\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}\right)^{i}\left\lVert
x_{t_{1}}\right\rVert+\sum_{j=1}^{i-1}\left(\frac{\left\lVert
A\right\rVert}{\gamma^{\prime}}\frac{2\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}\right)^{j}\left(\frac{\left\lVert
A\right\rVert}{\gamma^{\prime}}C_{\gamma}+C\right)\right\\},\quad\forall
t_{i}\leq t\leq t_{i+1}.$

Proof:  Similar to the steps in proof of Lemma E.1, we obtain that

$\frac{\left\lVert P_{2}^{*}x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}=\frac{\left\lVert\Pi_{2}(\Pi_{u}+\Pi_{s})x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}=\frac{\left\lVert\Pi_{2}\Pi_{s}x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}\leq\frac{\left\lVert\Pi_{2}x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}=\frac{\left\lVert(I-\hat{\Pi}_{1}+\hat{\Pi}_{1}-\Pi_{1})x_{t_{i}}\right\rVert}{\left\lVert
x_{t_{i}}\right\rVert}\leq\gamma+\epsilon,$

which shows the first part of the result.

We now focus on the second part (bounding $\|x_{t}\|$). For the base case, We
either have $t_{1}=T$, thus $x_{t_{1}}=x_{T}$, in which case the stopping time
criteria is already met after Stage 1 of algorithm 1, or, if $t_{1}>T$, there
are two scenarios depending which of the two stopping criteria is violated at
time $t_{1}-1$ . If
$\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t_{1}-1}\right\rVert}{\left\lVert
x_{t_{1}-1}\right\rVert}>\gamma$, by Proposition E.2, we have $\left\lVert
x_{t_{1}-1}\right\rVert<C_{\gamma}$, where $C_{\gamma}$ is defined in (42), in
which case, we have

$\left\lVert x_{t_{1}}\right\rVert=\left\lVert
Ax_{t_{1}-1}+\eta_{t_{1}-1}\right\rVert\leq\left\lVert A\right\rVert
C_{\gamma}+C.$ (44)

In the second case, $\left\lVert x_{t_{1}-1}\right\rVert\leq\frac{C}{\delta}$,
so we have

$\left\lVert x_{t_{1}}\right\rVert<\left\lVert
A\right\rVert\frac{C}{\delta}+C.$

Therefore, to sum up the base case, we have

$\left\lVert x_{t_{1}}\right\rVert\leq\max\left\\{\left\lVert
A\right\rVert\frac{C}{\delta}+C,\left\lVert A\right\rVert
C_{\gamma}+C,\left\lVert x_{T}\right\rVert\right\\}$

For the induction case, given $\left\lVert x_{t_{i}}\right\rVert$, there are
again two cases depending on which criterion is violated at time $t_{i+1}-1$.
If $\left\lVert x_{t_{i+1}-1}\right\rVert\leq\frac{C}{\delta}$, we have

$\left\lVert x_{t_{i+1}}\right\rVert<\left\lVert
A\right\rVert\frac{C}{\delta}+C.$

Otherwise, if
$\frac{\left\lVert(I-\hat{\Pi}_{1})x_{t_{i+1}-1}\right\rVert}{\left\lVert
x_{t_{i+1}-1}\right\rVert}>\gamma$, by Proposition E.3, we obtain that

$\left\lVert
x_{t_{i+1}-1}\right\rVert<\frac{1}{\gamma^{\prime}}\left(\frac{2\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}\left\lVert
x_{i}\right\rVert+C_{\gamma}\right),$ (45)

where $\gamma^{\prime}$ is defined in Lemma E.1.

By the definition of $\omega_{i}$, the maximum of the above inequalities also
holds for all $x_{t}$ such that $t<t_{i+1}$. Therefore,

$\left\lVert x_{t_{i+1}}\right\rVert<\max\left\\{\left\lVert
A\right\rVert\frac{C}{\delta}+C,\frac{\left\lVert
A\right\rVert}{\gamma^{\prime}}\left(\frac{2\zeta_{\epsilon_{4}}(N_{2})}{1-\xi}\left\lVert
x_{i}\right\rVert+C_{\gamma}\right)+C\right\\},$

as required. Note that the same bound above also holds for all
$t_{i}<t<t_{i+1}$. Hence we get the desired result after a simple recursive
expansion. $\square$

We are now ready to bound $\left\lVert\hat{B}_{\tau}-B_{\tau}\right\rVert$.

######  Proposition E.5.

Under the premise of Theorem 4.2,

$\left\lVert\hat{B}_{\tau}-B_{\tau}\right\rVert<C_{B}\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}\delta,$

where $C_{B}:=(\zeta_{\epsilon_{1}}^{2}(A)(3\tau\left\lVert
A\right\rVert+\left\lVert B\right\rVert+\tau
C+1)+(\tau+1)C_{\Delta})\frac{\sqrt{m}}{\alpha}$.

Proof:  We have

$\displaystyle\left\lVert b_{i}-\hat{b}_{i}\right\rVert=$
$\displaystyle\frac{1}{\alpha\left\lVert
x_{t_{i}}\right\rVert}\Bigg{\lVert}P_{1}^{*}x_{t_{i}+\tau}-M_{1}^{\tau}P_{1}^{*}x_{t_{i}}-\Delta_{\tau}P_{2}^{*}x_{t_{i}}-\sum_{j=1}^{\tau-1}(M_{1}^{\tau-j}P_{1}^{*}\eta_{t_{i}+j}-\Delta_{\tau-j}P_{2}^{*}\eta_{t_{i}+j})$
$\displaystyle-\left(\hat{P}_{1}^{*}x_{t_{i}+\tau}-\hat{M}_{1}^{\tau}\hat{P}_{1}^{*}x_{t_{i}}\right)\Bigg{\rVert}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\alpha\left\lVert
x_{t_{i}}\right\rVert}\Bigg{(}\left\lVert(P_{1}-\hat{P}_{1})^{*}\left(A^{\tau}x_{t_{i}}+B_{\tau}u_{t_{i}}\right)\right\rVert+\left\lVert\sum_{j=1}^{\tau-1}M_{1}^{\tau-j}(P_{1}-\hat{P}_{1})^{*}\eta_{t_{i}+j}\right\rVert+\left\lVert
M_{1}^{\tau}P_{1}^{*}x_{t_{i}}-\hat{M}_{1}^{\tau}\hat{P}_{1}^{*}x_{t_{i}}\right\rVert$
$\displaystyle+\left\lVert\Delta_{\tau}P_{2}^{*}x_{t_{i}}\right\rVert+\sum_{j=1}^{\tau-1}\left\lVert
M_{1}^{\tau-j}P_{1}^{*}\eta_{t_{i}+j}\right\rVert+\sum_{j=1}^{\tau-1}\left\lVert\Delta_{\tau-j}P_{2}^{*}\eta_{t_{i}+j}\right\rVert\Bigg{)}.$

Here, the first term is bounded by

$\displaystyle\left\lVert(P_{1}-\hat{P}_{1})^{*}\left(A^{\tau}x_{t_{i}}+B_{\tau}u_{t_{i}}\right)\right\rVert\leq$
$\displaystyle\left\lVert P_{1}-\hat{P}_{1}\right\rVert\left(\left\lVert
A^{\tau}\right\rVert+\left\lVert A^{\tau-1}B\right\rVert\right)\left\lVert
x_{t_{i}}\right\rVert$ $\displaystyle\leq$ $\displaystyle\left\lVert
x_{t_{i}}\right\rVert\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}(\left\lVert
A\right\rVert+\left\lVert B\right\rVert)\delta,$

where in the last inequality we applied Corollary B.2 and Gelfand’s formula;
the second term is bounded by

$\displaystyle\left\lVert\sum_{j=1}^{\tau-1}M_{1}^{\tau-j}(P_{1}-\hat{P}_{1})^{*}\eta_{t_{i}+j}\right\rVert\leq$
$\displaystyle\sum_{j=1}^{\tau-1}\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-j}C\delta$
$\displaystyle<$
$\displaystyle\tau\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}C\delta,$

where we used Corollary B.2 and Gelfand’s formula.

The third term is bounded above by

$\displaystyle\left\lVert
M_{1}^{\tau}P_{1}^{*}x_{t_{i}}-\hat{M}_{1}^{\tau}\hat{P}_{1}^{*}x_{t_{i}}\right\rVert\leq$
$\displaystyle\left(\left\lVert
M_{1}^{\tau}(P_{1}-\hat{P}_{1})^{*}\right\rVert+\left\lVert(M_{1}^{\tau}-\hat{M}_{1}^{\tau})\hat{P}_{1}^{*})\right\rVert\right)\left\lVert
x_{t_{i}}\right\rVert$ $\displaystyle<$
$\displaystyle\big{(}\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}\left\lVert
A\right\rVert\delta+3\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}\delta\big{)}\left\lVert
x_{t_{i}}\right\rVert$ $\displaystyle\leq$ $\displaystyle\left\lVert
x_{t_{i}}\right\rVert\zeta_{\epsilon_{1}}(A)^{2}\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}(3\tau+1)\left\lVert
A\right\rVert\delta,$

where we applied Gelfand’s formula and Proposition 5.2. The fourth term is
bounded by

$\displaystyle\frac{\left\lVert\Delta_{\tau}\right\rVert\left\lVert
P_{2}^{*}x_{t_{i}}\right\rVert}{\left\lVert x_{t_{i}}\right\rVert}\leq$
$\displaystyle C_{\Delta}(|\lambda_{1}|+\epsilon_{1})^{\tau}(\gamma+\epsilon)$
(46) $\displaystyle\leq$ $\displaystyle
C_{\Delta}(|\lambda_{1}|+\epsilon_{1})^{\tau}\delta,$ (47)

where in (46), we used Proposition G.1 of Hu et al. [2022] and Proposition
E.4, while and (47) we need to pick stopping time $\omega$ defined by
$\gamma$:

$\gamma\leq\delta-\epsilon=(\sqrt{2k}-1)\epsilon.$ (48)

For the second to last and the last term,

$\displaystyle\frac{1}{\left\lVert
x_{t_{i}}\right\rVert}\sum_{j=1}^{\tau-1}\left\lVert
M_{1}^{\tau-j}P_{1}^{*}\eta_{t_{i}+j}\right\rVert\leq$
$\displaystyle\frac{1}{\left\lVert
x_{t_{i}}\right\rVert}\sum_{j=1}^{\tau-1}\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-j}C$
$\displaystyle<$ $\displaystyle\frac{1}{\left\lVert
x_{t_{i}}\right\rVert}\tau\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}C$
$\displaystyle<$
$\displaystyle\tau\zeta_{\epsilon_{1}}(A)\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}\delta,$
(49) $\displaystyle\frac{1}{\left\lVert
x_{t_{i}}\right\rVert}\sum_{j=1}^{\tau-1}\left\lVert\Delta_{\tau-j}P_{2}^{*}\eta_{t_{i}+j}\right\rVert\leq$
$\displaystyle\frac{1}{\left\lVert x_{t_{i}}\right\rVert}\tau
C_{\Delta}(|\lambda_{1}|+\epsilon_{1})^{\tau}C$ $\displaystyle\leq$
$\displaystyle\tau C_{\Delta}(|\lambda_{1}|+\epsilon_{1})^{\tau}\delta,$ (50)

where in (49) and (50), we need

$\frac{C}{\left\lVert x_{t_{i}}\right\rVert}<\delta.$ (51)

We notice that (51) happens with high probability since the system runs mostly
in open loop. If the above inequality is not satisfied, we can keep the system
running in open loop until it is. If the above is never satisfied, then the
system is stable. More formally, as the first stopping time $t_{1}$ stated in
Proposition E.4 is never reached, the bound for $\left\lVert
x_{t_{1}}\right\rVert$ holds for all $x_{t}$.

Finally, to bound the error of the whole matrix, we simply apply the
definition

$\displaystyle\left\lVert\hat{B}_{\tau}-B_{\tau}\right\rVert=$
$\displaystyle\max_{\left\lVert
u\right\rVert=1}\left\lVert(\hat{B}_{\tau}-B_{\tau})u\right\rVert\leq\max_{\left\lVert
u\right\rVert=1}\sum_{i=1}^{m}|u_{i}|\left\lVert\hat{b}_{i}-b_{i}\right\rVert$
$\displaystyle<$ $\displaystyle(\zeta_{\epsilon_{1}}^{2}(A)(3\tau\left\lVert
A\right\rVert+\left\lVert B\right\rVert+\tau
C+1)+(\tau+1)C_{\Delta})\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}\delta\frac{\sqrt{m}}{\alpha}.$

$\square$

##  Appendix F Proof of Main Theorem

We assumed the system $(A,B)$ is controllable. As we are stabilizing the
system in $(M^{\tau},B_{\tau})$, we need to first show that
$(M^{\tau},B_{\tau})$ is stabilizable.

######  Proposition F.1.

If $(A,B)$ is controllable, then $(\hat{M}_{1}^{\tau},R_{1}\hat{B}_{\tau})$ is
stabilizable.

Proof: Since $(A,B)$ is controllable, by the PBH test criteria, there exists
$b$, such that for all unit left eigenvector $\bar{w}$ of $A$,
$\left\lVert\bar{w}^{*}B\right\rVert>b$.

Let $w^{*}$ denote an arbitrary unit left eigenvector of $N_{1}$ with
eigenvalue $\lambda$, so

$w^{*}N_{1}=\lambda
w\quad\Rightarrow\quad(R_{1}^{*}w)^{*}A=w^{*}R_{1}Q_{1}N_{1}R_{1}=\lambda(R_{1}^{*}w)^{*}.$

Therefore, $R_{1}^{*}w$ is a left eigenvector of $A$, which leads to

$\left\lVert
w^{*}R_{1}B\right\rVert=\left\lVert(R_{1}^{*}w)^{*}B\right\rVert>\left\lVert
R_{1}^{*}w\right\rVert b.$

By the construction of $R_{1}$, as $R$ is invertible, we see that all singular
values of $R_{1}$ are nonzero. Therefore, $\left\lVert R_{1}^{*}w\right\rVert
b>0$. Correspondingly, $(N_{1},R_{1}B)$ is controllable.

We then consider the system under $\tau$-hop control. Since $w$ is the left
eigenvector of $N_{1}$, it is also the left eigenvector of $N_{1}^{\tau}$. In
particular, $w^{*}N^{\tau-1}$ is a left eigenvector of $N_{1}$. Since $N_{1}$
is the expanding portion of $A$, we derive the following lower bound:

$\left\lVert
w^{*}\left(N_{1}^{\tau-1}R_{1}B\right)\right\rVert=\left\lVert\left(w^{*}N_{1}^{\tau-1}\right)R_{1}B\right\rVert\geq\lambda_{k}^{\tau-1}\left\lVert
R_{1}^{*}w\right\rVert b.$

Recall that $B_{\tau}=P_{1}^{*}A^{\tau-1}B$.

$\displaystyle B_{\tau}$
$\displaystyle=P_{1}^{*}\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}\begin{bmatrix}N_{1}^{\tau-1}&\\\
&N_{2}^{\tau-1}\end{bmatrix}\begin{bmatrix}R_{1}B\\\ R_{2}B\end{bmatrix}$
$\displaystyle=\begin{bmatrix}P_{1}^{*}Q_{1}&P_{1}^{*}Q_{2}\end{bmatrix}\begin{bmatrix}N_{1}^{\tau-1}R_{1}B\\\
N_{2}^{\tau-1}R_{2}B\end{bmatrix}$
$\displaystyle=N_{1}^{\tau-1}R_{1}B+P_{1}^{*}Q_{2}N_{2}^{\tau-1}R_{2}B.$

By Gelfand’s Formula, $\left\lVert
N_{2}^{\tau-1}\right\rVert\leq\zeta_{\epsilon_{4}}(N_{2})\left(\lambda_{k+1}+\epsilon_{4}\right)^{\tau-1}$.
Moreover, since $E_{u}^{\perp}$ and $E_{s}$ are $\xi$-close, by Lemma A.1 of
Hu et al. [2022], $P_{1}^{*}Q_{2}\leq\sqrt{2\xi}$.

Therefore, we know that

$\displaystyle\left\lVert w^{*}B\right\rVert=$ $\displaystyle\left\lVert
w^{*}\left(N_{1}^{\tau-1}R_{1}B+P_{1}^{*}Q_{2}N_{2}^{\tau-1}R_{2}B\right)\right\rVert$
$\displaystyle\geq$ $\displaystyle|\lambda_{k}|^{\tau-1}\left\lVert
R_{1}^{*}w\right\rVert b$ $\displaystyle-\sqrt{2\xi}\left\lVert
Q_{2}\right\rVert\left\lVert R_{2}\right\rVert\left\lVert
B\right\rVert\zeta_{\epsilon_{4}}(N_{2})\left(|\lambda_{k+1}|+\epsilon_{4}\right)^{\tau-1}$
$\displaystyle>$ $\displaystyle\frac{1}{2}\left\lVert R_{1}^{*}w\right\rVert
b,$

where the last inequality requires $\epsilon_{4}<1-\lambda_{k+1}$, and

$\tau\geq\frac{\log\frac{\left\lVert R_{1}^{*}w\right\rVert
b}{2\sqrt{2\xi}\left\lVert Q_{2}\right\rVert\left\lVert
R_{2}\right\rVert\left\lVert
B\right\rVert\zeta_{\epsilon_{4}}(N_{2})}}{\log\frac{|\lambda_{k}|}{|\lambda_{k+1}|+\epsilon_{4}}}.$
(52)

Therefore, we conclude $(M_{1}^{\tau},R_{1}B_{\tau})$ is also controllable, as
$M_{1}=N_{1}$.

Lastly, we prove $\left(\hat{M}_{1}^{\tau},R_{1}\hat{B}_{\tau}\right)$ is
stabilizable. Denote $\mathcal{A}:=M_{1}^{\tau}-R_{1}B_{\tau}K_{1}$. Since
$(M_{1}^{\tau},R_{1}B_{\tau})$ is controllable, we know there exists $K_{1}$
such that $\rho\left(\mathcal{A}\right)<1$. Since an asymptotically stable
linear system is also exponentially stable, by the Lyapunov equation, for
every $k\times k$ matrix $G>0$, the following discrete Lyapunov equation has a
unique solution $H=H^{*}>0$.

$\mathcal{A}^{*}H\mathcal{A}+G-H=0$

In particular, we pick $G$ such that $\sigma_{\min}(G)>2$ and
$W(v):=\frac{1}{\min\\{1,\sigma_{\min}(H)\\}}v^{*}Hv$ is a Lyapunov function
of $\mathcal{A}$. Moreover, $W(v)$ satisfies the following criteria regarding
$\left\lVert v\right\rVert$ and forward difference with respect to
$\mathcal{A}$:

$\left\lVert v\right\rVert^{2}\leq W(v)\leq\kappa(H)\left\lVert
v\right\rVert^{2},$
$\displaystyle\begin{array}[]{rcl}W\left(\mathcal{A}v\right)-W(v)&=&\frac{v^{*}\mathcal{A}^{*}H\mathcal{A}v-v^{*}Hv}{\min\\{1,\sigma_{\min}(H)\\}}\\\
&\leq&-v^{*}Gv\\\ &<&-2\left\lVert v\right\rVert^{2},\end{array}$

where $\kappa(H)$ is the condition number of $H$.

We now consider the forward difference with respect to
$\hat{\mathcal{A}}=\hat{M}_{1}^{\tau}-R_{1}\hat{B}_{\tau}K_{1}$, as a
consequence of Jensen’s inequality, for any $\iota>0$,

$\begin{split}W\left(\hat{\mathcal{A}}v\right)=&W\left(\mathcal{A}v+\left(\hat{\mathcal{A}}-\mathcal{A}\right)v\right)\\\
\leq&(1+\iota^{2})W(\mathcal{A}v)+\left(1+\frac{1}{\iota^{2}}\right)W\left(\left(\hat{\mathcal{A}}-\mathcal{A}\right)v\right),\end{split}$

and

$\displaystyle W\left(\hat{\mathcal{A}}v\right)-W(v)$ $\displaystyle=$
$\displaystyle
W(\mathcal{A}v)-W(v)+W\left(\hat{\mathcal{A}}v\right)-W(\mathcal{A}v)$
$\displaystyle\leq$ $\displaystyle
W(\mathcal{A}v)-W(v)+\iota^{2}W(\mathcal{A}v)+\left(1+\frac{1}{\iota^{2}}\right)W\left(\left(\hat{\mathcal{A}}-\mathcal{A}\right)v\right)$
$\displaystyle<$ $\displaystyle-2\left\lVert
v\right\rVert^{2}+\iota^{2}\kappa(H)\left\lVert
v\right\rVert^{2}+\left(1+\frac{1}{\iota^{2}}\right)\left\lVert\hat{\mathcal{A}}-\mathcal{A}\right\rVert^{2}\left\lVert
v\right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle-\left\lVert
v\right\rVert^{2},$

The last inequality requires

$\iota^{2}<\frac{1}{2\kappa(H)},\qquad\left\lVert\hat{\mathcal{A}}-\mathcal{A}\right\rVert^{2}<\frac{1}{2}\frac{\iota^{2}}{1+\iota^{2}}.$

By Proposition 5.2 and E.5, we get

$\displaystyle\begin{array}[]{rcl}\left\lVert\hat{M}_{1}^{\tau}-M_{1}^{\tau}\right\rVert&<&3\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}\delta,\\\
\left\lVert\hat{B}_{\tau}-B_{\tau}\right\rVert&<&C_{B}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta.\end{array}$

So we require

$\delta<\frac{\frac{1}{6}\frac{\iota^{2}}{1+\iota^{2}}}{\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}+\left\lVert
K_{1}\right\rVert C_{B}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}}.$ (53)

When all requirements above are satisfied, by Theorem 2 of Jiang and Wang
[2002], we conclude $\left(\hat{M}_{1}^{\tau},R_{1}\hat{B}_{\tau}\right)$ is
stabilizable. $\square$

As the control matrix $\hat{K}_{1}$ is obtained by the learner, we denote
constant $\mathcal{K}$ such that
$\left\lVert\hat{K}_{1}\right\rVert<\mathcal{K}$ to be a user-defined
constant.

After the proof of the stabilizability of the system after transformation, we
are now ready to prove the main theorem.

Proof: [proof of Theorem 4.2] We shall bound each of the four terms in
$\hat{L}$ defined in (9). We first guarantee that the diagonal blocks are
stable. For the top-left block, by Proposition F.1, there exists positive-
definite matrix $\bar{U}$ such that
$\left\lVert\hat{M}_{1}^{\tau}-\hat{B}_{\tau}\hat{K}_{1}\right\rVert_{\bar{U}}=\mathcal{U}<1$,
where $\left\lVert\cdot\right\rVert_{\bar{U}}$ denotes the weighted norm
induced by $\bar{U}$. Therefore,

$\displaystyle\rho(\hat{L}_{1,1})\leq$ $\displaystyle\left\lVert
M_{1}^{\tau}+P_{1}^{*}A^{\tau-1}B\hat{K}_{1}\hat{P}_{1}^{*}P_{1}\right\rVert_{\bar{U}}$
(54) $\displaystyle\leq$ $\displaystyle\left\lVert
M_{1}^{\tau}-\hat{M}_{1}^{\tau}\right\rVert_{\bar{U}}+\left\lVert\hat{M}_{1}^{\tau}-\hat{B}_{\tau}\hat{K}_{1}\right\rVert_{\bar{U}}+\left\lVert(B_{\tau}-\hat{B}_{\tau})\hat{K}_{1}\right\rVert_{\bar{U}}+\left\lVert
B_{\tau}\hat{K}_{1}(I-\hat{P}_{1}^{*}P_{1})\right\rVert_{\bar{U}}$
$\displaystyle\leq$
$\displaystyle\kappa(\bar{U})^{\frac{1}{2}}\left(\left\lVert
M_{1}^{\tau}-\hat{M}_{1}^{\tau}\right\rVert+\left\lVert
B_{\tau}-\hat{B}_{\tau}\right\rVert\left\lVert\hat{K}_{1}\right\rVert+\left\lVert
B_{\tau}\right\rVert\left\lVert\hat{K}_{1}\right\rVert\left\lVert
I-\hat{P}_{1}^{*}P_{1}\right\rVert\right)+\mathcal{U}$ $\displaystyle\leq$
$\displaystyle 3\kappa(\bar{U})^{\frac{1}{2}}\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta+\kappa(\bar{U})^{\frac{1}{2}}C_{B}\mathcal{K}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta$
$\displaystyle+\kappa(\bar{U})^{\frac{1}{2}}\zeta_{\epsilon_{1}}(A)(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\left\lVert
B\right\rVert\mathcal{K}\delta+\mathcal{U}$ (55) $\displaystyle<$
$\displaystyle\kappa(\bar{U})^{\frac{1}{2}}(C_{B}\mathcal{K}+\zeta_{\epsilon_{1}}(A)\left\lVert
B\right\rVert\mathcal{K}+1)(\lambda_{1}|+\epsilon)^{\tau-1}\delta+\mathcal{U}$
(56) $\displaystyle<$ $\displaystyle\frac{1}{2}+\frac{\mathcal{U}}{2},$ (57)

where in (F) we apply proposition E.1 of Hu et al. [2022] and Proposition 5.2
and Proposition E.5; In (56), we require

$\frac{1}{\tau}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}>3\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}.$ (58)

In (57), we require

$\delta<\frac{(1-\mathcal{U})(\lambda_{1}|+\epsilon)^{-(\tau-1)}}{2\kappa(\bar{U})^{\frac{1}{2}}(C_{B}\mathcal{K}+\zeta_{\epsilon_{1}}(A)\left\lVert
B\right\rVert\mathcal{K}+1)}.$ (59)

For the bottom-right block, it is straightforward to see that

$\displaystyle\rho(\hat{L}_{2,2})\leq$ $\displaystyle\left\lVert
M_{2}^{\tau}\right\rVert+\left\lVert
P_{2}^{*}A^{\tau-1}\right\rVert\left\lVert
B\right\rVert\left\lVert\hat{K}_{1}\right\rVert\left\lVert\hat{P}_{1}^{*}P_{2}\right\rVert$
$\displaystyle\leq$
$\displaystyle\zeta_{\epsilon_{2}}(M_{2})(|\lambda_{k+1}|+\epsilon_{2})^{\tau}+\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}(|\lambda_{k+1}|+\epsilon_{2})^{\tau-1}\delta$
$\displaystyle<$ $\displaystyle\frac{1}{2},$

where the last inequality requires

$\tau>\frac{\log
1/(4\zeta_{\epsilon_{2}}(M_{2}))}{\log(|\lambda_{k+1}|+\epsilon_{2})},$ (60)
$\delta<\frac{1}{4\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}}(|\lambda_{k+1}|+\epsilon_{2})^{-(\tau-1)}.$ (61)

Now it suffices to bound the spectral norms of off-diagonal blocks. Note that,
by applying Proposition G.1 of Hu et al. [2022], the top right block is
bounded as

$\displaystyle\rho(\hat{L}_{2,1})\leq$
$\displaystyle\left\lVert\Delta_{\tau}\right\rVert+\left\lVert
B_{\tau}\right\rVert\left\lVert\hat{K}_{1}\right\rVert\left\lVert\hat{P}_{1}^{*}P_{2}\right\rVert$
$\displaystyle<$ $\displaystyle
C_{\Delta}(|\lambda_{1}|+\epsilon_{1})^{\tau}+\zeta_{\epsilon_{1}}(A)\left\lVert
B\right\rVert\mathcal{K}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}\delta$
$\displaystyle<$
$\displaystyle(C_{\Delta}+1)(|\lambda_{1}|+\epsilon_{1})^{\tau},$

where the last inequality requires

$\delta<\frac{1}{\zeta_{\epsilon_{1}}(A)\left\lVert
B\right\rVert\mathcal{K}}(|\lambda_{1}|+\epsilon_{1})^{-(\tau-1)}.$ (62)

The bottom-left block is bounded as

$\displaystyle\rho(\hat{L}_{1,2})\leq$ $\displaystyle\left\lVert
P_{2}^{*}A^{\tau-1}\right\rVert\left\lVert
B\right\rVert\left\lVert\hat{K}_{1}\right\rVert$ $\displaystyle<$
$\displaystyle\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}(|\lambda_{k+1}|+\epsilon_{2})^{\tau-1}.$

By Lemma 5.3 of Hu et al. [2022], we can guarantee that

$\rho\left(\hat{L}_{\tau}\right)\leq\frac{1}{2}+\frac{\mathcal{U}}{2}+\chi\left(\hat{L}_{\tau}\right)\frac{(C_{\Delta}+1)\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}}{|\lambda_{1}|+\epsilon_{1}}\left((|\lambda_{1}|+\epsilon_{1})(|\lambda_{k+1}|+\epsilon_{2})\right)^{\tau-1}<1,$
(63)

which requires

$\tau>\frac{\log\frac{(1-\mathcal{U})(|\lambda_{1}|+\epsilon_{1})(|\lambda_{k+1}|+\epsilon_{2})}{2\chi(\hat{L}_{\tau})(C_{\Delta}+1)\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}}}{\log((|\lambda_{1}|+\epsilon_{1})(|\lambda_{k+1}|+\epsilon_{2}))}.$
(64)

Note that the above constraints make sense only if
$|\lambda_{1}||\lambda_{k+1}|<1$. Therefore, when all constraints above are
satisfied, system (8) is ultimately bounded, and so is system (1).

We will then collect all the constraints. Combining (58) (60) and (64), we
obtain

$\displaystyle\tau>$ $\displaystyle\max\Bigg{\\{}\frac{\log
1/(4\zeta_{\epsilon_{2}}(M_{2}))}{\log(|\lambda_{k+1}|+\epsilon_{2})},\frac{\log\frac{(\mathcal{U}+1)(|\lambda_{1}|+\epsilon_{1})(|\lambda_{k+1}|+\epsilon_{2})}{2\chi(\hat{L}_{\tau})(C_{\Delta}+1)\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}}}{\log((|\lambda_{1}|+\epsilon_{1})(|\lambda_{k+1}|+\epsilon_{2}))},$
$\displaystyle-\frac{1}{\log(|\lambda_{1}|+\epsilon_{1})}W_{-1}\left(-\frac{\log(|\lambda_{1}|+\epsilon_{1})}{3\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}(|\lambda_{1}|+\epsilon_{1})}\right)\Bigg{\\}},$

where $W_{-1}$ denotes the non-principle branch of the Lambert-W function.
Here we utilize the fact that, for $x>\frac{1}{\log a},y=\frac{a^{*}}{x}$ is
monotone increasing with inverse function $x=-\frac{1}{\log
a}W_{-1}\left(-\frac{\log a}{y}\right)$, which can be upper bounded by Theorem
1 in Chatzigeorgiou [2013] as

$\begin{split}&\tau>\frac{\log\frac{\sqrt{\xi}}{1-\xi}+\log\frac{1}{c}+\log\chi\left(\hat{L}_{\tau}\right)+5\log\bar{\zeta}+\log\frac{\left\lVert
A\right\rVert}{|\lambda_{1}|-|\lambda_{k+1}|}+C_{\tau}}{\log|\lambda_{1}|}\\\
&=O(1),\end{split}$ (65)

where
$\bar{\zeta}:=\max\left\\{\zeta_{\epsilon_{1}}(A),\zeta_{\epsilon_{2}}(M_{2}),\zeta_{\epsilon_{2}}(N_{2}),\zeta_{\epsilon_{3}}(N_{1}^{-1})\right\\}$,
and $C_{\tau}$ is a numerical constant.

We then collect all the bound on $\gamma,\alpha,\delta$ as follows:

$\gamma>\epsilon,$ (66) $\alpha<\frac{1}{\left\lVert B\right\rVert}=O(1).$
(67)

Combining (53), (59), (61), (62) yields the following bound on $\delta$:

$\begin{split}\delta<\max&\Bigg{\\{}\frac{\frac{1}{6}\frac{\iota^{2}}{1+\iota^{2}}}{\tau\left\lVert
A\right\rVert\zeta_{\epsilon_{1}}(A)^{2}\left(|\lambda_{1}|+\epsilon_{1}\right)^{\tau-1}+\left\lVert
K_{1}\right\rVert
C_{B}(|\lambda_{1}|+\epsilon_{1})^{\tau-1}},\frac{(1-\mathcal{U})(\lambda_{1}|+\epsilon)^{-(\tau-1)}}{2\kappa(\bar{U})^{\frac{1}{2}}(C_{B}\mathcal{K}+\zeta_{\epsilon_{1}}(A)\left\lVert
B\right\rVert\mathcal{K}+1)},\\\
&\frac{1}{4\zeta_{\epsilon_{2}}(M_{2})\left\lVert
B\right\rVert\mathcal{K}}(|\lambda_{k+1}|+\epsilon_{2})^{-(\tau-1)},\frac{1}{\zeta_{\epsilon_{1}}(A)\left\lVert
B\right\rVert\mathcal{K}}(|\lambda_{1}|+\epsilon_{1})^{-(\tau-1)}\Bigg{\\}}.\end{split}$

which can be simplified to

$\delta<\frac{C_{\delta}}{\sqrt{m}\bar{\zeta}^{3}(\left\lVert
A\right\rVert+\left\lVert
B\right\rVert)}|\lambda_{1}|^{-2\tau}=O(m^{-1/2}|\lambda_{1}|^{-2\tau}),$ (68)

where $C_{\delta}$ is a constant collecting minor factors. Recall that
$\delta=\sqrt{2k}\epsilon$. Substitute the above in (17) transfers the bound
on $\delta$ into a bound on $T$:

$T>\frac{2\log\bigg{(}\frac{8k^{\frac{k}{2}+4}(n-k)\left(\frac{C}{1-|\lambda_{k+1}|}\right)\left(\frac{\sqrt{m}\bar{\zeta}^{3}(\left\lVert
A\right\rVert+\left\lVert
B\right\rVert)}{C_{\delta}|\lambda_{1}|^{-2\tau}}\right)}{\sqrt{\pi}\theta\text{gap}\epsilon}\bigg{)}}{\log|\lambda_{k}|}=O\left(k\log
k+\log(n-k)+\log m-\log\text{gap}\right)$ (69)

Different from Hu et al. [2022], we do not explicitly choose $\omega$ but let
$(\omega_{i})_{i\in\\{1,\dots,m\\}}$ be the stopping time defined in
Proposition E.4.

Combining the above constant with Theorem 5.1, we conclude that Algorithm 1
controls $x$ with the following bound:

$\begin{split}\left\lVert
x\right\rVert\leq&\exp\left(O\left(T+\sum_{i=1}^{m}\omega_{i}+\tau
m\right)\right)\\\
\leq&\exp\Bigg{(}O\Bigg{(}\frac{1}{\log|\lambda_{k}|}\Bigg{(}-\log\text{gap}+k\log
k-\log\theta+\log(n-k)\\\ &+\log|\lambda_{1}|+\log
C-\log\left(1-|\lambda_{k+1}|\right)+(1+\log|\lambda_{1}|)m\Bigg{)}\Bigg{)}\Bigg{.}\end{split}$

Assuming that the eigenvalue-related terms are constants, the algorithm
achieves $\exp(O(k\log k+\log(n-k)+m-\log\text{gap}))$ space complexity for
$\left\lVert x\right\rVert$.

This finishes the proof of Theorem 4.2. $\square$

##  Appendix G Additional Mathematical Background

In this section, we introduce some relevant math background used in this
paper. The notation of this section is independent of the rest of the paper.

######  Theorem G.1 (Davis-Kahan).

Let $A$ be an $n\times n$ Hermitian matrix, and suppose we have the following
spectral decomposition for $A$

$A=\sum_{i=1}^{n}\lambda_{i}u_{i}u_{i}^{*},$

where $\lambda_{i}$’s are the eigenvalues of $A$ such that
$\lambda_{1}>\dots>\lambda_{n}$, and $u_{i}$’s are corresponding eigenvectors.
Let $H$ be another $n\times n$ perturbation matrix, and the spectral
decomposition of $A+H$ is

$A+H=\sum_{i=1}^{n}\mu_{i}v_{i}v_{i}^{*}.$

Define

$P=\sum_{i=1}^{k}u_{i}u_{i}^{*}:=UU^{*}$

to be the orthogonal projection operator to the $k$-dimensional eigenspace
spanned by $u_{1}\dots,u_{k}$. Similarly, define
$Q=\sum_{i=1}^{k}v_{i}v_{i}^{*}:=VV^{*}$.

Suppose there exists $\delta>0$, such that $|\lambda_{i}-\mu_{j}|>\delta$ for
all $i\in\\{1,\dots,k\\},j\in\\{k+1,\dots,n\\}$, then the operator norm of
$\left\lVert P-Q\right\rVert_{op}$ satisfy

$\left\lVert P-Q\right\rVert_{op}\leq\left\lVert
P-Q\right\rVert_{F}\leq\frac{\sqrt{2k}\left\lVert
H\right\rVert_{op}}{\delta},$

where $\left\lVert\cdot\right\rVert_{F}$ denotes the Frobenius norm.

This is a relatively common theorem, and the proof detail can be found at, for
instance, Cao [2021].

######  Lemma G.2 (Gelfand’s formula).

For any square matrix $X$, we have

$\rho(X)=\lim_{t\rightarrow\infty}\left\lVert X^{t}\right\rVert^{1/t}.$

In other words, for any $\epsilon>0$, there exists a constant
$\zeta_{\epsilon}(X)$ such that

$\sigma_{\max}(X^{t})=\left\lVert
X\right\rVert\leq\zeta_{\epsilon}(X)(\rho(X)+\epsilon)^{t}.$

Further, if $X$ is invertible, let $\lambda_{\min}(X)$ denote the eigenvalue
of $X$ with minimum modulus, then

$\sigma_{\min}(X^{t})\geq\frac{1}{\zeta_{\epsilon}(X^{-1})}\left(\frac{|\lambda_{\min}(X)|}{1+\epsilon|\lambda_{\min}(X)|}\right)^{t}.$

The proof can be found in existing literatures (e.g. Horn and Johnson [2012].

##  Appendix H Indexing

For the convenience of readers, we provide a table summarizing all constants
appearing in the bounds.

Table 1: Lists of parameters and constants appearing in the bound.

Constant | Appearance | Explanation
---|---|---
$T$ | Stage 1 |  $T$ initialization steps to separate unstable components.
$\omega_{i}$ | Stage 3 |  Stopping time in each iteration to learn $B_{\tau}$.
$\alpha$ | Stage 3 |  $u_{t_{i}}=\alpha\left\lVert x_{t_{i}}\right\rVert e_{i}$ to estimate columns of $B_{\tau}$.
$\tau$ | Stage 3 |  $\tau$-steps between consecutive control inputs are injected.

Table 2: System parameters.

Constant | Appearance | Explanation
---|---|---
$C$ | Section 2 | Upper bound the magnitude of noise.
$\lambda_{i}$ | Section 3.1 |  (Complex) eigenvalue of $A$ with $i$-th largest modulus.
$\xi$ |  Definition 3.1 of Hu et al. [2022] |  $E_{u}^{\perp}$ and $E_{s}$ are $\xi$-close subspaces, i.e. $\sigma_{\min}P_{2}^{*}Q_{1}>1-\xi$.
$\zeta_{\epsilon}(\cdot)$ | Lemma G.2 | Gelfand constant for the norm of matrix exponents

Table 3: Shorthand notations (introduced in proofs).

Constant | Appearance | Explanation
---|---|---
$C_{\Delta}$ |  Proposition G.1 of Hu et al. [2022] |  $C_{\Delta}:=\zeta_{\epsilon_{1}}(M_{1})\zeta_{\epsilon_{2}}(M_{2})\frac{(2-\xi)\sqrt{2\xi}\left\lVert A\right\rVert}{1-\xi}\frac{2|\lambda_{k+1}|}{|\lambda_{1}+\epsilon_{1}-|\lambda_{k+1}|-\epsilon_{2}}$.
$C_{\gamma}$ |  (42) in the proof of Proposition E.2 |  $C_{\gamma}:=\frac{\zeta_{\epsilon_{4}}(N_{2})C}{\gamma^{\prime}(1-\xi)}\frac{1}{1-(|\lambda_{k+1}|+\epsilon_{4})}$.
$C_{B}$ | Proposition E.5 |  $(\zeta_{\epsilon_{1}}^{2}(A)(\left\lVert A\right\rVert+\left\lVert B\right\rVert+(C+2)\tau+1)+(\tau+1)C_{\Delta})\frac{\sqrt{m}}{\alpha}$.
$\mathcal{K}$ | Stage 4 |  Upper bounding $\left\lVert\hat{K}_{1}\right\rVert$ chosen by the user.
$\mathcal{U}$ | Stage 4 |  Upper bounding $\left\lVert\hat{M}_{1}^{\tau}-\hat{B}_{\tau}\hat{K}_{1}\right\rVert_{\bar{U}}$.
gap | Theorem 4.2 |  $\text{gap}:=\left|\prod_{m_{1}\neq m_{2}}(\lambda_{m_{1}}^{-1}-\lambda_{m_{2}}^{-1})\right|,m_{1},m_{2}\in\\{1,\dots,k\\}$.