filtering set-up leads to a sequence of inverse problems of the form (2.1),
where the forward model is given by the observation map, and the prior
_forecast distribution_ blends the dynamics map with previous probabilistic
estimates. Throughout this subsection, we write
$\normn{\hatmpost-\mpostt}_{p}\equiv\insquare{\E\normn{\hatmu^{(t)}-\mu^{(t)}}^{p}_{2}}^{1/p}$
and
$\normn{\hatCpostt-\Cpostt}_{p}\equiv\insquare{\E\normn{\hatCpost^{(t)}-\Cpost^{(t)}}^{p}}^{1/p}$.

| Kalman filter | Square root EnKF
---|---|---
Input |  $\\{\yt,\At,M^{(t)}\\}_{t=1}^{T}$, $\Gamma$, $\mu^{(0)},\Sigma^{(0)}$ |  $\\{\yt,\At,M^{(t)}\\}_{t=1}^{T}$, $\Gamma$, $\\{\upost_{n}^{(0)}\\}_{n=1}^{N}\iid\mathcal{N}(\mu^{(0)},\Sigma^{(0)})$
Forecast |  | $\uprt_{n}=M^{(t)}\upostone_{n},~{}~{}n=1,\dots,N$
$\mprt=M^{(t)}\mpostone$ | $\hatmprt=\frac{1}{N}\sum_{n=1}^{N}\uprt_{n}$
$\Cprt=M^{(t)}\Cpostone(M^{(t)})^{\top}$ | $\hatCprt=\frac{1}{N-1}\sum_{n=1}^{N}(\uprt_{n}-\hatmprt)(\uprt_{n}-\hatmprt)^{\top}$
Analysis |  | $\upostt_{n}=\msM(\uprt_{n},\hatCprt;\At,\yt,\Gamma),~{}~{}n=1,\dots,N$
$\mpostt=\msM(\mprt,\Cprt;\At,\yt,\Gamma)$ | $\hatmpostt=\frac{1}{N}\sum_{n=1}^{N}\upostt_{n}$
$\Cpostt=\msC(\Cprt;\At,\Gamma)$ | $\hatCpostt=\frac{1}{N-1}\sum_{n=1}^{N}(\upostt_{n}-\hatmpostt)(\upostt_{n}-\hatmpostt)^{\top}$
Output | $\\{\mpost^{(t)},\Cpost^{(t)}\\}_{t=1}^{T}$ | $\\{\hatmpostt,\hatCpostt\\}_{t=1}^{T}$
Table 1:  Comparison of the Kalman filter and square root EnKF considered in
[59]. The forecast and analysis steps are to be repeated for $t=1,\dots,T$
iterations.

We will use two auxiliary lemmas to prove the main result of this subsection,
Corollary A.12 below.

######  Lemma A.10 (Continuity and Boundedness of Covariance-Update Operator
in $L^{p}$ [59, Corollary 4.8]).

Let $\msC$ be the covariance-update operator defined in (2.4). Let
$Q\in\mcS_{+}^{d}$ be a random matrix and $P\in\mcS_{+}^{d}$ be a
deterministic matrix, $\Gamma\in\mcS_{++}^{k}$, $A\in\R^{k\times d}$,
$y\in\R^{k},$ and $m,m^{\prime}\in\R^{d}$. Then, for any $1\leq p<\infty$, the
following holds:

$\displaystyle\begin{split}\normn{\msC(Q)-\msC(P)}_{p}&\leq\normn{Q-P}_{p}(1+\normn{A}^{2}\normn{\Gamma^{-1}}\normn{P})\\\
&+(\normn{A}^{2}\normn{\Gamma^{-1}}+\normn{A}^{4}\normn{\Gamma^{-1}}^{2}\normn{P})\normn{Q}_{2p}\normn{Q-P}_{2p}.\end{split}$

######  Lemma A.11 (Continuity and Boundedness of Mean-Update Operator in
$L^{p}$ [59, Corollary 4.10]).

Let $\msM$ be the mean-update operator defined in (2.3). Let
$P,Q\in\mcS_{+}^{d}$, $\Gamma\in\mcS_{++}^{k}$, $A\in\R^{k\times d}$,
$y\in\R^{k},$ and $m,m^{\prime}\in\R^{d}$. Assume that $Q$ and $m$ are random,
and that $P$ and $m^{\prime}$ are deterministic. The following holds:

$\displaystyle\begin{split}\norm{\msM(m,Q)-\msM(m^{\prime},P)}_{p}&\leq\norm{m-m^{\prime}}_{p}+\normn{A}^{2}\normn{\Gamma^{-1}}\normn{Q}_{2p}\norm{m-m^{\prime}}_{2p}\\\
&+\normn{Q-P}_{p}\normn{A}\normn{\Gamma^{-1}}\bigl{(}1+\normn{A}^{2}\normn{\Gamma^{-1}}\normn{P}\bigr{)}\norm{y-Am^{\prime}}_{2}.\end{split}$

The next result shows how our one-step bounds in Theorems 2.3 and 2.5 can be
extended to provide non-asymptotic bounds on the performance of the multi-step
square root EnKF. The proof follows a similar argument to the proof of [59,
Theorem 6.1].

######  Corollary A.12.

Consider the square root EnKF defined in Table 1. Suppose that $N\gtrsim
r_{2}(\Cpost^{(0)})$. Then, for any $t\geq 1$ and $p\geq 1,$

$\displaystyle\normn{\hatmpostt-\mpostt}_{p}$
$\displaystyle\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}},\normn{y^{(l)}-A^{(l)}\mpr^{(l)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}}),$
$\displaystyle\normn{\hatCpostt-\Cpostt}_{p}$
$\displaystyle\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}}).$

###### Proof.

The proof follows by strong induction on the predicate in the statement of the
theorem. To that end, the base case ($t=1$) holds by Theorems 2.3 and 2.5,
which state that, for any $p\geq 1,$

$\displaystyle\normn{\hatmpost^{(1)}-\mpost^{(1)}}_{p}$
$\displaystyle\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\normn{M^{(1)}},\normn{A^{(1)}},\normn{\Cpost^{(0)}},\normn{y^{(1)}-A^{(1)}\mpr^{(1)}},\normn{\Gamma^{-1}}),$
$\displaystyle\normn{\hatCpost^{(1)}-\Cpost^{(1)}}_{p}$
$\displaystyle\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\normn{M^{(1)}},\normn{A^{(1)}},\normn{\Cpost^{(0)}},\normn{\Gamma^{-1}}).$

Suppose now that the claim holds for $l=2,\dots,t-1.$ Then, for $l=t$, we have
by Lemma A.10

$\displaystyle\normn{\hatCpostt-\Cpostt}_{p}$
$\displaystyle=\normn{\msC(\hatCprt)-\msC(\Cprt)}_{p}$
$\displaystyle\leq\normn{\hatCprt-\Cprt}_{p}(1+\normn{\At}^{2}\normn{\Gamma^{-1}}\normn{\Cprt})$
$\displaystyle+(\normn{\At}^{2}\normn{\Gamma^{-1}}+\normn{\At}^{4}\normn{\Gamma^{-1}}^{2}\normn{\Cprt})\normn{\hatCprt}_{2p}\normn{\hatCprt-\Cprt}_{2p}.$
(A.15)

By the definition of $\hatCprt,\Cprt$ together with the inductive hypothesis,
it follows that, for $\mathfrak{p}\in\\{p,2p\\},$

$\displaystyle\normn{\hatCprt-\Cprt}_{\mathfrak{p}}$
$\displaystyle=\normn{M^{(t)}(\hatCpost^{(t-1)}-\Cpost^{(t-1)})(M^{(t)})^{\top}}_{\mathfrak{p}}$
$\displaystyle\leq\normn{M^{(t)}}^{2}\normn{\hatCpost^{(t-1)}-\Cpost^{(t-1)}}_{\mathfrak{p}}$
$\displaystyle\lesssim_{p}\normn{M^{(t)}}^{2}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}}\\}_{l=1}^{t-1},\normn{\Gamma^{-1}})$
$\displaystyle=\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}}).$

Further, we have

$\displaystyle\normn{\hatCprt}_{2p}$
$\displaystyle\leq\normn{\hatCprt-\Cprt}_{2p}+\normn{\Cprt}$
$\displaystyle\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}})+\normn{M^{(t)}}^{2}\normn{\Cpost^{(t-1)}}.$

Plugging these two results into (A.4) gives

$\displaystyle\normn{\hatCpostt-\Cpostt}_{p}$
$\displaystyle\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}}).$

Similarly, by Lemma A.11 we have

$\displaystyle\normn{\hatmpostt-\mpostt}_{p}$
$\displaystyle=\normn{\msM(\hatmprt,\hatCprt)-\msM(\mprt,\Cprt)}_{p}$
$\displaystyle\leq\normn{\hatmprt-\mprt}_{p}+\normn{\At}^{2}\normn{\Gamma^{-1}}\normn{\hatCprt}_{2p}\normn{\hatmprt-\mprt}_{2p}$
$\displaystyle+\normn{\hatCprt-\Cprt}_{p}\normn{\At}\normn{\Gamma^{-1}}\bigl{(}1+\normn{\At}^{2}\normn{\Gamma^{-1}}\normn{\Cprt}\bigr{)}\normn{\yt-\At\mprt}_{2}.$
(A.16)

By the definition of $\hatmprt,\mprt$ together with the inductive hypothesis,
we have, for $\mathfrak{p}\in\\{p,2p\\},$

$\displaystyle\normn{\hatmprt-\mprt}_{\mathfrak{p}}$
$\displaystyle=\normn{M^{(t)}(\hatmpost^{(t-1)}-\mpost^{(t-1)})}_{\mathfrak{p}}$
$\displaystyle\leq\normn{M^{(t)}}\normn{\hatmpost^{(t-1)}-\mpost^{(t-1)}}_{\mathfrak{p}}$
$\displaystyle\lesssim_{p}\normn{M^{(t)}}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}},\normn{y^{(l)}-A^{(l)}\mpr^{(l)}}\\}_{l=1}^{t-1},\normn{\Gamma^{-1}})$
$\displaystyle=\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}},\normn{y^{(l)}-A^{(l)}\mpr^{(l)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}}).$

Plugging this bound and the one for $\normn{\hatCprt}_{2p}$ derived previously
in the proof into (A.4) yields

$\normn{\hatmpostt-\mpostt}_{p}\lesssim_{p}\sqrt{\frac{r_{2}(\Cpost^{(0)})}{N}}\times
c(\\{\normn{M^{(l)}},\normn{A^{(l)}},\normn{\Cpost^{(l-1)}},\normn{y^{(l)}-A^{(l)}\mpr^{(l)}}\\}_{l=1}^{t},\normn{\Gamma^{-1}}).\qed$

##  Appendix B Proofs: Section 3

This appendix contains the proofs of all the theorems in Section 3. Results on
covariance estimation are in Subsection B.1 and our main results on ensemble
Kalman updates are in Subsection B.2.

###  B.1 Covariance Estimation

Here we establish Theorems 3.1 and 3.3. We first collect some required
technical results in Subsection B.1.1. Next we study covariance and cross-
covariance estimation under soft sparsity in Subsections B.1.2 and B.1.3,
respectively.

####  B.1.1 Background and Preliminaries

######  Definition B.1 ([92, Definition 2.2.17]).

Given a set $T$, an admissible sequence of partitions of $T$ is an increasing
sequence $(\Delta_{n})$ of partitions of $T$ such that
$\text{card}(\Delta_{0})=1$ and $\text{card}(\Delta_{n})\leq 2^{2^{n}}$ for
$n\geq 1$.

The notion of an admissible sequence of partitions allows us to define the
following notion of complexity of a set $T$, often referred to as generic
complexity.

######  Definition B.2 ([92, Definition 2.2.19]).

Let $(T,\mathsf{d})$ be a possibly infinite metric space, and define

$\gamma_{2}(T,\mathsf{d})=\inf\sup_{t\in T}\sum_{n\geq
0}2^{n/2}\text{Diam}\bigl{(}\Delta_{n}(t)\bigr{)},$

where $\Delta_{n}(t)$ denotes the unique element of the partition to which $t$
belongs, and the infimum is taken over all admissible sequences of partitions.

The following theorem is known as the Majorizing Measure Theorem and provides
upper and lower bounds for centered Gaussian processes in terms of the generic
complexity.

######  Theorem B.3 ([92, Theorem 2.4.1]).

Let $X_{t}$, $t\in T$ be a centered Gaussian process which induces a metric
$\mathsf{d}_{X}:T\times T\to[0,\infty]$ defined by

$\displaystyle\mathsf{d}_{X}^{2}(s,t)=\E\insquare{(X_{s}-X_{t})^{2}}.$

Then there exists an absolute constant $L>0$ such that

