# A note on the smallest eigenvalue of the empirical covariance of causal
Gaussian processes

Ingvar Ziemann

###### Abstract

We present a simple proof for bounding the smallest eigenvalue of the
empirical covariance in a causal Gaussian process. Along the way, we establish
a one-sided tail inequality for Gaussian quadratic forms using a causal
decomposition. Our proof only uses elementary facts about the Gaussian
distribution and the union bound. We conclude with an example in which we
provide a performance guarantee for least squares identification of a vector
autoregression.

##  1 Introduction

We consider a causal Gaussian process
$X_{0:T-1}=(X_{0}^{\mathsf{T}},\dots,X_{T-1}^{\mathsf{T}})^{\mathsf{T}}$
evolving on $\mathbb{R}^{d}$. In this note we provide an elementary proof of
the fact that the empirical covariance:

$\displaystyle\widehat{\Sigma}_{X}\triangleq\frac{1}{T}\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}$
(1.1)

is never much smaller than its (conditional) expectation. Analyzing the lower
tail of (1.1) has been the subject of a number of recent papers as it is
crucial to characterize the rate of convergence in linear system
identification [8, 2, 9, 12, 6, 11, 3, 13]. In these references, a number of
elegant but rather advanced techniques can be found to control the lower tail
of (1.1) for various models (but mainly linear dynamical systems). Of these,
the perhaps most well-known being the adaptation of the small-ball method of
[5] by [8]. Our aim with this note is to give a more accessible proof of these
results in the Gaussian setup, but which also easily extends to any causal
Gaussian process (Theorem 3.2), e.g., ARMA processes (Section 4). The main
idea here is based on [17], which shows that one can often encode such "small-
ball behavior", even for highly dependent processes, by a one-sided
exponential inequality (Theorem 3.1).

#### Motivation

The primary reason for our interest (and that of the above-mentioned
references) in (1.1) is the fact that in the linear regression model:

$\displaystyle Y_{t}$ $\displaystyle=A_{\star}X_{t}+V_{t}$ $\displaystyle
t=0,\dots,T-1$ $\displaystyle(V_{t}\textnormal{ noise})$

the error of the least squares estimator $\widehat{A}$ of the unknown
parameter $A_{\star}$ can be expressed as:

$\displaystyle\widehat{A}-A_{\star}$ (1.2)
$\displaystyle=\left[\left(\sum_{t=0}^{T-1}V_{t}X_{t}^{\mathsf{T}}\right)\left(\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right)^{-1/2}\right]\left(\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right)^{-1/2}.$

The leftmost term of (1.2) (in square brackets) can be shown to be (almost)
time-scale invariant in many situations. For instance, if the noise
$V_{0:T-1}$ is a sub-Gaussian martingale difference sequence with respect to
the filtration generated by the covariates $X_{0:T-1}$, one can invoke the so-
called self-normalized martingale theorem of [7, 1] to show this. Whenever
this is the case, the dominant term in the rate of convergence of the least
squares estimator is
$\left(\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right)^{-1/2}$. Thus, providing
control of the smallest eigenvalue of (1.1) effectively yields control of the
rate of convergence of the least squares estimator in many situations. Put
differently, the smallest eigenvalue of (1.1) quantifies the notion of
persistency of excitation often encountered in system identification [4, 16].
We also remark that two-sided bounds are often unsatisfactory for this
purpose, and will indeed become hopeless for processes that are not strictly
stable. Nevertheless, a one-sided bound is often still possible.

#### Notation

For an integer $n\in\mathbb{N}$, we define the shorthand
$[n]\triangleq\\{1,\dots,n\\}$. The Euclidean norm on $\mathbb{R}^{d}$ is
denoted $\|\cdot\|$, and the unit sphere in $\mathbb{R}^{d}$ is denoted
$\mathbb{S}^{d-1}$. The identity matrix acting on $\mathbb{R}^{d}$ is denoted
$I_{d}$. The trace of a matrix $M\in\mathbb{R}^{d_{1}\times d_{2}}$ is denoted
$\operatorname{tr}M$, its tranpose $M^{\mathsf{T}}$, and its operator norm is
$\|M\|_{\mathsf{op}}\triangleq\sup_{v\in\mathbb{S}^{d_{2}-1}}\|Mv\|$. If a
square matrix $M\in\mathbb{R}^{d\times d}$ further is positive semidefinite,
we also write $\lambda_{\min}(M)$ for its smallest eigenvalue and
$\lambda_{\max}(M)$ for its largest. For $i,j\in\mathbb{N}$ with $i<j$, and a
sequence of vectors $x_{i},\dots,x_{j}\in\mathbb{R}^{d}$ we set
$(v_{i}^{\mathsf{T}},\dots,v_{j}^{\mathsf{T}})^{\mathsf{T}}\triangleq
v_{i:j}\in\mathbb{R}^{(j-i+1)d}$. If $M_{i},i\in[N]$ are matrices, the matrix
$\operatorname{blkdiag}(M_{1},\dots,M_{n})$ denotes the block matrix with the
$M_{i}$ on its main diagonal ordered from $M_{1}$ (top-left) to $M_{n}$
(bottom-right) and all other entries identically zero. Expectation (resp.
probability) with respect to all the randomness of the underlying probability
space is denoted by $\mathbf{E}$ (resp. $\mathbf{P}$). Finally, the shorthand
$W\sim N(0,I_{d})$ introduces $W$ as a mean zero Gaussian random vector in
$\mathbb{R}^{d}$ with covariance matrix $I_{d}$.

