$\begin{split}\mathcal{A}=\big{\\{}\left\|\widehat{\Sigma}_{X_{S_{u}S_{u}}}-{\Sigma}_{X_{S_{u}S_{u}}}\right\|_{op}^{2}\leq\frac{CM^{2}}{n}s_{u}\\\
\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X_{S_{u}S_{u}}}-{\Sigma}^{\frac{1}{2}}_{X_{S_{u}S_{u}}}\right\|_{op}^{2}\leq\frac{CM^{2}}{n}s_{u}\\\
\left\|\widehat{\Sigma}_{Y}-{\Sigma}_{Y}\right\|_{op}^{2}\leq\frac{CM^{2}q}{n}\\\
\left\|\widehat{\Sigma}^{\frac{1}{2}}_{Y}-{\Sigma}^{\frac{1}{2}}_{Y}\right\|_{op}^{2}\leq\frac{CM^{2}q}{n}\big{\\}}\\\
\end{split}$ (52)

#### Bound on (A).

On the event $\mathcal{A}$, we have:

$\begin{split}\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}B^{*}\right\|_{F}&=\sqrt{\mathop{\sf
Tr}\big{(}{B^{*}}^{\top}\widehat{\Sigma}_{X}B^{*}\big{)}}=\sqrt{\mathop{\sf
Tr}\big{(}{B^{*}}^{\top}[\widehat{\Sigma}_{X}]_{SS}B^{*}\big{)}}=\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X_{SS}}B^{*}\right\|_{F}\\\
&\leq\left\|[\widehat{\Sigma}^{\frac{1}{2}}_{X}-\Sigma^{\frac{1}{2}}_{X}]_{SS}B^{*}\right\|_{F}+\left\|[\Sigma^{\frac{1}{2}}_{X}]_{SS}B^{*}\right\|_{F}\\\
&\leq
M\sqrt{\frac{Cs_{u}}{n}}\sqrt{\frac{1}{\sigma_{\min}(\Sigma_{X})}}\sqrt{r}\lambda_{1}+\lambda_{1}\sqrt{r}\\\
&\leq
M\sqrt{r}\lambda_{1}\bigg{(}\sqrt{C\frac{s_{u}}{\sigma_{\min}(\Sigma_{X})n}}+1\bigg{)}\\\
&\leq
C^{\prime}M\bigg{(}\frac{1}{{\sqrt{\sigma_{\min}(\Sigma_{X})}}}+1\bigg{)}{\sqrt{r}\lambda_{1}}\qquad\qquad\text{
by Assumption }\mathcal{H}_{1}.\end{split}$ (53)

where $C^{\prime}$ is a constant that depends on $C$. The third line further
makes use of the fact that
$\|B^{*}\|_{F}\leq\left\|\Sigma_{X}^{-\frac{1}{2}}\right\|_{op}\left\|\Sigma_{X}^{\frac{1}{2}}B^{*}\right\|_{F}\leq\sqrt{\frac{1}{\sigma_{\min}(\Sigma_{X})}}\sqrt{r}\lambda_{1}.$
Therefore:

$\begin{split}\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}B^{*}\right\|_{F}&\leq{M}\times
C^{\prime}\Big{(}\frac{1}{{\sqrt{\sigma_{\min}(\Sigma_{X})}}}+1\Big{)}{\sqrt{r}\lambda_{1}}\leq
C^{\prime\prime}M^{\frac{3}{2}}\sqrt{r}\lambda_{1},\\\ \end{split}$ (54)

with $C^{\prime\prime}=2C^{\prime}$ a constant that therefore only depends on
$C$.

#### Bound (B).

We note that

$\begin{split}\left\|{B^{*}}^{\top}(\widehat{\Sigma}_{X}-\Sigma_{X})B^{*}\right\|_{F}&=\left\|{B^{*}}^{\top}\big{[}\widehat{\Sigma}_{X}-\Sigma_{X}\big{]}_{SS}B^{*}\right\|_{F}\\\
&\leq\left\|\Sigma_{X}^{\frac{1}{2}}B^{*}\right\|_{F}^{2}~{}\left\|\big{[}\Sigma_{X}\big{]}^{-\frac{1}{2}}_{SS}\big{[}\widehat{\Sigma}_{X}-\Sigma_{X}\big{]}_{SS}\big{[}\Sigma_{X}\big{]}^{-\frac{1}{2}}_{SS}\right\|_{op}\\\
\end{split}$ (55)

Therefore, on the event $\mathcal{A}$:

$\begin{split}\left\|{B^{*}}^{\top}(\widehat{\Sigma}_{X}-\Sigma_{X})B^{*}\right\|_{F}&\leq\left\|\Sigma_{X}^{\frac{1}{2}}B^{*}\right\|_{F}^{2}~{}\left\|\big{[}\Sigma_{X}\big{]}^{-\frac{1}{2}}_{SS}\right\|_{op}^{2}~{}\left\|\big{[}\widehat{\Sigma}_{X}-\Sigma_{X}\big{]}_{SS}\right\|_{op}\\\
&\leq\tilde{C}M\frac{r\lambda_{1}^{2}}{\sigma_{\min}(\Sigma_{X})}\sqrt{\frac{s_{u}}{n}}\\\
&\leq\tilde{C}M^{2}r\lambda_{1}^{2}\sqrt{\frac{s_{u}}{n}}\end{split}$ (56)

where in the last line, we have used the assumption that
$\sigma_{\min}(\Sigma_{X})\geq\frac{1}{M},$ and $\tilde{C}=\sqrt{C}$ (with $C$
the constant of event $\mathcal{A}$) is a constant that does not depend on the
dimensions.

#### Combined bound (A) + (B).

We proceed to bounding Equation (51) on the event
$\mathcal{G}=\Big{\\{}\rho>4\max_{j\in[p]}\big{\|}\big{[}\widehat{\Sigma}_{XY}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\widehat{\Sigma}_{X}{B}^{*}\big{]}_{j\cdot}\big{\|}\Big{\\}}$,
assuming $\mathcal{H}_{1}$ (i.e. $\frac{s_{u}(\log(ep/s_{u})+q)}{n}\leq
c_{0}$):

$\begin{split}&\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}\\\
&\leq C^{\prime}M^{\frac{5}{2}}\sqrt{s_{u}\frac{q+\log
p}{n}}\bigg{(}C^{\prime}M^{\frac{5}{2}}\sqrt{s_{u}\frac{q+\log
p}{n}}+2C^{\prime\prime}M^{\frac{3}{2}}\sqrt{r}\lambda_{1}\bigg{)}+{C}^{\prime\prime\prime}M^{2}r\lambda_{1}^{2}\sqrt{\frac{s_{u}}{n}}\\\
&\leq\widetilde{C}M^{5}\sqrt{s_{u}\frac{(q+\log
p)}{n}}(1+2\cdot\sqrt{r})\quad\text{ where we use the fact that }r\leq q\\\
&\leq\widetilde{C}^{\prime}M^{5}\sqrt{rs_{u}\frac{(q+\log p)}{n}}\
\end{split}$ (57)

for $\widetilde{C}$ and $\widetilde{C}^{\prime}$ constants that do not depend
on the dimension. Therefore, since we’ve shown the event $\mathcal{G}$ holds
with high probability:

$\begin{split}\left\|\widehat{V}_{0}-VO\right\|_{F}&\leq\frac{2\sqrt{2}}{\lambda_{r}}\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}\leq\widetilde{C}^{\prime}\frac{M^{5}}{\lambda_{r}}\sqrt{rs_{u}\frac{(q+\log
p)}{n}}\\\ \end{split}$ (58)

with the same probability.

#### Error bound on $\widehat{V}$.

Let $\mathcal{O}_{r,r}=\\{O\in\mathbb{R}^{r\times r}:O^{\top}O=I_{r}\\}$
denote the set of rotation matrices in $\mathbb{R}^{r}$. Thus, we have on the
event $\mathcal{A}\cap\mathcal{G}=\mathcal{G}$ (since
$\mathcal{G}\subset\mathcal{A}$, by the proof of Lemma 9):

$\begin{split}\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{V}-VO\right\|_{F}&=\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\widehat{V}_{0}-\Sigma_{Y}^{-\frac{1}{2}}{V}_{0}O\right\|_{F}\\\
&\leq\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}(\widehat{V}_{0}-{V}_{0}O)\right\|_{F}+\left\|\big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\big{)}{V}_{0}\right\|_{F}\\\
&\leq\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}~{}\left\|\widehat{V}_{0}-{V}_{0}O\right\|_{F}+\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\right\|_{op}\sqrt{r}\\\
&\leq
2\sqrt{M}\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{V}_{0}-{V}_{0}O\right\|_{F}+C^{\prime}_{2}M^{2}\sqrt{\frac{qr}{n}}\\\
&\leq C_{3}\frac{M^{5}\sqrt{M}}{\lambda_{r}}\sqrt{rs_{u}\frac{q+\log
p}{n}}+C^{\prime}_{2}M^{2}\sqrt{\frac{qr}{n}}\\\
&=C^{\prime}M^{\frac{11}{2}}\sqrt{\frac{qr}{n}}\bigg{(}\sqrt{\frac{s_{u}(1+\log
p/q)}{\lambda^{2}}}+1\bigg{)}\\\
&=2C^{\prime}M^{\frac{11}{2}}\sqrt{rs_{u}\frac{q+\log p}{\lambda^{2}n}}\\\
\end{split}$ (59)

where we used the fact that
$\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}\leq 2{\sqrt{M}}$
(Equation (24)), and that on $\mathcal{A}$

$\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\right\|_{op}\leq\left\|\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\right\|_{op}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}\left\|\Sigma_{Y}^{-\frac{1}{2}}\right\|_{op}\leq
2C^{\frac{1}{2}}M^{2}\sqrt{\frac{q}{n}}.$

#### Error bound on $\widehat{U}$.

Let
$\widetilde{O}=\text{argmin}_{O\in\mathcal{O}_{rr}}\left\|\widehat{U}-UO\right\|_{F}$,
we have:

$\begin{split}\left\|\widehat{U}-U\widetilde{O}\right\|_{F}&\leq\left\|\widehat{U}-UO\right\|_{F}=\left\|\widehat{B}\widehat{V}_{0}\widehat{\Lambda}^{-1}-B^{*}V_{0}\Lambda^{-1}{O}\right\|_{F}\\\
\leq&\left\|(\widehat{B}-B^{*})\widehat{V}_{0}\widehat{\Lambda}^{-1}\right\|_{F}+\left\|B^{*}(\widehat{V}_{0}-V_{0}O)\widehat{\Lambda}^{-1}\right\|_{F}+\left\|B^{*}V_{0}(O\widehat{\Lambda}^{-1}-\Lambda^{-1}O)\right\|_{F}\\\
\leq&\left\|\widehat{B}-B^{*}\right\|_{F}~{}\left\|\widehat{\Lambda}^{-1}\right\|_{op}+\|B^{*}\|_{op}~{}\left\|\widehat{V}_{0}-V_{0}O\right\|_{F}~{}\left\|\widehat{\Lambda}^{-1}\right\|_{op}+\|B^{*}V_{0}\|_{F}~{}\left\|\widehat{\Lambda}^{-1}-O^{\top}\Lambda^{-1}O\right\|_{op}\\\
\end{split}$ (60)

Note that

$\begin{split}\left\|\widehat{\Lambda}^{-1}-O^{\top}\Lambda^{-1}\right\|_{op}&=\left\|\widehat{\Lambda}^{-1}(O^{\top}\Lambda
O-\widehat{\Lambda})O^{\top}\Lambda^{-1}\right\|_{op}\\\
&\leq\left\|\widehat{\Lambda}^{-1}\right\|_{op}~{}\left\|O^{\top}\Lambda
O-\widehat{\Lambda}\right\|_{op}~{}\left\|\Lambda^{-1}\right\|_{op}\end{split}$
(61)

Thus

$\begin{split}\|\widehat{U}-U\widetilde{O}\|_{F}\leq\Big{(}\|\widehat{B}-B^{*}\|_{F}&+\|B^{*}\|_{op}~{}\|\widehat{V}-VO\|_{F}\\\
+&\|B^{*}V_{0}\|_{F}~{}\|\Lambda^{-1}\|_{op}~{}\|O^{\top}\Lambda
O-\widehat{\Lambda}\|_{op}\Big{)}\|\widehat{\Lambda}^{-1}\|_{op}\\\
\end{split}$ (62)

By Lemma 2 of Gao et al. [2015]

$\begin{split}\left\|O\Lambda
O^{\top}-\widehat{\Lambda}\right\|_{op}&\leq\frac{\left\|O\Lambda^{2}O^{\top}-\widehat{\Lambda}^{2}\right\|_{op}}{{\sigma_{\min}\big{(}O\Lambda
O^{\top}\big{)}}+{\sigma_{\min}\big{(}\widehat{\Lambda}\big{)}}}\end{split}$
(63)

We also note that

$\begin{split}\widehat{V}_{0}\widehat{\Lambda}^{2}\widehat{V}_{0}^{\top}-V_{0}\Lambda^{2}V_{0}^{\top}&=\big{(}\widehat{V}_{0}-V_{0}O\big{)}\widehat{\Lambda}^{2}\widehat{V}_{0}^{\top}+V_{0}O\widehat{\Lambda}^{2}\widehat{V}_{0}^{\top}-V_{0}O\widehat{\Lambda}^{2}\big{(}V_{0}O\big{)}^{\top}+V_{0}\big{(}O\widehat{\Lambda}^{2}O^{\top}-\Lambda^{2}\big{)}V_{0}^{\top}\\\
&=\big{(}\widehat{V}_{0}-V_{0}O\big{)}\widehat{\Lambda}^{2}\widehat{V}_{0}^{\top}+V_{0}O\widehat{\Lambda}^{2}\big{(}\widehat{V}_{0}-V_{0}O\big{)}^{\top}+V_{0}\big{(}O\widehat{\Lambda}^{2}O^{\top}-\Lambda^{2}\big{)}V_{0}^{\top}\\\
\end{split}$ (64)