$\displaystyle\frac{1}{L}\gamma_{2}(T,\mathsf{d}_{X})\leq\E\insquare{\,\sup_{t\in
T}X_{t}\,}\leq L\gamma_{2}(T,\mathsf{d}_{X}).$

We will be primarily interested in the case that $T=\mcF$ is some function
class on the probability space $(\mcX,\mcA,\P)$, and with $\mathsf{d}$ being
the metric induced either by $\|\cdot\|_{L_{2}}$ or $\|\cdot\|_{\psi_{2}}$. We
denote these spaces by $(\mcF,L_{2})$ and $(\mcF,\psi_{2})$ respectively
throughout this section. The next result is an exponential generic chaining
bound, which was introduced in [28, Corollary 5.7] and described in [57,
Theorem 8]. We present it as it was described in the latter reference.

######  Theorem B.4 ([57, Theorem 8]).

Let $(\mcX,\mcA,\P)$ be a probability space and consider the random sample
$X,X_{1},\dots,X_{N}\iid\P$. Let $\mcF$ be a class of measurable functions on
$(\mcX,\mcA)$. There exists a universal constant $c>0$ such that, for all
$t\geq 1,$ it holds with probability at least $1-e^{-t}$ that

$\displaystyle\sup_{f\in\mcF}\abs{\frac{1}{N}\sum_{n=1}^{N}f^{2}(X_{n})-\E[f^{2}(X)]}\leq
c\inparen{\sup_{f\in\mcF}\normn{f}_{\psi_{2}}\frac{\gamma_{2}(\mcF,\psi_{2})}{\sqrt{N}}\lor\frac{\gamma^{2}_{2}(\mcF,\psi_{2})}{N}\lor\sup_{f\in\mcF}\normn{f}^{2}_{\psi_{2}}\sqrt{\frac{t}{N}}\lor\sup_{f\in\mcF}\normn{f}^{2}_{\psi_{2}}\frac{t}{N}}$

######  Lemma B.5 (Expectation Bound from Probability Bound, [92, Lemma
2.2.3]).

Let $Y\geq 0$ be a random variable satisfying

$\displaystyle\P(Y\geq r)\leq a\exp\inparen{-\frac{r^{2}}{b^{2}}},\qquad r\geq
0,$

for certain numbers $a\geq 2$ and $b>0$. Then there is a universal constant
$c$ such that

$\displaystyle\E[Y]\leq cb\sqrt{\log a}.$

Finally, we recall the following dimension-free bound for the maxima of sub-
Gaussian random variables.

######  Lemma B.6 (Dimension-Free Sub-Gaussian Maxima, [101, Lemma 2.4]).

Let $X_{1},\dots X_{N}$ be not necessarily independent sub-Gaussian random
variables with

$\displaystyle\P(X_{n}>x)\leq ce^{-x^{2}/c\sigma^{2}_{n}},\qquad\text{for all
}x\geq 0,~{}1\leq n\leq N,$

where $\sigma_{n}\geq 0$ is given, or alternatively
$\normn{X_{n}}_{\psi_{2}}\lesssim\sigma_{n}$. Then, for any $t\geq 1,$ it
holds with probability at least $1-ce^{-ct}$ that

$\displaystyle\max_{n\leq N}X_{n}\lesssim\sqrt{t}\max_{n\leq
N}\sigma_{(n)}\sqrt{\log(n+1)},$

where $\sigma_{(1)}\geq\sigma_{(2)}\geq\dots\sigma_{(N)}$ is the decreasing
rearrangement of $\sigma_{1},\dots,\sigma_{N}$. Further

$\displaystyle\E\insquare{\max_{n\leq N}X_{n}}\lesssim\max_{n\leq
N}\sigma_{(n)}\sqrt{\log(n+1)}.$

###### Proof.

The proof of the upper bound is based on the proof of Proposition 2.4.16 in
[92]. By permutation invariance, we can assume without loss of generality that
$\sigma_{1}\geq\sigma_{2}\geq\dots\geq\sigma_{N}$. Then

$\displaystyle\P\inparen{\max_{n\leq
N}\frac{X_{n}}{\sigma_{n}\sqrt{\log(n+1)}}\geq\sqrt{t}}\leq\sum_{n=1}^{N}\P\Bigl{(}X_{n}\geq\sigma_{n}\sqrt{t\log(n+1)}\Bigr{)}\lesssim\sum_{n=1}^{N}\exp\inparen{-\frac{t}{c}\log(n+1)}.$

For $t\geq 2c$, the final expression in the above display is finite, and we
may write

$\displaystyle\sum_{n=1}^{N}\exp\inparen{-\frac{t}{c}\log(n+1)}$
$\displaystyle=\sum_{n=2}^{N+1}\exp\inparen{-\frac{t}{c}\log(n)}\leq\exp\inparen{-\frac{t}{c}\log(2)}+\int_{2}^{\infty}x^{-t/c}dx\leq
ce^{-t/c}.$

Therefore, for any $t\geq 2c$, it holds with probability at least
$1-ce^{-t/c}$ that

$\displaystyle\max_{n\leq N}X_{n}\lesssim\sqrt{t}\max_{n\leq
N}\sigma_{(n)}\sqrt{\log(n+1)}.$

This implies that, for any $t\geq 1$, it holds with probability at least
$1-ce^{-(t\lor 2c)/c}$ that

$\displaystyle\max_{n\leq N}X_{n}\lesssim(\sqrt{t}\lor\sqrt{2c})\max_{n\leq
N}\sigma_{(n)}\sqrt{\log(n+1)}\lesssim\sqrt{t}\max_{n\leq
N}\sigma_{(n)}\sqrt{\log(n+1)}.$

Since $1-ce^{-(t\lor 2c)/c}\geq 1-ce^{-t/c}$ it holds that, for any $t\geq 1$,
with probability at least $1-ce^{-t/c}$

$\displaystyle\max_{n\leq N}X_{n}\lesssim\sqrt{t}\max_{n\leq
N}\sigma_{(n)}\sqrt{\log(n+1)}.$

It follows by Lemma B.5 that

$\displaystyle\E\insquare{\max_{n\leq
N}\frac{X_{n}}{\sigma_{n}\sqrt{\log(n+1)}}}\leq c,$

which in turn implies

$\E\insquare{\max_{n\leq N}X_{n}}\lesssim\max_{n\leq
N}\sigma_{n}\sqrt{\log(n+1)}=\max_{n\leq N}\sigma_{(n)}\sqrt{\log(n+1)}.\qed$

####  B.1.2 Covariance Estimation under Soft Sparsity

This subsection contains the proof of Theorem 3.1. We follow the approach in
[57, Theorem 4], but we restrict our attention to finite dimensional spaces.
Our proof will rely on the following max-norm covariance estimation bound,
which may be of independent interest.

######  Theorem B.7 (Covariance Estimation with Sample Covariance —Max-Norm
Bound).

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar(X_{1})=\Sigma^{X}.$ Let
$\hatSigma^{X}=(N-1)^{-1}\sum_{n=1}^{N}(X_{n}-\mu^{X})(X_{n}-\mu^{X})^{\top}$.
Then there exists a constant $c$ such that, for all $t\geq 1,$ it holds with
probability at least $1-ce^{-t}$ that

$\displaystyle\normn{\hatSigma^{X}-\Sigma^{X}}_{\max}\leq
c\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}},$

where

$\displaystyle
r_{\infty}(\Sigma^{X})\equiv\frac{\max_{j}\Sigma^{X}_{(j)}\log(j+1)}{\Sigma^{X}_{(1)}}.$

###### Proof.

The proof of this result is based on the proof of the upper bound of Theorem 4
of [57], in conjunction with Theorem B.4. We deal with the case $\mu^{X}=0$
first. To this end, let $Z_{1},\dots,Z_{N}$ be $d$-dimensional i.i.d. sub-
Gaussian random vectors with zero mean and $\tvar[Z_{1}]=\Sigma^{X}$. We
denote the distribution of $Z_{1}$ by $\P$, and note that
$\normn{\cdot}_{\psi_{1}}$, $\normn{\cdot}_{\psi_{2}},$ and
$\normn{\cdot}_{L_{2}}$ are defined implicitly with respect to $\P$. Let
$\hatSigma^{0}=N^{-1}\sum_{n=1}^{N}Z_{n}Z_{n}^{\top}$. We rewrite the
expectation of interest as a squared empirical process term over an
appropriate class of functions. For $j\geq 1$ we denote the $j$-th canonical
vector (the vector with $1$ in the $j$-th index and zero otherwise) by
$e_{j}$. Then, we note that

$\displaystyle\normn{\hatSigma^{0}-\Sigma^{X}}_{\max}$
$\displaystyle=\sup_{i,j}\inp$
$\displaystyle=\sup_{i,j}\insquare{\inp{\frac{e_{i}+e_{j}}{2},(\hatSigma^{0}-\Sigma^{X})\frac{e_{i}+e_{j}}{2}}-\inp{\frac{e_{i}-e_{j}}{2},(\hatSigma^{0}-\Sigma^{X})\frac{e_{i}-e_{j}}{2}}}$
$\displaystyle\leq 2\sup_{u\in\mcU}\abs{\inp{(\hatSigma^{0}-\Sigma^{X})u,u}},$

where $\mcU=\bigl{\\{}u\in\R^{d}:u=\pm\frac{1}{2}(e_{i}\pm e_{j}),~{}1\leq
i,j\leq d\ \bigr{\\}}$. Define the set of functions
$\mcF_{U}=\bigl{\\{}\inp{\cdot,u}:u\in\mcU\bigr{\\}}$, and note that, for any
$f\in\mcF_{\mcU}$, $-f\in\mcF_{\mcU}$ and $\E[f(Z_{1})]=0$. It then follows by
Theorem B.4 that for the same universal constant $c$ in the statement of the
theorem,

$\displaystyle 2\sup_{u\in\mcU}\abs{\inp{(\hatSigma^{0}-\Sigma^{X})u,u}}$
$\displaystyle=2\sup_{u\in\mcU}\abs{\frac{1}{N}\sum_{n=1}^{N}\inp{Z_{n},u}^{2}-\inp{u,\Sigma^{X}u}}$
$\displaystyle=2\sup_{f\in\mcF_{\mcU}}\abs{\frac{1}{N}\sum_{n=1}^{N}f^{2}(Z_{n})-\E[f^{2}(Z_{1})]}$
$\displaystyle\leq
2c\inparen{\sup_{f\in\mcF_{\mcU}}\normn{f}_{\psi_{2}}\frac{\gamma_{2}(\mcF_{\mcU};\psi_{2})}{\sqrt{N}}\lor\frac{\gamma^{2}_{2}(\mcF_{\mcU};\psi_{2})}{N}\lor\sup_{f\in\mcF_{\mcU}}\normn{f}^{2}_{\psi_{2}}\sqrt{\frac{t}{N}}\lor\sup_{f\in\mcF_{\mcU}}\normn{f}^{2}_{\psi_{2}}\frac{t}{N}}.$

Using the equivalence of the $\psi_{2}$ and $L_{2}$ norms for linear
functionals, we have

$\displaystyle\sup_{f\in\mcF_{\mcU}}\normn{f}_{\psi_{2}}$
$\displaystyle\lesssim\sup_{f\in\mcF_{\mcU}}\normn{f}_{L_{2}}=\max_{u\in\mcU}\sqrt{\E\bigl{[}\inp{Z_{1},u}^{2}\bigr{]}}=\max_{u\in\mcU}\sqrt{\langle
u,\Sigma^{X}u\rangle}=\frac{1}{2}\max_{i,j}\sqrt{\bigl{\langle}e_{i}\pm
e_{j},\Sigma^{X}(e_{i}\pm e_{j})\bigr{\rangle}}$
$\displaystyle=\frac{1}{2}\max_{i,j}\sqrt{\langle
e_{i},\Sigma^{X}e_{i}\rangle+\langle e_{j},\Sigma^{X}e_{j}\rangle\pm 2\langle
e_{i},\Sigma^{X}e_{j}\rangle}=\frac{1}{2}\max_{i,j}\sqrt{\Sigma^{X}_{ii}+\Sigma^{X}_{jj}\pm
2\Sigma^{X}_{ij}}\leq\sqrt{\Sigma^{X}_{(1)}}.$

To control the generic complexity $\gamma_{2}(\mcF_{U},\psi_{2})$, let
$Y\sim\mcN(0,\Sigma^{X})$ be a $d$-dimensional Gaussian vector, with induced
metric

$\displaystyle\mathsf{d}_{Y}(u,v)=\sqrt{\E\bigl{[}(\inp{Y,u}-\inp{Y,v})^{2}\bigr{]}}=\normn{\inp{\cdot,u}-\inp{\cdot,v}}_{L_{2}},\qquad
u,v\in\mcU.$