##  2 Preliminaries

Fix two integers $T$ and $k$ such that $T/k\in\mathbb{N}$. We consider a
($k$)-causal Gaussian process
$X_{0:T-1}=(X_{0}^{\mathsf{T}},\dots,X_{T-1}^{\mathsf{T}})^{\mathsf{T}}$
evolving on $\mathbb{R}^{d}$. More precisely, we assume the existence of a
Gaussian white process evolving on $\mathbb{R}^{p}$, $W_{0:T-1}\sim
N(0,I_{pT})$, and a (block-) lower triangular matrix
$\mathbf{L}\in\mathbb{R}^{dT\times pT}$ such that
$X_{0:T-1}=\mathbf{L}W_{0:T-1}$. We say that $X_{0:T-1}$ is $k$-causal if the
matrix $\mathbf{L}$ has the form:

$\displaystyle\mathbf{L}=\begin{bmatrix}\mathbf{L}_{1,1}&0&0&0&0\\\
\mathbf{L}_{2,1}&\mathbf{L}_{2,2}&0&0&0\\\
\mathbf{L}_{3,1}&\mathbf{L}_{3,2}&\mathbf{L}_{3,3}&0&0\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
\mathbf{L}_{T/k,1}&\dots&\dots&\dots&\dots\mathbf{L}_{T/k,T/k}\end{bmatrix}=\begin{bmatrix}\mathbf{L}_{1}\\\
\mathbf{L}_{2}\\\ \mathbf{L}_{3}\\\ \vdots\\\ \mathbf{L}_{T/k}\end{bmatrix}$

where each $\mathbf{L}_{ij}\in\mathbb{R}^{dk\times
pk},i,j\in[T/k]\triangleq\\{1,2,\dots,T/k\\}$. Obviously, every $1$-causal
process is $k$-causal for every $k\in\mathbb{N}$ (for appropriate $T$). To
every $k$-causal Gaussian process, we also associate a decoupled random
process
$\tilde{X}_{0:T-1}=\mathrm{blkdiag}(\mathbf{L}_{11},\dots,\mathbf{L}_{T/k,T/k})W_{0:T-1}$.
This decoupled process will effectively dictate our lower bound, and we will
show under relatively mild assumptions that

$\displaystyle\lambda_{\min}\left(\frac{1}{T}\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right)\gtrsim\lambda_{\min}\left(\frac{1}{T}\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)$

with probability that approaches $1$ at an exponential rate in the sample size
$T$.

Our proof will make heavy use of the following lemma.

######  Lemma 2.1.

Fix $x\in\mathbb{R}^{n}$ and let $W\sim N(0,I_{m})$. For any positive
semidefinite $Q\in\mathbb{R}^{(n+m)\times(n+m)}$ of the form
$Q=\begin{bmatrix}Q_{11}&Q_{12}\\\ Q_{21}&Q_{22}\end{bmatrix}$ and any
$\lambda\geq 0$ we have that:

$\displaystyle\mathbf{E}\exp\left(-\lambda\begin{bmatrix}x\\\
W\end{bmatrix}^{\mathsf{T}}\begin{bmatrix}Q_{11}&Q_{12}\\\
Q_{21}&Q_{22}\end{bmatrix}\begin{bmatrix}x\\\
W\end{bmatrix}\right)\leq\exp\left(-\lambda\operatorname{tr}Q_{22}+\frac{\lambda^{2}}{2}\operatorname{tr}Q_{22}^{2}\right).$

In principle, we will use Lemma 2.1 to "throw away" the inter-block
correlation in $\mathbf{L}$, thereby reducing the process $X_{0:T-1}$ to
$\tilde{X}_{0:T-1}$, which is easier to analyze.

##  3 Results

Repeated application of Lemma 2.1 to the process
$X_{0:T-1}=\mathbf{L}W_{0:T-1}$ yields our main result.

######  Theorem 3.1.

Fix an integer $k\in\mathbb{N}$, let $T\in N$ be divisible by $k$ and suppose
$X_{0:T-1}$ is a $k$-causal Gaussian process. Fix also a matrix
$\Delta\in\mathbb{R}^{d^{\prime}\times d}$. Then for every $\lambda\geq 0$:

$\mathbf{E}\exp\left(-\lambda\sum_{t=0}^{T-1}\|\Delta
X_{t}\|_{2}^{2}\right)\leq\exp\Bigg{(}-\lambda\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]\\\
+\frac{\lambda^{2}}{2}\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]^{2}\Bigg{)}.$

It is worth pointing out that
$\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]=\sum_{t=0}^{T-1}\mathbf{E}\|\Delta\tilde{X}_{t}\|_{2}^{2}.$
Hence Theorem 3.1 effectively passes the expectation inside the exponential at
the cost of working with the possibly less excited process $\tilde{X}_{0:T-1}$
and a quadratic correction term. Note also that the assumption that $T$ is
divisible by $k$ is not particularly important. If not, let $T^{\prime}$ be
the largest integer such that $T^{\prime}/k\in\mathbb{N}$ and $T^{\prime}\leq
T$ and apply the result with $T^{\prime}$ in place of $T$.