Then, by the triangle inequality

$\begin{split}\left\|V_{0}(O^{\top}\Lambda^{2}O-\widehat{\Lambda}^{2})\widehat{V}_{0}^{\top}\right\|_{op}\leq~{}&\left\|\widehat{V}_{0}\widehat{\Lambda}^{2}\widehat{V}_{0}^{\top}-V_{0}\Lambda^{2}V_{0}^{\top}\right\|_{op}\\\
&+\left\|(\widehat{V}_{0}-V_{0}O)\widehat{\Lambda}^{2}\widehat{V}_{0}^{\top}\right\|_{op}+\left\|V_{0}O\widehat{\Lambda}^{2}(\widehat{V}_{0}-V_{0}O)^{\top}\right\|_{op}\end{split}$
(65)

Thus

$\begin{split}\left\|O^{\top}\Lambda^{2}O-\widehat{\Lambda}^{2}\right\|_{op}&\leq\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{op}+2\left\|\widehat{V}_{0}-V_{0}O\right\|_{F}~{}\left\|\widehat{\Lambda}^{2}\right\|_{op}\\\
&\leq\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}+\frac{4\sqrt{2}}{\lambda_{r}}\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}\left\|\widehat{\Lambda}^{2}\right\|_{op}\\\
&\leq\widetilde{C}^{\prime}M^{5}\delta_{n}\left(1+\frac{4\sqrt{2}}{\lambda_{r}}\left\|\widehat{\Lambda}^{2}\right\|_{op}\right)\\\
\end{split}$ (66)

with $\delta_{n}=\sqrt{rs_{u}\frac{(q+\log p)}{n}},$ where we have used
Equation (57) on the event $\mathcal{G}$ to bound
$\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}.$
Now, by Weyl’s inequality:

$\begin{split}\Big{|}\left\|\widehat{\Lambda}^{2}\right\|_{op}-\left\|\Lambda^{2}\right\|_{op}\Big{|}&\leq\left\|\
\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{op}\\\
&\leq\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}\leq\widetilde{C}^{\prime}M^{5}\delta_{n}\end{split}$
(67)

Thus $\forall
i\in[r],\quad\sigma_{i}(\widehat{\Lambda}^{2})\in[\sigma_{i}(\Lambda^{2})-\widetilde{C}^{\prime}M^{5}\delta_{n},~{}~{}\sigma_{i}(\Lambda^{2})+\widetilde{C}^{\prime}M^{5}\delta_{n}]$
on $\mathcal{G}.$ This means that the LHS in Equation (63) is bounded by:

$\begin{split}\left\|O\Lambda
O^{\top}-\widehat{\Lambda}\right\|_{op}&\leq\frac{1}{{\sqrt{\lambda_{r}^{2}-\widetilde{C}^{\prime}M^{5}\delta_{n}}}+\sqrt{\lambda_{r}^{2}}}\widetilde{C}^{\prime}M^{5}\delta_{n}\left(1+\frac{4\sqrt{2}}{\lambda_{r}}\left(\lambda_{1}^{2}+\widetilde{C}^{\prime}M^{\frac{5}{2}}\delta_{n}\right)\right)\\\
&\leq
2C^{\prime}\frac{M^{5}}{{3\lambda}}\delta_{n}\left(1+\frac{4\sqrt{2}}{\lambda}\left(\lambda_{1}^{2}+\frac{3}{4}\lambda^{2}\right)\right)\quad\text{assuming
}\widetilde{C}^{\prime}M^{5}\delta_{n}\leq\frac{3\lambda^{2}}{4}\\\
&\leq\frac{C^{\prime\prime}M^{5}}{\lambda^{2}}\delta_{n}\\\ \end{split}$ (68)

Finally, we need a bound on $\left\|\widehat{\Lambda}^{-1}\right\|_{op}$. We
use again Weyl’s inequality on the event $\mathcal{G}$ (as in Equation (67))
and the assumption that
$\widetilde{C}^{\prime}M^{5}\delta_{n}\leq\frac{3\lambda^{2}}{4}$ to conclude
that:

$\begin{split}\left\|\widehat{\Lambda}^{-1}\right\|_{op}=\frac{1}{\sigma_{\min}(\widehat{\Lambda})}\leq\frac{1}{\sqrt{\sigma_{\min}({\Lambda}^{2})-\widetilde{C}^{\prime}M^{5}\delta_{n}}}\leq\frac{2}{\lambda}.\end{split}$
(69)

Combining all the previous together, the error bound for $U$ in Equation (62)
becomes on the event $\mathcal{G}$:

$\begin{split}\left\|\widehat{U}-U\widetilde{O}\right\|_{F}&\leq\frac{2}{{\lambda}}\Bigg{(}C^{\prime\prime}M^{3}\sqrt{\frac{s_{u}(q+\log
p)}{n}}\\\
&+\sqrt{M}\lambda_{1}\cdot\bigg{(}C^{\prime}M^{\frac{11}{2}}\sqrt{\frac{qr}{n}}\bigg{(}\sqrt{\frac{s_{u}(1+\log
p/q)}{\lambda^{2}}}+1\bigg{)}\bigg{)}\\\
&+\sqrt{Mr}\frac{\lambda_{1}}{\lambda}\times
C^{\prime\prime\prime}\frac{M^{5}}{\lambda^{2}}\sqrt{rs_{u}\frac{(q+\log
p)}{n}}\Bigg{)}\\\
&\leq~{}\widetilde{C}\frac{2M^{6}}{{\lambda}}\cdot\sqrt{rs_{u}\frac{(q+\log
p)}{n}}\Big{(}\sqrt{\frac{\lambda^{2}}{r}}+2\frac{\sqrt{r}}{\lambda^{3}}\Big{)}\\\
&\leq\widetilde{C}^{\prime}\frac{M^{6}}{{\lambda^{4}}}\cdot
r\cdot\sqrt{s_{u}\frac{(q+\log p)}{n}}\\\ \end{split}$ (70)

with $\widetilde{C}^{\prime}$ a constant that solely depends on $C^{\prime}$
and $c_{0}$. ∎

###  D.4 CCA with general $\ell_{2}$ penalty

We also note in passing that our framework also lends itself well to the
addition of an $\ell_{2}$ regularization on canonical directions of the
general form $\operatorname{Pen}(U)=\mathop{\sf Tr}(U^{\top}KU).$ Here $K$ is
a positive semi-definite kernel matrix, which can be easily adapted depending
on the application. For example, a choice of $K=I_{p}$ will force the CCA
procedure to shrink the canonical directions $U$ to zero, thus determining the
covariates in $X$ that exhibit the strongest impact on the canonical
correlation. Alternatively, penalty matrices of the form
$K=I-\frac{11^{\top}}{p}$ will have the effect of pulling values in each
column of $U$ closer to the global mean, thus controlling the heterogeneity in
the coefficients. In this case, one can simply replace the OLS step in
Algorithm 1 by its penalized version:

$\widehat{B}=\mathop{\rm argmin}_{B\in\mathbb{R}^{p\times
q}}\frac{1}{n}\|Y_{0}-XB\|_{F}^{2}+\rho\mathop{\sf Tr}(B^{\top}KB).$ (71)

While this paper focuses on sparse prior, this penalty is also provided in our
open-source CCAR3 code repository.

##  Appendix E Proofs: graph-sparse CCAR3

We consider now the graph-sparse CCA problem introduced in Section 3.3. For a
graph $\mathcal{G}$ on $p$ nodes and $m$ edges indicating the relationships
between the $p$ covariates of $X$, let
$\mathcal{F}_{\mathcal{G}}(s_{u},p,m,q,r,\lambda,M)$ to be the collection of
all covariance matrices $\Sigma$ satisfying (2) and

$\displaystyle 1.$ $U\in\mathbb{R}^{p\times r}$ and $V\in\mathbb{R}^{q\times
r}$ with $|{\rm supp}{(\Gamma U)}|\leq s_{u}$ ; (72) $\displaystyle 2.$
$\sigma_{\min}(\Sigma_{X})\wedge\sigma_{\min}(\Sigma_{Y})\geq\frac{1}{M}$ and
$\sigma_{\max}(\Sigma_{X})\vee\sigma_{\max}(\Sigma_{Y})\leq M$; $\displaystyle
3.$ $\lambda_{r}\geq\lambda$ and $\lambda_{1}\leq 1-\frac{1}{M}$.

We denote $\Gamma$ the incidence matrix of the graph $\mathcal{G}$, and by
$\Gamma^{\dagger}$ its pseudo inverse. Denoting
$\Pi=I_{p}-\Gamma^{\dagger}\Gamma$, we decompose $U\in\mathbb{R}^{p\times r}$
as a sum of terms carried by the orthogonal subspaces: $U=\Pi
U+\Gamma^{\dagger}\Gamma U.$

We begin with a few observations on the properties of the matrices $\Gamma$
and $\Pi$.

  1. 1.

By the property of the incidence matrix,

$\Gamma^{\top}\Gamma=A-D=L\hskip 85.35826pt(*)$

is the (unnormalized) Laplacian of the graph [Hütter and Rigollet, 2016]. Here
$A$ denotes the adjacency of the graph and $D$ is a diagonal matrix such that
$D_{ii}$ is the degree of node $i$. We denote $\kappa_{2}=\sigma_{\min}(L)$.

  2. 2.

$\Pi$ is the projection operator of $\mathbb{R}^{p}$ unto the nullspace of
$\Gamma^{\dagger}\Gamma$, thus, $\Pi^{2}=\Pi.$ Moreover, by ($*$), $\Pi$
corresponds to the eigenvectors associated to the eigenvalue 0 of the
Laplacian.

  3. 3.

Consequently, we have an explicit formulation for $\Pi$ [Chung, 1996]. Let
$n_{c}$ be the number of connected components of $G$, and let $C_{i}$ denote
the $i^{th}$ connected component of $G$. Let
$\mathbf{1}_{C_{i}}\in\mathbb{R}^{p\times 1}$ be the indicator (column) vector
of the $i^{th}$ connected component, i.e $[\mathbf{1}_{C_{i}}]_{j}=1$ if $j\in
C_{i}$ and 0 otherwise. Then

$\Pi=\sum_{i\in[n_{c}]}\frac{\mathbf{1}_{C_{i}}\mathbf{1}_{C_{i}}^{\top}}{|C_{i}|}.$

  4. 4.

Since $\Pi$ is a projection matrix then for any $B\in\mathbb{R}^{p\times q}$
it holds $\left\|\Pi B\right\|_{F}\leq\left\|B\right\|_{F}.$

  5. 5.

We also have:

$\|\Gamma B\|^{2}_{F}\leq\sigma_{\max}(L)\|B\|^{2}_{F},$

where $\sigma_{\max}(L)$ denotes the maximum eigenvalue of the Laplacian of
the graph $G$. By property of the eigenvalues of the Laplacian, we thus have:

$\|\Gamma B\|^{2}_{F}\leq 2d_{\max}\|B\|^{2}_{F},$

where $d_{\max}$ is the maximum degree of the graph [Chung, 1996].

Similarly to the analysis of Hütter and Rigollet [2016], we introduce the
scaling constant:

$\rho(\Gamma)=\max_{j\in[p]}\big{\|}\Gamma^{\dagger}_{\cdot j}\big{\|}$ (73)

###  E.1 Useful Lemmas for the Graph Setting

######  Lemma 10.

For $i\in[n]$, let $W_{i}\sim N(0,\bar{\Sigma})$ denote a set of multivariate
random variables with covariance matrix
$\bar{\Sigma}=I_{q}-V_{0}\Lambda^{2}V_{0}^{\top}$, where
$V_{0}=\Sigma_{X}^{\frac{1}{2}}V$, with the notations introduced in section
3.1. Let $X_{i}\sim N(0,{\Sigma}_{X})$ denote a set of multivariate normal
observations independent of $W$. Assume

$M\frac{{q}+s_{u}\log\big{(}\frac{ep}{s_{u}}\big{)}}{n}\leq c_{0}$
($\mathcal{H}_{1,\mathcal{G}}$)

for $c_{0}\in(0,1).$ Then, for a constant $C^{\prime}>0$, there exists $C>0$
that solely depends on $C^{\prime}$ such that:

$\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}W}{n}\right]_{j\cdot}\right\|\leq
C\cdot\left(1+\frac{M}{\kappa_{2}}\right)\cdot\sqrt{\frac{q+\log m}{n}}$ (74)

with probability at least $1-\exp\\{-C^{\prime}(q+\log m)\\}.$ Here we assume
that $c_{0}$ is small enough so that $C^{\prime}c_{0}\leq c_{3}-\log c_{2}-1$
with $c_{3},c_{2}$ the universal constants of Theorem 6.5 of Wainwright
[2019].

Proof We note first that:

$\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}W}{n}\right]_{j\cdot}\right\|\leq\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}W}{n}-\Sigma_{X\Gamma^{\dagger},W}\right]_{j\cdot}\right\|+\max_{j\in[p]}\left\|\left[\Sigma_{X\Gamma^{\dagger},W}\right]_{j\cdot}\right\|$
(75)

where $\Sigma_{X\Gamma^{\dagger},W}$ is the cross-covariance matrix between
the transformed variables $X\Gamma^{\dagger}$ and $W.$ We also note that, by
independence of $W$ and $X$:

$\max_{j\in[m5r]}\left\|\left[\Sigma_{X\Gamma^{\dagger},W}\right]_{j\cdot}\right\|=0$