Using again the equivalence of the $\psi_{2}$ and $L_{2}$ norms for linear
functionals, we have that

$\displaystyle\gamma_{2}(\mcF_{\mcU};\psi_{2})\lesssim\gamma_{2}(\mcF_{\mcU};L_{2})=\gamma_{2}(\mcU;\mathsf{d}_{Y}).$

It follows then by Theorem B.3 that

$\displaystyle\gamma_{2}(\mcU;\mathsf{d}_{Y})$
$\displaystyle\lesssim\E\insquare{\,\sup_{u\in\mcU}\inp{Y,u}}$
$\displaystyle=\E\insquare{\max_{i,j}\inp{Y,\pm\frac{1}{2}(e_{i}\pm e_{j})}}$
$\displaystyle\leq\E\insquare{\max_{j}\Bigl{|}\inp{Y,e_{j}}\Bigr{|}}$
$\displaystyle\lesssim\max_{j}\sqrt{\Sigma^{X}_{(j)}\log(j+1)},$

where the final inequality follows by Lemma B.6. We have shown that with
probability at least $1-e^{-t}$

$\displaystyle\normn{\hatSigma^{0}-\Sigma^{X}}_{\max}$
$\displaystyle\lesssim\inparen{\sqrt{\Sigma^{X}_{(1)}\max_{j}\frac{\Sigma^{X}_{(j)}\log(j+1)}{N}}\lor\max_{j}\frac{\Sigma^{X}_{(j)}\log(j+1)}{N}\lor\Sigma^{X}_{(1)}\sqrt{\frac{t}{N}}\lor\Sigma^{X}_{(1)}\frac{t}{N}}$
$\displaystyle=\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\frac{r_{\infty}(\Sigma^{X})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}}.$
(B.1)

In the un-centered case, taking $X_{n}=Z_{n}+\mu^{X}$, we have
$\hatSigma^{X}=\hatSigma^{0}-\barZ\barZ^{\top}$ and it follows that

$\displaystyle\normn{\hatSigma^{X}-\Sigma^{X}}_{\max}\leq\normn{\hatSigma^{0}-\Sigma^{X}}_{\max}+\normn{\barZ\barZ^{\top}}_{\max}.$

By Lemma B.6, with probability at least $1-ce^{-t}$

$\displaystyle\normn{\barZ\barZ^{\top}}_{\max}\leq\normn{\barZ}_{\max}^{2}\leq\frac{t}{N}\max_{j\leq
d}\Sigma^{X}_{(j)}\log(j+1)=t\Sigma^{X}_{(1)}\frac{r_{\infty}(\Sigma^{X})}{N}.$
(B.2)

Denote the set on which (B.1) occurs by $E_{1}$, and the set on which (B.2)
occurs by $E_{2}$. Then the intersection $E=E_{1}\cap E_{2}$ has probability
at least $1-ce^{-t}$, and it holds on $E$ that

$\displaystyle\normn{\hatSigma^{X}-\Sigma^{X}}_{\max}$
$\displaystyle\lesssim\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\frac{r_{\infty}(\Sigma^{X})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}}$
$\displaystyle=\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}}.\qed$

######  Lemma B.8.

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar[X_{1}]=\Sigma^{X}.$ Let
$\hatSigma^{X}=(N-1)^{-1}\sum_{n=1}^{N}(X_{n}-\mu^{X})(X_{n}-\mu^{X})^{\top}$.
Then, for any $p\geq 1,$

$\displaystyle\insquare{\E\normn{\hatSigma^{X}-\Sigma^{X}}^{p}_{\max}}^{1/p}\lesssim_{p}\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\frac{r_{\infty}(\Sigma^{X})}{N}}.$

###### Proof.

To ease notation, let
$B\equiv\Sigma_{(1)}^{X}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\frac{r_{\infty}(\Sigma^{X})}{N}}$,
then using that for positive $W$,
$\E[W^{p}]=p\int_{0}^{\infty}w^{p-1}\P(W>w)\,dw$ gives

$\displaystyle\insquare{\E\normn{\hatSigma-\Sigma}^{p}_{\max}}$
$\displaystyle=p\int_{0}^{\infty}x^{p-1}\P(\normn{\hatSigma^{X}-\Sigma^{X}}_{\max}>x)\,dx$
$\displaystyle\leq
p\int_{0}^{B}x^{p-1}dx+\int_{B}^{\infty}x^{p-1}\P(\normn{\hatSigma^{X}-\Sigma^{X}}_{\max}>x)\,dx$
$\displaystyle\lesssim
B^{p}+p\int_{0}^{\infty}x^{p-1}\exp\inparen{-\min\inparen{\frac{Nx^{2}}{(\Sigma^{X}_{(1)})^{2}},\frac{Nx}{\Sigma^{X}_{(1)}},\frac{Nx}{r_{\infty}(\Sigma^{X})\Sigma^{X}_{(1)}}}}\,dx$
$\displaystyle=B^{p}+p\max\inparen{\frac{\Gamma(p/2)}{2}\inparen{\frac{(\Sigma^{X}_{(1)})^{2}}{N}}^{p/2},\Gamma(p)\inparen{\frac{\Sigma^{X}_{(1)}}{N}}^{p},\Gamma(p)\inparen{\frac{r_{\infty}(\Sigma^{X})\Sigma^{X}_{(1)}}{N}}^{p}},$

where the last line follows by direct integration. We therefore have

$\displaystyle\insquare{\E\normn{\hatSigma^{X}-\Sigma^{X}}^{p}_{\max}}^{1/p}$
$\displaystyle\lesssim
B+c(p)\max\inparen{\frac{\Sigma^{X}_{(1)}}{\sqrt{N}},\frac{\Sigma^{X}_{(1)}}{N},\frac{r_{\infty}(\Sigma^{X})\Sigma^{X}_{(1)}}{N}}\leq
c(p)\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\frac{r_{\infty}(\Sigma^{X})}{N}},$

where the final inequality holds due to the fact that
$r_{\infty}(\Sigma^{X})\gtrsim 1$. ∎

######  Theorem B.9 (Covariance Estimation with Localized Sample Covariance
—Operator-Norm Bound).

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar[X_{1}]=\Sigma^{X}$. Further, assume that
$\Sigma^{X}\in\msU_{d}(q,R_{q})$ for some $q\in[0,1)$ and $R_{q}>0$. Let
$\hatSigma^{X}=(N-1)^{-1}\sum_{n=1}^{N}(X_{n}-\barX)(X_{n}-\barX)^{\top}$ and,
for any $t\geq 1$, set

$\displaystyle\rho_{N}\asymp\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}}$

and let $\hatSigma_{\rho_{N}}^{X}$ be the localized sample covariance
estimator. There exists a constant $c>0$ such that, with probability at least
$1-ce^{-t}$, it holds that

$\displaystyle\normn{\hatSigma_{\rho_{N}}^{X}-\Sigma^{X}}\lesssim
R_{q}\rho_{N}^{1-q}.$

###### Proof.

The localized sample covariance matrix has elements

$\displaystyle[\hatSigma_{\rho_{N}}^{X}]_{ij}=\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}},\qquad
1\leq i,j\leq d.$

By Theorem B.7, it holds with probability at least $1-ce^{-t}$ that

$\displaystyle\normn{\hatSigma^{X}-\Sigma^{X}}_{\max}\lesssim\rho_{N}.$

The remainder of the analysis is carried out conditional on this event,
following the approach taken in [103, Theorem 6.27]. Define the set of indices
of the $i$-th row of $\Sigma^{X}$ that exceed $\rho_{N}/2$ by

$\displaystyle\mcI_{i}(\rho_{N}/2)\equiv\inparen{j\in\inparen{1,\dots,d}:\abs{\Sigma^{X}_{ij}}\geq\rho_{N}/2},\qquad
i=1,\dots,d.$

We then have

$\displaystyle\normn{\Sigma^{X}-\hatSigma_{\rho_{N}}^{X}}$
$\displaystyle\leq\normn{\Sigma^{X}-\hatSigma_{\rho_{N}}^{X}}_{\infty}$
$\displaystyle=\max_{i=1,\dots,d}\sum_{j=1}^{d}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}$
$\displaystyle=\max_{i=1,\dots,d}\inparen{\sum_{j\in\mcI_{i}(\rho_{N}/2)}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}+\sum_{j\notin\mcI_{i}(\rho_{N}/2)}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}},$

where $\hatSigma^{X}_{ij}$ is element $(i,j)$ of $\hatSigma^{X}$. For
$j\in\mcI_{i}(\rho_{N}/2)$, it holds that $|\Sigma^{X}_{ij}|\geq\rho_{N}/2$ so
that

$\displaystyle\sum_{j\in\mcI_{i}(\rho_{N}/2)}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}$
$\displaystyle\leq\sum_{j\in\mcI_{i}(\rho_{N}/2)}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}}+\abs{\hatSigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}$
$\displaystyle\leq\sum_{j\in\mcI_{i}(\rho_{N}/2)}\normn{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}}_{\max}+\abs{\hatSigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}$
$\displaystyle\leq\sum_{j\in\mcI_{i}(\rho_{N}/2)}\inparen{\frac{\rho_{N}}{2}+\rho_{N}}$
$\displaystyle=|\mcI_{i}(\rho_{N}/2)|\frac{3\rho_{N}}{2},$

where we have used the fact that

$\displaystyle\abs{\hatSigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}=0\times\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}+\hatSigma^{X}_{ij}\times\indicator_{|\hatSigma^{X}_{ij}|\leq\rho_{N}}\leq\rho_{N}.$

Further, since

$\displaystyle
R_{q}\geq\sum_{j=1}^{d}|\Sigma^{X}_{ij}|^{q}\geq|\mcI_{i}(\rho_{N}/2)|\inparen{\frac{\rho_{N}}{2}}^{q},$

it follows that $|\mcI_{i}(\rho_{N}/2)|\leq 2^{q}\rho_{N}^{-q}R_{q}$, and so

$\displaystyle\sum_{j\in\mcI_{i}(\rho_{N}/2)}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}\leq|\mcI_{i}(\rho_{N}/2)|\frac{3\rho_{N}}{2}\leq\frac{3}{2}2^{-q}\rho_{N}^{1-q}R_{q}.$

For $j\notin\mcI_{i}(\rho_{N})$, then $|\Sigma^{X}_{ij}|\leq\rho_{N}/2$ and so

$\displaystyle|\hatSigma^{X}_{ij}|\leq|\hatSigma^{X}_{ij}-\Sigma^{X}_{ij}|+|\Sigma^{X}_{ij}|\leq\|\hatSigma^{X}-\Sigma^{X}\|_{\max}+|\Sigma^{X}_{ij}|\leq\frac{\rho_{N}}{2}+\frac{\rho_{N}}{2}=\rho_{N}.$

This implies that
$\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}=0$, and
therefore for $q\in[0,1)$, since $|\Sigma^{X}_{ij}|/(\rho_{N}/2)\leq 1$, it
holds that

$\displaystyle\sum_{j\notin\mcI_{i}(\rho_{N}/2)}\abs{\Sigma^{X}_{ij}-\hatSigma^{X}_{ij}\indicator_{|\hatSigma^{X}_{ij}|\geq\rho_{N}}}$
$\displaystyle\leq\sum_{j\notin\mcI_{i}(\rho_{N}/2)}|\Sigma^{X}_{ij}|=\frac{\rho_{N}}{2}\sum_{j\notin\mcI_{i}(\rho_{N}/2)}\frac{|\Sigma^{X}_{ij}|}{\frac{\rho_{N}}{2}}$
$\displaystyle\leq\frac{\rho_{N}}{2}\sum_{j\notin\mcI_{i}(\rho_{N}/2)}\inparen{\frac{|\Sigma^{X}_{ij}|}{\rho_{N}/2}}^{q}\leq\rho_{N}^{1-q}R_{q}.$

Combining these two results gives

$\normn{\Sigma^{X}-\hatSigma_{\rho_{N}}^{X}}\leq 4\rho_{N}^{1-q}R_{q}.\qed$

###### Proof of Theorem 3.1.

The result follows immediately by Theorem B.9. ∎

####  B.1.3 Cross-Covariance Estimation under Soft Sparsity

This subsection contains the proof of Theorem 3.3. The presentation is
parallel to that in Subsection B.1.2. We will use a max-norm cross-covariance
estimation bound, analogous to Theorem B.7. The proof relies on a high
probability bound for product function classes that was shown in [74, Theorem
1.13]. We present here a simplified version of that more general statement
that suffices for our purposes.

######  Theorem B.10.