The significance of Theorem 3.1 is demonstrated by the following simple
calculation. Namely, for any fixed $\Delta\in\mathbb{R}^{d^{\prime}\times
d}\setminus\\{0\\}$ and $\lambda\geq 0$ we have that:

$\displaystyle\mathbf{P}\left(\sum_{t=0}^{T-1}\|\Delta
X_{t}\|^{2}\leq\frac{1}{2}\sum_{t=0}^{T-1}\mathbf{E}\|\Delta\tilde{X}_{t}\|^{2}\right)$
(3.1)
$\displaystyle\leq\mathbf{E}\exp\left(\frac{\lambda}{2}\sum_{t=0}^{T-1}\mathbf{E}\|\Delta\tilde{X}_{t}\|^{2}-\lambda\sum_{t=0}^{T-1}\|\Delta
X_{t}\|^{2}\right)\quad(\textnormal{Chernoff})$
$\displaystyle\leq\exp\Bigg{(}-\frac{\lambda}{2}\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]$
$\displaystyle+\frac{\lambda^{2}}{2}\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]^{2}\Bigg{)}\quad(\textnormal{\lx@cref{creftypecap~refnum}{thm:expineq}})$
$\displaystyle=\exp\left(-\frac{\left(\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]\right)^{2}}{8\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]^{2}}\right)$

by optimizing $\lambda$ in the last line. The point is that the bound (3.1)
decays exponentially in $T$ as long as blocks on the diagonal of $\mathbf{L}$
have order constant condition number. In most applications, this can typically
be achieved by a judicious choice of $k$. This leads us to define the
following parameter:

$\psi_{k}\triangleq\inf_{\Delta\in\mathbb{R}^{d^{\prime}\times
d}\setminus\\{0\\}}\left\\{\frac{\left(\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]\right)^{2}}{T\sum_{j=1}^{T/k}\operatorname{tr}\left[\mathbf{L}_{j,j}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{j,j}\right]^{2}}\right\\}.$
(3.2)

Here, (3.2) is essentially a moment equivalence condition [Cf. 17, Definition
4.1]. Note that $\psi_{k}$ depends implictly on $k$ since the block-length
dictates the covariance structure of $\tilde{X}_{0:T-1}$. We remark that if
all the diagonal blocks of $\mathbf{L}$ are identical, the process
$\tilde{X}_{0:T-1}$ has period $k$. Hence in which case by Cauchy-Schwarz:
$\psi_{k}\geq 1/k$. This is for instance true for any linear time invariant
dynamics and thus, for these, we always have at least $\psi_{k}\geq 1/k$.
Returning to our over-arching goal of providing control of the smallest
eigenvalue of the empirical covariance matrix (1.1), we now combine (3.1)
(using $d^{\prime}=1$) with a union bound.

######  Theorem 3.2.

Suppose
$\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)>0$.
Under the hypotheses of Theorem 3.1 we have that:

$\mathbf{P}\left(\lambda_{\min}\left(\frac{1}{T}\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right)\leq\lambda_{\min}\left(\frac{1}{8T}\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)\right)\\\
\leq\Bigg{(}16\sqrt{1+\frac{\psi_{k}T\lambda_{\max}(\mathbf{E}[X_{0:T-1}X_{0:T-1}^{\mathsf{T}}])}{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)}}\sqrt{\frac{\lambda_{\max}\left(\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}\right)}{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)}}\Bigg{)}^{d}\exp\left(\frac{-\psi_{k}T}{8}\right).$
(3.3)

Note that we always have—although this is far from sharp:111Write $\mathbf{L}$
in terms of $T$-many block rows to express $\mathbf{L}^{\mathsf{T}}\mathbf{L}$
as sums of products of these rows and then apply the triangle inequality. An
improvement on this estimate is possible for instance if the process is a
stable linear system, see [3].

$\frac{\lambda_{\max}(\mathbf{E}[X_{0:T-1}X_{0:T-1}^{\mathsf{T}}])}{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)}\leq\frac{\sum_{t=0}^{T-1}\lambda_{\max}\left(\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right)}{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)}.$
(3.4)

As long as
$\sum_{t=0}^{T-1}\lambda_{\max}\left(\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right)\Big{/}\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)=O(\mathrm{poly}(T))$
and $\psi_{k}=O(T^{\alpha})$ for some $\alpha\in(0,1)$, Theorem 3.2 gives a
nontrivial lower bound on the smallest eigenvalue of (1.1) which holds with
probabilty approaching $1$ at an exponential rate in the sample size $T$.

##  4 Example: Identification of Vector Autoregressions

We consider linear time-invariant dynamics of the form:

$Z_{t}=\sum_{l=1}^{L}A_{l}Z_{t-l}+HW_{t},\qquad Z_{-L:-1}=0\qquad
t=0,1,2,\dots$ (4.1)

where each $A_{l}\in\mathbb{R}^{d\times d}$ with $l\in[L]$ and
$H\in\mathbb{R}^{d\times p}$.