Let
$Z_{i}\sim\mathcal{N}_{p}\big{(}0,(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}\big{)}$,
$W_{i}\sim\mathcal{N}_{q}(0,\bar{\Sigma})$, and
$\mathbf{1}_{j}^{\top}\in\mathbb{R}^{1\times m}$ the vector indicator of row
$j$ (i.e. $[\mathbf{1}_{j}]_{i}=0$ for all $i\neq j$, and
$[\mathbf{1}_{j}]_{j}=1$). Thus, denoting $\widetilde{X}=X\Gamma^{\dagger}$,
we may write

$\mathbf{1}_{j}^{\top}(\widehat{\Sigma}_{\widetilde{X}W}-\Sigma_{\widetilde{X}W})=\frac{1}{n}\sum_{i=1}^{n}\big{(}\mathbf{1}_{j}^{\top}Z_{i}W_{i}^{\top}-\mathbb{E}(\mathbf{1}_{j}^{\top}Z_{i}W_{i}^{\top})\big{)}.$

We also note that

$\left\|\Sigma_{\widetilde{X}}\right\|_{op}=\left\|(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}\right\|_{op}=\sup_{u\in\mathbb{R}^{m}}\frac{u^{\top}(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}u}{\|u\|^{2}}\leq
M\frac{\|\Gamma^{\dagger}u\|^{2}}{\|u\|^{2}}\leq\frac{M}{\kappa_{2}}.$

Here, as we defined above, constant $\kappa_{2}$ that appears in the previous
is the smallest non-zero eigenvalue of the Laplacian $L=\Gamma^{\top}\Gamma$.
Moreover we note that

$\left\|\bar{\Sigma}\right\|_{op}=\left\|I-V_{0}\Lambda^{2}V_{0}^{\top}\right\|_{op}\leq
1.$

Define for each $j\in[p]$ the matrix
$H_{i}^{(j)}=\begin{pmatrix}\mathbf{1}_{j}^{\top}Z_{i}\\\ W_{i}\end{pmatrix}.$
Since $\mathbf{1}_{j}^{\top}Z_{i}W_{i}^{\top}$ is a submatrix of
$H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}$

$\begin{split}\max_{j\in[p]}\Big{\|}\mathbf{1}_{j}^{\top}(\widehat{\Sigma}_{\widetilde{X}W}-{\Sigma}_{\widetilde{X}W})\Big{\|}&\leq\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\\\
\end{split}$ (76)

Denoting
$\mathcal{H}^{(j)}=\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}=\begin{pmatrix}\mathbf{1}_{j}^{\top}\Sigma_{\widetilde{X}}\mathbf{1}_{j}&\mathbf{1}_{j}^{\top}\Sigma_{\widetilde{X}W}\\\
\Sigma_{W\widetilde{X}}\mathbf{1}_{j}&\bar{\Sigma}\end{pmatrix}=\begin{pmatrix}\mathbf{1}_{j}^{\top}\Sigma_{\widetilde{X}}\mathbf{1}_{j}&0\\\
0&\bar{\Sigma}\end{pmatrix},$ where the last equality follows from the fact
that $W$ and $X$ are independent, by assumption. This implies:

$\begin{split}\left\|\mathcal{H}^{(j)}\right\|_{op}&=\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\mathbf{1}_{j}^{\top}\Sigma_{\widetilde{X}}\mathbf{1}_{j}u_{1}^{2}+{u_{2}^{\top}\bar{\Sigma}u_{2}}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\frac{M}{\kappa_{2}}u_{1}^{2}+\|u_{2}\|^{2}\leq\frac{M}{\kappa_{2}}+1\end{split}$
(77)

By Theorem 6.5 of Wainwright [2019], there exists universal constants
$c_{1},c_{2},c_{3}>0$ such that:

$\begin{split}\mathbb{P}&\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\geq\left\|\mathcal{H}^{(j)}\right\|_{op}\left(2c_{1}\sqrt{\frac{q+1}{n}}+t\right)\right]\\\
&\leq c_{2}\exp\big{\\{}-c_{3}n\min\\{{t},{t^{2}}\\}\big{\\}}.\end{split}$

Thus, by a simple union bound, we conclude that

$\begin{split}&\mathbb{P}\left[\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\geq\left\|\mathcal{H}^{(j)}\right\|_{op}\left(2c_{1}\sqrt{\frac{q+1}{n}}+t\right)\right]\\\
&\leq c_{2}m\exp\big{\\{}-c_{3}n\min\\{{t},{t^{2}}\\}\big{\\}}\end{split}$

Now, we write $c_{2}=e^{\gamma_{2}({q+\log m})}$ for an appropriate constant
$\gamma_{2}$ and take
$t^{2}=\frac{1+C^{\prime}+(\gamma_{2})_{+}}{c_{3}}\cdot\frac{q+\log m}{n}$ for
any $C^{\prime}>0$ while assuming $c_{0}$ small enough so that $t\leq 1$. This
implies that

$\begin{split}&\mathbb{P}\left[\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\geq
C^{\prime}_{3}\times\left(1+\frac{M}{\kappa_{2}}\right)\sqrt{\frac{q+\log
m}{n}}\right]\\\ &\leq\exp\big{\\{}\gamma_{2}(q+\log m)+\log
m-\left(1+C^{\prime}+(\gamma_{2})_{+}\right)(q+\log m)\big{\\}}\\\
&\leq\exp\\{-C^{\prime}(q+\log m)\\}\end{split}$ (78)

where $C=2c_{1}+\sqrt{\frac{1+C^{\prime}+(\gamma_{2})_{+}}{c_{3}}}.$ ∎

######  Lemma 11.

Let $(X,Y)\sim N(0,\Sigma)$ where $\Sigma$ is a covariance matrix in
$\mathcal{F}_{\mathcal{G}}(s_{u},p,m,q,r,\lambda,M)$ as defined in (72). Let
$\Gamma$ be the incidence matrix corresponding to the graph $G$ on $p$ nodes
and $m$ edges. Denote the support of $\Gamma U$ as ${\rm supp}(\Gamma U)$.
Assume that $\mathcal{H}_{1,\mathcal{G}}$ holds and that $|{\rm supp}(\Gamma
U)|\leq s_{u}$. Then, for a constant $C^{\prime}>0$, there exists $C>0$ that
solely depends on $C^{\prime}$ and $c_{0}$ such that:

$\max_{j\in[q]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\Sigma_{Y}^{-\frac{1}{2}}\right]_{j\cdot}\right\|\leq
C\left(1+{\frac{M}{\kappa_{2}}}\right)\cdot\sqrt{\frac{q+\log
m}{n}}+\sqrt{\frac{M}{\kappa_{2}}}$ (79)

with probability at least $1-\exp\\{-C^{\prime}(q+\log m)\\}$. Here we assume
that $c_{0}$ is small enough so that $C^{\prime}c_{0}\leq c_{3}-\log c_{2}-1$
with $c_{3},c_{2}$ the universal constants of Theorem 6.5 of Wainwright
[2019].

Proof Consider the term:

$\begin{split}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\Sigma_{Y}^{-\frac{1}{2}}\right]_{\cdot
j}\right\|\leq&\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{X\Gamma^{\dagger},Y\Sigma_{Y}^{-\frac{1}{2}}}\right]_{j\cdot}\right\|\\\
+&\max_{j\in[p]}\left\|\left[\Sigma_{X\Gamma^{\dagger},Y\Sigma_{Y}^{-\frac{1}{2}}}\right]_{j\cdot}\right\|\end{split}$
(80)

Introducing $\mathbf{1}_{j}^{\top}\in\mathbb{R}^{1\times m}$ the vector
indicator of row $j$ (i.e. $[\mathbf{1}_{j}]_{i}=0$ for all $i\neq j$, and
$[\mathbf{1}_{j}]_{j}=1$), we observe that:

$\max_{j\in[p]}\left\|\left[\Sigma_{X\Gamma^{\dagger},Y\Sigma_{Y}^{-\frac{1}{2}}}\right]_{j\cdot}\right\|=\max_{j\in[p]}\left\|\mathbf{1}_{j}^{\top}\Sigma_{X\Gamma^{\dagger},Y\Sigma_{Y}^{-\frac{1}{2}}}\right\|_{F}\leq\left\|\Sigma_{X\Gamma^{\dagger},Y\Sigma_{Y}^{-\frac{1}{2}}}\right\|_{op}\leq\sqrt{\frac{M}{\kappa_{2}}}\lambda_{1}.$
(81)

We now turn to the first term on the RHS of equation (80). The proof is
identical to that of Lemma 10, by introducing the transformed variables
$Z_{i}=X_{i}\Gamma^{\dagger}\sim\mathcal{N}_{p}\big{(}0,(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}\big{)}$
and
$\widetilde{Y}_{i}=Y_{i}\Sigma_{Y}^{-\frac{1}{2}}\sim\mathcal{N}_{q}(0,I_{q})$,
and writing

$\mathbf{1}_{j}^{\top}\left((\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-(\Gamma^{\dagger})^{\top}\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right)=\frac{1}{n}\sum_{i=1}^{n}\big{(}\mathbf{1}_{j}^{\top}Z_{i}\widetilde{Y}_{i}^{\top}-\mathbb{E}(\mathbf{1}_{j}^{\top}Z_{i}\widetilde{Y}_{i}^{\top})\big{)}.$

Define for each $j\in[p]$ the matrix
$H_{i}^{(j)}=\begin{pmatrix}\mathbf{1}_{j}^{\top}Z_{i}\\\
\widetilde{Y}_{i}\end{pmatrix}.$ We have then:

$\begin{split}\max_{j\in[p]}\bigg{\|}\mathbf{1}_{j}^{\top}\Big{(}(\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-(\Gamma^{\dagger})^{\top}\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}\Big{)}\bigg{\|}&\leq\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\\\
\end{split}$ (82)

Denoting
$\mathcal{H}^{(j)}=\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}=\begin{pmatrix}\mathbf{1}_{j}^{\top}(\Gamma^{\dagger})^{\top}\Sigma_{X}(\Gamma^{\dagger})\mathbf{1}_{j}&\mathbf{1}_{j}^{\top}(\Gamma^{\dagger})^{\top}\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}\\\
\Sigma_{Y}^{-\frac{1}{2}}\Sigma_{YX}(\Gamma^{\dagger})\mathbf{1}_{j}&I_{q}\end{pmatrix}$,
this implies:

$\begin{split}\left\|\mathcal{H}^{(j)}\right\|_{op}&=\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\mathbf{1}_{j}^{\top}(\Gamma^{\dagger})^{\top}\Sigma_{X}(\Gamma^{\dagger})\mathbf{1}_{j}u_{1}^{2}+2u_{1}\mathbf{1}_{j}^{\top}(\Gamma^{\dagger})^{\top}\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}u_{2}+{u_{2}^{\top}u_{2}}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\frac{M}{\kappa_{2}}u_{1}^{2}+2\lambda_{1}\sqrt{\frac{M}{\kappa_{2}}}u_{1}\|u_{2}\|+\|u_{2}\|^{2}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}{\frac{M}{\kappa_{2}}}u_{1}^{2}+\sqrt{\frac{M}{\kappa_{2}}}(u_{1}^{2}+\|u_{2}\|^{2})+\|u_{2}\|^{2}\\\
&=2\left(1+\frac{M}{\kappa_{2}}\right)\\\ \end{split}$ (83)

By the same arguments as for Lemma 10, we can show that for a constant
$C^{\prime}>0$, there exists $C>0$ that solely depends on $C^{\prime}$ such
that, for $c_{0}$ small enough:

$\begin{split}&\mathbb{P}\left[\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}(H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top})\right\|_{op}\geq
C\cdot 2(1+{\frac{M}{\kappa_{2}}})\cdot\sqrt{\frac{q+\log m}{n}}\right]\\\
&\leq\exp\big{\\{}-C^{\prime}(q+\log m)\big{\\}}.\end{split}$ (84)

This concludes the proof. ∎

######  Lemma 12.

Let $X,Y\sim\mathcal{F}_{\mathcal{G}}(s_{u},p,m,q,r,\lambda,M)$ as defined in
(72). Assume that

$M\frac{\log n_{c}+q}{n}\leq c_{0},$ ($\mathcal{H}_{1,\mathcal{G},\Pi}$)

with $c_{0}\in(0,1).$ Then, for a constant $C^{\prime}>0$, there exists $C>0$
that solely depends on $C^{\prime}$ such that

$\left\|\Pi^{\top}\frac{X^{\top}Y}{n}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}\leq\sqrt{Mn_{c}}\left(C\sqrt{M}\cdot\sqrt{\frac{q+\log
n_{c}}{n}}+1\right)$ (85)

with probability at least $1-\exp\big{\\{}C^{\prime}(q+\log n_{c})\big{\\}}$.
Here we assume that $c_{0}$ is small enough so that $C^{\prime}c_{0}\leq
c_{3}-\log c_{2}-1$ with $c_{3},c_{2}$ the universal constants of Theorem 6.5
of Wainwright [2019].

Proof In this case:

$\begin{split}\left\|\Pi\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}^{2}&=\sum_{j\in[n_{c}]}\left\|\mathbf{1}_{C_{j}}\frac{\mathbf{1}_{C_{j}}^{\top}}{|C_{j}|}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}^{2}\\\
&=\sum_{j\in[n_{c}]}\Bigg{\|}\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\Bigg{\|}^{2}\qquad(\star)\\\
&\leq
n_{c}\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|^{2}\\\
\end{split}$

where in $(\star)$, we have used the fact that