Let $(\mcX,\mcA,\P)$ be a probability space and consider the random sample
$X,X_{1},\dots,X_{N}\iid\P$. Let $\mcF,\mcG$ be two classes of measurable
functions on $(\mcX,\mcA)$ such that $0\in\mcF$ and $0\in\mcG$. There exist
positive universal constants $c_{1},c_{2},c_{3}$ such that, for all $t\geq 1$,
it holds with probability at least $1-c_{1}e^{-c_{2}t}$ that

$\displaystyle\sup_{f\in\mcF,g\in\mcG}\abs{\frac{1}{N}\sum_{n=1}^{N}f(X_{n})g(X_{n})-\E\bigl{[}f(X)g(X)\bigr{]}}$
$\displaystyle\hskip 28.45274pt\leq
c_{3}\insquare{\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sup_{f\in\mcF}\normn{f}_{\psi_{2}}\gamma_{2}(\mcG,\psi_{2})\lor\sup_{g\in\mcG}\normn{g}_{\psi_{2}}\gamma_{2}(\mcF,\psi_{2})}\lor\frac{\gamma_{2}(\mcF,\psi_{2})\gamma_{2}(\mcG,\psi_{2})}{N}}.$

###### Proof.

For notational brevity, throughout this proof we write $\gamma_{2}(\mcF)$
instead of $\gamma_{2}(\mcF,\psi_{2})$ and $\mathsf{d}_{\psi_{2}}(\mcF)$
instead of $\sup_{f\in\mcF}\normn{f}$ and similarly for the class $\mcG$. The
result follows by an application of [74, Theorem 1.13] and the ensuing remark,
which deals with the case $\mcF=\mcG$, but is easily extended to the general
case considered here. Together they imply that, for any $u\geq 1$, it holds
with probability at least
$1-2\exp\inparen{-cu^{2}\inparen{\frac{\gamma_{2}^{2}(\mcF)}{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}^{2}(\mcG)}{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}}}$
that

$\displaystyle\sup_{f\in\mcF,g\in\mcG}\abs{\frac{1}{N}\sum_{n=1}^{N}f(X_{n})g(X_{n})-\E\bigl{[}f(X)g(X)\bigr{]}}\lesssim\frac{u^{2}}{N}\gamma_{2}(\mcF)\gamma_{2}(\mcG)+\frac{u}{\sqrt{N}}\inparen{\gamma_{2}(\mcF)\mathsf{d}_{\psi_{2}}(\mcG)+\gamma_{2}(\mcG)\mathsf{d}_{\psi_{2}}(\mcF)}.$
(B.3)

We seek to rewrite (B.3) so that all problem specific terms appear only in the
upper bound. To this end, let

$\displaystyle t\equiv
u^{2}\inparen{\frac{\gamma_{2}^{2}(\mcF)}{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}^{2}(\mcG)}{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}}\implies
u=\sqrt{t}\inparen{\frac{\mathsf{d}_{\psi_{2}}(\mcF)}{\gamma_{2}(\mcF)}\lor\frac{\mathsf{d}_{\psi_{2}}(\mcG)}{\gamma_{2}(\mcG)}}$

and note that since $u\geq 1$, it must hold that
$t\geq\inparen{\frac{\gamma_{2}^{2}(\mcF)}{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}^{2}(\mcG)}{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}}$.
Therefore, for any
$t\geq\inparen{\frac{\gamma_{2}^{2}(\mcF)}{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}^{2}(\mcG)}{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}}$,
we have that with probability at least $1-2e^{-ct}$, the right-hand side of
(B.3) becomes

$\displaystyle\frac{t}{N}\inparen{\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}{\gamma^{2}_{2}(\mcF)}\lor\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}{\gamma^{2}_{2}(\mcG)}}\gamma_{2}(\mcF)\gamma_{2}(\mcG)+\frac{\sqrt{t}}{\sqrt{N}}\inparen{\frac{\mathsf{d}_{\psi_{2}}(\mcF)}{\gamma_{2}(\mcF)}\lor\frac{\mathsf{d}_{\psi_{2}}(\mcG)}{\gamma_{2}(\mcG)}}\inparen{\gamma_{2}(\mcF)\mathsf{d}_{\psi_{2}}(\mcG)+\gamma_{2}(\mcG)\mathsf{d}_{\psi_{2}}(\mcF)}.$

The above implies that, for any $t\geq 1$, it holds with probability at least

$1-2\exp\inparen{-c\inparen{t\lor\inparen{\frac{\gamma_{2}^{2}(\mcF)}{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}^{2}(\mcG)}{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}}}}\geq
1-2e^{-ct},$

that

$\displaystyle\frac{1}{N}\inparen{t\lor\inparen{\frac{\gamma_{2}^{2}(\mcF)}{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}^{2}(\mcG)}{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}}}\inparen{\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcF)}{\gamma^{2}_{2}(\mcF)}\lor\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcG)}{\gamma^{2}_{2}(\mcG)}}\gamma_{2}(\mcF)\gamma_{2}(\mcG)$
(B.4) $\displaystyle+$
$\displaystyle\frac{1}{\sqrt{N}}\inparen{\sqrt{t}\lor\inparen{\frac{\gamma_{2}(\mcF)}{\mathsf{d}_{\psi_{2}}(\mcF)}\land\frac{\gamma_{2}(\mcG)}{\mathsf{d}_{\psi_{2}}(\mcG)}}}\inparen{\frac{\mathsf{d}_{\psi_{2}}(\mcF)}{\gamma_{2}(\mcF)}\lor\frac{\mathsf{d}_{\psi_{2}}(\mcG)}{\gamma_{2}(\mcG)}}\inparen{\gamma_{2}(\mcF)\mathsf{d}_{\psi_{2}}(\mcG)+\gamma_{2}(\mcG)\mathsf{d}_{\psi_{2}}(\mcF)}.$
(B.5)

Straightforward calculations then show that the first of the two terms, (B.4),
is bounded above by

$\displaystyle\frac{t}{N}\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcF)\gamma_{2}(\mcG)}{\gamma_{2}(\mcF)}\lor\frac{t}{N}\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcG)\gamma_{2}(\mcF)}{\gamma_{2}(\mcG)}\lor\frac{\gamma_{2}(\mcF)\gamma_{2}(\mcG)}{N},$

and (B.5) is similarly bounded above by

$\displaystyle\sqrt{\frac{t}{N}}\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcF)\gamma_{2}(\mcG)}{\gamma_{2}(\mcF)}\lor\sqrt{\frac{t}{N}}\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcG)\gamma_{2}(\mcF)}{\gamma_{2}(\mcG)}\lor\frac{\mathsf{d}_{\psi_{2}}(\mcG)\gamma_{2}(\mcF)}{\sqrt{N}}\lor\frac{\mathsf{d}_{\psi_{2}}(\mcF)\gamma_{2}(\mcG)}{\sqrt{N}}.$

Note then that since $0\in\mcF$,

$\displaystyle\mathsf{d}_{\psi_{2}}(\mcF)=\sup_{f\in\mcF}\normn{f}_{\psi_{2}}\leq\sup_{f_{1},f_{2}\in\mcF}\normn{f_{1}-f_{2}}_{\psi_{2}}=\tdiam_{\psi_{2}}(\mcF)\leq\gamma_{2}(\mcF),$

where the final equality holds since
$\gamma_{2}(\mcF)=\inf\sup_{f\in\mcF}\sum_{n=0}^{\infty}2^{n/2}\tdiam_{\psi_{2}}(\Delta_{n}(f))$,
and for $n=0$, $\Delta_{0}=\mcF$. Similarly,
$\mathsf{d}_{\psi_{2}}(\mcG)\leq\gamma_{2}(\mcG)$, and so
$\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcF)\gamma_{2}(\mcG)}{\gamma_{2}(\mcF)}\leq
d_{\psi_{2}}(\mcF)\gamma_{2}(\mcG)$ and
$\frac{\mathsf{d}^{2}_{\psi_{2}}(\mcG)\gamma_{2}(\mcF)}{\gamma_{2}(\mcG)}\leq
d_{\psi_{2}}(\mcG)\gamma_{2}(\mcF)$ which along with the fact that $t\geq 1$
completes the proof. ∎

######  Theorem B.11 (Cross-Covariance Estimation —Max-Norm Bound).

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar[X_{1}]=\Sigma^{X}$. Let
$Y_{1},\dots,Y_{N}$ be $k$-dimensional i.i.d. sub-Gaussian random vectors with
$\E[Y_{1}]=\mu^{Y}$ and $\tvar[Y_{1}]=\Sigma^{Y}$. Define
$\Sigma^{XY}=\E\bigl{[}(X-\mu^{X})(Y-\mu^{Y})^{\top}\bigr{]}$ and consider the
cross-covariance estimator

$\displaystyle\hatSigma^{XY}=\frac{1}{N-1}\sum_{n=1}^{N}(X_{n}-\barX)(Y_{n}-\barY)^{\top}.$

Then there exist positive universal constants $c_{1},c_{2}$ such that, for all
$t\geq 1,$ it holds with probability at least $1-c_{1}e^{-c_{2}t}$ that

$\displaystyle\normn{\hatSigma^{XY}-\Sigma^{XY}}_{\max}$
$\displaystyle\lesssim(\Sigma_{(1)}^{X}\lor\Sigma_{(1)}^{Y})\inparen{\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sqrt{r_{\infty}(\Sigma^{X})}\lor\sqrt{r_{\infty}(\Sigma^{Y})}}\lor\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{r_{\infty}(\Sigma^{Y})}{N}}}.$

###### Proof.

Assume first that $\mu^{X}=\mu^{Y}=0$. Let $Z_{1},\dots,Z_{N}$ be
$d$-dimensional i.i.d. sub-Gaussian random vectors with zero mean and
$\tvar[Z_{1}]=\Sigma^{X}$, and similarly let $V_{1},\dots,V_{N}$ be
$k$-dimensional i.i.d. sub-Gaussian random vectors with zero mean and
$\tvar[V_{1}]=\Sigma^{Y}$. Further, let
$W_{n}\equiv[Z_{n}^{\top},V_{n}^{\top}]^{\top}$ for $n=1,\dots,N$. We denote
the distribution of $W_{1}$ by $\P$ and note that $\normn{\cdot}_{\psi_{2}}$
and $\normn{\cdot}_{L_{2}}$ are defined implicitly with respect to $\P$
throughout this proof. Define
$\hatSigma^{0}=N^{-1}\sum_{n=1}^{N}Z_{n}V_{n}^{\top}$. Define the dilation
operator: $\mcH:\R^{d\times k}\to\R^{(d+k)\times(d+k)}$ by

$\displaystyle\mcH(A)=\begin{bmatrix}O&A\\\ A^{\top}&O\end{bmatrix},$

see for example [99, Section 2.1.16], and note that
$\normn{A}_{\max}=\normn{\mcH(A)}_{\max}$. Let $\mcB^{m}$ be the space of
standard basis vectors in $m$ dimensions, i.e. any $b\in\mcB^{m}$ is an
$m$-dimensional vector with $1$ in a single coordinate and $0$ otherwise.
Then, for $e_{i},e_{j}\in\mcB^{d+k}$, we have

$\displaystyle\normn{\hatSigma^{0}-\Sigma^{XY}}_{\max}=\normn{\mcH(\hatSigma^{0})-\mcH(\Sigma^{XY})}_{\max}$
$\displaystyle=\max_{1\leq i,j\leq
d+k}\inp{(\mcH(\hatSigma^{0})-\mcH(\Sigma^{XY}))e_{i},e_{j}}$
$\displaystyle\leq
2\sup_{u\in\mcU}\abs{\inp{(\mcH(\hatSigma^{0})-\mcH(\Sigma^{XY}))u,u}},$

where

$\displaystyle\mcU\equiv\biggl{\\{}u\in\R^{d+k}:u=\pm\frac{1}{2}(e_{i}\pm
e_{j})\text{ and }e_{i},e_{j}\in\mcB^{d+k}\biggr{\\}}.$

Writing $u=[u_{1}^{\top},u_{2}^{\top}]^{\top}$ where $u_{1}\in\R^{d}$ and
$u_{2}\in\R^{k}$, we have

$\displaystyle\inp{\mcH(\hatSigma^{0})u,u}=\frac{2}{N}\sum_{n=1}^{N}\inp{u_{1},Z_{n}}\inp{u_{2},V_{n}}=\frac{2}{N}\sum_{n=1}^{N}f_{u}(W_{n}),$

where $f_{u}(W_{n})\equiv\inp{\msA_{1}W_{n},u_{1}}\inp{\msA_{2}W_{n},u_{2}}$
and where $\msA_{1}\equiv[I_{d},O_{d\times k}]\in\R^{d\times(d+k)}$ and
$\msA_{2}\equiv[O_{k\times d},I_{k}]\in\R^{k\times(d+k)}$ are the relevant
selection matrices so that $\msA_{1}W_{n}=Z_{n}$ and $\msA_{2}W_{n}=V_{n}$. We
define the class of functions

