2\exp(-\epsilon^{2}\lfloor n/3\rfloor/(2M^{2}))$

since $\widetilde{T}_{n,12,1}$ is a third order $U$-statistic. Also we note
that by the same argument used in bounding $h_{1}$, we can get

$|h_{3}|\leq\frac{1}{12}\\{V_{k1}^{4}+V_{l1}^{4}+V_{h1}^{4}+V_{k2}^{4}+V_{l2}^{4}+V_{h2}^{4}+8|\mathbf{U}_{h\cdot}|_{q}^{2}+8|\mathbf{U}_{k\cdot}|_{q}^{2}+8|\mathbf{U}_{l\cdot}|_{q}^{2}\\}.$

It follows from Cauchy-Schwartz inequality that $|T_{12,2}|\leq
E^{1/2}(h_{3}^{2})P^{1/2}(|h_{3}|>M)$. By using exactly the same argument used
for (S3), we can show that $P(|h_{3}|>M)\leq C\exp(-C_{3}M^{2/3})$ for some
$C_{3}=C_{3}(\sigma_{0},C_{0},q)>0$. Hence $|T_{12,2}|\leq
C\exp(-C_{3}M^{2/3})$. We can choose $\epsilon>0$ such that
$C\exp(-C_{3}M^{2/3})\leq\epsilon/2$. Therefore, for $\epsilon\geq
2C\exp(-C_{3}M^{2/3})$, we have
$P(|\widetilde{T}_{n,12,2}-T_{12,2}|>\epsilon)\leq
P(|\widetilde{T}_{n,12,2}|\geq\epsilon/2)$. By setting $M=\log^{3/2}(n)$ and
adopting the same argument as used in bounding
$P(|\widetilde{R}_{n,12,2}|\geq\epsilon/2)$, we can derive that
$P(|\widetilde{T}_{n,12,2}|\geq\epsilon/2)\leq 12\exp(-C_{4}n\epsilon^{2})$
when $n\geq n_{1}$ and $\epsilon\in(D_{1}n^{-\gamma_{1}},16)$ for some
$C_{4}=C_{4}(\sigma_{0},C_{0},q)>0$, $D_{1}=D_{1}(\sigma_{0},C_{0},q)$,
$n_{1}=n_{1}(\sigma_{0},C_{0},q)$ and
$\gamma_{1}=\gamma_{1}(\sigma_{0},C_{0},q)$.

Combining the above results, we obtain that for
$16>\epsilon>D_{1}n^{-\gamma_{1}}$ and $n\geq n_{1}$, we have

$\displaystyle P(|\widetilde{T}_{n,12}-T_{12}|\geq 2\epsilon)$
$\displaystyle\leq$ $\displaystyle
12\exp(-C_{4}n\epsilon^{2})+2\exp(-\epsilon^{2}\lfloor n/3\rfloor/(2M^{2}))$
$\displaystyle\leq$ $\displaystyle 14\exp(-\epsilon^{2}n/(6\log^{3}(n))),$

where we choose $n_{1}$ such that $6\log^{3}(n_{1})>C_{4}^{-1}$.

Further we note that

$T_{n,12}-T_{12}=\frac{(n-1)(n-2)}{n^{2}}(\widetilde{T}_{n,12}-T_{12})-\frac{3n-2}{n^{2}}T_{12}+\frac{n-1}{n^{2}}(\widetilde{R}_{n,12}-R_{12})+\frac{n-1}{n^{2}}R_{12}.$

There exists a finite positive constant $C_{6}=C_{6}(\sigma_{0},C_{0},q)$ such
that $|R_{12}|\leq C_{6}$ and $|T_{12}|\leq C_{6}$ so if we choose
$\epsilon\geq 3C_{6}/n$, then $|\frac{3n-2}{n^{2}}T_{12}|\leq\epsilon$ and
$|\frac{n-1}{n^{2}}R_{12}|\leq\epsilon/3$. Then for $n\geq n_{1}$ and
$\epsilon>D_{1}n^{-\gamma_{1}}$,

$\displaystyle P(|T_{n,12}-T_{12}|>4\epsilon)$ $\displaystyle\leq$
$\displaystyle
P(|\widetilde{T}_{n,12}-T_{12}|>2\epsilon)+P(|\widetilde{R}_{n,12}-R_{12}|>2\epsilon/3)$
$\displaystyle\leq$ $\displaystyle
14\exp(-\epsilon^{2}n/(6\log^{3}(n)))+10\exp\left\\{-\frac{\epsilon^{2}n}{36\log^{3}(n)}\right\\}$
$\displaystyle\leq$ $\displaystyle
24\exp\left\\{-\frac{\epsilon^{2}n}{36\log^{3}(n)}\right\\}$

Thus the conclusion follows from the above inequality and Proposition S3.

∎

##  S6 Proofs for Theorems 2 & 3

###  S6.1 Two Generic Algorithms and Their Properties

We first describe two generic algorithms and their properties that will help
our proof for Theorems 2 & 3. Consider two matrices
$\mathbf{A},\mathbf{B}\in\mathbb{R}^{p\times p}$, their estimates
$\widehat{\mathbf{A}},\widehat{\mathbf{B}}\in\mathbb{R}^{p\times p}$ and
vectors $\mathbf{v},\mathbf{v}_{0},\mathbf{v}_{t}\in\mathbb{R}^{p}$. We have
Algorithm 3 for the penalized eigen-decomposition for $\mathbf{A}$, and
Algorithm 4 for the penalized generalized eigen-decomposition for
$(\mathbf{A},\mathbf{B})$. Algorithm 3 is originally proposed in Yuan and
Zhang (2013), and in our Algorithm 1 we use it repeatedly for $K$ times to
perform penalized eigen-decomposition for MDDM. Algorithm 4 is originally
proposed as the RIFLE Algorithm in Tan, Wang, Liu and Zhang (2018), and we use
it for $K$ times to perform penalized generalized eigen-decomposition for
MDDM.

  1. 1.

Input: $s,\widehat{\mathbf{A}}$.

  2. 2.

Initialize $\mathbf{v}_{0}$.

    1. (a)

Iterate over $t$ until convergence:

    2. (b)

Set $\mathbf{v}_{t}=\widehat{\mathbf{A}}\mathbf{v}_{t-1}$.

    3. (c)

If $\|\mathbf{v}_{t}\|_{0}\leq s$, set

$\mathbf{v}_{t}=\dfrac{\mathbf{v}_{t}}{\|\mathbf{v}_{t}\|_{2}};$

else

$\mathbf{v}_{t}=\dfrac{\mathrm{HT}(\mathbf{v}_{t},s)}{\|\mathrm{HT}(\mathbf{v}_{t},s)\|_{2}}$

  3. 3.

Output $\mathbf{v}_{\infty}$ at convergence.

Algorithm 3 A generic penalized eigen-decomposition algorithm.

Yuan and Zhang (2013) proved a property for Algorithm 3 that is important for
our proof. Assume that $\mathbf{A}$ has a unique leading eigenvector
$\mathbf{v}^{*}_{\mathbf{I}}$ with $\|\mathbf{v}^{*}_{\mathbf{I}}\|_{0}\leq
d$. Denote $\lambda_{1}^{\mathbf{I}},\ldots,\lambda^{\mathbf{I}}_{p}$ as the
eigenvalues. We assume that there exists a constant
$\Delta_{\mathbf{I}}=\lambda_{1}^{\mathbf{I}}-\max_{j>1}\lambda_{j}^{\mathbf{I}}$.
Also for any positive integer $k^{\prime}$, define

$\rho(\mathbf{E}_{\mathbf{A}},k^{\prime})=\sup_{\|\mathbf{u}\|_{2}=1,\|\mathbf{u}\|_{0}\leq
k^{\prime}}|\mathbf{u}^{\mathrm{\tiny T}}\mathbf{E}_{\mathbf{A}}\mathbf{u}|,$

where $\mathbf{E}_{\mathbf{A}}=\widehat{\mathbf{A}}-\mathbf{A}$, with
$\widehat{\mathbf{A}}$ being an estimate of $\mathbf{A}$. We have the
following proposition.

######  Proposition S4 ((Yuan and Zhang 2013) c.f Theorem 4).