$\left\|\mathbf{1}_{C_{j}}\frac{\mathbf{1}_{C_{j}}^{\top}}{|C_{j}|}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}^{2}=\sum_{k\in
C_{j}}\frac{1}{|C_{j}|}\left\|\left[\mathbf{1}_{C_{j}}\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right]_{k\cdot}\right\|^{2}=\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|^{2}.$

We now proceed to bound the term:

$\begin{split}\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|^{2}&\leq\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\Big{(}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{X,Y\Sigma_{Y}^{-\frac{1}{2}}}\Big{)}\right\|^{2}+\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\Sigma_{X,Y\Sigma_{Y}^{-\frac{1}{2}}}\right\|^{2}\\\
&\leq\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\Big{(}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{X,Y\Sigma_{Y}^{-\frac{1}{2}}}\Big{)}\right\|^{2}+\left\|\Sigma_{X,Y\Sigma_{Y}^{-\frac{1}{2}}}\right\|_{op}^{2}\\\
&\leq\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\Big{(}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{X,Y\Sigma_{Y}^{-\frac{1}{2}}}\Big{)}\right\|^{2}+{M}\lambda_{1}^{2}\end{split}$
(86)

We follow once again the outline of the proof of Lemma 7 in Gao et al. [2017].
Defining $Z_{i}\sim N(0,\Sigma_{X})$ and $\widetilde{Y}_{i}\sim N(0,I_{q})$,
we may write

$\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}\Big{(}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}\Big{)}=\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}Z_{i}\widetilde{Y}_{i}^{\top}-\mathbb{E}\bigg{(}\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}Z_{i}\widetilde{Y}_{i}^{\top}\bigg{)}\bigg{)}.$

Then, define
$H_{i}^{(j)}=\begin{pmatrix}\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}Z_{i}\\\
\widetilde{Y}_{i}\end{pmatrix}$. Since
$\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}\Big{(}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}\Big{)}$
is a submatrix of $H_{i}^{(j)}(H_{i}^{(j)})^{\top},$ we have

$\begin{split}\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}(\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}-\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}})\right\|&\leq\max_{j\in[n_{c}]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}(H_{i}^{(j)})^{\top}-\mathbb{E}H_{i}^{(j)}(H_{i}^{(j)})^{\top}\big{)}\right\|_{op}\\\
\end{split}$ (87)

where
$\mathcal{H}^{(j)}=\mathbb{E}H_{i}^{(j)}(H_{i}^{(j)})^{\top}=\begin{pmatrix}\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}\Sigma_{X}\frac{\mathbf{1}_{C_{j}}}{\sqrt{|C_{j}|}}&\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}\\\
\Sigma_{Y}^{-\frac{1}{2}}\Sigma_{YX}\frac{\mathbf{1}_{C_{j}}}{\sqrt{|C_{j}|}}&I_{q}\end{pmatrix}$.
We also note that

$\begin{split}\left\|H^{(j)}\right\|_{op}&=\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}\Sigma_{X}\frac{\mathbf{1}_{C_{j}}}{\sqrt{|C_{j}|}}u_{1}^{2}+2u_{1}\frac{\mathbf{1}^{\top}_{C_{j}}}{\sqrt{|C_{j}|}}\Sigma_{XY}\Sigma_{Y}^{-\frac{1}{2}}u_{2}+u_{2}^{\top}u_{2}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}Mu_{1}^{2}+2\lambda_{1}\sqrt{M}u_{1}\|u_{2}\|+\|u_{2}\|^{2}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}Mu_{1}^{2}+\lambda_{1}\sqrt{M}\left(u_{1}^{2}+\|u_{2}\|^{2}\right)+M\|u_{2}\|^{2}\\\
&\leq 2M\end{split}$ (88)

since $\lambda_{1}\leq 1$ and $\sqrt{M}\leq M.$ By similar arguments to Lemma
10 (application of a union bound combined with Theorem 6.5 of Wainwright
[2019], we conclude that for a constant $C^{\prime}>0$, there exists $C>0$
such that:

$\begin{split}&\mathbb{P}\left[\max_{j\in[n_{c}]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}(H_{i}^{(j)})^{\top}-\mathbb{E}H_{i}^{(j)}(H_{i}^{(j)})^{\top}\big{)}\right\|_{op}\geq
C\cdot 2M\cdot\sqrt{\frac{q+\log n_{c}}{n}}\right]\\\
&\leq\exp\big{\\{}-C^{\prime}(q+\log n_{c})\big{\\}}\end{split}$ (89)

We conclude the proof by noting that this implies

$\begin{split}\max_{j\in[n_{c}]}\left\|\frac{\mathbf{1}_{C_{j}}^{\top}}{\sqrt{|C_{j}|}}\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|^{2}&\leq
C^{2}\cdot 4M^{2}\frac{q+\log n_{c}}{n}+{M}\lambda_{1}^{2}\end{split}$ (90)

with the same probability. ∎

######  Lemma 13.

Let $(X,Y)\sim N(0,\Sigma)$ where $\Sigma$ is a covariance matrix in
$\mathcal{F}_{\mathcal{G}}(s_{u},p,m,q,r,\lambda,M)$ as defined in (72). Let
$W\sim N(0,I_{q})$ and independent of $(X,Y)$. Assume
($\mathcal{H}_{1,\mathcal{G},\Pi}$) for $c_{0}\in(0,1).$ Then, for a constant
$C^{\prime}>0$, there exists a constant $C>0$ that depends solely on $C$ such
that

$\left\|\frac{\Pi^{\top}X^{\top}W}{n}\right\|_{F}\leq
CM\sqrt{n_{c}}\sqrt{\frac{q+\log n_{c}}{n}}$ (91)

with probability at least $1-\exp\big{\\{}-C^{\prime}(q+\log n_{c})\big{\\}}$.
Here we assume that $c_{0}$ is small enough so that $C^{\prime}c_{0}\leq
c_{3}-\log c_{2}-1$, with $c_{3},c_{2}$ the universal constants of Theorem 6.5
of Wainwright [2019].

Proof The proof is identical to that of Lemma 12, by replacing the matrix
$\Sigma_{X,Y\Sigma_{Y}^{-\frac{1}{2}}}$ with $\Sigma_{X,W},$ which is 0 since
$X$ and $W$ are assumed to be independent, and adjusting the corresponding
$\left\|\mathcal{H}^{(j)}\right\|_{op}.$

∎

######  Lemma 14.

Let $X_{i}\sim N(0,\Sigma_{X})$ where $\Sigma_{X}$ is a covariance matrix as
defined in (72). Let $W_{i}\sim N(0,\bar{\Sigma})$ independently of $X.$
Assume

$M\frac{\log m+q}{n}\leq c_{0}$ ($\mathcal{H}_{1,\mathcal{G}}$)

Then, for a constant $C^{\prime}>0$, there exists a constant $C>0$ that
depends solely on $C^{\prime}$ such that

$\begin{split}\max_{j\in[p]}\left\|\mathbf{1}_{j}^{\top}\big{(}(\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{{X}W}-(\Gamma^{\dagger})^{\top}{\Sigma}_{{X}W}\big{)}\right\|&\leq
C\left(1+\frac{M}{\kappa_{2}}\right)\sqrt{\frac{\log m+q}{n}}\end{split}$ (92)

with probability at least $1-\exp\big{\\{}-C^{\prime}(q+\log m)\big{\\}}.$
Here we assume that $c_{0}$ is small enough so that $C^{\prime}c_{0}\leq
c_{3}-\log c_{2}-1$ with $c_{3},c_{2}$ the universal constants of Theorem 6.5
of Wainwright [2019]

Proof Let
$Z_{i}\sim\mathcal{N}_{m}\big{(}0,(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}\big{)}$
and $\widetilde{X}_{i}\sim\mathcal{N}_{q}(0,\bar{\Sigma})$, and
$\mathbf{1}_{j}^{\top}\in\mathbb{R}^{1\times m}$ the vector indicator of row
$j$ (i.e. $[\mathbf{1}_{j}]_{i}=0$ for all $i\neq j$, and
$[\mathbf{1}_{j}]_{j}=1$). Thus, denoting $\widetilde{X}=X\Gamma^{\dagger}$,
we may write

$\mathbf{1}_{j}^{\top}(\widehat{\Sigma}_{\widetilde{X}W}-\Sigma_{\widetilde{X}W})=\frac{1}{n}\sum_{i=1}^{n}\big{(}\mathbf{1}_{j}^{\top}Z_{i}W_{i}^{\top}-\mathbb{E}(\mathbf{1}_{j}^{\top}Z_{i}W_{i}^{\top})\big{)}.$

We also note that

$\left\|\Sigma_{\widetilde{X}}\right\|_{op}=\left\|(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}\right\|_{op}=\sup_{u\in\mathbb{R}^{m}}\frac{u^{\top}(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}u}{\|u\|^{2}}\leq
M\frac{\|\Gamma^{\dagger}u\|^{2}}{\|u\|^{2}}\leq\frac{M}{\kappa_{2}}.$

Moreover, one can show that

$\left\|\bar{\Sigma}\right\|_{op}=\left\|I-V_{0}\Lambda^{2}V_{0}^{\top}\right\|_{op}\leq
1.$

Define for each $j\in[p]$ the matrix
$H_{i}^{(j)}=\begin{pmatrix}\mathbf{1}_{j}^{\top}Z_{i}\\\ W_{i}\end{pmatrix}.$
We have then

$\begin{split}\max_{j\in[p]}\left\|\mathbf{1}_{j}^{\top}(\widehat{\Sigma}_{\widetilde{X}W}-{\Sigma}_{\widetilde{X}W})\right\|&\leq\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\\\
\end{split}$ (93)

Denote
$\mathcal{H}^{(j)}=\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}=\begin{pmatrix}\mathbf{1}_{j}^{\top}\Sigma_{\widetilde{X}}\mathbf{1}_{j}&0\\\
0&\bar{\Sigma}\end{pmatrix}$. This implies:

$\begin{split}\left\|\mathcal{H}^{(j)}\right\|_{op}&=\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\mathbf{1}_{j}^{\top}\Sigma_{\widetilde{X}}\mathbf{1}_{j}u_{1}^{2}+{u_{2}^{\top}\bar{\Sigma}u_{2}}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\frac{M}{\kappa_{2}}u_{1}^{2}+\|u_{2}\|^{2}\\\
&\leq\sup_{\begin{subarray}{c}u_{1}\in\mathbb{R},~{}u_{2}\in\mathbb{R}^{q}\\\
u_{1}^{2}+\|u_{2}\|^{2}=1\end{subarray}}\frac{M}{\kappa_{2}}u_{1}^{2}+\sqrt{\frac{M}{\kappa_{2}}}(u_{1}^{2}+\|u_{2}\|^{2})+\|u_{2}\|^{2}\\\
&\leq 1+\frac{M}{\kappa_{2}},\\\ \end{split}$ (94)

Therefore, by arguments similar to Lemma 10 (union bound and Theorem 6.5 of
Wainwright [2019]), we conclude that for any $C^{\prime}>0$ such that
$C^{\prime}c_{0}\leq c_{3}-\log c_{2}-1$, with $c_{3},c_{2}$ the universal
constants of Theorem 6.5 of Wainwright [2019], there exists $C>0$ such that:

$\begin{split}&\mathbb{P}\left[\max_{j\in[p]}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}-\mathbb{E}H_{i}^{(j)}\big{(}H_{i}^{(j)}\big{)}^{\top}\big{)}\right\|_{op}\geq
C\cdot\left(1+\frac{M}{\kappa_{2}}\right)\sqrt{\frac{q+\log m}{n}}\right]\\\
&\leq\exp\\{-C^{\prime}(\log m+q)\\}.\end{split}$ (95)

This concludes the proof. ∎

###  E.2 Proof of Theorem 5

######  Theorem.

Consider the family $\mathcal{F}_{\mathcal{G}}(s_{u},p,m,q,r,\lambda,M)$ of
covariance matrices satisfying assumptions. We assume that:

$M\frac{{q}+s_{u}\log\big{(}\frac{ep}{s_{u}}\big{)}}{n}\leq
c_{0}\quad\mbox{and}\quad\frac{\log n_{c}+q}{n}\leq c_{0},$
($\mathcal{H}_{1,\mathcal{G}}$)

We assume as well that $n$ is large enough so that:

$n\geq 10\vee 128M^{2}\Big{(}72n_{c}+576\rho(\Gamma)^{2}\log
p\big{(}96C^{\prime}\sqrt{n_{c}}+4\sqrt{s_{u}}\big{)}^{2}\Big{)},$

We write $\Delta=\widehat{B}-B^{*}$ with $B^{*}=U\Lambda
V^{\top}\Sigma_{Y}^{\frac{1}{2}}$, and choose $\rho\geq
CM^{2}\sqrt{\frac{q+\log m}{n}}$ for some large constant $C$. Then the
solution $\widehat{B}$ of the penalized regression problem (18) is such that,
there exist constants $C_{1}$ and $C_{2}$ that do not depend on the parameters
of the problem such that

$\begin{split}\left\|\widehat{\Sigma}_{X}^{1/2}\Delta\right\|_{F}^{2}&\leq
C_{1}M^{5}\left({n_{c}\frac{q+\log(n_{c})}{n}}+{\left(1+\frac{1}{\kappa_{2}}\right)^{2}\sigma_{\max}(L)\cdot{s_{u}\frac{q+\log
m}{n}}}\right)\\\ \qquad\left\|\Delta\right\|_{F}&\leq
C_{2}M^{3}\left(\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{s_{u}\frac{q+\log
m}{n}}\right)\end{split}$

with probability at least

$1-4\exp\\{-C^{\prime}(q+\log n_{c})\\}-q\exp\\{-c_{2}n\\}.$