Let $\kappa\triangleq\left\\{\inf
k:\det\left(\sum_{t=0}^{k-1}\mathbf{E}Z_{t:t-L+1}Z_{t:t-L+1}^{\mathsf{T}}\right)\neq
0\right\\}.$ Set also
$\Gamma_{k}=\frac{1}{k}\sum_{t=0}^{k-1}\mathbf{E}Z_{t:t-L+1}Z_{t:t-L+1}^{\mathsf{T}}$
and let us define $A\in\mathbb{R}^{dL\times dL}$ by:

$\displaystyle A$
$\displaystyle\triangleq\begin{bmatrix}A_{1}&A_{2}&\dots&\dots&A_{L}\\\
I_{d}&0&\dots&\dots&0\\\ 0&I_{d}&0&\dots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\ 0&\dots&0&I_{d}&0\end{bmatrix}.$ (4.2)

With these definitions in place, we may invoke Theorem 3.2 to control the
empirical covariance of $X_{t}=Z_{t:t-L+1}$. We will subsequently use the
lower bound of Theorem 3.2 as an ingredient toward obtaining a non-asymptotic
guarantee for least squares identification of vector autoregressions of order
$L$.

######  Corollary 4.1.

Fix an integer $k\geq\kappa$ such that $T/k\in\mathbb{N}$. If $Z_{0:T-1}$ is
given by (4.1), we have that:

$\mathbf{P}\left(\lambda_{\min}\left(\frac{1}{T}\sum_{t=0}^{T-1}Z_{t:t-L+1}Z_{t:t-L+1}^{\mathsf{T}}\right)\leq\frac{1}{8}\lambda_{\min}\left(\Gamma_{k}\right)\right)\\\
\leq\left(\frac{32T^{3/2}\sum_{t=0}^{T-1}\left\|HH^{\mathsf{T}}\right\|_{\mathsf{op}}\left\|A^{t-1}(A^{t-1})^{\mathsf{T}}\right\|_{\mathsf{op}}}{\sqrt{k}\lambda_{\min}\left(\Gamma_{k}\right)}\right)^{d}\times\exp\left(\frac{-T}{8k}\right).$
(4.3)

The proof of the above corollary follows immediately by Theorem 3.2, Lemma 5.1
combined with the observation that we may choose $\psi_{k}\geq 1/k$.

A few remarks are in order. First, (4.3) provides nontrivial control of the
smallest eigenvalue of the empirical covariance of any ARMA process that
satsifies: 1. the matrix $A$ in (4.2) satisfies $\rho(A)\leq 1$ (marginal
stability); and 2. $\kappa<\infty$ (controllability). The second condition can
be further simplified if
$\mathbf{E}(HW_{t})(HW_{t})^{\mathsf{T}}=HH^{\mathsf{T}}\succ 0$. Indeed, in
this case, by observing that $A$ has downshift action, we see that an
excitation of $\kappa=L$ is sufficient. Finally, we note that when specialized
to first order processes, our result essentially recover [8, Section D.1]—our
failure probabilities match with theirs up to logarithmic factors.

We now provide an identification guarantee for recovering the parameters
$A_{1:L}\triangleq A_{\star}$. The argument rests on the decomposition (1.2)
and then combines Corollary 4.1 with a self-normalized martingale bound due to
[7, 1].

######  Theorem 4.1.

Fix $\delta\in(0,1)$, an integer $k\geq\kappa$ such that $T/k\in\mathbb{N}$.
Let $Z_{0:T-1}$ be given by (4.1) and suppose further that

$\frac{T}{8k}\geq
d\log\left(\frac{32T^{3/2}\sum_{t=0}^{T-1}\left\|HH^{\mathsf{T}}\right\|_{\mathsf{op}}\left\|A^{t-1}(A^{t-1})^{\mathsf{T}}\right\|_{\mathsf{op}}}{\sqrt{k}\lambda_{\min}\left(\Gamma_{k}\right)}\right)+\log(1/\delta).$
(4.4)

It then holds on an event of probability at least $1-2\delta$ that the least
squares estimator for $A_{\star}=A_{1:L}$ achieves:

$\|\widehat{A}-A_{\star}\|_{\mathsf{op}}\leq\frac{32\|H\|_{\mathsf{op}}}{\sqrt{T\lambda_{\min}(\Gamma_{k})}}\sqrt{dL\log
C_{\mathsf{SYS}}(T,k)+2d\log 5+2\log\frac{1}{\delta}}$

where $C_{\mathsf{SYS}}(T,k)\triangleq
1+\frac{32\left(\sum_{t=1}^{T}\lambda_{\max}(\mathbf{E}X_{t}X_{t}^{\mathsf{T}})\right)^{2}}{\left(\lambda_{\min}\left(\sum_{t=1}^{k}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)\right)^{2}}$.

We are thus able to recover the main result of [8] and extend it to higher
order lags ($L>1$) with slightly modified (logarithmic) dependencies on system
parameters (and a slightly improved dependency on $\delta$).

##  5 Proofs

#### Proof of Theorem 3.1

Let $\mathbf{E}_{T-k-1}$ denote conditioning with respect to $X_{0:T-k-1}$. By
repeated use of the tower property we have that:

$\displaystyle\mathbf{E}\exp\left(-\lambda\sum_{t=0}^{T-1}\|\Delta
X_{t}\|_{2}^{2}\right)\leq\mathbf{E}\exp\left(-\lambda\sum_{t=0}^{k-1}\|\Delta
X_{t}\|_{2}^{2}\right)\times$ (5.1)
$\displaystyle\dots\times\mathbf{E}_{T-k-1}\exp\left(-\lambda\sum_{t=T-k}^{T-1}\|\Delta
X_{t}\|_{2}^{2}\right).$

We will bound each conditional expectation in (5.1) separately. Observe that

$\displaystyle\sum_{t=T-k}^{T-1}\|\Delta X_{t}\|_{2}^{2}=\begin{bmatrix}\Delta
X_{T-k}\\\ \vdots\\\ \Delta
X_{T-1}\end{bmatrix}^{\mathsf{T}}\begin{bmatrix}\Delta X_{T-k}\\\ \vdots\\\
\Delta X_{T-1}\end{bmatrix}$
$\displaystyle=W_{T-k:T-1}^{\mathsf{T}}\mathbf{L}_{T/k}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{T/k}W_{T-k:T-1}$

In light of Lemma 2.1 we have that:

$\mathbf{E}_{T-k-1}\exp\left(-\lambda\sum_{t=T-k}^{T-1}\|\Delta
X_{t}\|_{2}^{2}\right)\\\
\leq\exp\Bigg{(}-\lambda\operatorname{tr}\left[\mathbf{L}_{T/k,T/k}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{T/k,T/k}\right]\\\
+\frac{\lambda^{2}}{2}\operatorname{tr}\left[\mathbf{L}_{T/k,T/k}^{\mathsf{T}}\mathrm{blkdiag}(\Delta^{\mathsf{T}}\Delta)\mathbf{L}_{T/k,T/k}\right]^{2}\Bigg{)}.$

Repeatedly applying Lemma 2.1 as above yields the result. $\blacksquare$

#### Proof of Theorem 3.2

Let $\mathcal{N}_{\varepsilon}$ be an optimal $\varepsilon$-cover of the unit
sphere $\mathbb{S}^{d-1}$. We begin with the following observation which is
true for any $v\in\mathbb{S}^{d-1}$ and $v_{i}\in\mathcal{N}_{\varepsilon}$:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}v^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}v$
$\displaystyle\geq\frac{1}{2T}\sum_{t=0}^{T-1}v^{\mathsf{T}}_{i}X_{t}X_{t}^{\mathsf{T}}v_{i}-\frac{1}{2T}\sum_{t=0}^{T-1}(v-v_{i})^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}(v-v_{i}).$

The rest of the proof consists of lower bounding the first term uniformly over
$\mathcal{N}_{\varepsilon}$ and showing that the second term is of smaller
order. To this end we now fix a multiplier $q\in(1,\infty)$. We define the
events (i.e. $\Delta=v^{\mathsf{T}}$):

$\displaystyle\mathcal{E}_{1}$
$\displaystyle=\bigcup_{v\in\mathcal{N}_{\varepsilon}}\left\\{\frac{1}{T}\sum_{t=0}^{T-1}v^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}v\leq\frac{1}{2T}\sum_{t=0}^{T-1}\mathbf{E}v^{\mathsf{T}}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}v\right\\}$
(5.2) $\displaystyle\mathcal{E}_{2}$
$\displaystyle=\Bigg{\\{}\left\|\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}\geq
2q\times\left\|\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}\Bigg{\\}}.$

for any $v$, it is true on the complement of
$\mathcal{E}=\mathcal{E}_{1}\cup\mathcal{E}_{2}$ that for every
$v_{i}\in\mathcal{N}_{\varepsilon}$:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}v^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}v$
$\displaystyle\geq\frac{1}{2T}\sum_{t=0}^{T-1}v^{\mathsf{T}}_{i}X_{t}X_{t}^{\mathsf{T}}v_{i}-\frac{1}{2T}\sum_{t=0}^{T-1}(v-v_{i})^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}(v-v_{i})$
$\displaystyle\geq\frac{1}{4T}\sum_{t=0}^{T-1}\mathbf{E}v_{i}^{\mathsf{T}}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}v_{i}-\frac{q\varepsilon^{2}}{T}\left\|\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}$

where $v-v_{i}$ has norm at most $\varepsilon$ for some choice of $v_{i}$ by
the covering property. For this choice we have that:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}v^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}v$
$\displaystyle\geq\frac{1}{8T}\sum_{t=0}^{T-1}v_{i}^{\mathsf{T}}\mathbf{E}[\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}]v_{i}$

as long as:

$\displaystyle\varepsilon^{2}\leq\frac{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)}{8q\lambda_{\max}\left(\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}\right)}.$

To finish the proof, it suffices to estimate the failure probabilities
$\mathbf{P}(\mathcal{E}_{1})$ and $\mathbf{P}(\mathcal{E}_{2})$. By (3.1), a
volumetric argument [see e.g. 15, Example 5.8] (which controls the cardinality
of $\mathcal{N}_{\varepsilon}$) and our particular choice of $\varepsilon$ we
have:

$\displaystyle\mathbf{P}(\mathcal{E}_{1})$
$\displaystyle\leq\left(1+\frac{2}{\varepsilon^{2}}\right)^{d}\exp\left(\frac{-\psi_{k}T}{8}\right)$
$\displaystyle\leq\left(8\sqrt{\frac{q\lambda_{\max}\left(\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}\right)}{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}\tilde{X}_{t}\tilde{X}_{t}^{\mathsf{T}}\right)}}\right)^{d}\exp\left(\frac{-\psi_{k}T}{8}\right).$

The event $\mathcal{E}_{2}$ is controlled by (5.6) which yields:

$\displaystyle\mathbf{P}(\mathcal{E}_{2})\leq
5^{d}\exp\left(\frac{-(q-1)\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)}{8\lambda_{\max}(\mathbf{L}^{\mathsf{T}}\mathbf{L})}\right).$

By choosing

$q=1+\frac{\psi_{k}T\lambda_{\max}(\mathbf{L}^{\mathsf{T}}\mathbf{L})}{\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)},$

the result holds on the complement of $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ and
thus also holds with the desired probability. $\blacksquare$

###  5.1 Proofs related to AR processes

######  Lemma 5.1.

For $Z_{0:T-1}$ given by (4.1) and $X_{t}=Z_{t:t-L+1}$ we have that:

$\displaystyle\left\|\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}^{T}\right\|_{\mathsf{op}}\leq
T\|HH^{\mathsf{T}}\|_{\mathsf{op}}\sum_{k=0}^{T-1}\left\|A^{T-k-1}(A^{T-k-1})^{\mathsf{T}}\right\|_{\mathsf{op}}$

###### Proof.

We have that $X_{t+1}=AX_{t}+BW_{t}$ where
$B=\begin{bmatrix}H&0&\dots&0\end{bmatrix}^{\mathsf{T}}$. Notice now that
$X_{t}=\sum_{k=0}^{t-1}A^{t-k-1}BW_{k}$. It is straightforward to verify that
for $t\in[T]$:

$\displaystyle\mathbf{E}X_{t}X_{t}^{\mathsf{T}}=\sum_{k=0}^{t-1}A^{t-k-1}B\mathbf{E}[W_{k}W_{k}^{\mathsf{T}}]B^{\mathsf{T}}(A^{t-k-1})^{\mathsf{T}}.$

Since each $W_{k}$ has identity covariance, we thus also have that:

$\displaystyle\sum_{t=0}^{T-1}\left\|\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}\leq\sum_{t=0}^{T-1}\left\|\sum_{k=0}^{t-1}A^{t-k-1}BB^{\mathsf{T}}(A^{t-k-1})^{\mathsf{T}}\right\|_{\mathsf{op}}$
(5.3) $\displaystyle\leq
T\|BB^{\mathsf{T}}\|_{\mathsf{op}}\sum_{k=0}^{T-1}\left\|A^{T-k-1}(A^{T-k-1})^{\mathsf{T}}\right\|_{\mathsf{op}}.$

The result follows by noticing that
$\|BB^{\mathsf{T}}\|_{\mathsf{op}}=\left\|HH^{\mathsf{T}}\right\|_{\mathsf{op}}$.
∎

#### Proof of Theorem 4.1

Let $V_{t}=HW_{t}$ and note that this is $\|H\|_{\mathsf{op}}^{2}$-sub-
Gaussian. If we combine (1.2) with Corollary 4.1 we find that as long as (4.4)
holds we have that with probability at least $1-\delta$:

$\displaystyle\|\widehat{A}-A_{\star}\|_{\mathsf{op}}\leq\frac{16}{\sqrt{T\lambda_{\min}(\Gamma_{k})}}\left\|\left(\sum_{t=0}^{T-1}V_{t}X_{t}^{\mathsf{T}}\right)\left(\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}+\frac{T}{16}\Gamma_{k}\right)^{-1/2}\right\|_{\mathsf{op}}.$

Let now $v_{1:5^{d}}$ be an $\varepsilon$-net of the $d$-dimensional unit
sphere with $\varepsilon=0.5$. Such a net exists by virtue of a standard
volumetric argument [see e.g 15, Example 5.8]. Discretizing the operator norm
yields:

$\left\|\left(\sum_{t=1}^{T}V_{t}X_{t}^{\mathsf{T}}\right)\left(\frac{T}{16}\Gamma_{k}+\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}\right)^{-1/2}\right\|_{\mathsf{op}}^{2}\\\
\leq 2\sup_{i\in[5^{d}]}\left\lVert
v^{\mathsf{T}}_{i}\left(\sum_{t=1}^{T}V_{t}X_{t}^{\mathsf{T}}\right)\left(\frac{T}{16}\Gamma_{k}+\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}\right)^{-1/2}\right\rVert^{2}.$

If we combine Theorem 1 of [1] with a union bound over the $5^{d}$ elements
above we arrive at that with probability at least $1-\delta$:

$2\sup_{i\in[5^{d}]}\left\lVert
v_{i}^{\mathsf{T}}\left(\sum_{t=1}^{T}V_{t}X_{t}^{\mathsf{T}}\right)\left(\frac{T}{16}\Gamma_{k}+\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}\right)^{-1/2}\right\rVert\\\
\leq\Bigg{(}4\sigma^{2}\log\left(\det\left(I+\frac{16}{T}\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}\Gamma_{k}^{-1}\right)\right)+8d\sigma^{2}\log
5+8\sigma^{2}\log\frac{1}{\delta}\Bigg{)}^{1/2}$