In Algorithm 3, let $s=d+2s^{\prime}$ with $s^{\prime}\geq d$. Assume that
$\rho(\mathbf{E}_{\mathbf{A}},s)\leq\Delta_{\mathbf{I}}$. Define

$\gamma(s)=\dfrac{\lambda_{1}^{\mathbf{I}}-\Delta_{\mathbf{I}}+\rho(\mathbf{E}_{\mathbf{A}},s)}{\lambda_{1}^{\mathbf{I}}-\rho(\mathbf{E}_{\mathbf{A}},s)}<1,\quad\delta_{\mathbf{I}}(s)=\dfrac{\sqrt{2}\rho(\mathbf{E}_{\mathbf{A}},s)}{\sqrt{\rho(\mathbf{E}_{\mathbf{A}},s)^{2}+(\Delta_{\mathbf{I}}-2\rho(\mathbf{E}_{\mathbf{A}},s))^{2}}}.$

If $|\mathbf{v}_{0}^{\mathrm{\tiny
T}}\mathbf{v}^{*}_{\mathbf{I}}|\geq\theta+\delta_{\mathbf{I}}(s)$ for some
$\|\mathbf{v}_{0}\|_{0}\leq s^{\prime},\|\mathbf{v}_{0}\|=1,$ and
$\theta\in(0,1)$ such that

$\mu=\sqrt{[1+2\\{(\frac{d}{s^{\prime}})^{1/2}+\frac{d}{s^{\prime}}\\}]\\{1-0.5\theta(1+\theta)(1-\gamma(s)^{2})\\}}<1,$

then we either have

$\sqrt{1-|\mathbf{v}_{0}^{\mathrm{\tiny
T}}\mathbf{v}^{*}_{\mathbf{I}}|}<\sqrt{10}\delta_{\mathbf{I}}(s)/(1-\mu),$

or for all $t\geq 0$,

$\sqrt{1-|\mathbf{v}_{t}^{\mathrm{\tiny
T}}\mathbf{v}^{*}_{\mathbf{I}}|}\leq\mu^{t}\sqrt{1-|\mathbf{v}_{0}^{\mathrm{\tiny
T}}\mathbf{v}^{*}_{\mathbf{I}}|}+\sqrt{10}\delta_{\mathbf{I}}(s)/(1-\mu).$

  1. 1.

Input: $s,\widehat{\mathbf{A}},\widehat{\mathbf{B}}$ and step size $\eta>0$.

  2. 2.

Initialize $\mathbf{v}_{0}$.

  3. 3.

Iterate over $t$ until convergence:

    1. (a)

Set $\rho^{(t-1)}=\dfrac{\mathbf{v}_{t}^{\mathrm{\tiny
T}}\widehat{\mathbf{A}}\mathbf{v}_{t}}{\mathbf{v}_{t}^{\mathrm{\tiny
T}}\widehat{\mathbf{B}}\mathbf{v}_{t}}$.

    2. (b)

$\mathbf{C}=\mathbf{I}+(\eta/\rho^{(t-1)})\cdot(\widehat{\mathbf{A}}-\rho^{(t-1)}\widehat{\mathbf{B}})$.

    3. (c)

$\mathbf{v}_{t}=\mathbf{C}\mathbf{v}_{t-1}/\|\mathbf{C}\mathbf{v}_{t-1}\|_{2}$.

    4. (d)

$\mathbf{v}_{t}=\dfrac{\mathrm{HT}(\mathbf{v}_{t},s)}{\|\mathrm{HT}(\mathbf{v}_{t},s)\|_{2}}$.

  4. 4.

Output $\mathbf{v}_{\infty}$ at convergence.

Algorithm 4 A generic penalized generalized eigen-decomposition algorithm.

Based on the results in Tan, Wang, Liu and Zhang (2018), we can also derive
the following useful results for Algorithm 4. We assume that the matrix pair
$(\mathbf{A},\mathbf{B})$ has the leading generalized eigenvector
$\mathbf{v}^{*}$ such that $\|\mathbf{v}^{*}\|_{0}\leq d$. The generalized
eigenvalues of $(\mathbf{A},\mathbf{B})$ are referred to as
$\lambda_{j},j=1,\ldots,p$ and their estimates are
$\widehat{\lambda}_{j},j=1,\ldots,p$. We introduce the following notation:

$\displaystyle\text{cr}(\mathbf{A},\mathbf{B})$ $\displaystyle=$
$\displaystyle\min_{\mathbf{v}:\|\mathbf{v}\|_{2}=1}\\{(\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{v})^{2}+(\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{v})^{2}\\}^{1/2}>0$ (S6)
$\displaystyle\text{cr}(k^{\prime})$ $\displaystyle=$
$\displaystyle\inf_{F:|F|\leq
k^{\prime}}\text{cr}(\mathbf{A}_{F},\mathbf{B}_{F}),$ (S7)
$\displaystyle\delta(k^{\prime})$ $\displaystyle=$
$\displaystyle\sqrt{\rho(\mathbf{E}_{\mathbf{A}},k^{\prime})^{2}+\rho(\mathbf{E}_{\mathbf{B}},k^{\prime})^{2}},$
(S8)

where $\mathbf{E}_{\mathbf{B}}=\mathbf{B}-\widehat{\mathbf{B}}$, with
$\widehat{\mathbf{B}}$ being an estimate of $\mathbf{B}$. Also denote
$\kappa(\mathbf{B})$ as the condition number of $\mathbf{B}$ and
$\omega_{1}(F)=\sup_{\|\mathbf{u}\|_{0}\subset
F,\|\mathbf{u}\|_{2}=1}\frac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}}{\mathbf{u}^{\mathrm{\tiny T}}\mathbf{B}\mathbf{u}}$
for any index set $F$. We consider the following assumption:

######  Assumption S1.

For sufficiently large $n$, there are constants $b,c>0$, such that
$\dfrac{\delta(s)}{cr(s)}\leq b$ and $\rho(\mathbf{E}_{\mathbf{B}},s)\leq
c\lambda_{\min}(\mathbf{B})$ for any $s=o(n)$.

We also denote $c_{\text{upper}}=\dfrac{1+c}{1-c}$ for $c$ defined in
Assumption S1. We estimate $\mathbf{v}^{*}$ with the RIFLE algorithm with the
step size $\eta$. We choose $\eta$ such that
$\eta\lambda_{\max}(\mathbf{B})<1/(1+c)$. Further, in the RIFLE algorithm, let
$s=2s^{\prime}+d$ and choose $s^{\prime}=Cd$ for sufficiently large $C$. The
initial value $\mathbf{v}_{0}$ satisfies that $\|\mathbf{v}_{0}\|_{2}=1$.

######  Proposition S5 (Based on Theorem 1 and Corollary 1 in Tan, Wang, Liu
and Zhang (2018)).

Under Assumption S1, we have the following conclusions:

  1. 1.

For any $F$ such that $\mathrm{supp}(\mathbf{v}_{0})\subset F$, there exists a
constant $a$ such that

$(1-a)\omega_{1}(F)\leq\hat{\omega}_{1}(F)\leq(1+a)\omega_{1}(F).$ (S9)

  2. 2.

Choose $\eta$ such that

$\nu=\sqrt{1+2\\{(d/s^{\prime})^{1/2}+d/s^{\prime}\\}}\sqrt{1-\frac{1+c}{8}\eta\lambda_{\min}(\mathbf{B})\frac{1-\alpha}{c_{\text{upper}}\kappa(\mathbf{B})+\alpha}}<1,$
(S10)

where $\alpha=\frac{(1+a)\lambda_{2}}{(1-a)\lambda_{1}}$. Input an initial
vector $\mathbf{v}_{0}$ such that $\dfrac{|(\mathbf{v}^{*})^{\mathrm{\tiny
T}}\mathbf{v}_{0}|}{\|\mathbf{v}^{*}\|_{2}}\geq
1-\theta(\mathbf{A},\mathbf{B})$, where

$\theta(\mathbf{A},\mathbf{B})=\min\left[\dfrac{1}{8c_{\text{upper}}\kappa(\mathbf{B})},\dfrac{1/\alpha-1}{3c_{\text{upper}}\kappa(\mathbf{B})},\dfrac{1-\alpha}{30(1+c)c_{\text{upper}}^{2}\eta\lambda_{\max}(\mathbf{B})\kappa^{2}(\mathbf{B})\\{c_{\text{upper}}\kappa(\mathbf{B})+\alpha\\}}\right].$
(S11)