Proof We begin by the following observation. Since $(X,Y)$ are jointly
multivariate normal and writing $V_{0}=\Sigma_{Y}^{\frac{1}{2}}V$, conditioned
on $X$, the following holds:

$Y|X\sim\mathcal{N}\left(XB^{*}\Sigma_{Y}^{\frac{1}{2}},~{}\Sigma_{Y}^{\frac{1}{2}}(I-V_{0}\Lambda^{2}V_{0}^{\top})\Sigma_{Y}^{\frac{1}{2}}\right)$

Therefore

$Y\Sigma_{Y}^{-\frac{1}{2}}|X\sim\mathcal{N}\left(XB^{*},~{}(I-V_{0}\Lambda^{2}V_{0}^{\top})\right)$
(*)

We assume that

$M\frac{{q}+\big{(}s_{u}\log\big{(}\frac{ep}{s_{u}}\big{)}\vee\log
n_{c}\big{)}}{n}\leq c_{0}$ ($\mathcal{H}_{1,\mathcal{G}}$)

We now turn to the analysis of the regression problem (18)

$\text{argmin}_{B\in\mathbb{R}^{p\times q}}\|Y_{0}-XB\|_{F}^{2}+\rho~{}|\Gamma
B\|_{21}$

where we let $Y_{0}=Y\widehat{\Sigma}_{Y}^{\frac{1}{2}}$. By the KKT
conditions:

$\frac{2}{n}X^{\top}(X\widehat{B}-Y_{0})=\rho~{}\Gamma^{\top}D^{(\widehat{B})}\Gamma\widehat{B}$

where $D^{(\widehat{B})}$ is a diagonal matrix such that
$D^{(\widehat{B})}_{ii}=\frac{1}{\|[\Gamma\widehat{B}]_{i\cdot}\|}.$ Left-
multiplying this equality by $\widehat{B}^{\top}$ and taking the trace, we
obtain:

$\frac{2}{n}\mathop{\sf
Tr}\big{(}\widehat{B}^{\top}X^{\top}(Y_{0}-X\widehat{B})\big{)}=\rho\mathop{\sf
Tr}\big{(}\widehat{B}^{\top}\Gamma^{\top}D^{(\widehat{B})}\Gamma\widehat{B}\big{)}$

which is equivalent to

$\frac{2}{n}\big{\langle}X\widehat{B},~{}Y_{0}-X\widehat{B}\big{\rangle}=\rho\|\Gamma\widehat{B}\|_{21}$

This also implies that for any $B\in\mathbb{R}^{p\times q}$

$\frac{2}{n}\big{\langle}XB,~{}Y_{0}-X\widehat{B}\big{\rangle}=\rho\mathop{\sf
Tr}\big{(}B^{\top}\Gamma^{\top}D^{(\widehat{B})}\Gamma\widehat{B}\big{)}\leq\rho\|\Gamma
B\|_{21}$

For any $B\in\mathbb{R}^{p\times q}$, this means that

$\begin{split}\frac{2}{n}\big{\langle}X(B-\widehat{B}),~{}Y_{0}-X\widehat{B}\big{\rangle}&\leq\rho\big{(}\|\Gamma
B\|_{21}-\|\Gamma\widehat{B}\|_{21}\big{)}\\\
\implies\frac{2}{n}\big{\langle}X(B-\widehat{B}),~{}Y_{0}-Y\Sigma_{Y}^{-\frac{1}{2}}-X\widehat{B}+Y\Sigma_{Y}^{-\frac{1}{2}}\big{\rangle}&\leq\rho\big{(}\|\Gamma
B\|_{21}-\|\Gamma\widehat{B}\|_{21}\big{)}\\\
\implies\frac{2}{n}\big{\langle}X(B-\widehat{B}),~{}Y\big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\big{)}+X(B^{*}-\widehat{B})+W\big{\rangle}&\leq\rho\big{(}\|\Gamma
B\|_{21}-\|\Gamma\widehat{B}\|_{21}\big{)}\\\ \end{split}$ (96)

where we used $Y\Sigma_{Y}^{-\frac{1}{2}}=XB^{*}+W$, $W\sim N(0,\bar{\Sigma})$
with $\bar{\Sigma}=I_{q}-V_{0}\Lambda^{2}V_{0}^{\top}.$ Therefore, for any
$B\in\mathbb{R}^{p\times q}$

$\begin{split}\frac{2}{n}\big{\langle}X(\widehat{B}-B),&~{}X(\widehat{B}-B^{*})\big{\rangle}\\\
\leq&\frac{2}{n}\big{\langle}X(\widehat{B}-B),Y\big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\big{)}+W\big{\rangle}+\rho\big{(}\|\Gamma
B\|_{21}-\|\Gamma\widehat{B}\|_{21}\big{)}\\\ \end{split}$ (97)

This means that to proceed further, we need to bound the term:

$\begin{split}\big{\langle}X(\widehat{B}-B),~{}Y\big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\big{)}+W\big{\rangle}&=\big{\langle}\Pi(\widehat{B}-B),~{}\Pi^{\top}X^{\top}\big{(}Y\big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\big{)}+W\big{)}\big{\rangle}\\\
&+\big{\langle}\Gamma(\widehat{B}-B),(\Gamma^{\dagger})^{\top}X^{\top}\big{(}Y\big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\big{)}+W\big{)}\big{\rangle}\\\
&\leq\underbrace{\frac{1}{n}\left\|\Pi(\widehat{B}-B)\right\|_{F}~{}\left\|\Pi^{\top}X^{\top}\big{(}Y\big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\big{)}+W\big{)}\right\|_{F}}_{(A)}\\\
&+\underbrace{\big{\|}\Gamma(\widehat{B}-B)\big{\|}_{21}~{}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\big{)}\right]_{j\cdot}\right\|}_{(B)}\\\
&+\underbrace{\big{\|}\Gamma(\widehat{B}-B)\big{\|}_{21}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}W}{n}\right]_{j\cdot}\right\|}_{(C)}\end{split}$
(98)

#### Bound (A) in Equation (98).

We first consider the term:

$\begin{split}&\left\|\Pi(\widehat{B}-B)\|\right\|_{F}~{}\left\|\Pi^{\top}\frac{X^{\top}Y}{n}\big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\big{)}+\frac{\Pi^{\top}X^{\top}W}{n}\right\|_{F}\\\
&\leq\|\widehat{B}-B\|_{F}\cdot\bigg{(}\left\|\frac{1}{n}\Pi^{\top}X^{\top}Y\big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\big{)}\right\|_{F}+\left\|\frac{1}{n}\Pi^{\top}X^{\top}W)\right\|_{F}\bigg{)}\\\
&\leq\|\widehat{B}-B\|_{F}\cdot\Big{(}\left\|\Pi\widehat{\Sigma}_{XY}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}~{}\left\|\Sigma_{Y}^{\frac{1}{2}}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-I_{q}\right\|_{op}+\left\|\widehat{\Sigma}_{X\Pi,W}\right\|_{F}\Big{)}\\\
&\leq\|\widehat{B}-B\|_{F}\cdot\Big{(}\left\|\widehat{\Sigma}_{X\Pi,Y}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}~{}\left\|\Sigma_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\right\|_{op}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}+\left\|\widehat{\Sigma}_{X\Pi,W}\right\|_{F}\Big{)}\end{split}$
(99)

Let $\mathcal{A}_{Y}$ be the event:
$\mathcal{A}_{Y}=\Big{\\{}\left\|\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\right\|_{op}^{2}<CM^{2}\frac{q}{n}\Big{\\}}$,
with $C$ a constant chosen such that $\mathcal{A}_{Y}$ holds with probability
at least $1-\exp\\{-C^{\prime}q\\}$ with $C^{\prime}>0$ (see Lemma 7).

(i) Bounding the terms in operator norm. By Weyl’s inequality, letting
$\delta_{n}=\sqrt{\frac{q}{n}}$, we know that on $\mathcal{A}_{Y}$

$\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}\leq\frac{1}{\sigma_{\min}\Big{(}\Sigma_{Y}^{\frac{1}{2}}\Big{)}-\sqrt{CM^{2}}\cdot\delta_{n}}\leq
2\sqrt{M}$ (100)

as long as $\sqrt{CM^{2}}\cdot\sqrt{\frac{q}{n}}\leq\frac{1}{2\sqrt{M}}$.
Therefore, on $\mathcal{A}_{Y}$

$\left\|\Sigma_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\right\|_{op}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}\leq
2M^{\frac{3}{2}}\sqrt{C}\sqrt{\frac{q}{n}}.$

(ii) Bounding the terms in Frobenius norm.

We begin with the term $\left\|\widehat{\Sigma}_{\Pi
X,Y}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}$. For $C^{\prime}>0$, we denote as
$\mathcal{A}_{X\Pi,Y}$ the event

$\begin{split}\mathcal{A}_{X\Pi,Y}=\Big{\\{}\left\|\widehat{\Sigma}_{\Pi
X,Y}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}&\leq\sqrt{Mn_{c}}\Big{(}1+C\sqrt{M}\sqrt{\frac{q+\log
n_{c}}{n}}\Big{)}\Big{\\}}\\\ \end{split}$ (101)

for some constant $C$ that depends only on $C^{\prime}$. As shown in Lemma 12,
this event has probability at least $1-\exp\\{-C^{\prime}(\log n_{c}+q)\\}.$

On $\mathcal{A}_{Y}\cap\mathcal{A}_{X\Pi,Y}$, after readjusting our constant
$C$ to be the maximum of the constants in the bounds of $\mathcal{A}_{Y}$ and
$\mathcal{A}_{X\Pi,Y}$ we have:

$\begin{split}\left\|\widehat{\Sigma}_{X\Pi,Y}\Sigma_{Y}^{-\frac{1}{2}}\right\|_{F}~{}\left\|\Sigma_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\right\|_{op}&\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}\\\
&\leq\sqrt{Mn_{c}}\left(1+C\sqrt{M}\sqrt{\frac{q+\log n_{c}}{n}}\right)\cdot
2M^{\frac{3}{2}}\sqrt{C}\sqrt{\frac{q}{n}}\\\
&\leq\tilde{C}M^{2}\sqrt{\frac{qn_{c}}{n}}\Big{(}1+\sqrt{M}\cdot\sqrt{\frac{q+\log
n_{c}}{n}}\Big{)}\\\ &\leq 2\tilde{C}M^{2}\sqrt{\frac{qn_{c}}{n}}\qquad\text{
under assumption }\mathcal{H}_{1,\mathcal{G}}.\\\ \end{split}$ (102)

We now turn to the term
$\left\|\Pi\widehat{\Sigma}_{XW}\right\|_{F}=\left\|\widehat{\Sigma}_{X\Pi,W}\right\|_{F}$.
By Lemma 13, for $C^{\prime}>0$ we know that there exists $C>0$ a constant
that depends solely on $C^{\prime}$ such that:

$\begin{split}\left\|\Pi\widehat{\Sigma}_{XW}\right\|_{F}&\leq\left\|\Pi\widehat{\Sigma}_{X\widetilde{W}}\right\|_{F}\left\|\bar{\Sigma}^{\frac{1}{2}}\right\|_{op}\quad\text{
with }\quad\widetilde{W}\sim N(0,I_{q})\\\ &\leq
CM\sqrt{n_{c}\cdot\frac{q+\log n_{c}}{n}}\quad\text{since
}\quad\left\|\bar{\Sigma}^{\frac{1}{2}}\right\|_{op}\leq 1\\\ \end{split}$
(103)

with probability at least $1-\exp\\{-C^{\prime}(q+\log n_{c})\\}$. In the rest
of this proof, we denote as $\mathcal{A}_{X\Pi W}$ denote the event

$\begin{split}\mathcal{A}_{\Pi
XW}=\Big{\\{}\left\|\Pi\widehat{\Sigma}_{XY}W\right\|_{F}\leq
CM\sqrt{n_{c}\cdot\frac{q+\log n_{c}}{n}}\Big{\\}}.\\\ \end{split}$ (104)

Combing the results together and taking $C$ the maximum of all constants in
the corresponding bounds we deduce that on the event $\mathcal{A}_{\Pi
XW}\cap\mathcal{A}^{c}_{Y}\cap\mathcal{A}_{X\Pi,Y}$,

$\begin{split}\left\|\Pi^{\top}\frac{X^{\top}Y}{n}\Big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\Big{)}+\Pi^{\top}\frac{X^{\top}W}{n}\right\|_{F}&\leq
CM^{2}\sqrt{\frac{qn_{c}}{n}}+CM\sqrt{n_{c}\cdot\frac{q+\log n_{c}}{n}}\\\
&\leq CM^{2}\sqrt{n_{c}\frac{q+\log n_{c}}{n}}\\\ \end{split}$ (105)

To characterize the corresponding probability, we note that:

$\displaystyle\begin{split}\mathbb{P}\left[\mathcal{A}_{\Pi
XW}^{c}\cup\mathcal{A}_{Y}\cup\mathcal{A}_{X\Pi,Y}^{c}\right]&\leq\mathbb{P}\left[\mathcal{A}^{c}_{\Pi
XW}\right]+\mathbb{P}\left[\mathcal{A}^{c}_{Y}\right]+\mathbb{P}\left[\mathcal{A}_{X\Pi,Y}^{c}\right]\\\
&\leq\exp\\{-C^{\prime}(\log
n_{c}+q)\\}+\exp\\{-C^{\prime}q\\}+\exp\\{-C^{\prime}(q+\log n_{c})\\}\\\
&\leq 3\exp\\{-C^{\prime}(q+\log n_{c})\\}\end{split}$ (106)

#### Bound (B) in Equation (98).

We now proceed to bound the term:

$\begin{split}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\Big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\Big{)}\right]_{j\cdot}\right\|&\leq\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\Sigma_{Y}^{-\frac{1}{2}}\right]_{j\cdot}\right\|~{}\left\|\Sigma_{Y}^{\frac{1}{2}}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-I_{q}\right\|_{op}\\\
\leq\max_{j\in[p]}&\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}Y}{n}\Sigma_{Y}^{-\frac{1}{2}}\right]_{j\cdot}\right\|~{}\left\|\Sigma_{Y}^{\frac{1}{2}}-\widehat{\Sigma}_{Y}^{\frac{1}{2}}\right\|_{op}~{}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}\end{split}$
(107)

For $C^{\prime}>0$ a constant, let us denote as
$\mathcal{A}_{(\Gamma^{\dagger})^{\top}\Sigma_{XY}}$ the event:

$\mathcal{A}_{{(\Gamma^{\dagger})^{\top}\Sigma_{XY}}}=\bigg{\\{}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{XY}{\Sigma}_{Y}^{-\frac{1}{2}}\right]_{j\cdot}\right\|\geq\sqrt{\frac{M}{\kappa_{2}}}+C\left(1+\frac{M}{\kappa_{2}}\right)\cdot\sqrt{\frac{q+\log
m}{n}}\bigg{\\}}.$

In the previous equation, we’ve chosen $C$ to be a constant that depends
solely on $C^{\prime}$ such that, with probability at least
$1-\exp\\{-C^{\prime}(q+\log m)\\}+\exp\\{-C^{\prime}q\\}),$ the event
$\mathcal{A}_{{(\Gamma^{\dagger})^{\top}\Sigma_{XY}}}^{c}\cap\mathcal{A}_{Y}^{c}$
occurs (see Lemma 11). Thus

$\begin{split}\max_{j\in[p]}&\left\|\left[(\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{XY}\Big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-{\Sigma}_{Y}^{-\frac{1}{2}}\Big{)}\right]_{j\cdot}\right\|\\\
&\leq\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}{\widehat{\Sigma}}_{XY}{\Sigma}_{Y}^{-\frac{1}{2}}\right]_{j\cdot}\right\|\cdot\sqrt{CM^{2}\frac{q}{n}}\cdot
2\sqrt{M}\quad\text{ by Eq.(\ref{eq:op_norm_A}) }\\\ &\leq
M^{2}\bigg{(}\sqrt{\frac{1}{\kappa_{2}}}+C\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{M}\cdot\sqrt{\frac{q+\log
m}{n}}\bigg{)}\cdot\sqrt{\frac{q}{n}}\quad\text{ on
}\mathcal{A}_{{(\Gamma^{\dagger})^{\top}\Sigma_{XY}}}^{c}\\\ &\leq
C^{\prime}M^{2}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q}{n}}\qquad\text{under
}H_{1.\mathcal{G}}.\end{split}$ (108)

where $C^{\prime}=1\vee C$.

#### Bound (C) in Equation (98).

For $W\sim N(0,\bar{\Sigma})$ with covariance
${\bar{\Sigma}=I_{q}-V_{0}\Lambda^{2}V_{0}^{\top}}$, we now proceed to bound
the term:

$\begin{split}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}W}{n}\right]_{j\cdot}\right\|\end{split}$
(109)

For $C^{\prime}>0$, let us denote as $\mathcal{A}_{{X\Gamma^{\dagger},W}}$ the
event:

$\mathcal{A}_{{X\Gamma^{\dagger},W}}=\bigg{\\{}\max_{j\in[p]}\left\|\left[(\Gamma^{\dagger})^{\top}\frac{X^{\top}W}{n}\right]_{j\cdot}\right\|\geq
C\cdot(1+\frac{M}{\kappa_{2}})\sqrt{\frac{q+\log m}{n}}\bigg{\\}}.$

In the previous equation, we’ve chosen $C$ such that the event
$\mathcal{A}_{{X\Gamma^{\dagger},W}}^{c}$ occurs with probability at least
${1-\exp\\{-C^{\prime}(q+\log m)\\}}$ (see Lemma 10).

#### Bounding (A) +(B) + (C) in Equation (98).

Combining the three previous bounds and denoting by $C$ the maximum over all
constants in the corresponding bounds, we obtain that on the event
$\mathcal{G}=\mathcal{A}_{Y}^{c}\cap\mathcal{A}_{X\Pi
Y}^{c}\cap\mathcal{A}_{X\Gamma^{\dagger},W}^{c}\cap\mathcal{A}_{X\Gamma^{\dagger},Y}^{c}$

$\begin{split}\frac{1}{n}&\left\langle
X(\widehat{B}-B),~{}Y\Big{(}\widehat{\Sigma}_{Y}^{\frac{1}{2}}-\Sigma_{Y}^{\frac{1}{2}}\Big{)}+W\right\rangle\leq\|\widehat{B}-B\|_{F}\cdot
CM^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}\\\
&+\|\Gamma(\widehat{B}-B)\|_{21}\cdot\left(CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q}{n}}+CM\cdot\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q+\log
m}{n}}\right)\\\ &\leq C\|\widehat{B}-B\|_{F}\cdot
M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\|\Gamma(\widehat{B}-B)\|_{21}\cdot
CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q+\log m}{n}}\end{split}$
(110)

#### Bounding the regression error

For any $S\in[p]$:

$\begin{split}\|\Gamma
B\|_{21}-\|\Gamma\widehat{B}\|_{21}&\leq\big{\|}[\Gamma(B-\widehat{B})]_{S\cdot}\big{\|}_{21}+\big{\|}[\Gamma
B]_{S^{c}}\big{\|}_{21}-\big{\|}[\Gamma\widehat{B}]_{S^{c}}\big{\|}_{21}\\\
&\leq\big{\|}[\Gamma(B-\widehat{B})]_{S\cdot}\big{\|}_{21}+2\big{\|}[\Gamma
B]_{S^{c}}\big{\|}_{21}-\big{\|}[\Gamma(\widehat{B}-B)]_{S^{c}}\big{\|}_{21}\end{split}$
(111)

Therefore, choosing $\rho>4\cdot
CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q+\log m}{n}}$, Equation
97 implies the following bound on $\mathcal{G}$:

$\begin{split}\frac{2}{n}&\left\langle
X(\widehat{B}-B),X(\widehat{B}-B^{*})\right\rangle\leq
C^{\prime}\|\widehat{B}-B\|_{F}M^{3}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\frac{\rho}{2}\|\Gamma(\widehat{B}-B)\|_{21}\\\
&+\rho\Big{(}\big{\|}[\Gamma(B-\widehat{B})]_{S\cdot}\big{\|}_{21}+2\big{\|}[\Gamma
B]_{S^{c}}\big{\|}_{21}-\big{\|}[\Gamma(\widehat{B}-B)]_{S^{c}}\big{\|}_{21}\Big{)}\\\
\end{split}$ (112)

Therefore, for $B=B^{*}$ and choosing $S=S_{u}={\rm supp}{(\Gamma B^{*})}$ we
have:

$\begin{split}\frac{1}{n}\|X\Delta\|_{F}^{2}\leq
C^{\prime}M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}\|\Delta\|_{F}+\rho\bigg{(}\frac{3}{2}\big{\|}[\Gamma\Delta]_{S\cdot}\big{\|}_{21}-\frac{1}{2}\big{\|}[\Gamma\Delta]_{S^{c}}\big{\|}_{21}\bigg{)}\\\
\end{split}$ (113)

where we denote $\Delta=\widehat{B}-B^{*}$. Note that, by Cauchy-Schwarz,

$\begin{split}\big{\|}[\Gamma\Delta]_{S\cdot}\big{\|}_{21}&=\sum_{j\in[S]}\big{\|}[\Gamma\Delta]_{j\cdot}\big{\|}\leq\sqrt{s_{u}}\sqrt{\sum_{j\in[S]}\big{\|}[\Gamma\Delta]_{j\cdot}\big{\|}^{2}}\\\
&\leq\sqrt{s_{u}}\cdot\|\Gamma\Delta\|_{F}\leq\sqrt{s_{u}\sigma_{\max}(L)}\cdot\|\Delta\|_{F}\end{split}$
(114)

The expression in Equation (113) can be thus simplified to

$\begin{split}\frac{1}{n}\|X\Delta\|_{F}^{2}\leq\|\Delta\|_{F}\left(C^{\prime}M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\frac{3\rho}{2}\sqrt{s_{u}\sigma_{\max}(L)}\right)-\frac{\rho}{2}\big{\|}[\Gamma\Delta]_{S^{c}}\big{\|}_{21}\\\
\end{split}$ (115)

Note that Equation (115) implies the following generalized cone constraint:

$\begin{split}\big{\|}[\Gamma\Delta]_{S^{c}}\big{\|}_{21}&\leq\|\Delta\|_{F}\Bigg{(}2C^{\prime}\frac{M^{2}}{4CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q+\log
m}{n}}}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+3\sqrt{s_{u}\sigma_{\max}(L)}\Bigg{)}\\\
&\leq\|\Delta\|_{F}\Bigg{(}\widetilde{C}\sqrt{{n_{c}}}+3\sqrt{s_{u}\sigma_{\max}(L)}\Bigg{)}\quad\text{
since }n_{c}<<m\\\ \end{split}$ (116)

Equation (115) also implies:

$\begin{split}\frac{1}{n}\|X\Delta\|_{F}^{2}&\leq\|\Delta\|_{F}\left(C^{\prime}M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\frac{3\rho}{2}\sqrt{s_{u}\sigma_{\max}(L)}\right)\\\
\end{split}$ (117)

To proceed any further, we must show a Restricted Eigenvalue property on our
generalised cone (Eq. 116). To this end, we leverage Lemma 2.2 in Tran et al.
[2022].

######  Lemma 15 (Lemma 2.2 in Tran et al. [2022]).

If $X\in\mathbb{R}^{n\times p}$ has i.i.d. $\mathcal{N}(0,{\Sigma_{X}})$ rows
and $p\geq 2$, $n\geq 10$, then the event

$\left\|\frac{Xv}{\sqrt{n}}\right\|^{2}\geq
v^{\top}\left(\frac{1}{64}{\Sigma_{X}}\right)v-72\sigma_{\text{max}}(\Sigma_{X})n_{c}\frac{\|v\|^{2}}{n}-576\rho(\Gamma)^{2}\frac{\sigma_{\text{max}}({\Sigma_{X}})\log
p}{n}\|\Gamma v\|_{1}^{2}$

holds for all $v\in\mathbb{R}^{p}$ with probability at least
$1-c_{1}\exp\\{-nc_{2}\\}$, for some universal constants $c_{1},c_{2}>0$.

Let $\mathcal{A}^{j}_{\kappa}$ and $\mathcal{A}_{\kappa}$ denote the events:

$\mathcal{A}^{j}_{\kappa}=\left\\{\left\|\frac{X\Delta_{\cdot
j}}{\sqrt{n}}\right\|^{2}\geq\Delta_{\cdot
j}^{\top}\left(\frac{1}{64}\Sigma_{X}\right)\Delta_{\cdot
j}-72\sigma_{\text{max}}(\Sigma_{X})n_{c}\frac{\|\Delta_{\cdot
j}\|^{2}}{n}-576\rho(\Gamma)^{2}\frac{\sigma_{\text{max}}(\Sigma_{X})\log
p}{n}\|\Gamma\Delta_{\cdot j}\|_{1}^{2}\right\\}$
$\mathcal{A}_{\kappa}=\left\\{\frac{\|{X}\Delta\|_{F}^{2}}{{n}}\geq\frac{1}{64}\left\|\Sigma^{\frac{1}{2}}_{X}\Delta\right\|_{F}^{2}-\frac{72Mn_{c}}{n}\|\Delta\|_{F}^{2}-576\frac{\rho(\Gamma)^{2}M\log
p}{n}\sum_{j\in[q]}\big{\|}[\Gamma\Delta]_{\cdot j}\big{\|}_{1}^{2}\right\\}$

By Lemma 15, applying a simple union bound for $q$ vectors
$\mathcal{A}_{\kappa}^{c}\subset\bigcup_{j\in[q]}(\mathcal{A}_{\kappa}^{j})^{c}$,
therefore:

$\begin{split}\mathbb{P}[\mathcal{A}_{\kappa}^{c}]&\leq\sum_{jin[q]}\mathbb{P}\big{[}(\mathcal{A}_{\kappa}^{j})^{c}\big{]}\leq
qe^{-c_{2}n}\end{split}$ (118)

This means in particular:

$\begin{split}\frac{1}{64}\left\|\Sigma^{\frac{1}{2}}_{X}\Delta\right\|_{F}^{2}\leq\frac{\|{X}\Delta\|_{F}^{2}}{{n}}+\frac{72Mn_{c}}{n}\|\Delta\|_{F}^{2}+576\frac{\rho(\Gamma)^{2}M\log
p}{n}\sum_{j\in[q]}\big{\|}[\Gamma\Delta]_{\cdot
j}\big{\|}_{1}^{2}\end{split}$ (119)

We note that for any $v\in\mathbb{R}^{p\times q}$

$\begin{split}\sum_{j\in[q]}\big{\|}[\Gamma v]_{\cdot
j}\big{\|}_{1}^{2}&=\sum_{j\in[q]}\sum_{a\in[p]}\big{|}[\Gamma
v]_{aj}\big{|}\sum_{b\in[p]}\big{|}[\Gamma
v]_{bj}\big{|}=\sum_{a\in[p]}\sum_{b\in[p]}\sum_{j\in[q]}\big{|}[\Gamma
v]_{aj}\big{|}\big{|}[\Gamma v]_{bj}\big{|}\\\
&\leq\sum_{a\in[p]}\sum_{b\in[p]}\big{\|}[\Gamma
v]_{a\cdot}\big{\|}~{}\big{\|}[\Gamma
v]_{b\cdot}\big{\|}=\Big{(}\sum_{a\in[p]}\big{\|}[\Gamma
v]_{a\cdot}\big{\|}\Big{)}^{2}=\|\Gamma v\|_{21}^{2}\end{split}$ (120)