$\displaystyle\mcF_{\mcU}\equiv\biggl{\\{}f_{u}(\cdot)=\inp{\msA_{1}\cdot,u_{1}}\inp{\msA_{2}\cdot,u_{2}}:u=[u_{1}^{\top},u_{2}^{\top}]^{\top}\in\mcU\biggr{\\}}.$

It is clear then that $\mcF_{\mcU}\subset\mcF_{1}\cdot\mcF_{2},$ where

$\displaystyle\mcU_{1}$
$\displaystyle\equiv\biggl{\\{}u_{1}\in\R^{d}:u_{1}=\pm\frac{1}{2}(e_{i}\pm
e_{j})\text{ and
}e_{i},e_{j}\in\mcB_{d}\biggr{\\}},\quad\mcF_{1}\equiv\\{f(\cdot)=\inp{\msA_{1}\cdot,u_{1}}:u_{1}\in\mcU_{1}\\},$
$\displaystyle\mcU_{2}$
$\displaystyle\equiv\biggl{\\{}u_{2}\in\R^{k}:u_{2}=\pm\frac{1}{2}(e_{i}\pm
e_{j})\text{ and
}e_{i},e_{j}\in\mcB_{k}\biggr{\\}},\quad\mcF_{2}\equiv\\{f(\cdot)=\inp{\msA_{2}\cdot,u_{2}}:u_{2}\in\mcU_{2}\\},$

and

$\displaystyle\mcF_{1}\cdot\mcF_{2}\equiv\bigl{\\{}f(\cdot)=f_{1}(\cdot)f_{2}(\cdot):f_{1}\in\mcF_{1},f_{2}\in\mcF_{2}\bigr{\\}}.$

We can then apply the product empirical process concentration bound of Theorem
B.10, which implies that, with probability $1-c_{1}e^{-c_{2}t}$,

$\displaystyle\sup_{u\in\mcU}\abs{\inp{(\mcH(\hatSigma^{0})-\mcH(\Sigma^{XY}))u,u}}=$
$\displaystyle\sup_{f_{u}\in\mcF_{\mcU}}\abs{\frac{1}{N}\sum_{n=1}^{N}f_{u}(W_{n})-\E\bigl{[}f_{u}(W_{n})\bigr{]}}$
$\displaystyle\lesssim$
$\displaystyle\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\mathsf{d}_{\psi_{2}}(\mcF_{1})\gamma_{2}(\mcF_{2})\lor\mathsf{d}_{\psi_{2}}(\mcF_{2})\gamma_{2}(\mcF_{1})}\lor\frac{\gamma_{2}(\mcF_{1})\gamma_{2}(\mcF_{2})}{N},$
(B.6)

where we use the notational shorthand
$\gamma_{2}(\mcF_{1})=\gamma_{2}(\mcF_{1},\psi_{2})$ and
$\mathsf{d}_{\psi_{2}}(\mcF_{1})=\sup_{f\in\mcF_{1}}\normn{f}_{\psi_{2}},$ and
similarly for $\mcF_{2}$. Following a similar approach to the one taken in the
proof of Theorem B.7, it follows by the equivalence of $\psi_{2}$ and $L_{2}$
norms for linear functionals that

$\displaystyle
d_{\psi_{2}}(\mcF_{1})=\sup_{f_{1}\in\mcF_{1}}\normn{f_{1}}_{\psi_{2}}\lesssim\sup_{f_{1}\in\mcF_{1}}\normn{f_{1}}_{L_{2}}=\max_{u_{1}\in\mcU_{1}}\sqrt{\langle
u_{1},\Sigma^{X}u_{1}\rangle}\leq\sqrt{\Sigma^{X}_{(1)}},$

and similarly that $d_{\psi_{2}}(\mcF_{2})\leq\sqrt{\Sigma^{Y}_{(1)}}$.
Further,

$\displaystyle\gamma_{2}(\mcF_{1})=\gamma_{2}(\mcF_{1},\psi_{2})\lesssim\gamma_{2}(\mcF_{1},L_{2})=\gamma_{2}(\mcU_{1},\mathsf{d}_{X}),$

where

$\displaystyle\mathsf{d}_{X}(u,v)$
$\displaystyle=\sqrt{\E\insquare{(\inp{g_{X},u}-\inp{g_{X},v})^{2}}},\qquad
g_{X}\sim\mcN(0,\Sigma^{X}).$

By Theorem B.3 and Lemma B.6,

$\displaystyle\gamma_{2}(\mcU_{1},\mathsf{d}_{X})$
$\displaystyle\lesssim\E\insquare{\sup_{u_{1}\in\mcU_{1}}\inp{g_{X},u_{1}}}=\E\insquare{\max_{i,j\leq
d}\inp{g_{X},\pm\frac{1}{2}(e_{i}\pm e_{j})}}$
$\displaystyle\leq\E\insquare{\max_{i\leq
d}\inp{g_{X},e_{i}}}\lesssim\max_{i\leq d}\sqrt{\Sigma^{X}_{(i)}\log(i+1)}.$

Similarly, $\gamma_{2}(\mcF_{2})\lesssim\max_{j\leq
k}\sqrt{\Sigma^{Y}_{(j)}\log(j+1)}.$ In summary, we have that

$\displaystyle\normn{\hatSigma^{0}-\Sigma^{XY}}_{\max}$
$\displaystyle\lesssim\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sqrt{\Sigma^{X}_{(1)}}\max_{j\leq
k}\sqrt{\Sigma^{Y}_{(j)}\log(j+1)}\lor\sqrt{\Sigma^{Y}_{(1)}}\max_{i\leq
d}\sqrt{\Sigma^{X}_{(i)}\log(i+1)}}$ $\displaystyle\lor\frac{\max_{i\leq
d}\sqrt{\Sigma^{X}_{(i)}\log(i+1)}\max_{j\leq
k}\sqrt{\Sigma^{Y}_{(j)}\log(j+1)}}{N}$
$\displaystyle\lesssim\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\Sigma_{(1)}^{X}\sqrt{r_{\infty}(\Sigma^{X})}\lor\Sigma_{(1)}^{Y}\sqrt{r_{\infty}(\Sigma^{Y})}}\lor\sqrt{\frac{\Sigma_{(1)}^{X}r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{\Sigma_{(1)}^{Y}r_{\infty}(\Sigma^{Y})}{N}}$
$\displaystyle\lesssim(\Sigma_{(1)}^{X}\lor\Sigma_{(1)}^{Y})\inparen{\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sqrt{r_{\infty}(\Sigma^{X})}\lor\sqrt{r_{\infty}(\Sigma^{Y})}}\lor\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{r_{\infty}(\Sigma^{Y})}{N}}}.$

In the un-centered case, take $X_{n}=Z_{n}+\mu^{X}$ and $Y_{n}=V_{n}+\mu^{Y}$
for $n=1,\dots,N$, then $\hatSigma^{XY}=\hatSigma^{0}-\barX\barY^{\top}$, and
so

$\displaystyle\normn{\hatSigma^{XY}-\Sigma^{XY}}_{\max}$
$\displaystyle\leq\normn{\hatSigma^{0}-\Sigma^{XY}}_{\max}+\normn{\barX\barY^{\top}}_{\max}.$

The first term is controlled by appealing to the result in the centered case.
For the second term, we note that by Lemma B.6

$\displaystyle\normn{\barX\barY^{\top}}_{\max}\leq\normn{\barX}_{\max}\normn{\barY}_{\max}$
$\displaystyle\lesssim\frac{1}{N}\max_{i\leq
d}\sqrt{\Sigma^{X}_{(i)}\log(i+1)}\max_{j\leq
k}\sqrt{\Sigma^{Y}_{(j)}\log(j+1)}$
$\displaystyle\leq\sqrt{\frac{\Sigma_{(1)}^{X}r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{\Sigma_{(1)}^{Y}r_{\infty}(\Sigma^{Y})}{N}}.\qed$

######  Theorem B.12 (Cross-Covariance Estimation with Localized Sample Cross-
Covariance —Operator-Norm bound).

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar[X_{1}]=\Sigma^{X}$. Let
$Y_{1},\dots,Y_{N}$ be $k$-dimensional i.i.d. sub-Gaussian random vectors with
$\E[Y_{1}]=\mu^{Y}$ and $\tvar[Y_{1}]=\Sigma^{Y}$. Define
$\Sigma^{XY}=\E\bigl{[}(X-\mu^{X})(Y-\mu^{Y})^{\top}\bigr{]}$ and consider the
estimator

$\displaystyle\hatSigma^{XY}=\frac{1}{N-1}\sum_{n=1}^{N}(X_{n}-\barX)(Y_{n}-\barY)^{\top}.$

Assume that $\Sigma^{XY}\in\mcU_{d,k}(q_{1},R_{q_{1}})$ and
$\Sigma^{YX}\in\mcU_{k,d}(q_{2},R_{q_{2}})$ where $q_{1},q_{2}\in[0,1)$ and
$R_{q_{1}},R_{q_{2}}$ are positive constants. For any $t\geq 1$, set

$\displaystyle\rho_{N}\asymp(\Sigma_{(1)}^{X}\lor\Sigma_{(1)}^{Y})\inparen{\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sqrt{r_{\infty}(\Sigma^{X})}\lor\sqrt{r_{\infty}(\Sigma^{Y})}}\lor\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{r_{\infty}(\Sigma^{Y})}{N}}},$

and let $\hatSigma^{XY}_{\rho_{N}}$ be the localized sample cross-covariance
estimator. There exist positive universal constants $c_{1},c_{2}$ such that,
with probability at least $1-c_{1}e^{-c_{2}t}$,

$\displaystyle\normn{\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY}}\lesssim
R_{q_{1}}\rho_{N}^{1-q_{1}}\lor R_{q_{2}}\rho_{N}^{1-q_{2}}.$

###### Proof of Theorem B.12.

Let $E$ denote the event on which
$\normn{\hatSigma^{XY}-\Sigma^{XY}}_{\max}=\normn{\hatSigma^{YX}-\Sigma^{YX}}_{\max}\lesssim\rho_{N}$.
By Theorem B.11, $E$ holds with probability at least $1-c_{1}e^{-c_{2}t}$.
Conditional on $E$, and following an analysis identical to the one in the
proof of Theorem B.9 with $\hatSigma^{XY}(\hatSigma^{YX})$ and
$\Sigma^{XY}(\Sigma^{YX})$ in place of $\hatSigma^{X}$ and $\Sigma^{X}$
respectively, it follows that

$\displaystyle\normn{\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY}}_{\infty}$
$\displaystyle\lesssim R_{q_{1}}\rho_{N}^{1-q_{1}},$

and

$\displaystyle\normn{\hatSigma^{YX}_{\rho_{N}}-\Sigma^{YX}}_{\infty}\lesssim
R_{q_{2}}\rho_{N}^{1-q_{2}}.$

The result then follows by noting that

$\displaystyle\normn{\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY}}$
$\displaystyle=\normn{\mcH(\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY})}\leq\normn{\mcH(\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY})}_{\infty}$
$\displaystyle=\normn{\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY}}_{\infty}\lor\normn{\hatSigma^{YX}_{\rho_{N}}-\Sigma^{YX}}_{\infty}\lesssim
R_{q_{1}}\rho_{N}^{1-q_{1}}\lor R_{q_{2}}\rho_{N}^{1-q_{2}},$

where $\mcH$ is the dilation operator defined in the proof of Theorem B.11. ∎

###### Proof of Theorem 3.3.

The proof follows immediately from Theorem B.12: since
$\upr_{1},\dots,\upr_{N}$ are i.i.d. Gaussian they are sub-Gaussian. Moreover,
since $\mcG$ is Lipschitz, by [102, Theorem 5.2.2],
$\normn{\mcG(\upr_{1})-\E[\mcG(\upr_{1})]}_{\psi_{2}}\leq\normn{\mcG}_{\text{Lip}}\normn{\Cpr}^{1/2}<\infty$,
and so $\mcG(\upr_{1}),\dots,\mcG(\upr_{N})$ are i.i.d. sub-Gaussian random
vectors. ∎

######  Lemma B.13 (Stein’s Lemma [90]).

Let $\upr\sim\mcN(\mpr,\Cpr)$ be a $d$-dimensional Gaussian vector. Let
$h:\R^{d}\to\R$ such that $\partial_{j}h\equiv\partial h(u)/\partial u_{j}$
exists almost everywhere and $\E[|\partial_{j}h(\upr)|]<\infty$,
$j=1,\dots,d$. Then

$\displaystyle\text{Cov}\bigl{(}\upr_{j},h(\upr)\bigr{)}=\sum_{l=1}^{d}\Cpr_{jl}\E[\partial_{l}h(\upr)].$