Further denote

$\xi=\min_{j>1}\dfrac{\lambda_{1}-(1+a)\lambda_{j}}{\sqrt{1+\lambda_{1}^{2}}\sqrt{1+(1-a)^{2}\lambda_{j}^{2}}}.$
(S12)

Assume that $\xi>\delta(s)/cr(s)$ and we have

$\sqrt{1-\dfrac{|(\mathbf{v}^{*})^{\mathrm{\tiny
T}}\mathbf{v}_{t}|}{\|\mathbf{v}^{*}\|_{2}}}\leq\nu^{t}\sqrt{\theta(\mathbf{A},\mathbf{B})}+\dfrac{\sqrt{10}}{1-\nu}\dfrac{2}{\xi\\{cr(s)-\delta(s)\\}}\delta(s).$
(S13)

We rewrite Proposition S5 in the following more user-friendly form. We denote

$\displaystyle\phi$ $\displaystyle=$
$\displaystyle\lambda_{1}-\lambda_{2},\quad
a^{*}=\min\\{1/2,\frac{\Delta}{\lambda_{1}+\lambda_{2}},\frac{\lambda_{\min}(\mathbf{B})}{2}\\}$
(S14) $\displaystyle\xi^{*}$ $\displaystyle=$
$\displaystyle\dfrac{\lambda_{1}-\lambda_{2}}{2(1+\lambda_{1}^{2})},\quad\alpha^{*}=\frac{(1+a^{*})\lambda_{2}}{(1-a^{*})\lambda_{1}}.$
(S15)

We have the following lemma.

######  Lemma S3.

Assume that Assumption S1 holds. Choose $\eta$ such that

$\nu^{*}=\sqrt{1+2\\{(d/s^{\prime})^{1/2}+d/s^{\prime}\\}}\sqrt{1-\frac{1+c}{8}\eta\lambda_{\min}(\mathbf{B})\frac{1-\frac{\lambda_{2}}{\lambda_{1}}}{c_{\text{upper}}\kappa(\mathbf{B})+3\frac{\lambda_{2}}{\lambda_{1}}}}<1.$

Also assume that $\delta(s)<\min\\{1/2,\lambda_{\min}(\mathbf{B})/2\\}$,
$\dfrac{2\delta(s)}{\lambda_{\min}(\mathbf{B})}+\dfrac{2\delta(s)}{\lambda_{\min}(\mathbf{B})\lambda_{1}(F)}<a^{*}$
and $\xi^{*}>2\delta(s)/cr(s)$. Input an initial vector $\mathbf{v}_{0}$ such
that $\dfrac{|(\mathbf{v}^{*})^{\mathrm{\tiny
T}}\mathbf{v}_{0}|}{\|\mathbf{v}^{*}\|_{2}}\geq
1-\theta^{*}(\mathbf{A},\mathbf{B})$, where
$0<\theta^{*}(\mathbf{A},\mathbf{B})<1$,

$\theta^{*}(\mathbf{A},\mathbf{B})=\min\left[\dfrac{1}{8c_{\text{upper}}\kappa(\mathbf{B})},\dfrac{1/\alpha^{*}-1}{3c_{\text{upper}}\kappa(\mathbf{B})},\dfrac{1-\alpha^{*}}{30(1+c)c_{\text{upper}}^{2}\eta\lambda_{\max}(\mathbf{B})\kappa^{2}(\mathbf{B})\\{c_{\text{upper}}\kappa(\mathbf{B})+\alpha^{*}\\}}\right].$
(S16)

We have

$|\sin\Theta(\mathbf{v}^{*},\mathbf{v}_{\infty})|\leq\dfrac{\sqrt{20}}{1-\nu^{*}}\dfrac{2}{\xi^{*}\\{cr(s)-\delta(s)\\}}\delta(s).$
(S17)

###### Proof of Lemma S3.

We prove Lemma S3 by showing that all the conditions in Proposition S5 are
met. Note that

$\hat{\omega}_{1}(F)=\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\widehat{\mathbf{A}}\mathbf{u}}{\mathbf{u}^{\mathrm{\tiny
T}}\widehat{\mathbf{B}}\mathbf{u}}=\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}+\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{\mathbf{A}}-\mathbf{A})\mathbf{u}}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}+\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{\mathbf{B}}-\mathbf{B})\mathbf{u}}.$ (S18)

It is obvious that

$\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}-\delta(s)}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}+\delta(s)}\leq\hat{\omega}_{1}(F)\leq\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}+\delta(s)}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}-\delta(s)}$ (S19)

Because
$a^{*}>\dfrac{2\delta(s)}{\lambda_{\min}(\mathbf{B})}+\dfrac{2\delta(s)}{\lambda_{\min}(\mathbf{B})\lambda_{1}(F)}$,
by Lemma S4, we have that Assumption S1 implies

$(1-a^{*})\omega_{1}(F)\leq\hat{\omega}_{1}(F)\leq(1+a^{*})\omega_{1}(F).$
(S20)

Also, by our definition, $a^{*}\leq 1/2$. It follows that
$\frac{\lambda_{2}}{\lambda_{1}}\leq\frac{(1+a)\lambda_{2}}{(1-a)\lambda_{1}}=\alpha\leq\frac{3\lambda_{2}}{\lambda_{1}}$.
Hence, $\nu\leq\nu^{*}<1$, where $\nu$ is defined in (S10). In addition,
because
$a^{*}\leq\frac{\phi}{\lambda_{1}+\lambda_{2}}\leq\frac{\phi}{2\lambda_{2}}$,
we have $\xi\geq\xi^{*}$, where $\xi$ is defined in (S12). Finally, because
$\dfrac{1}{8c_{\text{upper}}\kappa(\mathbf{B})}<1$, we have
$\theta^{*}(\mathbf{A},\mathbf{B})<1$. Because
$a^{*}\leq\dfrac{\phi}{\lambda_{1}+\lambda_{2}}$, we have $1-\gamma^{*}>0$ and
thus $\theta^{*}(\mathbf{A},\mathbf{B})>0$.

By Proposition S5, we have

$\displaystyle\sqrt{1-\dfrac{|(\mathbf{v}^{*})^{\mathrm{\tiny
T}}\mathbf{v}_{t}|}{\|\mathbf{v}^{*}\|_{2}}}$ $\displaystyle\leq$
$\displaystyle\nu^{t}\sqrt{\theta(\mathbf{A},\mathbf{B})}+\dfrac{\sqrt{10}}{1-\nu}\dfrac{2}{\xi\\{cr(s)-\delta(s)\\}}\delta(s)$
(S21) $\displaystyle\leq$
$\displaystyle(\nu^{*})^{t}\sqrt{\theta^{*}(\mathbf{A},\mathbf{B})}+\dfrac{\sqrt{10}}{1-\nu^{*}}\dfrac{2}{\xi^{*}\\{cr(s)-\delta(s)\\}}\delta(s).$
(S22)

Let $t\rightarrow\infty$ and we have that
$\sqrt{1-\dfrac{|(\mathbf{v}^{*})^{\mathrm{\tiny
T}}\mathbf{v}_{\infty}|}{\|\mathbf{v}^{*}\|_{2}}}\leq\dfrac{\sqrt{10}}{1-\nu^{*}}\dfrac{2}{\xi^{*}\\{cr(s)-\delta(s)\\}}\delta(s).$
Finally, we note that $1-\dfrac{|(\mathbf{v}^{*})^{\mathrm{\tiny
T}}\mathbf{v}_{\infty}|}{\|\mathbf{v}^{*}\|_{2}}=1-|\cos\Theta(\mathbf{v}^{*},\mathbf{v}_{\infty})|$.
Since
$\sin^{2}\Theta(\mathbf{v}^{*},\mathbf{v}_{\infty})=(1+|\cos\Theta(\mathbf{v}^{*},\mathbf{v}_{\infty})|)(1-|\cos\Theta(\mathbf{v}^{*},\mathbf{v}_{\infty})|)\leq
2(1-|\cos\Theta(\mathbf{v}^{*},\mathbf{v}_{\infty})|)$, we have the desired
conclusion. ∎