where $\sigma=\|H\|_{\mathsf{op}}$.

To finish the proof, it remains to control
$\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}$. However, part of the proof of Theorem
3.2 actually reveals that on the same event as above we have that

$\left\|\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}\leq\frac{2T\left(\sum_{t=1}^{T}\lambda_{\max}(\mathbf{E}X_{t}X_{t}^{\mathsf{T}})\right)^{2}}{k\lambda_{\min}\left(\sum_{t=1}^{T}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)}.$

Hence

$\left\|\frac{16}{T}\sum_{t=1}^{T}X_{t}X_{t}^{\mathsf{T}}\Gamma_{k}^{-1}\right\|_{\mathsf{op}}\leq\frac{32\left(\sum_{t=1}^{T}\lambda_{\max}(\mathbf{E}X_{t}X_{t}^{\mathsf{T}})\right)^{2}}{\left(\lambda_{\min}\left(\sum_{t=1}^{k}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]\right)\right)^{2}}$

and the result follows by bounding the determinant above by $C_{\mathsf{SYS}}$
(an upper bound on the relevant largest eigenvalue) raised to the power of its
dimension—$dL$. $\blacksquare$

###  5.2 Facts about the Gaussian distribution

We begin by stating a version of Lemma 2.1 in [10]. To make this note self-
contained, we provide a short proof.

######  Lemma 5.2.

Fix $x\in\mathbb{R}^{n}$ and let $W\sim N(0,I_{m})$. For any positive
semidefinite $Q\in\mathbb{R}^{(n+m)\times(n+m)}$ of the form
$Q=\begin{bmatrix}Q_{11}&Q_{12}\\\ Q_{21}&Q_{22}\end{bmatrix}$ and any
$\lambda\geq 0$ we have that:

$\displaystyle\mathbf{E}\exp\left(-\lambda\begin{bmatrix}x\\\
W\end{bmatrix}^{\mathsf{T}}\begin{bmatrix}Q_{11}&Q_{12}\\\
Q_{21}&Q_{22}\end{bmatrix}\begin{bmatrix}x\\\
W\end{bmatrix}\right)\leq\left(\det(I+2\lambda Q_{22})\right)^{-1/2}.$ (5.4)

###### Proof.

Let $Q_{\lambda}\triangleq\begin{bmatrix}Q_{11}&Q_{12}\\\
Q_{21}&Q_{22}-(2\lambda)^{-1}I_{m}\end{bmatrix}$. We then have:

$\mathbf{E}\exp\left(-\lambda\begin{bmatrix}x\\\
W\end{bmatrix}^{\mathsf{T}}\begin{bmatrix}Q_{11}&Q_{12}\\\
Q_{21}&Q_{22}\end{bmatrix}\begin{bmatrix}x\\\ W\end{bmatrix}\right)\\\
=\int_{\mathbb{R}^{m}}\exp\left(-\lambda\begin{bmatrix}x\\\
w\end{bmatrix}^{\mathsf{T}}\begin{bmatrix}Q_{11}&Q_{12}\\\
Q_{21}&Q_{22}-(2\lambda)^{-1}I_{m}\end{bmatrix}\begin{bmatrix}x\\\
w\end{bmatrix}\right)dw\\\ =\exp\left(-\lambda
x^{\mathsf{T}}(Q_{\lambda}/Q_{22})x\right)\\\
\times\int_{\mathbb{R}^{m}}\exp\left((w+\mu)^{\mathsf{T}}(Q_{22}-(2\lambda)^{-1}I_{m})(w+\mu)\right)dw$
(5.5)

by using the LDU decomposition of $Q_{\lambda}$ to block-diagonalize and where
$\mu=(Q_{22}+(2\lambda)^{-1})^{-1}Q_{12}x$. Since $(Q_{\lambda}/Q_{22})\succeq
0$, we have that $\exp\left(-\lambda
x^{\mathsf{T}}(Q_{\lambda}/Q_{22})x\right)\leq 1$ and it is readily verified
that the integral on the last line of (5.5) evaluates to right hand side of
(5.4), as per requirement. ∎

See 2.1

#### Proof of Lemma 2.1

We take (5.4) as a starting point and manipulate the determinant on the right
hand side. In particular, by writing the determinant as a sum
($\exp\circ\log=\mathrm{identity}$) and by invoking $\log(1+x)\geq x-x^{2}/2$
(valid for $x\geq 0$) for each eigenvalue, we have the result. $\blacksquare$

######  Lemma 5.3.

For any
$\lambda\in\left[0,\frac{1}{4\lambda_{\max}(\mathbf{L}^{\mathsf{T}}\mathbf{L})}\right]$
and $v\in\mathbb{R}^{d}$ with $\|v\|_{2}^{2}\leq 1$, we have that:

$\displaystyle\mathbf{E}\exp\left(\lambda\sum_{t=0}^{T-1}v^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}v\right)\leq\exp\left(4\lambda\sum_{t=0}^{T-1}v^{\mathsf{T}}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]v\right).$

###### Proof.