######  Lemma B.14 (Soft-Sparsity of Cross-Covariance —Nonlinear Forward Map).

Let $\upr$ be a $d$-dimensional Gaussian random vector with $\E[\upr]=\mpr$
and $\tvar[\upr]=\Cpr\in\msU_{d}(q,c)$. Consider the function
$\mcG:\R^{d}\to\R^{k}$ with coordinate functions $\mcG_{1},\dots,\mcG_{k}$.
Assume that for each $i=1,\dots,d$ and $j=1,\dots,k$, $\mcG_{j}:\R^{d}\to\R$
for $j=1,\dots,k$, such that
$\partial_{i}\mcG_{j}\equiv\partial\mcG_{j}(\upr)/\partial\upr_{i}$ exists
almost everywhere, and $\E[|\partial_{i}\mcG_{j}|]<\infty$. Let
$D\mcG\in\R^{k\times d}$ denote the Jacobian of $\mcG$, and assume that
$\E\bigl{[}(D\mcG)^{\top}\bigr{]}\in\msU_{d,k}(q,a)$ for some $q\in[0,1)$ and
$a>0$. Then,

$\displaystyle\Cpr^{\,up}\in\msU_{d,k}\bigl{(}q,ac\normn{\E[D\mcG]}_{\max}^{1-q}\normn{\Cpr}_{\max}^{1-q}\bigr{)}.$

###### Proof.

By Stein’s Lemma (Lemma B.13), the $i$-th row sum of $\Cpr^{\,up}$ is given by

$\displaystyle\sum_{j=1}^{k}C^{\,up}_{ij}=\sum_{j=1}^{k}\sum_{l=1}^{d}\Cpr_{il}\E\bigl{[}\partial_{l}\mcG_{j}(\upr)\bigr{]}$
$\displaystyle=\sum_{l=1}^{d}\Cpr_{il}\sum_{j=1}^{k}\E\bigl{[}\partial_{l}\mcG_{j}(\upr)\bigr{]}$
$\displaystyle=\normn{\E[D\mcG]}_{\max}\sum_{l=1}^{d}\Cpr_{il}\sum_{j=1}^{k}\frac{\E[\partial_{l}\mcG_{j}(\upr)]}{\normn{\E[D\mcG]}_{\max}}$
$\displaystyle\leq\normn{\E[D\mcG]}_{\max}^{1-q}\sum_{l=1}^{d}\Cpr_{il}\sum_{j=1}^{k}\E[\partial_{l}\mcG_{j}(\upr)]^{q}$
$\displaystyle\leq a\normn{\E[D\mcG]}_{\max}^{1-q}\sum_{l=1}^{d}\Cpr_{il}$
$\displaystyle\leq ac\normn{\E[D\mcG]}_{\max}^{1-q}\normn{\Cpr}_{\max}^{1-q},$

where the first inequality holds since $q\in[0,1)$ and
$\E[\partial_{l}\mcG_{j}(\upr)]\leq\normn{\E[D\mcG]}_{\max}$. ∎

######  Lemma B.15 (Product of Two Soft-Sparse Matrices).

Fix $q\in[0,1)$ and let $S\in\msU_{d}(q,s)$ and assume $S^{\top}=S$. Let
$B\in\msU_{k,d}(q,b)$. Then
$BS\in\msU_{k,d}(q,bs\normn{B}_{\max}^{1-q}\normn{S}_{\max}^{1-q})$.

###### Proof.

The $(i,j)$-th element of $BS$ is given by
$[BS]_{ij}=\sum_{l=1}^{d}B_{il}S_{lj}$, and so the sum of the $i$-th row of
$BS$ satisfies

$\displaystyle\sum_{j=1}^{d}[BS]_{ij}=\sum_{j=1}^{d}\sum_{l=1}^{d}B_{il}S_{lj}=\sum_{l=1}^{d}B_{il}\sum_{j=1}^{d}S_{lj}$
$\displaystyle=\normn{B}_{\max}\normn{S}_{\max}\sum_{l=1}^{d}\frac{B_{il}}{\normn{B}_{\max}}\sum_{j=1}^{d}\frac{S_{lj}}{\normn{S}_{\max}}$
$\displaystyle\leq\normn{B}_{\max}\normn{S}_{\max}\sum_{l=1}^{d}\inparen{\frac{B_{il}}{\normn{B}_{\max}}}^{q}\sum_{j=1}^{d}\inparen{\frac{S_{lj}}{\normn{S}_{\max}}}^{q}$
$\displaystyle\leq\normn{B}_{\max}^{1-q}\normn{S}_{\max}^{1-q}bs,$

where the first inequality holds since $q\in[0,1)$, and the second follows by
the symmetry of $S$. ∎

######  Lemma B.16 (Product of Three Soft-Sparse Matrices).

Fix $q\in[0,1)$ and let $S\in\msU_{d}(q,s)$ with $S^{\top}=S$. Let
$B\in\msU_{k,d}(q,b_{1})$ and $B^{\top}\in\msU_{d,k}(q,b_{2})$, that is, $B$
is both row and column sparse. Then
$BSB^{\top}\in\msU_{k,d}(q,b_{1}b_{2}s\normn{B}^{2(1-q)}_{\max}\normn{S}_{\max}^{1-q})$.

###### Proof.

The $(i,j)$-th element of $BSB^{\top}$ is given by

$\displaystyle[BSB^{\top}]_{ij}=\sum_{m=1}^{d}[BS]_{im}B^{\top}_{mj}=\sum_{m=1}^{d}[BS]_{im}B_{jm}=\sum_{m=1}^{d}\inparen{\sum_{l=1}^{d}B_{il}S_{lm}}B_{jm}.$

Therefore, the sum of the $i$-th row of $BSB^{\top}$ satisfies

$\displaystyle\sum_{j=1}^{k}[BSB^{\top}]_{ij}$
$\displaystyle=\sum_{j=1}^{k}\sum_{m=1}^{d}\sum_{l=1}^{d}B_{il}S_{lm}B_{jm}=\sum_{m=1}^{d}\sum_{l=1}^{d}B_{il}S_{lm}\sum_{j=1}^{k}B_{jm}$
$\displaystyle\leq\normn{B}^{1-q}_{\max}b_{2}\sum_{m=1}^{d}\sum_{l=1}^{d}B_{il}S_{lm}\leq
b_{1}b_{2}s\normn{B}^{2(1-q)}_{\max}\normn{S}_{\max}^{1-q},$

where the final inequality follows by Lemma B.15. ∎

######  Lemma B.17 (Sample Covariance Deviation).

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar[X_{1}]=\Sigma^{X}.$ Let
$\hatSigma^{X}_{N}=(N-1)^{-1}\sum_{n=1}^{N}(X_{n}-\mu^{X})(X_{n}-\mu^{X})^{\top}$.
Then

$\displaystyle\hatSigma_{N}^{X}-\hatSigma_{N-1}^{X}$
$\displaystyle\asymp\frac{1}{N}X_{N}X_{N}^{\top}-\frac{1}{N}\hatSigma^{0}_{N-1}-\frac{1}{N^{2}}X_{N}X_{N}^{\top}-\inparen{\inparen{\frac{N-1}{N}}^{2}-1}\barX_{N-1}\barX_{N-1}^{\top}$
$\displaystyle-\inparen{\frac{N-1}{N^{2}}}\inparen{X_{N}\barX_{N-1}^{\top}+\barX_{N-1}X_{N}^{\top}},$

where $\hatSigma^{0}_{N}=N^{-1}\sum_{n=1}^{N}X_{n}X_{n}^{\top}$.

###### Proof.

We work with the biased sample covariance estimator
$\frac{1}{N}\sum_{n=1}^{n}(X_{n}-\barX_{N})(X_{n}-\barX_{N})^{\top},$ which is
equivalent to the unbiased covariance estimator up to constants. Note then
that

$\displaystyle\hatSigma_{N}^{X}$
$\displaystyle\asymp\frac{1}{N}\sum_{n=1}^{N}(X_{n}-\barX_{N})(X_{n}-\barX_{N})^{\top}=\frac{1}{N}\sum_{n=1}^{N}X_{n}X_{n}^{\top}-\barX_{N}\barX_{N}^{\top}=\hatSigma_{N}^{0}-\barX_{N}\barX_{N}^{\top}.$

We now seek to control the difference $\hatSigma_{N}^{X}-\hatSigma_{N-1}^{X}.$
To that end, note that

$\displaystyle\barX_{N}\barX_{N}^{\top}$
$\displaystyle=\inparen{\frac{1}{N}X_{N}+\frac{N-1}{N}\barX_{N-1}}\inparen{\frac{1}{N}X_{N}+\frac{N-1}{N}\barX_{N-1}}^{\top}$
$\displaystyle=\frac{1}{N^{2}}X_{N}X_{N}^{\top}+\inparen{\frac{N-1}{N}}^{2}\barX_{N-1}\barX_{N-1}^{\top}+\inparen{\frac{N-1}{N^{2}}}\inparen{X_{N}\barX_{N-1}^{\top}+\barX_{N-1}X_{N}^{\top}},$

and so

$\displaystyle\barX_{N}\barX_{N}^{\top}-\barX_{N-1}\barX_{N-1}^{\top}$
$\displaystyle=\frac{1}{N^{2}}X_{N}X_{N}^{\top}+\inparen{\inparen{\frac{N-1}{N}}^{2}-1}\barX_{N-1}\barX_{N-1}^{\top}$
$\displaystyle+\inparen{\frac{N-1}{N^{2}}}\inparen{X_{N}\barX_{N-1}^{\top}+\barX_{N-1}X_{N}^{\top}}.$
(B.7)

Therefore,

$\displaystyle\hatSigma_{N}^{X}-\hatSigma_{N-1}^{X}$
$\displaystyle\asymp\inparen{\frac{1}{N}\sum_{n=1}^{N}X_{n}X_{n}^{\top}-\barX_{N}\barX_{N}^{\top}}-\inparen{\frac{1}{N-1}\sum_{n=1}^{N-1}X_{n}X_{n}^{\top}-\barX_{N-1}\barX_{N-1}^{\top}}$
$\displaystyle=\frac{1}{N}X_{N}X_{N}^{\top}+\inparen{\inparen{\frac{1}{N}-\frac{1}{N-1}}\sum_{n=1}^{N-1}X_{n}X_{n}^{\top}}+\inparen{\barX_{N-1}\barX_{N-1}^{\top}-\barX_{N}\barX_{N}^{\top}}$
$\displaystyle=\frac{1}{N}X_{N}X_{N}^{\top}-\frac{1}{N}\hatSigma^{0}_{N-1}-\frac{1}{N^{2}}X_{N}X_{N}^{\top}-\inparen{\inparen{\frac{N-1}{N}}^{2}-1}\barX_{N-1}\barX_{N-1}^{\top}$
$\displaystyle-\inparen{\frac{N-1}{N^{2}}}\inparen{X_{N}\barX_{N-1}^{\top}+\barX_{N-1}X_{N}^{\top}},$
(B.8)

where the last equality follows by (B.1.3). ∎

######  Lemma B.18 (Sample Cross-Covariance Deviation).

Let $X_{1},\dots,X_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random vectors
with $\E[X_{1}]=\mu^{X}$ and $\tvar[X_{1}]=\Sigma^{X}.$ Let
$Y_{1},\dots,Y_{N}$ be $k$-dimensional i.i.d. sub-Gaussian random vectors with
$\E[Y_{1}]=\mu^{Y}$ and $\tvar[Y_{1}]=\Sigma^{Y}.$ Let
$\hatSigma^{XY}_{N}=(N-1)^{-1}\sum_{n=1}^{N}(X_{n}-\mu^{X})(Y_{n}-\mu^{Y})^{\top}$.
Then

$\displaystyle\hatSigma_{N}^{XY}-\hatSigma_{N-1}^{XY}$
$\displaystyle\asymp\frac{1}{N}X_{N}Y_{N}^{\top}-\frac{1}{N}\hatSigma^{0,XY}_{N-1}-\frac{1}{N^{2}}X_{N}Y_{N}^{\top}-\inparen{\inparen{\frac{N-1}{N}}^{2}-1}\barX_{N-1}\barY_{N-1}^{\top}$
$\displaystyle-\inparen{\frac{N-1}{N^{2}}}\inparen{X_{N}\barY_{N-1}^{\top}+\barX_{N-1}Y_{N}^{\top}},$

where $\hatSigma^{0,XY}_{N-1}=N^{-1}\sum_{n=1}^{N}X_{n}Y_{n}$.

###### Proof.

The result follows using the same approach utilized in the proof of Lemma B.17
and is omitted for brevity. ∎

######  Lemma B.19 (Covariance Estimation with Known Particle — Operator-Norm
Bound).