######  Lemma S4.

Consider two symmetric matrices $\mathbf{A},\mathbf{B}$, where
$\lambda_{\min}(\mathbf{B})>0$. For any $F\subset\\{1,\ldots,p\\}$, denote

$\lambda_{1}(F)=\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}}{\mathbf{u}^{\mathrm{\tiny T}}\mathbf{B}\mathbf{u}}.$
(S23)

For any
$0<\epsilon<\min\\{\frac{1}{2},\dfrac{\lambda_{\min}(\mathbf{B})}{2}\\}$, we
have that

$\displaystyle\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}+\epsilon}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}-\epsilon}$ $\displaystyle\leq$
$\displaystyle(1+a)\lambda_{1}(F),$ (S24)
$\displaystyle\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}-\epsilon}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}+\epsilon}$ $\displaystyle\geq$
$\displaystyle(1-a)\lambda_{1}(F),$ (S25)

where
$a=\dfrac{2\epsilon}{\lambda_{\min}(\mathbf{B})}+\dfrac{2\epsilon}{\lambda_{\min}(\mathbf{B})\omega_{1}(F)}$.

###### Proof of Lemma S4.

For (S24), note that, for any $\mathbf{u}$, we have $\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}-\epsilon\geq\\{1-\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}\\}\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}.$ So

$\displaystyle\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}+\epsilon}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}-\epsilon}$ (S26) $\displaystyle\leq$
$\displaystyle\dfrac{1}{1-\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\cdot\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}}+\dfrac{1}{1-\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\cdot\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{1}{\mathbf{u}^{\mathrm{\tiny T}}\mathbf{B}\mathbf{u}}$ (S27)
$\displaystyle\leq$
$\displaystyle\dfrac{1}{1-\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\cdot\omega_{1}(F)+\dfrac{2\epsilon}{\lambda_{\min}(\mathbf{B})\omega_{1}(F)}\cdot\omega_{1}(F),$
(S28)

where in the last inequality we use the fact that
$\epsilon<\dfrac{\lambda_{\min}(\mathbf{B})}{2}$. Also note that, for any
$0<x<1/2$, we have $\dfrac{1}{1-x}<1+2x$. It follows that
$\dfrac{1}{1-\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\leq
1+\dfrac{2\epsilon}{\lambda_{\min}(\mathbf{B})}.$ Hence,

$\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}+\epsilon}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}-\epsilon}\leq\left\\{1+\dfrac{2\epsilon}{\lambda_{\min}(\mathbf{B})}+\dfrac{2\epsilon}{\lambda_{\min}(\mathbf{B})\omega_{1}(F)}\right\\}\omega_{1}(F)=(1+a)\omega_{1}(F).$
(S29)

Similarly, for (S25), we note that, for any $\mathbf{u}$,
$\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}+\epsilon\leq\\{1+\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}\\}\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}.$ So

$\displaystyle\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}-\epsilon}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}+\epsilon}$ $\displaystyle\geq$
$\displaystyle\dfrac{1}{1+\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\cdot\omega_{1}(F)-\dfrac{1}{1+\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\cdot\dfrac{\epsilon}{\lambda_{\max}(\mathbf{B})},$
(S30) $\displaystyle\geq$
$\displaystyle\dfrac{1}{1+\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}\cdot\omega_{1}(F)-\dfrac{\epsilon}{\lambda_{\max}(\mathbf{B})\omega_{1}(F)}\cdot\omega_{1}(F).$
(S31)

Because $\frac{1}{1+x}>1-x$ for any $x>0$, we have
$\dfrac{1}{1+\frac{\epsilon}{\lambda_{\min}(\mathbf{B})}}>1-\dfrac{\epsilon}{\lambda_{\min}(\mathbf{B})}$.
Hence,

$\sup_{\|\mathbf{u}\|_{2}=1,\mathrm{supp}(\mathbf{u})\subset
F}\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{A}\mathbf{u}-\epsilon}{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{B}\mathbf{u}+\epsilon}\geq(1-\dfrac{\epsilon}{\lambda_{\min}(\mathbf{B})}-\dfrac{\epsilon}{\lambda_{\max}(\mathbf{B})\omega_{1}(F)})\omega_{1}(F)\geq(1-a)\omega_{1}(F).$
(S32)

The conclusion follows. ∎

###  S6.2 Additional technical lemmas

We first derive several lemmas concerning a parameter $\boldsymbol{\beta}_{k}$
(either in the penalized eigen-decomposition or the penalized generalized
eigen-decomposition) and its estimate $\widehat{\boldsymbol{\beta}}_{k}$. We
denote
$\eta_{k}=|\sin\Theta(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k})|$,
and $\hat{\lambda}_{k}=\widehat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\widehat{\mathbf{M}}\widehat{\boldsymbol{\beta}}_{k}$.

######  Lemma S5.

If $\|\boldsymbol{\beta}_{k}\|_{0}\leq s,k=1,\ldots,K$, we have that

$\displaystyle\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}-\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}})\|_{1}$ $\displaystyle\leq$ $\displaystyle 2s\eta_{k}$ (S33)

###### Proof of Lemma S5.

For (S33), set
${\bm{\zeta}}_{k}=\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}-\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}})$. We have that

$\displaystyle\|{\bm{\zeta}}_{k}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\|\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}-\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\|_{F}^{2}={\mathrm{Tr}}((\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}-\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}})(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}-\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}))$ (S34) $\displaystyle=$ $\displaystyle
2(1-(\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\hat{\boldsymbol{\beta}}_{k})^{2})=2\eta^{2}_{k}$ (S35)

Hence, by the Cauchy-Schwarz inequality,

$\displaystyle\|{\bm{\zeta}}_{k}\|_{1}\leq\sqrt{\|{\bm{\zeta}}_{k}\|_{0}}\|{\bm{\zeta}}_{k}\|_{2}\leq\sqrt{2s^{2}}\cdot\sqrt{2\eta_{k}^{2}}=2s\eta_{k}$
(S36)

∎

######  Lemma S6.

If $\|\boldsymbol{\beta}_{k}\|_{0}\leq s$, we have that

$\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{1}\leq s.$ (S37)

###### Proof of Lemma S6.

By the Cauchy-Schwarz inequality, we have that

$\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{1}\leq\sqrt{\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{0}}\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{2}$ (S38)

Note that
$\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{0}\leq s^{2}$ and

$\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{2}^{2}=\|\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\|_{F}^{2}={\mathrm{Tr}}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny T}})=1$ (S39)

where we use the fact that $\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\boldsymbol{\beta}_{k}=1$. And we have the desired conclusion. ∎

Throughout the rest of this section, we also repeatedly use the fact that, for
a vector $\mathbf{u}$, if $\|\mathbf{u}\|_{2}=1$, $\|\mathbf{u}\|_{0}\leq s$,
we must have that $\|\mathbf{u}\|_{1}\leq\sqrt{s}$.

###  S6.3 Proof for Theorem 2

In this subsection, we assume that
$\boldsymbol{\Sigma}_{\mathbf{X}}=\mathbf{I}$,
$\widehat{\boldsymbol{\beta}}_{k}$ are solutions produced by Algorithm 1 for
the penalized eigen-decomposition problem, and
$\widehat{\lambda}_{k}=(\widehat{\boldsymbol{\beta}}_{k})^{\mathrm{\tiny
T}}\widehat{\mathbf{M}}\widehat{\boldsymbol{\beta}}_{k}$. We assume all the
conditions in Theorem 2. We have the following result.

######  Lemma S7.

If $\|\widehat{\boldsymbol{\beta}}_{k}\|_{0}\leq
s,\|\boldsymbol{\beta}_{k}\|_{0}\leq s$, we have that

$|\hat{\lambda}_{k}-\lambda_{k}|\leq
s(2\eta_{k}+1)\epsilon+(\lambda_{1}+\lambda_{k})\eta_{k}^{2}.$ (S40)

###### Proof of Lemma S7.

Note that