thus must thus bound $\|\Gamma\Delta\|_{21}^{2}$. Combining Equations (114)
and (116) we get

$\begin{split}\big{\|}[\Gamma\Delta]\big{\|}_{21}&\leq\|\Delta\|_{F}\Big{(}\widetilde{C}\sqrt{{n_{c}}}+3\sqrt{s_{u}\sigma_{\max}(L)}\Big{)}+\sqrt{s_{u}\sigma_{\max}(L)}\|\Delta\|_{F}\\\
&\leq\|\Delta\|_{F}\left(\widetilde{C}\sqrt{n_{c}}+4\sqrt{s_{u}\sigma_{\max}(L)}\right)\\\
\end{split}$ (121)

Combined with Equations (121) and (117), Equation (119) becomes:

$\begin{split}\frac{1}{64}\left\|\Sigma^{\frac{1}{2}}_{X}\Delta\right\|_{F}^{2}&\leq\frac{\|{X}\Delta\|_{F}^{2}}{{n}}+\frac{72Mn_{c}}{n}\|\Delta\|_{F}^{2}\\\
&+576\frac{\rho(\Gamma)^{2}M\log
p}{n}\|\Delta\|^{2}_{F}\left(\widetilde{C}\sqrt{n_{c}}+4\sqrt{s_{u}\sigma_{\max}(L)}\right)^{2}\\\
&\leq\|\Delta\|_{F}\Big{(}C^{\prime}M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\frac{3\rho}{2}\sqrt{s_{u}\sigma_{\max}(L)}\Big{)}\\\
&+\frac{M}{n}\|\Delta\|^{2}_{F}\left(72n_{c}+576\rho(\Gamma)^{2}\log
p\left(2\widetilde{C}^{2}{n_{c}}+32s_{u}\sigma_{\max}(L)\right)\right)\end{split}$
(122)

This implies

$\begin{split}\frac{1}{64M}\|\Delta\|^{2}_{F}&\leq\|\Delta\|_{F}\Big{(}C^{\prime}M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\frac{3\rho}{2}\sqrt{s_{u}\sigma_{\max}(L)}\Big{)}\\\
&+\frac{Mn_{c}}{n}\|\Delta\|^{2}_{F}\left(\widetilde{C}\left(1+\rho(\Gamma)^{2}\log
p\right)+\widetilde{C}^{\prime}\rho(\Gamma)^{2}\frac{s_{u}\log
p\cdot\sigma_{\max}(L)}{n_{c}}\right)\\\ \end{split}$ (123)

Assuming that $n$ is such that:

$n\geq 128M^{2}n_{c}\left(\widetilde{C}\left(1+\rho(\Gamma)^{2}\log
p\right)+\widetilde{C}^{\prime}\rho(\Gamma)^{2}\frac{s_{u}\log
p\cdot\sigma_{\max}(L)}{n_{c}}\right)$

we get

$\begin{split}\|\Delta\|_{F}&\leq
128C^{\prime}M^{3}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+192\rho
M\sqrt{s_{u}\sigma_{\max}(L)}\\\ &\leq
128C^{\prime}M^{3}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+768M^{3}\cdot
C_{3}^{\prime}\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{s_{u}\frac{q+\log
m}{n}}\\\
&\leq\widetilde{C}M^{3}\left(\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{s_{u}\frac{q+\log
m}{n}}\right)\end{split}$ (124)

Consequently, Equation (117) summarises to

$\begin{split}\frac{1}{n}\|X\Delta\|_{F}^{2}\leq~{}&\widetilde{C}M^{3}\left(\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{s_{u}\frac{q+\log
m}{n}}\right)\\\
&\cdot\left(C^{\prime}M^{2}\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\frac{12CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{q+\log
m}{n}}}{2}\sqrt{s_{u}\sigma_{\max}(L)}\right)\\\ &\leq
CM^{5}\left(\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\sqrt{\left(1+\frac{1}{\kappa_{2}}\right)^{2}\sigma_{\max}(L)\cdot{s_{u}\frac{q+\log
m}{n}}}\right)^{2}\\\ &\leq
CM^{5}\left({n_{c}\frac{q+\log(n_{c})}{n}}+{\left(1+\frac{1}{\kappa_{2}}\right)^{2}\sigma_{\max}(L)\cdot{s_{u}\frac{q+\log
m}{n}}}\right)\\\ \end{split}$ (125)

where we adjusted the constant $C$ from line to line to represent the maximum
of the constants on the previous line. We conclude the proof by characterizing
the probability of the event

$\mathcal{G}=\mathcal{A}_{Y}^{c}\cap\mathcal{A}_{X\Pi
Y}^{c}\cap\mathcal{A}_{X\Gamma^{\dagger},W}^{c}\cap\mathcal{A}_{X\Gamma^{\dagger},Y}^{c}\cap\mathcal{A}_{\kappa}$

as follows

$\begin{split}&\mathbb{P}[\mathcal{G}]=1-\mathbb{P}[\mathcal{A}_{Y}\cup\mathcal{A}_{X\Pi
Y}\cup\mathcal{A}_{X\Gamma^{\dagger},W}\cup\mathcal{A}_{X\Gamma^{\dagger},Y}\cup\mathcal{A}_{\kappa}^{c}]\\\
&\geq 1-\mathbb{P}[\mathcal{A}_{Y}]-\mathbb{P}[\mathcal{A}_{X\Pi
Y}]-\mathbb{P}[\mathcal{A}_{X\Gamma^{\dagger},W}]-\mathbb{P}[\mathcal{A}_{X\Gamma^{\dagger},Y}]-\mathbb{P}[\mathcal{A}_{\kappa}^{c}]\\\
&\geq 1-\exp\\{-Cq\\}-2\exp\\{-C(q+\log m)\\}-\exp\\{-C(q+\log
n_{c})\\}-q\exp\\{-c_{2}n\\}\\\ &\geq 1-4\exp\\{-C(q+\log
n_{c})\\}-q\exp\\{-c_{2}n\\}\end{split}$ (126)

∎

###  E.3 Proof of Theorem 6

######  Theorem.

Consider the family $\mathcal{F}_{\mathcal{G}}(s_{u},p,m,q,r,\lambda,M)$ of
covariance matrices satisfying assumptions. We assume as well that $n$ is
large enough so that:

$n\geq 10\vee 128M^{2}\Big{(}72n_{c}+576\rho(\Gamma)^{2}\log
p\big{(}96C^{\prime}\sqrt{n_{c}}+4\sqrt{s_{u}}\big{)}^{2}\Big{)},$

and such that:

$M\frac{{q}+s_{u}\log\big{(}\frac{ep}{s_{u}}\big{)}}{n}\leq c_{0}\qquad\text{
and }\qquad M\frac{\log n_{c}+q}{n}\leq c_{0}$ ($\mathcal{H}_{1,\mathcal{G}}$)

Then, there exists orthogonal matrices $O\in\mathbb{R}^{r\times r}$ and
$\tilde{O}\in\mathbb{R}^{r\times r}$ such that the canonical directions
$\widehat{U}$ and $\widehat{V}$ estimated using Algorithm B.3 have errors
bounded by:

$\begin{split}\big{\|}\widehat{V}-VO\big{\|}_{F}&\leq
CM^{\frac{11}{2}}\frac{\sqrt{r}}{\lambda}\left(\sqrt{{n_{c}\frac{q+\log(n_{c})}{n}}}+\left(1+\frac{1}{\kappa_{2}}\right){\sqrt{\sigma_{\max}(L)}}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right)\\\ \|\widehat{U}-U\widetilde{O}\|_{F}&\leq
CM^{6}\frac{{r}}{\lambda^{4}}\cdot\left(\sqrt{n_{c}{\frac{q+\log(n_{c})}{n}}}+\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\sigma_{\max}(L)}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right).\\\ \end{split}$

with probability at least

$1-4\exp\\{-C^{\prime}(q+\log n_{c})\\}-q\exp\\{-c_{2}n\\}.$

Here $C$ is a constant that depends solely on $C^{\prime}$ and $c_{0}$, and
$c_{2}$ is a universal constant that does not depend on the dimensions.

Proof The proof is very similar to that of Theorem 4. Note that, in that
proof, the errors depended on getting an adequate bound for the term:

$\begin{split}&\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}\leq\left\|\Delta^{\top}\widehat{\Sigma}_{X}\widehat{B}\right\|_{F}+\left\|{B^{*}}^{\top}\widehat{\Sigma}_{X}\Delta\right\|_{F}+\left\|{B^{*}}^{\top}(\widehat{\Sigma}_{X}-\Sigma_{X})B^{*}\right\|_{F}\\\
&\leq\left\|\widehat{\Sigma}_{X}^{\frac{1}{2}}\Delta\right\|_{F}~{}\Big{(}\left\|\widehat{\Sigma}_{X}^{\frac{1}{2}}\Delta\right\|_{F}+2\underbrace{\left\|\widehat{\Sigma}_{X}^{\frac{1}{2}}B^{*}\right\|_{F}}_{(A)}\Big{)}+\underbrace{\left\|{B^{*}}^{\top}\big{[}\widehat{\Sigma}_{X}-\Sigma_{X}\big{]}_{TT}B^{*}\right\|_{F}}_{(B)}.\\\
\end{split}$ (127)

We thus simply need to bound the terms (A) and (B).

#### Bound (A).

Denote $\widehat{\Sigma}_{X\Pi}=\Pi\widehat{\Sigma}_{X}\Pi$ and
$\Sigma_{X\Pi}=\Pi\Sigma_{X}\Pi$. Let $\mathcal{A}_{X\Pi}$ be the event:

$\mathcal{A}_{X\Pi}=\left\\{\left\|\widehat{\Sigma}_{X\Pi}-\Sigma_{X\Pi}\right\|_{op}^{2}>CM^{2}\frac{n_{c}}{n}\right\\}.$

Here $C$ was chosen so that, by arguments identical to that of Lemma 13, we
know that

$\mathbb{P}[\mathcal{A}_{X\Pi}]\leq\exp\\{-C^{\prime}n_{c}\\}$

for $C^{\prime}>0$. Similarly, denote
$\widehat{\Sigma}_{X\Gamma^{\dagger}}=(\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{X}\Gamma^{\dagger}$
and
${\Sigma_{X\Gamma^{\dagger}}=(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}}$.
Let $\mathcal{A}_{X\Gamma^{\dagger}}$ be the event:

$\mathcal{A}_{X\Gamma^{\dagger}}=\left\\{\left\|\left[\widehat{\Sigma}_{X\Gamma^{\dagger}}\right]_{SS}-\left[\Sigma_{X\Gamma^{\dagger}}\right]_{SS}\right\|_{op}^{2}>CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)^{2}\frac{s_{u}}{n}\right\\}.$

Here $C$ was chosen so that, by arguments similar to that of Lemma 11, we know
that

$\mathbb{P}[\mathcal{A}_{X\Gamma^{\dagger}}]\leq\exp\\{-C^{\prime}s_{u}\\}$

for $C^{\prime}>0$. Finally, we let $\mathcal{A}_{X\Gamma^{\dagger},X\Pi}$ be
the event:

$\mathcal{A}_{X\Gamma^{\dagger},X\Pi}=\left\\{\left\|\left[\widehat{\Sigma}_{X\Gamma^{\dagger},X\Pi}\right]_{SS}-\left[\Sigma_{X\Gamma^{\dagger},X\Pi}\right]_{SS}\right\|_{op}^{2}>CM^{2}\left(1+\frac{1}{\kappa_{2}}\right)^{2}\frac{\log
m+q}{n}\right\\}.$

Here $C$ was chosen so that, by arguments similar to that of Lemma 14,

$\mathbb{P}[\mathcal{A}_{X\Gamma^{\dagger},X\Pi}]\leq\exp\\{-C^{\prime}(\log
m+q)\\}.$

Therefore, on $\mathcal{A}_{X\Gamma^{\dagger}}^{c}\cap\mathcal{A}_{X\Pi}^{c}$,
we have:

$\begin{split}\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}(B^{*})\right\|_{F}&\leq\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}(\Pi
B^{*})\right\|_{F}+\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}(\Gamma^{\dagger})(\Gamma
B^{*})\right\|_{F}\\\ &=\mathop{\sf Tr}\Big{(}(\Pi
B^{*})^{\top}\Pi\Sigma_{X}\Pi(\Pi B^{*})\Big{)}^{\frac{1}{2}}+\mathop{\sf
Tr}\Big{(}(\Gamma
B^{*})^{\top}(\Gamma^{\dagger})^{\top}\Sigma^{\frac{1}{2}}_{X}\Gamma^{\dagger}(\Gamma
B^{*})\Big{)}^{\frac{1}{2}}\\\
&\leq\|B^{*}\|_{F}\cdot\bigg{[}\max_{j\in[c]}\frac{\mathbf{1}_{C_{j}}^{\top}}{|C_{j}|}\widehat{\Sigma}_{X}\frac{\mathbf{1}_{C_{j}}}{|C_{j}|}\bigg{]}^{\frac{1}{2}}+\left\|[\Gamma
B^{*}]_{S\cdot}\right\|_{F}~{}\left\|\left[(\Gamma^{\dagger})^{\top}\widehat{\Sigma}_{X}\Gamma^{\dagger}\right]_{SS}\right\|_{op}^{\frac{1}{2}}\\\
&\leq\|B^{*}\|_{F}\cdot\left(\left\|\Pi\Sigma_{X}\Pi\right\|_{op}+M\sqrt{C\frac{n_{c}}{n}}\right)^{\frac{1}{2}}\\\
&+\left\|[\Gamma
B^{*}]_{S\cdot}\right\|_{F}\left(\left\|\left[(\Gamma^{\dagger})^{\top}\Sigma_{X}\Gamma^{\dagger}\right]_{SS}\right\|_{op}+M\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\frac{Cs_{u}}{n}}\right)^{\frac{1}{2}}\\\
&\leq\tilde{C}M\sqrt{r}\lambda_{1}+C\sqrt{\sigma_{\max}(L)\cdot
Mr}\lambda_{1}\left(\frac{M}{\kappa_{2}}+M\left(1+\frac{1}{\kappa_{2}}\right)\right)^{\frac{1}{2}}\\\
&\leq\tilde{C}M\sqrt{r}\lambda_{1}\left(1+\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)^{\frac{1}{2}}\right)\\\
\\\ \end{split}$ (128)