Consider the set-up in Lemma B.17 and assume additionally that $X_{n}$ is
known for some $n\in\\{1,\dots,N\\}$. Then with probability at least
$1-ce^{-t}$

$\displaystyle\normn{\hatSigma^{X}_{N}-\Sigma^{X}}$
$\displaystyle\lesssim\frac{c(\normn{X_{n}}_{2},\normn{\mu^{X}}_{2})}{N}+\normn{\Sigma^{X}}\inparen{\sqrt{\frac{r_{2}(\Sigma^{X})}{N}}\lor\frac{r_{2}(\Sigma^{X})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}}.$

###### Proof.

By symmetry, we can assume without loss of generality that $n=N$. Let $E_{1}$
denote the event on which
$\normn{\barX_{N-1}-\mu^{X}}_{2}\lesssim\sqrt{\normn{\Sigma^{X}}\frac{r_{2}(\Sigma^{X})\lor
t}{N-1}}\asymp\sqrt{\normn{\Sigma^{X}}\frac{r_{2}(\Sigma^{X})\lor t}{N}}$.
Then by Theorem A.1, $\P(E_{1})\geq 1-e^{-t}$ and on $E_{1}$ it holds that

$\displaystyle\normn{\hatSigma^{X}_{N}-\hatSigma^{X}_{N-1}}$
$\displaystyle\lesssim\frac{1}{N}\normn{X_{N}X_{N}^{\top}}+\frac{1}{N}\normn{\hatSigma^{0}_{N-1}}+\inparen{\inparen{\frac{N-1}{N}}^{2}-1}\normn{\barX_{N-1}\barX_{N-1}^{\top}}$
$\displaystyle+\frac{N-1}{N^{2}}\inparen{\normn{X_{N}\barX_{N-1}^{\top}}+\normn{\barX_{N-1}X_{N}^{\top}}}$
$\displaystyle\lesssim\frac{1}{N}\normn{X_{N}}^{2}_{2}+\frac{1}{N}\normn{\hatSigma^{0}_{N-1}}+\frac{1}{N}\normn{\barX_{N-1}}^{2}_{2}+\frac{1}{N}\normn{X_{N}}_{2}\normn{\barX_{N-1}}_{2}$
$\displaystyle\leq\frac{1}{N}\normn{X_{N}}^{2}_{2}+\frac{1}{N}\normn{\hatSigma^{0}_{N-1}-\Sigma^{X}}+\frac{1}{N}\normn{\Sigma^{X}}+\frac{1}{N}\normn{\barX_{N-1}-\mu^{X}}^{2}_{2}+\frac{1}{N}\normn{\mu^{X}}^{2}_{2}$
$\displaystyle+\frac{1}{N}\normn{X_{N}}_{2}\normn{\barX_{N-1}-\mu^{X}}_{2}+\frac{1}{N}\normn{X_{N}}_{2}\normn{\mu^{X}}_{2}$
$\displaystyle\lesssim\frac{1}{N}\normn{X_{N}}^{2}_{2}+\frac{1}{N}\normn{\hatSigma^{0}_{N-1}-\Sigma^{X}}+\frac{1}{N}\normn{\Sigma^{X}}+\normn{\Sigma^{X}}\frac{r_{2}(\Sigma^{X})\lor
t}{N^{2}}+\frac{1}{N}\normn{\mu^{X}}^{2}_{2}$
$\displaystyle+\normn{X_{N}}_{2}\sqrt{\normn{\Sigma^{X}}}\frac{\sqrt{r_{2}(\Sigma^{X})\lor
t}}{N^{3/2}}+\frac{1}{N}\normn{X_{N}}_{2}\normn{\mu^{X}}_{2},$ (B.9)

where the first line follows by Lemma B.17. Let $E_{2}$ denote the event on
which

$\displaystyle\normn{\hatSigma^{X}_{N-1}-\Sigma^{X}}$
$\displaystyle\lesssim\normn{\Sigma^{X}}\inparen{\sqrt{\frac{r_{2}(\Sigma^{X})}{N-1}}\lor\frac{r_{2}(\Sigma^{X})}{N-1}\lor\sqrt{\frac{t}{N-1}}\lor\frac{t}{N-1}}$
$\displaystyle\asymp\normn{\Sigma^{X}}\inparen{\sqrt{\frac{r_{2}(\Sigma^{X})}{N}}\lor\frac{r_{2}(\Sigma^{X})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}}.$

Then by Proposition 2.1, $\P(E_{2})\geq 1-ce^{-t}$. It holds on $E_{1}\cap
E_{2}$ that

$\displaystyle\normn{\hatSigma^{X}_{N}-\Sigma^{X}}$
$\displaystyle\leq\normn{\hatSigma^{X}_{N}-\hatSigma^{X}_{N-1}}+\normn{\hatSigma^{X}_{N-1}-\Sigma^{X}}$
$\displaystyle\lesssim\frac{1}{N}\normn{X_{N}}^{2}_{2}+\frac{1}{N}\normn{\hatSigma^{0}_{N-1}-\Sigma^{X}}+\frac{1}{N}\normn{\Sigma^{X}}+\normn{\Sigma^{X}}\frac{r_{2}(\Sigma^{X})\lor
t}{N^{2}}+\frac{1}{N}\normn{\mu^{X}}^{2}_{2}$
$\displaystyle+\normn{X_{N}}_{2}\sqrt{\normn{\Sigma^{X}}}\frac{\sqrt{r_{2}(\Sigma^{X})\lor
t}}{N^{3/2}}+\frac{1}{N}\normn{X_{N}}_{2}\normn{\mu^{X}}_{2}+\normn{\Sigma^{X}}\inparen{\sqrt{\frac{r_{2}(\Sigma^{X})}{N}}\lor\frac{r_{2}(\Sigma^{X})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}}$
$\displaystyle\lesssim\frac{c(\normn{X_{N}}_{2},\normn{\mu^{X}}_{2})}{N}+\normn{\Sigma^{X}}\inparen{\sqrt{\frac{r_{2}(\Sigma^{X})}{N}}\lor\frac{r_{2}(\Sigma^{X})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}},$

where the first inequality holds by $\eqref{eq:diffsCovarsOpNorm}$. The result
follows by noting that $\P(E_{1}\cap E_{2})\geq 1-ce^{-t}.$ ∎

######  Lemma B.20 (Covariance Estimation with Known Particle — Maximum-Norm
Bound).

Consider the set-up in Lemma B.17 and assume additionally that $X_{n}$ is
known for some $n\in\\{1,\dots,N\\}$. Then with probability at least
$1-ce^{-t}$

$\displaystyle\normn{\hatSigma^{X}_{N}-\Sigma^{X}}_{\max}$
$\displaystyle\lesssim\frac{c(\normn{X_{n}}_{\infty},\normn{\mu^{X}}_{\infty})}{N}+\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}}.$

###### Proof.

As in the proof of Lemma B.19, we may assume that $n=N$. Let $E_{1}$ denote
the event on which
$\normn{\barX_{N-1}-\mu^{X}}_{\infty}\lesssim\sqrt{t\Sigma^{X}_{(1)}\frac{r_{\infty}(\Sigma^{X})}{N-1}}\asymp\sqrt{t\Sigma^{X}_{(1)}\frac{r_{\infty}(\Sigma^{X})}{N}}$.
Then by Lemma B.6, $\P(E_{1})\geq 1-ce^{-ct}$ and on $E_{1}$, using similar
calculations to those used to derive (B.1.3), it holds that

$\displaystyle\normn{\hatSigma^{X}_{N}-\hatSigma^{X}_{N-1}}_{\max}$
$\displaystyle\lesssim\frac{1}{N}\normn{X_{N}}^{2}_{\infty}+\frac{1}{N}\normn{\hatSigma^{0}_{N-1}-\Sigma^{X}}_{\max}+\frac{1}{N}\normn{\Sigma^{X}}_{\max}+t\Sigma^{X}_{(1)}\frac{r_{\infty}(\Sigma^{X})}{N^{2}}+\frac{1}{N}\normn{\mu^{X}}^{2}_{\infty}$
$\displaystyle+\normn{X_{N}}_{\infty}\sqrt{t\Sigma^{X}_{(1)}}\frac{\sqrt{r_{\infty}(\Sigma^{X})}}{N^{3/2}}+\frac{1}{N}\normn{X_{N}}_{\infty}\normn{\mu^{X}}_{\infty}.$
(B.10)

Let $E_{2}$ be the event on which

$\displaystyle\normn{\hatSigma^{X}_{N-1}-\Sigma^{X}}_{\max}\lesssim\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}}.$

By Theorem B.7, $\P(E_{2})\geq 1-ce^{-t}$. Finally, note that the desired
result holds on $E_{1}\cap E_{2}$ and that $\P(E_{1}\cap E_{2})\geq
1-ce^{-t},$ which completes the proof. ∎

######  Lemma B.21 (Cross-Covariance Estimation with Known Particle — Maximum-
Norm Bound).

Consider the set-up in Lemma B.18 and assume additionally that $(X_{n},Y_{n})$
is known for some $n\in\\{1,\dots,N\\}$. Then with probability at least
$1-ce^{-t}$

$\displaystyle\normn{\hatSigma^{XY}_{N}-\Sigma^{XY}}_{\max}$
$\displaystyle\lesssim\frac{c(\normn{X_{n}}_{\infty},\normn{\mu^{X}}_{\infty},\normn{Y_{n}}_{\infty},\normn{\mu^{Y}}_{\infty})}{N}$
$\displaystyle+(\Sigma_{(1)}^{X}\lor\Sigma_{(1)}^{Y})\inparen{\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sqrt{r_{\infty}(\Sigma^{X})}\lor\sqrt{r_{\infty}(\Sigma^{Y})}}\lor\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{r_{\infty}(\Sigma^{Y})}{N}}}.$

###### Proof.

The result follows using the same approach utilized in the proof of Lemma B.17
and utilizing the statements of Lemma B.18 and Theorem B.11. We omit the
details for brevity. ∎

######  Lemma B.22 (Covariance Estimation with Localized Sample Covariance and
with Known Particle —Operator-Norm Bound).

Consider the set-up in Theorem B.9 and assume additionally that $X_{n}$ is
known for some $n\in\\{1,\dots,N\\}$. For any $t\geq 1$, set

$\displaystyle\rho_{N}\asymp\frac{c(\normn{X_{n}}_{\infty},\normn{\mu^{X}}_{\infty})}{N}+\Sigma^{X}_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Sigma^{X})}{N}}$

and let $\hatSigma_{\rho_{N}}^{X}$ be the localized sample covariance
estimator. There exists a constant $c>0$ such that, with probability at least
$1-ce^{-t}$, it holds that

$\displaystyle\normn{\hatSigma_{\rho_{N}}^{X}-\Sigma^{X}}\lesssim
R_{q}\rho_{N}^{1-q}.$

###### Proof.

The proof follows in identical fashion to that of Theorem B.9, except that we
now use the max-norm bound established in Lemma B.20 in place of Theorem B.7.
∎

######  Lemma B.23 (Cross-Covariance Estimation with Localized Sample
Covariance and with Known Particle —Operator-Norm Bound).

Consider the set-up in Theorem B.12 and assume additionally that
$(X_{n},Y_{n})$ is known for some $n\in\\{1,\dots,N\\}$. For any $t\geq 1$,
set

$\displaystyle\rho_{N}$
$\displaystyle\asymp\frac{c(\normn{X_{n}}_{\infty},\normn{\mu^{X}}_{\infty},\normn{Y_{n}}_{\infty},\normn{\mu^{Y}}_{\infty})}{N}$
$\displaystyle+(\Sigma_{(1)}^{X}\lor\Sigma_{(1)}^{Y})\inparen{\inparen{\frac{t}{N}\lor\sqrt{\frac{t}{N}}}\inparen{\sqrt{r_{\infty}(\Sigma^{X})}\lor\sqrt{r_{\infty}(\Sigma^{Y})}}\lor\sqrt{\frac{r_{\infty}(\Sigma^{X})}{N}}\sqrt{\frac{r_{\infty}(\Sigma^{Y})}{N}}}.$

There exists positive universal constants $c_{1},c_{2}$ such that, with
probability at least $1-c_{1}e^{-c_{2}t}$,

$\displaystyle\normn{\hatSigma^{XY}_{\rho_{N}}-\Sigma^{XY}}\lesssim
R_{q_{1}}\rho_{N}^{1-q_{1}}\lor R_{q_{2}}\rho_{N}^{1-q_{2}}.$

###### Proof.

The proof follows in identical fashion to that of Theorem B.9, except that we
now use the max-norm bound established in Lemma B.21 in place of Theorem B.7.
∎

###  B.2 Proof of Main Results in Section 3

###### Proof of Theorem 3.5.