$\displaystyle|\hat{\lambda}_{k}-\lambda_{k}|=|\langle\widehat{\mathbf{M}},\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\rangle-\langle\mathbf{M},\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\rangle|$ (S41) $\displaystyle\leq$
$\displaystyle|\langle\widehat{\mathbf{M}}-\mathbf{M},\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}-\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\rangle|+|\langle\widehat{\mathbf{M}}-\mathbf{M},\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\rangle|+|\langle\mathbf{M},\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}-\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny T}}\rangle|$
(S42) $\displaystyle\equiv$ $\displaystyle L_{1}+L_{2}+L_{3}$ (S43)

By Lemma S5,

$\displaystyle
L_{1}\leq\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\|\mathrm{vec}(\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}-\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny T}})\|_{1}\leq
2s\eta_{k}\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq 2s\eta_{k}\epsilon.$
(S44)

By Lemma S6,

$\displaystyle
L_{2}\leq\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{1}\leq s\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq s\epsilon.$
(S45)

For $L_{3}$, note that
$\mathbf{M}=\sum_{j=1}^{p}\lambda_{j}\boldsymbol{\beta}_{j}\boldsymbol{\beta}_{j}^{\mathrm{\tiny
T}}$, which implies that

$\langle\mathbf{M},\widehat{\boldsymbol{\beta}}_{k}\widehat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\rangle=\sum_{j=1}^{p}\lambda_{j}(\widehat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\boldsymbol{\beta}_{j})^{2}=\sum_{j=1}^{p}\lambda_{j}\cos^{2}\boldsymbol{\Theta}(\hat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{j}).$

Also note that
$\sum_{j=1}^{p}\cos^{2}\boldsymbol{\Theta}(\hat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{j})=1$.
Hence,

$\displaystyle L_{3}$ $\displaystyle=$
$\displaystyle|\sum_{j=1}^{p}\lambda_{j}\cos^{2}\boldsymbol{\Theta}(\boldsymbol{\beta}_{j},\hat{\boldsymbol{\beta}}_{k})-\lambda_{k}|$
(S46) $\displaystyle\leq$ $\displaystyle\sum_{j\neq
k}\lambda_{j}\cos^{2}\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{j})+\lambda_{k}|\cos^{2}\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k})-1|$
(S47) $\displaystyle\leq$ $\displaystyle\lambda_{1}\sum_{j\neq
k}\cos^{2}\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{j})+\lambda_{k}(1-\cos^{2}\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k}))$
(S48) $\displaystyle\leq$
$\displaystyle(\lambda_{1}+\lambda_{k})(1-\cos^{2}\boldsymbol{\Theta}(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k}))$
(S49) $\displaystyle=$ $\displaystyle(\lambda_{1}+\lambda_{k})\eta_{k}^{2}$
(S50)

∎

In Lemmas S8–S10, we assume that the event
$\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq\epsilon$ has happened.

######  Lemma S8.

For the first direction $\widehat{\boldsymbol{\beta}}_{1}$, we have that
$|\sin\Theta(\widehat{\boldsymbol{\beta}}_{1},\boldsymbol{\beta}_{1})|\leq
Cs\epsilon$ and $|\hat{\lambda}_{1}-\lambda_{1}|\leq Cs\epsilon$.

###### Proof of Lemma S8.

It is easy to see that

$\displaystyle\rho(\widehat{\mathbf{M}}-\mathbf{M},s)=\sup_{\|\mathbf{u}\|_{2}=1,\|\mathbf{u}\|_{0}\leq
s}s|\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{\mathbf{M}}-\mathbf{M})\mathbf{u}|\leq\sup_{\|\mathbf{u}\|_{2}=1,\|\mathbf{u}\|_{0}\leq
s}\|\mathbf{u}\|_{1}^{2}\cdot\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq
s\epsilon.$ (S51)

Under our assumptions about $\epsilon$, by Proposition S4, we have
$\lvert\sin\Theta(\widehat{\boldsymbol{\beta}}_{1},\boldsymbol{\beta}_{1})\rvert\leq
Cs\epsilon$ at convergence. Lemma S7 further implies that
$|\hat{\lambda}_{1}-\lambda_{1}|\leq Cs\epsilon$. ∎

######  Lemma S9.

If $|\sin\Theta(\widehat{\boldsymbol{\beta}}_{j},\boldsymbol{\beta}_{j})|\leq
Cs\epsilon$ for sufficiently small $\epsilon$, all $j\leq k$, then
$\rho(\widehat{\mathbf{M}}_{k+1}-\mathbf{M}_{k+1},s)\leq Cs\epsilon$.

###### Proof of Lemma S9.

Define
$\mathbf{N}_{l}=\hat{\lambda}_{l}\hat{\boldsymbol{\beta}}_{l}\hat{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}-\lambda_{l}\boldsymbol{\beta}_{l}\boldsymbol{\beta}_{l}^{\mathrm{\tiny
T}}$. Then

$\widehat{\mathbf{M}}_{k+1}-\mathbf{M}_{k+1}=(\widehat{\mathbf{M}}-\mathbf{M})-\sum_{l\leq
k}\mathbf{N}_{l}.$ (S52)

It follows that

$\rho(\widehat{\mathbf{M}}_{k+1}-\mathbf{M}_{k+1},s)\leq\rho(\widehat{\mathbf{M}}-\mathbf{M},s)+\sum_{l\leq
k}\rho(\mathbf{N}_{l},s).$ (S53)

According to the proof in Lemma S8,
$\rho(\widehat{\mathbf{M}}-\mathbf{M},s)\leq s\epsilon$.

For any vector $\mathbf{u}$, we have

$\displaystyle\mathbf{u}^{\mathrm{\tiny T}}\mathbf{N}_{l}\mathbf{u}$
$\displaystyle=$ $\displaystyle\widehat{\lambda}_{l}(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{\boldsymbol{\beta}}_{l})^{2}-{\lambda}_{l}(\mathbf{u}^{\mathrm{\tiny
T}}{\boldsymbol{\beta}}_{l})^{2}$ (S54) $\displaystyle=$
$\displaystyle(\widehat{\lambda}_{l}-\lambda_{l})(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{\boldsymbol{\beta}}_{l})^{2}+\lambda_{l}\\{(\mathbf{u}^{\mathrm{\tiny
T}}\boldsymbol{\beta}_{l})^{2}-(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{\boldsymbol{\beta}}_{l})^{2}\\}\equiv L_{1}+L_{2}$ (S55)

By Lemma S7, we have that $|\hat{\lambda}_{l}-\lambda_{l}|\leq Cs\epsilon$
when
$|\sin\Theta(\widehat{\boldsymbol{\beta}}_{j},\boldsymbol{\beta}_{j})|\leq
Cs\epsilon$. Also, $|\mathbf{u}^{\mathrm{\tiny
T}}\boldsymbol{\beta}_{l}|\leq\|\mathbf{u}\|_{2}\cdot\|\boldsymbol{\beta}_{l}\|_{2}=1$.
It follows that $L_{1}\leq Cs\epsilon$. For $L_{2}$, we assume that
$\cos\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l})>0$
without loss of generality, because otherwise we can consider the proof for
$-\widehat{\boldsymbol{\beta}}_{l}$. Note that

$\displaystyle L_{2}$ $\displaystyle\leq$
$\displaystyle\lambda_{l}|\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l})|\cdot|\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{\boldsymbol{\beta}}_{l}+\boldsymbol{\beta}_{l})|$
$\displaystyle\leq$
$\displaystyle\lambda_{l}\|\mathbf{u}\|_{2}^{2}\cdot\|\widehat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l}\|_{2}(\|\widehat{\boldsymbol{\beta}}_{l}\|_{2}+\|\boldsymbol{\beta}_{l}\|_{2})$
$\displaystyle=$ $\displaystyle
C\|\widehat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l}\|_{2}$
$\displaystyle=$ $\displaystyle
C\sqrt{2-2\widehat{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\boldsymbol{\beta}_{l}}=\sqrt{2(1-\cos\Theta(\widehat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l}))}$
$\displaystyle=$ $\displaystyle
C\sqrt{1-\cos^{2}\Theta(\widehat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l})}/\sqrt{1+\cos\Theta(\widehat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l})}$
$\displaystyle\leq$ $\displaystyle
C|\sin\Theta(\widehat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l})|$
$\displaystyle\leq$ $\displaystyle Cs\epsilon.$

Hence, $\rho(\mathbf{N}_{l},s)\leq Cs\epsilon$ and the conclusion follows. ∎