where $\tilde{C}$ is a constant that does not depend on the dimensions and is
readjusted from line to line to denote the maximum of the constants of the
previous line. In the penultimate line, we have used the assumption
$\mathcal{H}_{1,\mathcal{G}}$ to bound $\sqrt{\frac{n_{c}}{n}}$ and
$\sqrt{\frac{s_{u}}{n}}$, and the fact that $\|\Gamma
B^{*}\|_{F}\leq\sqrt{\sigma_{\max}(L)}\|B^{*}\|_{F}.$

#### Bound (B).

On
$\mathcal{A}_{X\Pi}^{c}\cap\mathcal{A}_{X\Gamma^{\dagger}}^{c}\cap\mathcal{A}_{X\Gamma^{\dagger},X\Pi}^{c}$
we have:

$\begin{split}\left\|{B^{*}}^{\top}(\Sigma_{X}-\widehat{\Sigma}_{X})B^{*}\right\|_{F}&\leq\left\|{B^{*}}^{\top}\Pi(\Sigma_{X}-\widehat{\Sigma}_{X})\Pi
B^{*}\right\|_{F}\\\ &+\left\|(\Gamma
B^{*})^{\top}(\Gamma^{\dagger})^{\top}(\Sigma_{X}-\widehat{\Sigma}_{X})\Gamma^{\dagger}\Gamma
B^{*}\right\|_{F}\\\
&+2\left\|{B^{*}}^{\top}(\Pi\Sigma_{X}-\widehat{\Sigma}_{X})\Gamma^{\dagger}\Gamma
B^{*}\right\|_{F}\\\ &\leq\|\Pi
B^{*}\|^{2}_{F}\left\|\Pi(\Sigma_{X}-\widehat{\Sigma}_{X})\Pi\right\|_{op}\\\
&+\left\|\left[(\Gamma^{\dagger})^{\top}(\Sigma_{X}-\widehat{\Sigma}_{X})\Gamma^{\dagger}\right]_{SS}\right\|_{op}\left\|[\Gamma
B^{*}]_{S\cdot}\right\|_{F}^{2}\\\
&+2\left\|\left[\Pi(\Sigma_{X}-\widehat{\Sigma}_{X})\Gamma^{\dagger}\right]_{\cdot
S}\right\|_{op}\|\Pi B^{*}\|_{F}~{}\|[\Gamma B^{*}]_{S\cdot}\|_{F}\\\
&\leq\|B^{*}\|^{2}_{F}\sqrt{M^{2}C\frac{n_{c}}{n}}+\sqrt{C\frac{M^{2}}{\kappa_{2}^{2}}\cdot\frac{s_{u}}{n}}{\sigma_{\max}(L)}~{}\|B^{*}\|^{2}_{F}\\\
&+2\sqrt{\sigma_{\max}(L)}\cdot\sqrt{M\left(1+\frac{1}{\kappa_{2}}\right)\cdot\frac{s_{u}+n_{c}}{n}}~{}\|B^{*}\|^{2}_{F}\\\
&\leq
CM^{2}\lambda_{1}^{2}r\left(1+\left(1+\frac{1}{\kappa_{2}}\right)\sigma_{\max}(L)\right)\sqrt{\frac{n_{c}+s_{u}}{n}}\end{split}$
(129)

Therefore

$\begin{split}&\Big{\|}\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\Big{\|}_{F}\\\
&\leq\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}(\widehat{B}-B^{*})\right\|^{2}_{F}+2\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}(\widehat{B}-B^{*})\right\|_{F}~{}\left\|\widehat{\Sigma}^{\frac{1}{2}}_{X}(B^{*})\right\|_{F}+\left\|{B^{*}}^{\top}(\Sigma_{X}-\widehat{\Sigma}_{X})B^{*}\right\|_{F}\\\
&\leq
CM^{5}\left({{n_{c}\frac{q+\log(n_{c})}{n}}}+{\left(1+\frac{1}{\kappa_{2}}\right)^{2}\sigma_{\max}(L)\cdot{s_{u}\frac{q+\log
m}{n}}}\right)\\\
&+2\sqrt{CM^{5}\left(n_{c}\frac{q+\log(n_{c})}{n}+{\left(1+\frac{1}{\kappa_{2}}\right)^{2}\sigma_{\max}(L)\cdot{s_{u}\frac{q+\log
m}{n}}}\right)}\\\
&\cdot\tilde{C}M\sqrt{r}\lambda_{1}\left(1+\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)^{\frac{1}{2}}\right)\\\
&+CM^{2}\lambda_{1}^{2}r\left(1+\left(1+\frac{1}{\kappa_{2}}\right)\sigma_{\max}(L)\right)\sqrt{\frac{n_{c}+s_{u}}{n}}\end{split}$
(130)

implying that

$\begin{split}&\Big{\|}\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\Big{\|}_{F}\\\
&\leq
CM^{5}\left(\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\sigma_{\max}(L)}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right)\\\
&\cdot\left[\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\sigma_{\max}(L)}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}+\left(\sqrt{\sigma_{\max}(L)}\left(1+\frac{1}{\kappa_{2}}\right)+1\right)\sqrt{r}\right]\\\
&\leq
CM^{5}\sqrt{r}\left(\sqrt{n_{c}\frac{q+\log(n_{c})}{n}}+\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\sigma_{\max}(L)}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right)\end{split}$ (131)

where we readjust the constant $C$ appropriately from line to line by taking
it to be the maximunm of the constants of the previous line, and use the fact
that by assumptions $\mathcal{H}_{1,\mathcal{G},\Pi}$ and
$\mathcal{H}_{1,\mathcal{G}}$, $n_{c}\frac{q+\log(n_{c})}{n}\vee
s_{u}\frac{q+\log(m)}{n}\leq c_{0}$ is small.

#### Bounding $\|\widehat{V}-VO\|$.

Let $\mathcal{O}_{r,r}=\\{O\in\mathbb{R}^{r\times r}:~{}O^{\top}O=I_{r}\\}$
and let

$\delta_{n}=\sqrt{{n_{c}\frac{q+\log(n_{c})}{n}}}+\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\sigma_{\max}(L)}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}.$

We use the same arguments as for the proof of Theorem 4. We have:

$\begin{split}\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{V}-VO\right\|_{F}&=\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\widehat{V}_{0}-\Sigma_{Y}^{-\frac{1}{2}}{V}_{0}O\right\|_{F}\\\
&\leq\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}(\widehat{V}_{0}-{V}_{0}O)\right\|_{F}+\left\|\big{(}\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\big{)}{V}_{0}\right\|_{F}\\\
&\leq\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}\right\|_{op}~{}\left\|\widehat{V}_{0}-{V}_{0}O\right\|_{F}+\left\|\widehat{\Sigma}_{Y}^{-\frac{1}{2}}-\Sigma_{Y}^{-\frac{1}{2}}\right\|_{op}\sqrt{r}\\\
&\leq
C_{1}\sqrt{M}\min_{O\in\mathcal{O}_{r,r}}\left\|\widehat{V}_{0}-{V}_{0}O\right\|_{F}+\sqrt{C\frac{qr}{n}}\cdot
2M\\\ &\leq\tilde{C}\frac{\sqrt{M}}{\lambda}\cdot
C^{\prime}M^{5}\delta_{n}\cdot\sqrt{r}+\sqrt{C\frac{qr}{n}}\cdot 2M\\\
&\leq\widetilde{C}M^{\frac{11}{2}}\sqrt{r}\left(\sqrt{{n_{c}\frac{q+\log(n_{c})}{n\lambda^{2}}}}+\left(1+\frac{1}{\kappa_{2}}\right)\frac{\sqrt{\sigma_{\max}(L)}}{\lambda}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}+\sqrt{\frac{q}{n}}\right)\\\
&\leq\widetilde{C}M^{\frac{11}{2}}\frac{\sqrt{r}}{\lambda}\left(\sqrt{{n_{c}\frac{q+\log(n_{c})}{n}}}+\left(1+\frac{1}{\kappa_{2}}\right){\sqrt{\sigma_{\max}(L)}}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right)\\\ \end{split}$ (132)

where we readjust the constant $\tilde{C}$ from line to line.

#### Bounding $\|\widehat{U}-U\widetilde{O}\|$.

By similarity with the proof of the sparse case, the error in $U$ is thus
bounded by:

$\begin{split}\|\widehat{U}-U\widetilde{O}\|_{F}\leq\Big{(}\|\widehat{B}-B^{*}\|_{F}&+\|B^{*}\|_{op}~{}\|\widehat{V}-VO\|_{F}\\\
+&\|B^{*}V_{0}\|_{F}~{}\|\Lambda^{-1}\|_{op}~{}\|O^{\top}\Lambda
O-\widehat{\Lambda}\|_{op}\Big{)}\|\widehat{\Lambda}^{-1}\|_{op}\end{split}$
(133)

Let
$\delta_{n}=\left(\sqrt{{n_{c}\frac{q+\log(n_{c})}{n}}}+\left(1+\frac{1}{\kappa_{2}}\right){\sqrt{\sigma_{\max}(L)}}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right)$. On the event $\mathcal{G}$ we then have

$\begin{split}\left\|O\Lambda
O^{\top}-\widehat{\Lambda}\right\|_{op}&\leq\frac{\|O\Lambda^{2}O^{\top}-\widehat{\Lambda}^{2}\|_{op}}{\sqrt{\sigma\big{(}O\Lambda^{2}O^{\top}\big{)}}+\sqrt{\sigma\big{(}\widehat{\Lambda}^{2}\big{)}}}\\\
&\leq\frac{\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}+\frac{4\sqrt{2}}{\lambda_{r}}\left\|\widehat{B}^{\top}\widehat{\Sigma}_{X}\widehat{B}-{B^{*}}^{\top}\Sigma_{X}B^{*}\right\|_{F}\left\|\widehat{\Lambda}^{2}\right\|_{op}}{\sqrt{\sigma\big{(}O\Lambda^{2}O^{\top}\big{)}}+\sqrt{\sigma\big{(}\widehat{\Lambda}^{2}\big{)}}}\\\
&\leq\frac{CM^{5}{\sqrt{r}}\delta_{n}+\frac{4\sqrt{2}}{\lambda_{r}}CM^{5}\delta_{n}{\sqrt{r}}\left\|\widehat{\Lambda}^{2}\right\|_{op}}{\sqrt{-CM^{5}\delta_{n}+\lambda_{r}^{2}}+\sqrt{\lambda_{r}^{2}}}\\\
&\leq\frac{2CM^{5}{\sqrt{r}}\delta_{n}}{3\lambda}\left({1+\frac{4\sqrt{2}}{\lambda_{r}}\left(\lambda_{1}^{2}+CM^{5}{\sqrt{r}}\delta_{n}\right)}\right)\text{
assuming }C{\sqrt{r}}M^{5}\delta_{n}\leq\frac{1}{2}\lambda^{2}\\\ &\leq
C\frac{\delta_{n}{\sqrt{r}}M^{5}}{\lambda^{2}}\left({\lambda+{4\sqrt{2}}\left(\lambda_{1}^{2}+\frac{1}{2}\lambda^{2}\right)}\right)\leq
CM^{5}{\sqrt{r}}\frac{\delta_{n}}{\lambda^{2}}\end{split}$ (134)

by appropriately readjusting the constant $C$. Therefore Equation (133)
becomes:

$\begin{split}\|\widehat{U}-U\widetilde{O}\|_{F}&\leq\left(\|\widehat{B}-B^{*}\|_{F}+M^{\frac{1}{2}}\lambda_{1}~{}\frac{CM^{\frac{11}{2}}{\sqrt{r}}\delta_{n}}{\lambda}+M^{\frac{1}{2}}\lambda_{1}\sqrt{r}\frac{1}{\lambda}CM^{5}\frac{\delta_{n}{\sqrt{r}}}{\lambda^{2}}\right)\\\
&\cdot\left(\|\Lambda^{-1}\|_{op}+\|\widehat{\Lambda}^{-1}-\Lambda^{-1}\|_{op}\right)\\\
&\leq\delta_{n}\left(\widetilde{C}M^{3}+CM^{6}\lambda_{1}~{}\frac{2{r}}{\lambda^{3}}\right)\cdot
2\frac{1}{\lambda}\leq\widetilde{C}\delta_{n}M^{6}\frac{{r}}{\lambda^{4}}\\\
&\leq
CM^{6}\frac{{r}}{\lambda^{4}}\cdot\left(\sqrt{n_{c}{\frac{q+\log(n_{c})}{n}}}+\left(1+\frac{1}{\kappa_{2}}\right)\sqrt{\sigma_{\max}(L)}\cdot\sqrt{{s_{u}\frac{q+\log
m}{n}}}\right).\\\ \end{split}$ (135)

∎