Let $\mathbf{L}_{v}=(I_{T}\otimes v^{\mathsf{T}})\mathbf{L}$. Since
$(v^{\mathsf{T}}X)_{0:T-1}=\mathbf{L}_{v}W_{0:T-1}$, a standard calculation
gives

$\displaystyle\mathbf{E}\exp\left(\lambda
W_{0:T-1}^{\mathsf{T}}\mathbf{L}_{v}^{\mathsf{T}}\mathbf{L}_{v}W_{0:T-1}\right)=\left(\det(I-2\lambda\mathbf{L}_{v}^{\mathsf{T}}\mathbf{L}_{v})\right)^{-1/2}$
$\displaystyle=\exp\left(-\sum_{i=1}^{Td}\log\left(1-2\lambda\times\lambda_{i}(\mathbf{L}_{v}^{\mathsf{T}}\mathbf{L}_{v})\right)\right).$

The result follows by repeated application of the numerical inequality:
$-\log(1-x)\leq 2x$ (which is valid for all $x\in[0,1/2]$). ∎

The preceding lemma easily yields an upper tail-bound for the empirical
covariance by a Chernoff argument:

$\displaystyle\mathbf{P}\left(\sum_{t=0}^{T-1}v^{\mathsf{T}}X_{t}X_{t}^{\mathsf{T}}v\geq
q\sum_{t=0}^{T-1}v^{\mathsf{T}}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]v\right)\leq\exp\left(\frac{-(q-1)\sum_{t=0}^{T-1}v^{\mathsf{T}}\mathbf{E}[X_{t}X_{t}^{\mathsf{T}}]v}{8\lambda_{\max}(\mathbf{L}^{\mathsf{T}}\mathbf{L})}\right).$

In turn, combining (5.6) with an $\varepsilon$-net argument and a union bound
we arrive at the following [cf. 14, Exercise 4.4.3b].

$\mathbf{P}\left(\left\|\frac{1}{T}\sum_{t=0}^{T-1}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}\geq
2q\left\|\frac{1}{T}\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right\|_{\mathsf{op}}\right)\\\
\leq
5^{d}\exp\left(\frac{-(q-1)\lambda_{\min}\left(\sum_{t=0}^{T-1}\mathbf{E}X_{t}X_{t}^{\mathsf{T}}\right)}{8\lambda_{\max}(\mathbf{L}^{\mathsf{T}}\mathbf{L})}\right).$
(5.6)

#### Acknowledgements

This note was prepared while the author was still at KTH. It was prompted by a
question asked by Samet Oymak (can the method described in [17] give sharp
bounds for linear Gaussian models?). The author also thanks Yassir Jedra,
Henrik Sandberg and Anastasios Tsiamis for several helpful discussions and
acknowledges support by the Swedish Research Council (grant 2016-00861).

## References

  * AYPS [11] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  Advances in neural information processing systems, 24, 2011.
  * FTM [18] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Finite time identification in unstable linear systems.  Automatica, 96:342–353, 2018.
  * JP [22] Yassir Jedra and Alexandre Proutiere.  Finite-time identification of linear systems: Fundamental limits and optimal algorithms.  IEEE Transactions on Automatic Control, 2022.
  * Lju [99] Lennart Ljung.  System identification: theory for the user.  PTR Prentice Hall, Upper Saddle River, NJ, 28, 1999.
  * Men [14] Shahar Mendelson.  Learning without concentration.  In Conference on Learning Theory, pages 25–39. PMLR, 2014.
  * OO [21] Samet Oymak and Necmiye Ozay.  Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.  IEEE Transactions on Automatic Control, 67(4):1914–1928, 2021.
  * PLS [09] Victor H Peña, Tze Leung Lai, and Qi-Man Shao.  Self-normalized processes: Limit theory and Statistical Applications.  Springer, 2009.
  * SMT+ [18] Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht.  Learning without mixing: Towards a sharp analysis of linear system identification.  In Conference On Learning Theory, pages 439–473. PMLR, 2018.
  * SR [19] Tuhin Sarkar and Alexander Rakhlin.  Near Optimal Finite Time Identification of Arbitrary Linear Dynamical Systems.  In International Conference on Machine Learning, pages 5610–5618, 2019.
  * TB [23] Stephen Tu and Ross Boczar.  An elementary proof of anti-concentration for degree two non-negative gaussian polynomials.  arXiv preprint arXiv:2301.05992, 2023.
  * TFS [22] Stephen Tu, Roy Frostig, and Mahdi Soltanolkotabi.  Learning from many trajectories.  arXiv preprint arXiv:2203.17193, 2022.
  * TP [19] Anastasios Tsiamis and George J. Pappas.  Finite sample analysis of stochastic system identification.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3648–3654. IEEE, 2019.
  * TZMP [22] Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas.  Statistical learning theory for control: A finite sample perspective.  arXiv preprint arXiv:2209.05423, 2022.
  * Ver [18] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge University Press, 2018.
  * Wai [19] Martin J. Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * WRMDM [05] Jan C Willems, Paolo Rapisarda, Ivan Markovsky, and Bart LM De Moor.  A Note on Persistency of Excitation.  Systems & Control Letters, 54(4):325–329, 2005.
  * ZT [22] Ingvar Ziemann and Stephen Tu.  Learning with little mixing.  arXiv preprint arXiv:2206.08269. NeurIPS’22, 2022.