######  Lemma S10.

Assume that
$|\sin\Theta(\hat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l})|<Cs\epsilon$
for any $l<k$, where $0<\epsilon<\min\\{\dfrac{\Delta}{4s},\theta\\}$ for
$\theta$ defined in Theorem 2. We have that
$|\sin\Theta(\hat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k})|\leq
Cs\epsilon$.

###### Proof of Lemma S10.

The conclusion follows from Lemma S9 and Proposition S4. ∎

###### Proof of Theorem 2.

Under the event $\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq\epsilon$, we
have that
$|\sin\Theta(\widehat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k})|\leq
Cs\epsilon$ by Lemmas S8–S10. Then by Theorem 1 we have the desired
conclusion. ∎

###  S6.4 Proof for Theorem 3

In this subsection we prove Theorem 3, where ${\bm{\Sigma}}_{\mathbf{X}}$
could be different from the identity matrix. We first present a simple lemma,
which is a modified version of Lemma 6 in Mai and Zhang (2019).

######  Lemma S11.

For two vectors $\mathbf{u},\mathbf{v}$ and a positive definite matrix
${\bm{\Sigma}}$, define
$\xi_{\mathbf{I}}=1-\cos\boldsymbol{\Theta}(\mathbf{v},\mathbf{u}),\xi_{{\bm{\Sigma}}}=1-\cos\boldsymbol{\Theta}({\bm{\Sigma}}^{1/2}\mathbf{v},{\bm{\Sigma}}^{1/2}\mathbf{u})$.
We have that

$\dfrac{\lambda_{\min}({\bm{\Sigma}})}{\lambda_{\max}({\bm{\Sigma}})}\xi_{{\bm{\Sigma}}}\leq\xi_{\mathbf{I}}\leq\dfrac{\lambda_{\max}({\bm{\Sigma}})}{\lambda_{\min}({\bm{\Sigma}})}\xi_{{\bm{\Sigma}}}$

###### Proof of Lemma S11.

We first show the latter half of the desired inequality. Without loss of
generality, we assume that $\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{u}=1,\mathbf{v}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{v}=1$, because we can always normalize
$\mathbf{u},\mathbf{v}$ to satisfy these conditions.

Note that

$\displaystyle\lambda_{\min}({\bm{\Sigma}})(\mathbf{u}-\mathbf{v})^{\mathrm{\tiny
T}}(\mathbf{u}-\mathbf{v})$ $\displaystyle\leq$
$\displaystyle(\mathbf{u}-\mathbf{v})^{\mathrm{\tiny
T}}{\bm{\Sigma}}(\mathbf{u}-\mathbf{v})$ $\displaystyle=$
$\displaystyle\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{u}-2\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{v}+\mathbf{v}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{v}=2\xi_{{\bm{\Sigma}}}$
$\displaystyle\lambda_{\max}({\bm{\Sigma}})\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}$ $\displaystyle\geq$ $\displaystyle\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{u}=1$
$\displaystyle\lambda_{\max}({\bm{\Sigma}})\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{v}$ $\displaystyle\geq$ $\displaystyle\mathbf{v}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{v}=1$

Consequently,

$\displaystyle(\mathbf{u}-\mathbf{v})^{\mathrm{\tiny
T}}(\mathbf{u}-\mathbf{v})\leq\frac{2\xi_{{\bm{\Sigma}}}}{\lambda_{\min}({\bm{\Sigma}})}$
$\displaystyle\mathbf{u}^{\mathrm{\tiny T}}\mathbf{u}\geq
1/\lambda_{\max}({\bm{\Sigma}}),\mathbf{v}^{\mathrm{\tiny T}}\mathbf{v}\geq
1/\lambda_{\max}({\bm{\Sigma}})$

Now

$\displaystyle\dfrac{2\lambda_{\max}({\bm{\Sigma}})\xi_{{\bm{\Sigma}}}}{\lambda_{\min}({\bm{\Sigma}})}$
$\displaystyle\geq$
$\displaystyle\dfrac{2\xi_{{\bm{\Sigma}}}}{\lambda_{\min}({\bm{\Sigma}})\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}}\sqrt{\mathbf{v}^{\mathrm{\tiny T}}\mathbf{v}}}$
$\displaystyle\geq$
$\displaystyle\dfrac{(\mathbf{u}-\mathbf{v})^{\mathrm{\tiny
T}}(\mathbf{u}-\mathbf{v})}{\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}}\sqrt{\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{v}}}=\dfrac{\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}}}{\sqrt{\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{v}}}+\dfrac{\sqrt{\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{v}}}{\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}}}-2\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{v}}{\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}}\sqrt{\mathbf{v}^{\mathrm{\tiny T}}\mathbf{v}}}$
$\displaystyle\geq$ $\displaystyle 2-2\dfrac{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{v}}{\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\mathbf{u}}\sqrt{\mathbf{v}^{\mathrm{\tiny
T}}\mathbf{v}}}=2\xi_{\mathbf{I}},$

and we have the second half of the inequality. For the first half of the
inequality, define
$\mathbf{u}^{*}={\bm{\Sigma}}^{1/2}\mathbf{u},\mathbf{v}^{*}={\bm{\Sigma}}^{1/2}$.
Apply the second half of the inequality to vectors
$\mathbf{u}^{*},\mathbf{v}^{*}$ and matrix ${\bm{\Sigma}}^{-1}$, and we have
the desired conclusion. ∎

We now show the following lemma parallel to Lemma S7. Recall that
$\eta_{k}=|\sin\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k})|$.

######  Lemma S12.

If $\|\widehat{\boldsymbol{\beta}}_{k}\|_{0}\leq
s,\|\boldsymbol{\beta}_{k}\|_{0}\leq s$, we have that

$|\hat{\lambda}_{k}-\lambda_{k}|\leq
s(2\eta_{k}+1)\epsilon+2\dfrac{\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}(\lambda_{1}+\lambda_{k})\eta_{k}^{2}.$
(S56)

###### Proof of Lemma S12.

Note that

$\displaystyle|\hat{\lambda}_{k}-\lambda_{k}|=|\langle\widehat{\mathbf{M}},\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\rangle-\langle\mathbf{M},\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\rangle|$ (S57) $\displaystyle\leq$
$\displaystyle|\langle\widehat{\mathbf{M}}-\mathbf{M},\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}-\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\rangle|+|\langle\widehat{\mathbf{M}}-\mathbf{M},\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}}\rangle|+|\langle\mathbf{M},\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}-\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny T}}\rangle|$
(S58) $\displaystyle\equiv$ $\displaystyle L_{1}+L_{2}+L_{3}$ (S59)

By Lemma S5,

$\displaystyle
L_{1}\leq\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\|\mathrm{vec}(\hat{\boldsymbol{\beta}}_{k}\hat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}-\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny T}})\|_{1}\leq
2s\eta_{k}\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq 2s\eta_{k}\epsilon.$
(S60)

By Lemma S6,

$\displaystyle
L_{2}\leq\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\|\mathrm{vec}(\boldsymbol{\beta}_{k}\boldsymbol{\beta}_{k}^{\mathrm{\tiny
T}})\|_{1}\leq s\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq s\epsilon.$
(S61)

For $L_{3}$, note that
$\mathbf{M}={\bm{\Sigma}}_{\mathbf{X}}\left(\sum_{j=1}^{p}\lambda_{j}\boldsymbol{\beta}_{j}\boldsymbol{\beta}_{j}^{\mathrm{\tiny
T}}\right){\bm{\Sigma}}_{\mathbf{X}}$ by the proof of Lemma 1, which implies
that

$\langle\mathbf{M},\widehat{\boldsymbol{\beta}}_{k}\widehat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}\rangle=\sum_{j=1}^{p}\lambda_{j}(\widehat{\boldsymbol{\beta}}_{k}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{j})^{2}=\sum_{j=1}^{p}\lambda_{j}\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{j})$

Also note that
$\sum_{j=1}^{p}\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{j})=1$.
Without loss of generality, assume that
$\cos\boldsymbol{\Theta}(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k})>0$.
We have that