First, we may write

$\displaystyle\normn{\upost_{n}-\upost_{n}^{*}}_{2}$
$\displaystyle=\norm{\bigl{(}y-\mcG(\upr_{n})-\eta_{n}\bigr{)}\bigl{(}\msP(\hatCpr^{\,up},\hatCpr^{\,pp})-\msP(\Cpr^{\,up},\Cpr^{\,pp})\bigr{)}}_{2}$
$\displaystyle\leq\normn{y-\mcG(\upr_{n})-\eta_{n}}_{2}\normn{\msP(\hatCpr^{\,up},\hatCpr^{\,pp})-\msP(\Cpr^{\,up},\Cpr^{\,pp})}_{2}.$
(B.11)

For the second term in (B.2), it follows by Lemma A.7 that

$\displaystyle\normn{\msP(\hatCpr^{\,up},\hatCpr^{\,pp})-\msP(\Cpr^{\,up},\Cpr^{\,pp}))}_{2}$
$\displaystyle\leq\normn{\Gamma^{-1}}\normn{\hatCpr^{\,up}-C^{\,up}}+\normn{\Gamma^{-1}}^{2}\normn{\Cpr^{\,up}}\normn{\hatCpr^{\,pp}-\Cpr^{\,pp}}.$

In order to control the two deviation terms, we write
$W_{i}\equiv[\upr_{i}^{\top},\mcG^{\top}(\upr_{i})]^{\top}$ for $1\leq i\leq
N$. Further, let

$\displaystyle\hatCpr^{W}=\frac{1}{N-1}\sum_{i=1}^{N}(W_{i}-\barW_{N})(W_{i}-\barW_{N})^{\top},\qquad\Cpr^{W}=\begin{bmatrix}\Cpr&\Cpr^{\,up}\\\
\Cpr^{\,pu}&\Cpr^{\,pp}\end{bmatrix}.$

with $\barW_{N}=[\hatm^{\top},\overline{\mcG}^{\top}]^{\top}$ and
$\overline{\mcG}$ the sample mean of $\\{\mcG(u_{n})\\}_{n=1}^{N}.$ Since
$\upr\sim\mcN(m,\Cpr)$ and $\mcG$ is Lipschitz, by Gaussian concentration
[102, Theorem 5.2.2] it holds that
$\normn{\mcG(\upr)-\E[\mcG(\upr)]}_{\psi_{2}}\leq\normn{\mcG}_{\text{Lip}}\normn{\Cpr}^{1/2}$
and we can apply Lemma B.19. Letting $E_{1}$ be the event on which

$\displaystyle\normn{\hatCpr^{\,up}-C^{\,up}}\lor\normn{\hatCpr^{\,pp}-\Cpr^{\,pp}}$
$\displaystyle\leq\normn{\hatCpr^{W}-C^{W}}$
$\displaystyle\lesssim\frac{c(\normn{W_{n}},\normn{\E[W_{n}]})}{N}+\normn{C^{W}}\biggl{(}\sqrt{\frac{r_{2}(C^{W})}{N}}\lor\frac{r_{2}(C^{W})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\biggr{)},$

then Lemma B.19 ensures that $\P(E_{1})\geq 1-c_{1}e^{-c_{2}t}$. It follows
that on the event $E_{1}$, we also have

$\displaystyle\normn{\msP(\hatCpr^{\,up},\hatCpr^{\,pp})-\msP(\Cpr^{\,up},\Cpr^{\,pp}))}_{2}\lesssim\normn{\Gamma^{-1}}(1\lor\normn{\Cpr^{\,up}})\normn{C^{W}}\biggl{(}\sqrt{\frac{r_{2}(C^{W})}{N}}\lor\frac{r_{2}(C^{W})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\biggr{)}.$

The expression can be simplified by noting that since $C^{W}\succeq 0$,
$\normn{C^{W}}\leq\normn{C}+\normn{\Cpr^{\,pp}}$ and further since
$\ttrace(C^{W})=\ttrace(C)+\ttrace(\Cpr^{\,pp})$

$\displaystyle\normn{C^{W}}\inparen{\sqrt{\frac{r_{2}(C^{W})}{N}}\lor\frac{r_{2}(C^{W})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}}$
$\displaystyle\lesssim(\normn{C}\lor\normn{\Cpr^{\,pp}})\inparen{\sqrt{\frac{\ttrace(C)+\ttrace(\Cpr^{\,pp})}{N(\normn{C}\lor\normn{\Cpr^{\,pp}})}}\lor\frac{\ttrace(C)+\ttrace(\Cpr^{\,pp})}{N(\normn{C}\lor\normn{\Cpr^{\,pp}})}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}}$
$\displaystyle\lesssim(\normn{C}\lor\normn{\Cpr^{\,pp}})\inparen{\sqrt{\frac{r_{2}(C)}{N}}\lor\frac{r_{2}(C)}{N}\lor\sqrt{\frac{r_{2}(\Cpr^{\,pp})}{N}}\lor\frac{r_{2}(\Cpr^{\,pp})}{N}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}},$

where the last inequality follows by similar reasoning to that used in the
proof of Lemma A.3. ∎

###### Proof of Theorem 3.7.

As in the proof of Theorem 3.5, we have that

$\displaystyle\normn{\upost_{n}^{\rho}-\upost_{n}^{*}}_{2}\leq\normn{y-\mcG(\upr_{n})-\eta_{n}}_{2}\normn{\msP(\hatCpr^{\,up}_{\rho_{N}},\hatCpr^{\,pp}_{\rho_{N}})-\msP(\Cpr^{\,up},\Cpr^{\,pp})}_{2}.$

Further, by Lemma A.7,

$\displaystyle\normn{\msP(\hatCpr^{\,up}_{\rho_{N}},\hatCpr^{\,pp}_{\rho_{N}})-\msP(\Cpr^{\,up},\Cpr^{\,pp})}_{2}$
$\displaystyle\leq(\normn{\Gamma^{-1}}\lor\normn{\Gamma^{-1}}^{2})(1\lor\normn{\Cpr^{\,up}})(\normn{\hatCpr^{\,up}_{\rho_{N}}-C^{\,up}}+\normn{\hatCpr^{\,pp}_{\rho_{N}}-\Cpr^{\,pp}}).$

Let $E_{1}$ denote the event on which

$\displaystyle\normn{\hatCpr^{\,up}_{\rho_{N}}-C^{\,up}}\lesssim
R_{q_{1}}\rho_{N,1}^{1-q_{1}}\lor R_{q_{2}}\rho_{N,2}^{1-q_{2}}.$

By Lemma B.23 , $E_{1}$ has probability at least $1-c_{1}e^{-c_{2}t}$. Let
$E_{2}$ be the event on which

$\displaystyle\normn{\hatCpr^{\,pp}_{\rho_{N}}-C^{\,pp}}\lesssim
R_{q_{3}}\rho_{N,3}^{1-q_{3}}.$

By Lemma B.22, $E_{2}$ has probability at least $1-c_{1}e^{-c_{2}t}$.
Therefore, $E=E_{1}\cap E_{2}$ has probability at least $1-c_{1}e^{-c_{2}t}$,
and on $E$ it holds that

$\normn{\msP(\hatCpr^{\,up}_{\rho_{N}},\hatCpr^{\,pp}_{\rho_{N}})-\msP(\Cpr^{\,up},\Cpr^{\,pp})}_{2}\lesssim(\normn{\Gamma^{-1}}\lor\normn{\Gamma^{-1}}^{2})(1\lor\normn{\Cpr^{\,up}})(R_{q_{1}}\rho_{N,1}^{1-q_{1}}+R_{q_{2}}\rho_{N,2}^{1-q_{2}}+R_{q_{3}}\rho_{N,3}^{1-q_{3}}).\qed$

##  Appendix C Proofs: Section 4

This appendix contains the proofs of the auxiliary results discussed in
Section 4.

######  Lemma C.1 (Kalman Gain Deviation with Localization).

Let $\upr_{1},\dots,\upr_{N}$ be $d$-dimensional i.i.d. sub-Gaussian random
vectors with $\E[\upr_{1}]=m$ and
$\E\bigl{[}(\upr_{1}-m)(\upr_{1}-m)^{\top}\bigr{]}=\Cpr$. Assume further that
$\Cpr\in\msU_{d}(q,R_{q})$ for some $q\in[0,1)$ and $R_{q}>0$. For any $t\geq
1$, set

$\displaystyle\rho_{N}\asymp\Cpr_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Cpr)}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Cpr)}{N}}$

and let $\hatCpr_{\rho_{N}}$ be the localized sample covariance estimator.
There exists a positive universal constant $c$ such that, with probability at
least $1-ce^{-t}$,

$\displaystyle\normn{\msK(\hatCpr_{\rho_{N}})-\msK(\hatCpr)}\lesssim\normn{A}\normn{\Gamma^{-1}}R_{q}(1+\normn{A}^{2}\normn{\Gamma^{-1}}\normn{\Cpr})\rho_{N}^{1-q}.$

###### Proof.

By Lemma A.4 and Theorem 3.1, it follows immediately that

$\displaystyle\normn{\msK(\hatCpr_{\rho_{N}})-\msK(\hatCpr)}$
$\displaystyle\leq\normn{A}\normn{\Gamma^{-1}}\normn{\hatCpr_{\rho_{N}}-\Cpr}(1+\normn{A}^{2}\normn{\Gamma^{-1}}\normn{\Cpr})$
$\displaystyle\lesssim\normn{A}\normn{\Gamma^{-1}}R_{q}\rho_{N}^{1-q}(1+\normn{A}^{2}\normn{\Gamma^{-1}}\normn{\Cpr}).\qed$

######  Theorem C.2 (Square Root Ensemble Kalman Covariance Deviation with
Localization).

Consider the localized SR ensemble Kalman update given by (4.2), leading to an
estimate $\hatCpost$ of the posterior covariance $\Cpost$ defined in (1.2).
Assume that $\Cpr\in\msU_{d}(q,R_{q})$ for $q\in[0,1)$ and $R_{q}>0$. For any
$t\geq 1$, set

$\displaystyle\rho_{N}\asymp\Cpr_{(1)}\inparen{\sqrt{\frac{r_{\infty}(\Cpr)}{N}}\lor\sqrt{\frac{t}{N}}\lor\frac{t}{N}\lor\frac{tr_{\infty}(\Cpr)}{N}}.$

There exists a positive universal constant $c$ such that, with probability at
least $1-ce^{-t}$,

$\displaystyle\normn{\hatCpost-\Cpost}$ $\displaystyle\lesssim
R_{q}\rho_{N}^{1-q}\inparen{1+\normn{A}^{2}\normn{\Gamma^{-1}}\inparen{2\normn{\Cpr}+R_{q}\rho_{N}^{1-q}}+\normn{A}^{4}\normn{\Gamma^{-1}}^{2}\normn{\Cpr}(\normn{\Cpr}+R_{q}\rho_{N}^{1-q})}.$

###### Proof.

For the localized SR update we have $\hatCpost=\msC(\hatCpr_{\rho_{N}})$. From
Lemma A.6, the continuity of $\msC$ implies that

$\displaystyle\normn{\msC(\hatCpr_{\rho_{N}})-\msC(\Cpr)}$
$\displaystyle\leq\normn{\hatCpr_{\rho_{N}}-\Cpr}\Bigl{(}1+\normn{A}^{2}\normn{\Gamma^{-1}}\bigl{(}\normn{\hatCpr_{\rho_{N}}}+\normn{\Cpr}\bigr{)}+\normn{A}^{4}\normn{\Gamma^{-1}}^{2}\normn{\hatCpr_{\rho_{N}}}\normn{\Cpr}\Bigr{)}.$

Let $E$ denote the event on which

$\displaystyle\normn{\hatCpr_{\rho_{N}}-\Cpr}\lesssim R_{q}\rho_{N}^{1-q}.$

By Theorem B.12, $E$ has probability at least $1-ce^{-t}$. It also holds on
$E$ that

$\displaystyle\normn{\hatCpr_{\rho_{N}}}\leq\normn{\Cpr}+\normn{\hatCpr_{\rho_{N}}-\Cpr}\lesssim\normn{\Cpr}+R_{q}\rho_{N}^{1-q}.$

Therefore, it holds on $E$ that

$\displaystyle\normn{\hatCpost-\Cpost}$ $\displaystyle\lesssim
R_{q}\rho_{N}^{1-q}\inparen{1+\normn{A}^{2}\normn{\Gamma^{-1}}\inparen{2\normn{\Cpr}+R_{q}\rho_{N}^{1-q}}+\normn{A}^{4}\normn{\Gamma^{-1}}^{2}\normn{\Cpr}(\normn{\Cpr}+R_{q}\rho_{N}^{1-q})}.\qed$