$\displaystyle L_{3}$ $\displaystyle=$
$\displaystyle|\sum_{j=1}^{p}\lambda_{j}\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{j},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k})-\lambda_{k}|$
$\displaystyle\leq$ $\displaystyle\sum_{j\neq
k}\lambda_{j}\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\widehat{\boldsymbol{\beta}}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{j})+\lambda_{k}|\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\widehat{\boldsymbol{\beta}}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{k})-1|$
$\displaystyle\leq$ $\displaystyle\lambda_{1}\sum_{j\neq
k}\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\widehat{\boldsymbol{\beta}}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{j})+\lambda_{k}(1-\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\widehat{\boldsymbol{\beta}}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{k}))$
$\displaystyle\leq$
$\displaystyle(\lambda_{1}+\lambda_{k})(1-\cos^{2}\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k}))$
$\displaystyle=$
$\displaystyle(\lambda_{1}+\lambda_{k})(1-\cos\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k}))(1+\cos\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k}))$
$\displaystyle\leq$ $\displaystyle
2(\lambda_{1}+\lambda_{k})(1-\cos\boldsymbol{\Theta}({\bm{\Sigma}}_{\mathbf{X}}^{1/2}\boldsymbol{\beta}_{k},{\bm{\Sigma}}_{\mathbf{X}}^{1/2}\hat{\boldsymbol{\beta}}_{k}))$
$\displaystyle\leq$ $\displaystyle
2\dfrac{\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}(\lambda_{1}+\lambda_{k})(1-\cos\boldsymbol{\Theta}(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k})),$

where the last inequality follows from Lemma S11. Further note that
$1-\cos\boldsymbol{\Theta}(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k})=\dfrac{\sin^{2}\boldsymbol{\Theta}(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k})}{1+\cos\boldsymbol{\Theta}(\boldsymbol{\beta}_{k},\hat{\boldsymbol{\beta}}_{k})}\leq\eta_{k}^{2}$
and we have the desired conclusion. ∎

We consider the event
$\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq\epsilon,\|\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}}\|_{\max}\leq\epsilon$
for
$\sqrt{2}s\epsilon<\min\\{1/2,\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})\\}$
and
$\frac{\sqrt{2}s\epsilon}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}+\frac{\sqrt{2}s\epsilon}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})\lambda_{1}}<a^{*}$
and
$\dfrac{\sqrt{2}s\epsilon}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}<\frac{\Delta}{2(1+\lambda_{1}^{2})}$,
where $\Delta$ is defined as in Condition (C2) and
$a^{*}=\min\\{\frac{1}{2},\frac{\Delta}{\lambda_{1}+\lambda_{2}},\frac{\lambda_{\min}{({\bm{\Sigma}}_{\mathbf{X}})}}{2}\\}$.
As a direct consequence,
$\rho(\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}},s)\leq
s\epsilon$. Also note that
$\tilde{\boldsymbol{\beta}}_{k}=\dfrac{\widehat{\boldsymbol{\beta}}_{k}}{\|\widehat{\boldsymbol{\beta}}_{k}\|_{2}}$.
In the RIFLE algorithm, $\boldsymbol{\beta}_{k}^{0}$ is chosen to be
sufficiently close to $\boldsymbol{\beta}_{k}$, and the step size $\eta$
satisfies that $\eta\leq\frac{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}{2}$
and

$\sqrt{1+2\\{(d/s^{\prime})^{1/2}+d/s^{\prime}\\}}\sqrt{1-\frac{1}{16}\eta\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})\frac{\frac{\Delta}{\lambda_{K}}}{\kappa({\bm{\Sigma}}_{\mathbf{X}})+1}}<1.$
(S62)

Without loss of generality, in what follows we assume that
$\cos\boldsymbol{\Theta}(\widehat{\boldsymbol{\beta}}_{j},\boldsymbol{\beta}_{k})>0$,
because otherwise we can always consider $-\widehat{\boldsymbol{\beta}}_{j}$,
which spans the same susbspace as $\widehat{\boldsymbol{\beta}}_{j}$.

######  Lemma S13.

For the first direction $\widehat{\boldsymbol{\beta}}_{1}$, we have that
$|\sin\Theta(\widehat{\boldsymbol{\beta}}_{1},\boldsymbol{\beta}_{1})|\leq
Cs\epsilon$ and $|\hat{\lambda}_{1}-\lambda_{1}|\leq Cs\epsilon$.

###### Proof of Lemma S13.

It is easy to see that

$\displaystyle\rho(\widehat{\mathbf{M}}-\mathbf{M},s)=\sup_{\|\mathbf{u}\|_{2}=1,\|\mathbf{u}\|_{0}\leq
s}s|\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{\mathbf{M}}-\mathbf{M})\mathbf{u}|\leq\sup_{\|\mathbf{u}\|_{2}=1,\|\mathbf{u}\|_{0}\leq
s}\|\mathbf{u}\|_{1}^{2}\cdot\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq
s\epsilon.$ (S63)

Similarly,
$\rho(\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}},s)\leq
s\epsilon$. Denote
$\delta_{1}(s)=\sqrt{\rho^{2}(\widehat{\mathbf{M}}-\mathbf{M},s)+\rho^{2}(\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}},s)}$.
It follows that $\delta_{1}(s)\leq\sqrt{2}s\epsilon$. Under our assumptions
about $\epsilon$, we have that
$|\sin\Theta(\widehat{\boldsymbol{\beta}}_{1},\boldsymbol{\beta}_{1})|\leq
Cs\epsilon$ by Lemma S3. Lemma S12 further implies that
$|\hat{\lambda}_{1}-\lambda_{1}|\leq Cs\epsilon$. ∎

######  Lemma S14.

If $|\sin\Theta(\widehat{\boldsymbol{\beta}}_{j},\boldsymbol{\beta}_{j})|\leq
Cs\epsilon$ for sufficiently small $\epsilon$, all $j\leq k$, then
$\delta(s)\leq Cs\epsilon$.

###### Proof of Lemma S14.

It suffices to show that
$\rho(\widehat{\mathbf{M}}_{k+1}-\mathbf{M}_{k+1},s)\leq Cs\epsilon$. Define
$\mathbf{N}_{l}=\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\hat{\lambda}_{l}\hat{\boldsymbol{\beta}}_{l}\hat{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}}\lambda_{l}\boldsymbol{\beta}_{l}\boldsymbol{\beta}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}$. Then

$\widehat{\mathbf{M}}_{k+1}-\mathbf{M}_{k+1}=(\widehat{\mathbf{M}}-\mathbf{M})-\sum_{l\leq
k}\mathbf{N}_{l}.$ (S64)

It follows that

$\rho(\widehat{\mathbf{M}}_{k+1}-\mathbf{M}_{k+1},s)\leq\rho(\widehat{\mathbf{M}}-\mathbf{M},s)+\sum_{l\leq
k}\rho(\mathbf{N}_{l},s).$ (S65)

According to the proof in Lemma S13,
$\rho(\widehat{\mathbf{M}}-\mathbf{M},s)\leq s\epsilon$.

For any vector $\mathbf{u}$, we have

$\displaystyle\mathbf{u}^{\mathrm{\tiny T}}\mathbf{N}_{l}\mathbf{u}$
$\displaystyle=$ $\displaystyle\hat{\lambda}_{l}(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\hat{\boldsymbol{\beta}}_{l})^{2}-{\lambda}_{l}(\mathbf{u}^{\mathrm{\tiny
T}}{{\bm{\Sigma}}}_{\mathbf{X}}{\boldsymbol{\beta}}_{l})^{2}$ (S66)
$\displaystyle=$
$\displaystyle(\hat{\lambda}_{l}-\lambda_{l})(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l})^{2}+\lambda_{l}\\{(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l})^{2}-(\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l})\\}\equiv L_{1}+L_{2}$
(S67)

By Lemma S12, we have that $|\hat{\lambda}_{l}-\lambda_{l}|\leq Cs\epsilon$
when $\sin\Theta(\widehat{\boldsymbol{\beta}}_{j},\boldsymbol{\beta}_{j})\leq
Cs\epsilon$. Also,

$\displaystyle|\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}|$
$\displaystyle\leq$ $\displaystyle|\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}|+\|\mathbf{u}\|_{1}\cdot\|\widehat{\boldsymbol{\beta}}_{l}\|_{1}\|\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}}\|_{\max}\leq|\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}|+s\epsilon$ (S68)
$\displaystyle\leq$ $\displaystyle\sqrt{(\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\mathbf{u})\cdot(\widehat{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l})}+s\epsilon\leq\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})+s\epsilon.$
(S69)

It follows that $L_{1}\leq Cs\epsilon$. For $L_{2}$, note that
$(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l})^{2}-(\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l})=(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}+\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l})(\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}-\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l})$. On one hand,

$\displaystyle|\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}+\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}|\leq|\mathbf{u}^{\mathrm{\tiny
T}}\widehat{\bm{\Sigma}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}|+|\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}|$ (S70)
$\displaystyle\leq$ $\displaystyle\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\mathbf{u}\cdot\widehat{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\widehat{\boldsymbol{\beta}}_{l}}+\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{u}\cdot\boldsymbol{\beta}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\boldsymbol{\beta}_{l}}$ (S71) $\displaystyle=$
$\displaystyle\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\mathbf{u}}+\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\mathbf{u}}=\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\mathbf{u}+\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}})\mathbf{u}}+\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}\mathbf{u}}$ (S72) $\displaystyle\leq$
$\displaystyle\sqrt{\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})+s\epsilon}+\sqrt{\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})}$
(S73)

On the other hand,

$\displaystyle|\mathbf{u}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\hat{\boldsymbol{\beta}}_{l}-\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}|$ $\displaystyle\leq$
$\displaystyle|\mathbf{u}^{\mathrm{\tiny
T}}(\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}})\hat{\boldsymbol{\beta}}_{l}|+|\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}(\hat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l})|$
(S74) $\displaystyle\leq$ $\displaystyle s\epsilon+|\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}(\hat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l})|$
(S75) $\displaystyle\equiv$ $\displaystyle s\epsilon+L_{3}.$ (S76)

Further note that

$\displaystyle L_{3}$ $\displaystyle\leq$
$\displaystyle\sqrt{\mathbf{u}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\mathbf{u}\cdot(\hat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}(\hat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l})}\leq\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})\cdot\|\hat{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l}\|_{2}$
(S77) $\displaystyle=$
$\displaystyle\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})\cdot\dfrac{1}{\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}}\|\tilde{\boldsymbol{\beta}}_{l}-\sqrt{\tilde{\boldsymbol{\beta}}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}\cdot\boldsymbol{\beta}_{l}\|_{2}$
(S78) $\displaystyle\leq$
$\displaystyle\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})\cdot\dfrac{1}{\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}}\\{\|\tilde{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l}^{*}\|_{2}+|\dfrac{1}{\|\boldsymbol{\beta}_{l}\|_{2}}-\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}|\cdot\|\boldsymbol{\beta}_{l}\|_{2}\\},$
(S79)

where
$\boldsymbol{\beta}_{l}^{*}=\dfrac{\boldsymbol{\beta}_{l}}{\|\boldsymbol{\beta}_{l}\|_{2}}$.
By our assumption,
$\|\tilde{\boldsymbol{\beta}}_{l}-\boldsymbol{\beta}_{l}^{*}\|_{2}\leq\sqrt{2}\sin\Theta(\boldsymbol{\beta}_{l}^{*},\boldsymbol{\beta}_{l})\leq
Cs\epsilon$. For the second term, since
$(\boldsymbol{\beta}^{*}_{l})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}=\dfrac{\boldsymbol{\beta}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}}{\|\boldsymbol{\beta}_{l}\|_{2}^{2}}=\dfrac{1}{\|\boldsymbol{\beta}_{l}\|_{2}^{2}}$,
we have
$\|\boldsymbol{\beta}_{l}\|_{2}=\dfrac{1}{\sqrt{(\boldsymbol{\beta}^{*}_{l})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}}}$. It follows that,

$\displaystyle|\dfrac{1}{\|\boldsymbol{\beta}_{l}\|_{2}}-\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}|=|\sqrt{(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}}-\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}|$ (S80)
$\displaystyle\leq$
$\displaystyle|\sqrt{(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}}-\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}|+|\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}({\bm{\Sigma}}_{\mathbf{X}}-\widehat{{\bm{\Sigma}}}_{\mathbf{X}})\tilde{\boldsymbol{\beta}}_{l}|/(\sqrt{\tilde{\boldsymbol{\beta}}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}}+\sqrt{\tilde{\boldsymbol{\beta}}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}})$ (S81)
$\displaystyle\leq$
$\displaystyle\dfrac{|(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}|}{\sqrt{(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}}+\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}}+\dfrac{s\epsilon}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}.$
(S82)

Because $\sqrt{(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}}+\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}\geq\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})$,
it suffices to find a bound for $|(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}|$.

$\displaystyle|(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}|\leq|(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}|+s\epsilon$
(S83) $\displaystyle\leq$
$\displaystyle|(\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}|+|\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}(\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l})|+s\epsilon$
(S85) $\displaystyle\leq$
$\displaystyle\sqrt{(\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}(\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l})\cdot(\boldsymbol{\beta}_{l}^{*})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}}+\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}\cdot(\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l})^{\mathrm{\tiny
T}}{\bm{\Sigma}}_{\mathbf{X}}(\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l})}$
$\displaystyle+s\epsilon$ $\displaystyle\leq$ $\displaystyle
2\lambda_{\max}({\bm{\Sigma}}_{\mathbf{X}})\cdot\|\boldsymbol{\beta}_{l}^{*}-\tilde{\boldsymbol{\beta}}_{l}\|_{2}+s\epsilon$
(S86) $\displaystyle\leq$
$\displaystyle\sqrt{2\\{1-\cos\Theta(\boldsymbol{\beta}^{*}_{l},\tilde{\boldsymbol{\beta}}_{l})\\}}+s\epsilon\leq\sqrt{2}|\sin\Theta(\boldsymbol{\beta}_{l}^{*},\tilde{\boldsymbol{\beta}}_{l})|+s\epsilon\leq
Cs\epsilon,$ (S87)

which also implies that
$\dfrac{1}{\sqrt{\tilde{\boldsymbol{\beta}}_{l}^{\mathrm{\tiny
T}}\widehat{{\bm{\Sigma}}}_{\mathbf{X}}\tilde{\boldsymbol{\beta}}_{l}}}\leq\dfrac{1}{\boldsymbol{\beta}_{l}^{*}{\bm{\Sigma}}_{\mathbf{X}}\boldsymbol{\beta}_{l}^{*}-Cs\epsilon}\leq\dfrac{2}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}$
if $s\epsilon\leq\dfrac{\lambda_{\min({\bm{\Sigma}}_{\mathbf{X}})}}{2}$.
Finally, by (S65) we have the desired conclusion. ∎

Now we define $cr_{k}(s)=\inf_{F:|F|\leq
s}cr(\mathbf{M}_{k,F},{\bm{\Sigma}}_{F})$. We have the following lemma.

######  Lemma S15.

Assume that
$|\sin\Theta(\hat{\boldsymbol{\beta}}_{l},\boldsymbol{\beta}_{l})|<Cs\epsilon$
for any $l<k$. If
$\dfrac{2s\epsilon}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}+\dfrac{2s\epsilon}{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})\lambda_{1}}<\min\\{\frac{1}{2},\dfrac{\Delta}{\lambda_{1}+\lambda_{2}},\dfrac{\lambda_{\min}({\bm{\Sigma}}_{\mathbf{X}})}{2},\dfrac{\Delta}{2(1+\lambda_{1}^{2})}cr_{k}(s)\\}$,
we have that
$\sin\Theta(\hat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k})\leq
Cs\epsilon$.

###### Proof of Lemma S15.

Combine Lemma S14 with Lemma S3 and we have the desired conclusion. ∎

###### Proof of Theorem 3.

Combining Lemma S13 with Lemma S15, we have that if
$\|\widehat{\mathbf{M}}-\mathbf{M}\|_{\max}\leq\epsilon$,
$\|\widehat{{\bm{\Sigma}}}_{\mathbf{X}}-{\bm{\Sigma}}_{\mathbf{X}}\|_{\max}\leq\epsilon$,
then $|\sin\Theta(\hat{\boldsymbol{\beta}}_{k},\boldsymbol{\beta}_{k})|\leq
Cs\epsilon,k=1,\ldots,K$. By Theorem 1 we have the desired conclusion. ∎