# Minimax Estimation of Linear Functions of Eigenvectors
in the Face of Small Eigen-Gaps

Gen Li Department of Statistics and Data Science, The Wharton School,
University of Pennsylvania, Philadelphia, PA 19104, USA; email:
<EMAIL_ADDRESS>Changxiao Cai Department of Biostatistics,
University of Pennsylvania, Philadelphia, PA 19104, USA; email:
<EMAIL_ADDRESS>H. Vincent Poor Department of Electrical
and Computer Engineering, Princeton University, Princeton, NJ 08544, USA;
email<EMAIL_ADDRESS>Yuxin Chen11footnotemark: 1

Eigenvector perturbation analysis plays a vital role in various data science
applications. A large body of prior works, however, focused on establishing
$\ell_{2}$ eigenvector perturbation bounds, which are often highly inadequate
in addressing tasks that rely on fine-grained behavior of an eigenvector. This
paper makes progress on this by studying the perturbation of linear functions
of an unknown eigenvector. Focusing on two fundamental problems — matrix
denoising and principal component analysis — in the presence of Gaussian
noise, we develop a suite of statistical theory that characterizes the
perturbation of arbitrary linear functions of an unknown eigenvector. In order
to mitigate a non-negligible bias issue inherent to the natural “plug-in”
estimator, we develop de-biased estimators that (1) achieve minimax lower
bounds for a family of scenarios (modulo some logarithmic factor), and (2) can
be computed in a data-driven manner without sample splitting. Noteworthily,
the proposed estimators are nearly minimax optimal even when the associated
eigen-gap is substantially smaller than what is required in prior statistical
theory.

Keywords: linear forms of eigenvectors, matrix denoising, principal component
analysis, bias correction, small eigen-gap

###### Contents

  1. 1 Introduction
  2. 2 Problem formulation
    1. 2.1 Matrix denoising
    2. 2.2 Principal component analysis and covariance estimation
  3. 3 Main results
    1. 3.1 Matrix denoising
    2. 3.2 Principal component analysis
  4. 4 Related works
  5. 5 Analysis
    1. 5.1 Master theorems
    2. 5.2 Analysis for matrix denoising
      1. 5.2.1 Proof of eigenvalue perturbation theory (Theorem 7)
      2. 5.2.2 Proof of eigenvector perturbation theory (Theorem 1)
    3. 5.3 Analysis for principal component analysis
      1. 5.3.1 Proof of eigenvalue perturbation theory (Theorem 8)
      2. 5.3.2 Proof of eigenvector perturbation theory (Theorem 3)
  6. 6 Discussion
  7. A Proofs of master theorems
    1. A.1 Proof of Theorem 5
    2. A.2 Proof of Theorem 6
  8. B Proofs of auxiliary lemmas for Theorem 7
    1. B.1 Proof of Lemma 1
    2. B.2 Proof of Lemma 2
    3. B.3 Proof of Lemma 12
  9. C Proofs of auxiliary lemmas for Theorem 1
    1. C.1 Proof of Lemma 3
      1. C.1.1 Proof of Lemma 13
    2. C.2 Proof of Lemma 4
      1. C.2.1 Proof of Lemma 14
    3. C.3 Proof of Lemma 5
    4. C.4 Proof of Lemma 6
  10. D Proof of auxiliary lemmas in the analysis for Theorem 3
    1. D.1 Proof of Lemma 7
    2. D.2 Proof of Lemma 8
    3. D.3 Proof of Lemma 9
      1. D.3.1 Proof of Lemma 15
      2. D.3.2 Proof of Lemma 16
      3. D.3.3 Proof of Lemma 17
    4. D.4 Proof of Lemma 10
  11. E Proof for minimax lower bounds (Theorem 4)
    1. E.1 Proof of the lower bound (E.1)
    2. E.2 Proof of the lower bound (E.2)
  12. F Proof for the lower bound of the plug-in estimator (Theorem 2)
  13. G Technical lemmas
    1. G.1 Proof of Lemma 18
    2. G.2 Proof of Lemma 19
    3. G.3 Proof of Lemma 20

##  1 Introduction

A variety of large-scale data science applications involve extracting
actionable knowledge from the eigenvectors of a certain low-rank matrix.
Representative examples include principal component analysis (PCA) (Johnstone,
2001), phase synchronization (Singer, 2011), clustering in mixture models
(Löffler et al., 2019), community recovery (Abbe et al., 2020b; Lei and
Rinaldo, 2015), to name just a few. In reality, it is often the case that one
only observes a randomly corrupted version of the low-rank matrix of interest,
and has to retrieve information from the “empirical” eigenvectors (i.e., the
eigenvectors of the observed noisy matrix). This motivates the studies of
eigenvector perturbation theory from statistical viewpoints, with particular
emphasis on high-dimensional scenarios (Chen et al., 2021b). In the current
paper, we seek to further expand such a statistical theory, focusing on the
following two concrete models.

  * •

_Matrix denoising under i.i.d. Gaussian noise_. Let
$\bm{M}^{\star}\in\mathbb{R}^{n\times n}$ be an unknown rank-$r$ symmetric
matrix whose $l$-th eigenvector (resp. eigenvalue) is $\bm{u}_{l}^{\star}$
(resp. $\lambda_{l}^{\star}$). What we have observed is a corrupted version
$\bm{M}=\bm{M}^{\star}+\bm{H}$ of $\bm{M}^{\star}$, where
$\bm{H}=[H_{i,j}]_{1\leq i,j\leq n}$ represents a symmetric Gaussian random
matrix with
$H_{i,j}\overset{\mathsf{i.i.d.}}{\sim}\mathcal{N}(0,\sigma^{2}),i>j$ and
$H_{i,i}\overset{\mathsf{i.i.d.}}{\sim}\mathcal{N}(0,2\sigma^{2})$. The aim is
to estimate $\bm{u}_{l}^{\star}$ based on the $l$-th eigenvector of the data
matrix $\bm{M}$.

  * •

_Principal component analysis (PCA) and covariance estimation_. Imagine that
we have collected $n$ independent $p$-dimensional sample vectors
$\bm{s}_{i}\overset{\mathsf{ind.}}{\sim}\mathcal{N}(\bm{0},\bm{\Sigma})$,
$1\leq i\leq n$. Suppose that the underlying covariance matrix enjoys a
“spiked” structure $\bm{\Sigma}=\bm{\Sigma}^{\star}+\sigma^{2}\bm{I}_{p}$,
where $\bm{\Sigma}^{\star}\succeq\bm{0}$ is an unknown rank-$r$ matrix whose
$l$-th eigenvector (resp. eigenvalue) is given by $\bm{u}_{l}^{\star}$ (resp.
$\lambda_{l}^{\star}$). We seek to estimate $\bm{u}_{l}^{\star}$ by examining
the $l$-th eigenvector of the sample covariance matrix
$\frac{1}{n}\sum_{i=1}^{n}\bm{s}_{i}\bm{s}_{i}^{\top}$.

While a large body of prior literature has investigated eigenvector
perturbation theory for the aforementioned two models, the majority of past
works focused on $\ell_{2}$ statistical analysis, namely, quantifying the
$\ell_{2}$ estimation error of $\bm{u}_{l}$ when it is employed to estimate
$\bm{u}_{l}^{\star}$. Such $\ell_{2}$ perturbation theory, however, is often
too coarse if the ultimate goal is to retrieve fine-grained information from
the eigenvector of interest, say, some linear function of the eigenvector
$\bm{u}_{l}^{\star}$ (e.g., the Fourier transform of or any given entry of
$\bm{u}_{l}^{\star}$). Motivated by the inadequacy of existing $\ell_{2}$
theory, we seek to investigate how to faithfully estimate linear functionals
of the eigenvectors — that is, $\bm{a}^{\top}\bm{u}_{l}^{\star}$ for some
vector $\bm{a}\in\mathbb{R}^{n}$ given _a priori_. Towards achieving this
goal, two challenges stand out, which merit careful thinking.

  * •

_The need of bias correction_. A natural strategy towards estimating the
linear form $\bm{a}^{\top}\bm{u}_{l}^{\star}$ is to invoke the naive “plug-in”
estimator $\bm{a}^{\top}\bm{u}_{l}$. However, it has already been pointed out
in the literature (e.g., Koltchinskii et al. (2016); Koltchinskii and Xia
(2016)) that the plug-in estimator might suffer from a non-negligible bias.
This calls for careful designs of algorithms that allow for proper bias
correction in a data-driven yet efficient manner.

  * •

_How to cope with small eigen-gaps_. When estimating the eigenvector
$\bm{u}_{l}^{\star}$, most prior works require the associated eigen-gap
$\min_{i\neq l}|\lambda_{i}^{\star}-\lambda_{l}^{\star}|$ to exceed the
spectral norm of the perturbation matrix (i.e., $\bm{H}$ in the matrix
denoising case and
$\frac{1}{n}\sum_{i}\bm{s}_{i}\bm{s}_{i}^{\top}-\bm{\Sigma}$ in the PCA
setting) (Davis and Kahan, 1970; Chen et al., 2021b). However, there is no
lower bound in the literature that precludes us from achieving faithful
estimation when the eigen-gap violates such requirements. It would thus be of
great interest to understand the statistical limits when the eigen-gap of
interest is particularly small.

##### Main contributions.

This paper investigates estimating the linear form
$\bm{a}^{\top}\bm{u}_{i}^{\star}$ for the aforementioned two statistical
models under Gaussian noise, with particular emphasis on those scenarios with
small eigen-gaps. Our main contributions are summarized below.

  1. 1.

We develop fine-grained perturbation analysis for linear forms of
eigenvectors, which is valid even when the eigen-gap $\min_{i\neq
l}|\lambda_{i}^{\star}-\lambda_{l}^{\star}|$ is substantially smaller than the
spectral norm of the perturbation matrix. This eigen-gap condition
significantly improves upon what is required in prior theory.

  2. 2.

The natural “plug-in” estimator suffers from a non-negligible bias issue,
which is particularly severe when the associated eigen-gap is small. To
address this issue, we put forward a de-biased estimator for
$\bm{a}^{\top}\bm{u}_{l}^{\star}$ by multiplying the plug-in estimator by a
correction factor, which can be computed in a data-driven manner without the
need of sample splitting. The proposed estimator provably achieves enhanced
estimation accuracy compared to the plug-in estimator, and is shown to be
minimax optimal (up to some logarithmic factor) for a broad class of
scenarios.

##### Organization.

The rest of this paper is organized as follows. In Section 2, we formulate the
problem precisely and introduce basic definitions. Section 3 presents our main
theoretical findings, whereas Section 4 provides a non-exhaustive overview of
prior works. The analysis strategy of our main theorems is outlined in Section
5. The detailed proofs and auxiliary lemmas are postponed to the appendix. We
conclude this paper with a discussion of future directions in Section 6.

##### Notation.

For any vector $\bm{v}$, we denote by $\|\bm{v}\|_{2}$ and
$\|\bm{v}\|_{\infty}$ its $\ell_{2}$ norm and $\ell_{\infty}$ norm,
respectively; for any vectors $\bm{v}$ and $\bm{u}$, we use
$\langle\bm{v},\,\bm{u}\rangle$ to represent their inner product. For any
matrix $\bm{M}$, we let $\left\|\bm{M}\right\|$ and
$\left\|\bm{M}\right\|_{\mathrm{F}}$ denote the spectral norm and the
Frobenius norm of $\bm{M}$, respectively. For any matrix $\bm{U}$ whose
columns are orthonormal, we use $\bm{U}^{\perp}$ to denote a matrix whose
columns form an orthonormal basis of the orthogonal complement of the column
space of $\bm{U}$, and let
$\mathcal{P}_{\bm{U}}(\bm{M})=\bm{U}\bm{U}^{\top}\bm{M}$ be the Euclidean
projection of a matrix $\bm{M}$ onto the column space of $\bm{U}$. For any two
random matrices $\bm{Z}$ and $\bm{X}$, the notation
$\bm{Z}\overset{\mathrm{d}}{=}\bm{X}$ means $\bm{Z}$ and $\bm{X}$ are
identical in distribution. For notational simplicity, we write $[n]$ for the
set $\\{1,\cdots,n\\}$. For any $a,b\in\mathbb{R}$, we introduce the notation
$a\land b=\min\\{a,b\\}$, $a\lor b=\max\\{a,b\\}$, and $\min|a\pm
b|=\min\\{|a-b|,|a+b|\\}$. We denote by
$\mathcal{B}_{r}(\bm{z})\coloneqq\\{\bm{x}\,\mid\,\|\bm{x}-\bm{z}\|_{2}\leq
r\\}$ the ball of radius $r$ centered at $\bm{z}$. Throughout the paper, we
denote by $f(n)\lesssim g(n)$ or $f(n)=O(g(n))$ the condition $|f(n)|\leq
Cg(n)$ for some universal constant $C>0$ when $n$ is sufficiently large; we
use $f(n)\gtrsim g(n)$ or $f(n)=\Omega(g(n))$ to indicate that $f(n)\geq
C|g(n)|$ for some universal constant $C>0$ when $n$ is sufficiently large; and
we also use $f(n)\asymp g(n)$ or $f(n)=\Theta(g(n))$ to indicate that
$f(n)\lesssim g(n)$ and $f(n)\gtrsim g(n)$ hold simultaneously. In addition,
the standard notation $\widetilde{O}(g(n))$ (resp. $\widetilde{\Omega}(g(n))$)
is similar to $O(g(n))$ (resp. $\Omega(g(n))$) except that it hides the
logarithmic dependency. The notation $f(n)=o(g(n))$ means that
$\lim_{n\rightarrow\infty}f(n)/g(n)=0$, and $f(n)\gg g(n)$ (resp. $f(n)\ll
g(n)$) means that there exists some large (resp. small) constant $c_{1}>0$
(resp. $c_{2}>0$) such that $f(n)\geq c_{1}g(n)$ (resp. $f(n)\leq c_{2}g(n)$).
Finally, for any $1\leq l\leq r$, we set the expression $\sum_{k\neq l,1\leq
k\leq r}g(k)$ to be zero for any $g(\cdot)$ if $r=1$ (that is, the case where
no $k$ satisfies the requirement in the summation).

##  2 Problem formulation

###  2.1 Matrix denoising

Suppose that we are interested in a symmetric matrix
$\bm{M}^{\star}=[M_{i,j}^{\star}]_{1\leq i,j\leq n}\in\mathbb{R}^{n\times n}$
with eigen-decomposition

$\bm{M}^{\star}=\sum_{i=1}^{r}\lambda_{i}^{\star}\bm{u}_{i}^{\star}\bm{u}_{i}^{\star\top}=:\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top},$
(2.1)

where the $\bm{u}_{i}^{\star}$’s are orthonormal. Here,
$\\{\lambda_{i}^{\star}\\}$ denotes the set of non-zero eigenvalues of
$\bm{M}^{\star}$, and $\bm{u}_{i}^{\star}$ indicates the (normalized)
eigenvector associated with $\lambda_{i}^{\star}$. It is assumed throughout
that

$\lambda_{\min}^{\star}=|\lambda_{r}^{\star}|\leq\cdots\leq|\lambda_{1}^{\star}|=\lambda_{\max}^{\star},$
(2.2)

and the condition number of $\bm{M}^{\star}$ is defined as

$\kappa:=\frac{\lambda_{\max}^{\star}}{\lambda_{\min}^{\star}}.$ (2.3)

In addition, for any $1\leq l\leq r$, we introduce an eigen-gap (or eigenvalue
separation) metric that quantifies the distance between the eigenvalue
$\lambda_{l}^{\star}$ and the remaining spectrum:

$\Delta_{l}^{\star}\coloneqq\begin{cases}\min_{k:\,k\neq l,\,1\leq k\leq
r}\big{|}\lambda_{l}^{\star}-\lambda_{k}^{\star}\big{|},&\text{if}\quad
r>1,\\\ \lambda_{\max}^{\star},&\text{if}\quad r=1,\end{cases}$ (2.4)

which plays a crucial role in our perturbation theory.

What we have observed is a randomly corrupted data matrix
$\bm{M}=[M_{i,j}]_{1\leq i,j\leq n}$ as follows

$\bm{M}=\bm{M}^{\star}+\bm{H},$ (2.5)

where $\bm{H}=[H_{i,j}]_{1\leq i,j\leq n}$ represents a symmetric noise matrix
with independent random entries

$H_{i,j}\overset{\mathrm{ind.}}{\sim}\begin{cases}\mathcal{N}(0,2\sigma^{2}),&i=j,\\\
\mathcal{N}(0,\sigma^{2}),&i>j.\end{cases}$ (2.6)

Throughout this paper, we denote by $\lambda_{l}$ the $l$-th largest
eigenvalue (in magnitude) of $\bm{M}$, and let $\bm{u}_{l}$ represent the
associated eigenvector of $\bm{M}$. Our goal is to estimate linear functionals
of an eigenvector $\bm{u}_{l}^{\star}$ — that is,
$\bm{a}^{\top}\bm{u}_{l}^{\star}\,(1\leq l\leq r)$ for some fixed vector
$\bm{a}\in\mathbb{R}^{n}$ — based on the observed noisy data $\bm{M}$.

###  2.2 Principal component analysis and covariance estimation

Turning to principal component analysis (PCA) or covariance estimation, we
concentrate on the following spiked covariance model. Imagine that we have
collected a sequence of $n$ i.i.d. zero-mean Gaussian sample vectors in
$\mathbb{R}^{p}$ as follows

$\bm{s}_{i}\overset{\mathrm{ind.}}{\sim}\mathcal{N}\left(\bm{0},\bm{\Sigma}\right),\qquad
1\leq i\leq n,$

where

$\bm{\Sigma}=\bm{\Sigma}^{\star}+\sigma^{2}\bm{I}_{p}\in\mathbb{R}^{p\times
p}$

denotes the covariance matrix. Here and throughout, we assume that the “spiked
component” $\bm{\Sigma}^{\star}$ of $\bm{\Sigma}$ is an unknown rank-$r$
matrix with eigen-decomposition

$\displaystyle\bm{\Sigma}^{\star}$
$\displaystyle=\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}=\sum_{i=1}^{r}\lambda_{i}^{\star}\bm{u}_{i}^{\star}\bm{u}_{i}^{\star\top}\succeq\bm{0},$

where $\lambda_{i}^{\star}$ denotes the $i$-th largest eigenvalue of
$\bm{\Sigma}^{\star}$, with $\bm{u}_{i}^{\star}$ representing the associated
eigenvector. Akin to the matrix denoising case, we assume

$0<\lambda_{\min}^{\star}=\lambda_{r}^{\star}\leq\cdots\leq\lambda_{1}^{\star}=\lambda_{\max}^{\star},$

and introduce the condition number
$\kappa:=\lambda_{\max}^{\star}/\lambda_{\min}^{\star}$ and the eigen-
separation metric

$\Delta_{l}^{\star}\coloneqq\begin{cases}\min_{k:\,k\neq l,\,1\leq k\leq
r}\big{|}\lambda_{l}^{\star}-\lambda_{k}^{\star}\big{|},&\text{if}\quad
r>1,\\\ \lambda_{\max}^{\star},&\text{if}\quad r=1.\end{cases}$ (2.7)

Given a fixed vector $\bm{a}\in\mathbb{R}^{p}$, our aim is to develop a
reliable estimate of the linear functional $\bm{a}^{\top}\bm{u}_{l}^{\star}$
of an eigenvector $\bm{u}_{l}^{\star}$ ($1\leq l\leq r$), on the basis of the
sample vectors $\\{\bm{s}_{i}\\}_{1\leq i\leq n}$ (or the sample covariance
matrix $\frac{1}{n}\sum_{i=1}^{n}\bm{s}_{i}\bm{s}_{i}^{\top}$).

##  3 Main results

With the above description of the problem settings in place, we are ready to
present our findings concerning eigenvector perturbation. Given that we cannot
distinguish $\bm{u}_{l}^{\star}$ and $-\bm{u}_{l}^{\star}$ based on the
observed matrix, the error of an estimator $u_{\bm{a}}$ for estimating
$\bm{a}^{\top}\bm{u}_{l}^{\star}$ shall be measured via the following metric
that accounts for such a global ambiguity issue:

$\mathsf{dist}\left(u_{\bm{a}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)\coloneqq\min\left\\{\big{|}u_{\bm{a}}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\right\\}=\min\left\\{\big{|}u_{\bm{a}}-\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|},\big{|}u_{\bm{a}}+\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\right\\}.$
(3.1)

###  3.1 Matrix denoising

We begin with the matrix denoising problem introduced in Section 2.1.
Recalling that $\bm{u}_{l}$ is the eigenvector of $\bm{M}$ associated with
$\lambda_{l}$ ($1\leq l\leq n$), we investigate the following two estimators
when estimating the linear function $\bm{a}^{\top}\bm{u}_{l}^{\star}$.

  * •

A plug-in estimator:

$u_{\bm{a}}^{\mathsf{plugin}}\coloneqq\bm{a}^{\top}\bm{u}_{l};$ (3.2a)

  * •

A modified estimator that we propose (which we shall refer to as a _de-biased
estimator_ from now on):

$\displaystyle
u_{\bm{a}}^{\mathsf{debiased}}\coloneqq\sqrt{1+b_{l}}\,\bm{a}^{\top}\bm{u}_{l}\qquad\text{with}\quad
b_{l}$ $\displaystyle\coloneqq\sum_{i:\,r<i\leq
n}\frac{\sigma^{2}}{(\lambda_{l}-\lambda_{i})^{2}},$ (3.2b)

where $b_{l}$ can be computed directly using the eigenvalues of $\bm{M}$
without the need of sample splitting. As we shall see shortly, this new
estimator is put forward in order to remedy a non-negligible bias issue
underlying the naive plug-in estimator.

The following theorem quantifies the estimation errors for both of these
estimators.

######  Theorem 1 (Eigenvector perturbation).

Consider any $1\leq l\leq r$, and suppose that

$\sigma\sqrt{n}\leq c_{0}\lambda_{\min}^{\star},\qquad r\leq
c_{1}n/\log^{2}n\qquad\text{and}\qquad\Delta_{l}^{\star}>C_{0}\sigma\sqrt{r}\log
n$ (3.3)

for some sufficiently small (resp. large) constants $c_{0},c_{1}>0$ (resp.
$C_{0}>0$). Let $\bm{a}\in\mathbb{R}^{n}$ be any fixed vector with
$\|\bm{a}\|_{2}=1$. With probability at least $1-O(n^{-10}),$ the estimators
in (3.2) satisfy

$\displaystyle\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{plugin}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)$
$\displaystyle\lesssim E_{\mathsf{md},l}+\frac{\sigma^{2}n}{\lambda_{l}^{\star
2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|,$ (3.4a)
$\displaystyle\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{debiased}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)$
$\displaystyle\lesssim E_{\mathsf{md},l},$ (3.4b)

where $E_{\mathsf{md},l}$ is defined as

$\displaystyle E_{\mathsf{md},l}$ $\displaystyle\coloneqq\frac{\sigma^{2}r\log
n}{(\Delta_{l}^{\star})^{2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|+\sigma\sqrt{r\log\Big{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\Big{)}}\sum_{k:\,k\neq
l,1\leq k\leq
r}\frac{\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}{\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|}+\frac{\sigma\sqrt{\log\big{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\big{)}}}{\left|\lambda_{l}^{\star}\right|}.$
(3.5)

######  Remark 1.

While the rank $r$ of the true matrix $\bm{M}^{\star}$ might be unknown _a
prior_ in practice, it can often be estimated accurately in a data-driven
manner. For instance, under the model assumed herein, one might simply choose
$r$ by identifying the smallest (in magnitude) eigenvalue $\lambda_{l}$ that
is larger than $\lambda_{l+1}$ by an order of $\sigma\sqrt{n}$; see also Han
et al. (2019) for a different approach.

######  Remark 2.

While the quantity $b_{l}$ is provided in a data-driven manner (cf. (3.2b)),
we find it helpful to also make note of another expression derived from its
asymptotic limit. Specifically, the random matrix theory tells us that the
eigenvalues $\\{\lambda_{i}\\}_{r<i\leq n}$ of $\bm{M}$ obey the celebrated
semi-circular law asymptotically (see, e.g., Knowles and Yin (2013)), and
therefore the de-biased term $b_{l}$ satisfies (as $n$ grows):

$\displaystyle b_{l}=\sum_{i:\,r<i\leq
n}\frac{\sigma^{2}}{(\lambda_{l}-\lambda_{i})^{2}}$
$\displaystyle\,\approx\,\int_{-2}^{2}\frac{\sqrt{4-\lambda^{2}}}{2\pi\Big{(}\frac{\lambda_{l}}{\sigma\sqrt{n}}-\lambda\Big{)}^{2}}\mathrm{d}\lambda.$
(3.6)

##### Implications.

Theorem 1 develops statistical performance guarantees for the aforementioned
two estimators when estimating the linear form
$\bm{a}^{\top}\bm{u}_{l}^{\star}$ for a prescribed vector
$\bm{a}\in\mathbb{R}^{n}$. We now single out several main implications of our
results.

  * •

_Estimation guarantees in the face of a small eigen-gap_. In view of (3.3),
the eigen-gap $\Delta_{l}^{\star}$ is allowed to be substantially smaller than
the spectral norm $\|\bm{H}\|$ of the perturbation matrix. This stands in
stark contrast to, and significantly improves upon, the celebrated Davis-Kahan
$\sin\bm{\Theta}$ theorem that requires $\Delta_{l}^{\star}\gtrsim\|\bm{H}\|$
(Davis and Kahan, 1970; Chen et al., 2021b). To be more precise, recalling
from standard random matrix theory (Tao, 2012) that
$\|\bm{H}\|\asymp\sigma\sqrt{n}$ with high probability, one can compare our
result with classical matrix perturbation theory as follows

our eigen-gap requirement:
$\displaystyle\Delta_{l}^{\star}=\widetilde{\Omega}\left(\sigma\sqrt{r}\right);$
eigen-gap requirement in classical theory:
$\displaystyle\Delta_{l}^{\star}=\widetilde{\Omega}\left(\sigma\sqrt{n}\right).$

As a comparison, the prior work Bao et al. (2021) studied the distributions of
the singular vectors under the matrix denoising setting with $\sigma\asymp
n^{-1/2}$, provided that the eigen-gap exceeds $\Omega(1)$; our theory
improves their eigen-gap condition by a factor on the order of $\sqrt{n/r}$.

  * •

_Near minimaxity_. In order to assess the effectiveness of our proposed
estimator, it is helpful to compare the statistical guarantees in Theorem 1
with minimax lower bounds. Consider, for simplicity, the scenario where
$r=O(1)$ and $|\bm{a}^{\top}\bm{u}_{l}^{\star}|\leq(1-\epsilon)\|\bm{a}\|_{2}$
for any small non-zero constant $\epsilon>0$ (so that $\bm{a}$ is not
perfectly aligned with $\bm{u}_{l}^{\star}$), and an instance-dependent
minimax lower bound has been established in Cheng et al. (2021, Theorem 3) for
this scenario. Specifically, if we define the following two sets

$\displaystyle\mathcal{M}_{0}(\bm{M}^{\star})$
$\displaystyle:=\Big{\\{}\bm{A}\,\mid\,\mathsf{rank}(\bm{A})=r,\,\lambda_{i}(\bm{A})=\lambda_{i}^{\star}\,(1\leq
i\leq
r),\,\|\bm{A}-\bm{M}^{\star}\|_{\mathrm{F}}\leq\frac{\sigma}{2}\Big{\\}},$
$\displaystyle\mathcal{M}_{1}(\bm{M}^{\star})$
$\displaystyle:=\Big{\\{}\bm{A}\,\mid\,\mathsf{rank}(\bm{A})=r,\,\lambda_{i}(\bm{A})=\lambda_{i}^{\star}\,(1\leq
i\leq
r),\,\|\bm{u}_{l}(\bm{A})-\bm{u}_{l}^{\star}\|_{\mathrm{2}}\leq\frac{\sigma}{4\,|\lambda_{l}^{\star}|}\Big{\\}},$

then we necessarily have

$\displaystyle\inf_{u_{\bm{a},l}}\sup_{\bm{A}\in\mathcal{M}_{0}(\bm{M}^{\star})\cup\mathcal{M}_{1}(\bm{M}^{\star})}\mathbb{E}\Big{[}\mathsf{dist}\left(u_{\bm{a},l},\,\bm{a}^{\top}\bm{u}_{l}(\bm{A})\right)\Big{]}\gtrsim\frac{\sigma^{2}}{(\Delta_{l}^{\star})^{2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|+\sigma\max_{k:\,k\neq
l}\frac{\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}{\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|}+\frac{\sigma}{|\lambda_{l}^{\star}|},$
(3.8a) where the infimum is over all estimators $u_{\bm{a},l}$ based on the
observed matrix $\bm{M}=\bm{A}+\bm{H}$, and $\bm{u}_{l}(\bm{A})$ denotes the
$l$-th eigenvector of the matrix $\bm{A}$. In addition, the analysis for Cheng
et al. (2021, Theorem 3) directly implies that
$\displaystyle\inf_{u_{\bm{a},l}}\sup_{\bm{A}\in\mathcal{M}_{0}(\bm{M}^{\star})\cup\mathcal{M}_{1}(\bm{M}^{\star})}\mathbb{P}\bigg{\\{}\mathsf{dist}\left(u_{\bm{a},l},\,\bm{a}^{\top}\bm{u}_{l}(\bm{A})\right)\gtrsim\frac{\sigma^{2}}{(\Delta_{l}^{\star})^{2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|+\sigma\max_{k:\,k\neq
l}\frac{\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}{\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|}+\frac{\sigma}{|\lambda_{l}^{\star}|}\bigg{\\}}\geq\frac{1}{5}.$
(3.8b)

In comparison, our statistical guarantee (3.4b) for the proposed de-biased
estimator obeys

$\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{debiased}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)\leq\widetilde{O}\Bigg{(}\frac{\sigma^{2}}{(\Delta_{l}^{\star})^{2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|+\sigma\sum_{k:\,k\neq
l}\frac{\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}{\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|}+\frac{\sigma}{\left|\lambda_{l}^{\star}\right|}\Bigg{)}$

with high probability in this scenario, thereby matching the minimax lower
bound (3.8) (modulo some logarithmic factor). This confirms the near
optimality of our de-biased estimator when $r\asymp 1$.

##### Sub-optimality of the vanilla plug-in estimator.

Furthermore, Theorem 1 suggests that the statistical error (3.4a) of the
vanilla plug-in estimator $\bm{a}^{\top}\bm{u}_{l}$ might contain an
additional “bias” term

$E_{\mathsf{md},l}^{\mathsf{bias}}\coloneqq\frac{\sigma^{2}n}{\lambda_{l}^{\star
2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|$ (3.9)

when compared to that of the de-biased estimator (cf. (3.4b)). It is natural
to wonder if the theoretical guarantee of the plug-in estimator in (3.4a) is
tight or not. To answer the question, we develop the following lower bound on
the estimation error of the plug-in estimator $u_{\bm{a}}^{\mathsf{plugin}}$;
the proof is deferred to Appendix F.

######  Theorem 2.

Instate the assumptions of Theorem 1. Let $\bm{a}\in\mathbb{R}^{n}$ be any
fixed vector with $\|\bm{a}\|_{2}=1$. With probability at least $1/3$, the
plug-in estimator in (3.2) satisfies

$\displaystyle\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{plugin}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)\gtrsim\frac{\sigma^{2}n}{\lambda_{l}^{\star
2}}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|.$ (3.10)

In short, Theorem 2 demonstrates that it is impossible for the plug-in
estimator to get rid of this “bias” term (3.9). The influence of this extra
term becomes increasingly large and non-negligible as the correlation of
$\bm{a}$ and $\bm{u}_{l}^{\star}$ increases. To demonstrate the possibly
severe impact incurred by this additional term, let us examine a simple case
as follows.

  * •

_Example_. Suppose that $r=2$, $\lambda_{1}^{\star}=2\lambda_{2}^{\star}$ (so
that $\lambda_{1}^{\star}-\lambda_{2}^{\star}\asymp\lambda_{1}^{\star}$),
$|\bm{a}^{\top}\bm{u}_{l}^{\star}|\asymp 1$ and
$\sigma\sqrt{n}\asymp|\lambda_{1}^{\star}|$. As can be straightforwardly
verified, the main term (3.5) and the addition term (3.9) in this example
satisfy

$\displaystyle E_{\mathsf{md},1}$
$\displaystyle=\widetilde{O}\bigg{(}\frac{\sigma^{2}}{\lambda_{1}^{\star
2}}\left|\bm{a}^{\top}\bm{u}_{1}^{\star}\right|+\frac{\sigma}{|\lambda_{1}^{\star}|}\left|\bm{a}^{\top}\bm{u}_{2}^{\star}\right|+\frac{\sigma}{|\lambda_{1}^{\star}|}\bigg{)}=\widetilde{O}\bigg{(}\frac{\sigma^{2}}{\lambda_{1}^{\star
2}}+\frac{\sigma}{|\lambda_{1}^{\star}|}\bigg{)}=\widetilde{O}\bigg{(}\frac{1}{\sqrt{n}}\bigg{)};$
$\displaystyle E_{\mathsf{md},1}^{\mathsf{bias}}$
$\displaystyle\asymp\frac{\sigma^{2}n}{\lambda_{1}^{\star
2}}\left|\bm{a}^{\top}\bm{u}_{1}^{\star}\right|\asymp 1.$

In other words, the additional bias term $E_{\mathsf{md},1}^{\mathsf{bias}}$
could be a factor of $\widetilde{O}(\sqrt{n})$ times larger than the main term
$E_{\mathsf{md},1}$ in this case, and cannot be neglected.

The above discussion reveals the necessity of proper bias correction in order
to mitigate the undesired effect of the bias term
$E_{\mathsf{md},l}^{\mathsf{bias}}$. Aimed at addressing this issue, our de-
biased estimator $u_{\bm{a}}^{\mathsf{debiased}}$ compensates for the bias
term $E_{\mathsf{md},l}^{\mathsf{bias}}$ by properly rescaling the plug-in
estimator by a data-driven correction factor $\sqrt{1+b_{l}}$. Note that when
the signal-to-noise ratio is sufficiently large such that
$|\lambda_{l}^{\star}|\gtrsim\sigma n$, then $E_{\mathsf{md},l}$ becomes the
dominant term in the error bound; in such a case, there is no need for bias
correction.

##### Comparisons with prior works.

While estimation of linear forms of eigenvectors remains largely under-
explored in the literature, a small number of prior works have studied this
problem or its variants. Among them, perhaps the one that is the closest to
the current paper is Koltchinskii and Xia (2016), which considered estimating
linear forms of singular vectors under i.i.d. Gaussian noise. In what follows,
we briefly compare our result with Koltchinskii and Xia (2016), focusing on
the setting where the ground-truth matrix is symmetric (so that the
eigenvectors and the singular vectors become identical up to global signs).

  * •

To begin with, the theory in Koltchinskii and Xia (2016, Theorem 1.3) operates
under the assumption

$\Delta_{l}^{\star}=\Omega\big{(}\mathbb{E}[\|\bm{H}\|]\big{)}=\Omega(\sigma\sqrt{n}),$

which is $\widetilde{O}\big{(}\sqrt{n/r}\big{)}$ times more stringent than the
eigen-gap condition imposed in our theory (see (3.7)).

  * •

The estimation bias of the plug-in estimator was already pointed out in
Koltchinskii and Xia (2016). However, the approach proposed in Koltchinskii
and Xia (2016) required additional independent copies of $\bm{M}$ in order to
estimate — and hence correct — the bias effect (see Koltchinskii and Xia
(2016, Section 1)). By contrast, our de-biased estimator does not require an
additional set of data samples and allows one to use all available information
fully.

  * •

Next, we compare our theoretical guarantee with the one developed for the de-
biased estimator $u_{\bm{a}}^{\mathsf{debiased,KD}}$ proposed in Koltchinskii
and Xia (2016). When $r\asymp 1$, Koltchinskii and Xia (2016, Theorem 1.3)
asserts that

$\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{debiased,KD}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)\leq\widetilde{O}\bigg{(}\frac{\sigma}{\Delta_{l}^{\star}}\bigg{)}\eqqcolon
E_{\mathsf{md},l}^{\mathsf{KD}},$

provided that $\Delta_{l}^{\star}\gtrsim\sigma\sqrt{n}$. This result, however,
might fall short of attaining minimax optimality. More specifically, comparing
our error bound $E_{\mathsf{md},l}$ (cf. (3.5)) with
$E_{\mathsf{md},l}^{\mathsf{KD}}$ makes clear that the theoretical gain is on
the order of

$\frac{E_{\mathsf{md},l}^{\mathsf{KD}}}{E_{\mathsf{md},l}}=\widetilde{O}\left(\frac{\Delta_{l}^{\star}}{\sigma\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|}\,\land\,\frac{1}{\sum_{k:k\neq
l}\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}\,\land\,\frac{\left|\lambda_{l}^{\star}\right|}{\Delta_{l}^{\star}}\right).$

For concreteness, consider the case with $r\asymp 1$,
$|\bm{a}^{\top}\bm{u}_{k}^{\star}|\asymp 1/\sqrt{n}$ for all $k\neq l$,
$\Delta_{l}^{\star}\asymp\left|\lambda_{l}^{\star}\right|/\sqrt{n}$, and
$\Delta_{l}^{\star}\asymp\sigma\sqrt{n}$, thus leading to the gain

$\frac{E_{\mathsf{md},l}^{\mathsf{KD}}}{E_{\mathsf{md},l}}=\widetilde{O}\left(\sqrt{n}\right).$

In other words, our results might lead to considerable theoretical improvement
over Koltchinskii and Xia (2016) in the presence of a small eigen-gap.

######  Remark 3.

Note that the case $|\bm{a}^{\top}\bm{u}_{k}^{\star}|\asymp 1/\sqrt{n}$ is of
particular interest if one studies entrywise statistical performance; namely,
when $\bm{a}$ is taken to be the standard basis (i.e. $\bm{a}=\bm{e}_{i}$ for
some $i\in[n]$) and when the energy of $\bm{u}_{k}^{\star}$ is more or less
spread out across all entries (i.e.
$\|\bm{u}_{k}^{\star}\|_{\infty}\asymp\|\bm{u}_{k}^{\star}\|_{2}/\sqrt{n}$).

###  3.2 Principal component analysis

Next, we turn attention to the problem of principal component analysis as
formulated in Section 2.2. Denote by

$\bm{S}=[\bm{s}_{1},\cdots,\bm{s}_{n}]\in\mathbb{R}^{p\times n}$

the data matrix whose columns consist of i.i.d. samples
$\bm{s}_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(\bm{0},\bm{\Sigma})$,
and let $\lambda_{l}$ represent the $l$-th largest eigenvalue of
$\frac{1}{n}\bm{S}\bm{S}^{\top}$ with associated eigenvector $\bm{u}_{l}$. Our
focus is the following two estimators aimed at estimating the linear form
$\bm{a}^{\top}\bm{u}_{l}^{\star}$ $(1\leq l\leq r)$.

  * •

A plug-in estimator:

$u_{\bm{a}}^{\mathsf{plugin}}\coloneqq\bm{a}^{\top}\bm{u}_{l};$ (3.11a)

  * •

A “de-biased” estimator:

$u_{\bm{a}}^{\mathsf{debiased}}\coloneqq\sqrt{1+c_{l}}\,\bm{a}^{\top}\bm{u}_{l}.$
(3.11b)

Here, $c_{l}$ is a quantity that can be directly computed using the spectrum
of $\frac{1}{n}\bm{S}\bm{S}^{\top}$ as follows:

$c_{l}\coloneqq\begin{dcases}\frac{\lambda_{l}}{n+\sum_{i:\,r<i\leq
n}\frac{\lambda_{i}}{\lambda_{l}-\lambda_{i}}}\sum\limits_{i:\,r<i\leq
n}\frac{\lambda_{i}}{(\lambda_{l}-\lambda_{i})^{2}},&\text{if }n\geq p,\\\
\frac{\frac{\sigma^{2}p}{n}}{\lambda_{l}-\frac{\sigma^{2}p}{n}}+\frac{\lambda_{l}}{\lambda_{l}-\frac{\sigma^{2}p}{n}}\frac{\lambda_{l}}{n+\sum_{i:\,r<i\leq
n}\frac{\lambda_{i}}{\lambda_{l}-\lambda_{i}}}\sum\limits_{i:\,r<i\leq
n}\frac{\lambda_{i}-\frac{\sigma^{2}p}{n}}{(\lambda_{l}-\lambda_{i})^{2}},\qquad&\text{if
}n<p,\end{dcases}$ (3.12)

without any need of using sample splitting.

Akin to the matrix denoising counterpart, the plug-in estimator (3.11a) often
incurs some non-negligible estimation bias, which motivates the design of the
adjusted estimator (3.11b) to compensate for the bias.

We are now ready to present our statistical guarantees for the two estimators
introduced in (3.11).

######  Theorem 3.

Consider any $1\leq l\leq r$, and assume that

$\lambda_{\max}^{\star}\sqrt{\frac{r}{n}}+\sqrt{\lambda_{\max}^{\star}\sigma^{2}\frac{p}{n}}+\sigma^{2}\bigg{(}\frac{p}{n}+\sqrt{\frac{p}{n}}\bigg{)}\leq
C_{0}\frac{\lambda_{\min}^{\star}}{\log^{2}n}$ (3.13a)
$\text{and}\qquad\Delta_{l}^{\star}>C_{1}(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r}{n}}\log
n$ (3.13b)

hold for some sufficiently small (resp. large) constant $C_{0}>0$ (resp.
$C_{1}>0$). Consider any fixed vector $\bm{a}\in\mathbb{R}^{p}$ with
$\|\bm{a}\|_{2}=1$. Then with probability at least $1-O(n^{-10})$, the
estimators in (3.11) satisfy

$\displaystyle\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{plugin}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)$
$\displaystyle\lesssim
E_{\mathsf{PCA},l}+\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}p}{\lambda_{l}^{\star
2}n}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|,$ (3.14a)
$\displaystyle\mathsf{dist}\left(u_{\bm{a}}^{\mathsf{debiased}},\bm{a}^{\top}\bm{u}_{l}^{\star}\right)$
$\displaystyle\lesssim E_{\mathsf{PCA},l},$ (3.14b)

where the quantity $E_{\mathsf{PCA},l}$ is defined as

$\displaystyle E_{\mathsf{PCA},l}$
$\displaystyle\coloneqq\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})\,r\log
n}{(\Delta_{l}^{\star})^{2}n}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|+\sqrt{\frac{(\lambda_{\max}^{\star}+\sigma^{2})\,\sigma^{2}\kappa^{2}r}{\lambda_{l}^{\star
2}n}}\log^{2}n$ $\displaystyle\qquad+\sum_{k:k\neq
l}\frac{\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}{\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|\sqrt{n}}\sqrt{(\lambda_{l}^{\star}+\sigma^{2})(\lambda_{\max}^{\star}+\sigma^{2})(\kappa^{2}+r)\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}.$
(3.15)

######  Remark 4.

Akin to the matrix denoising case, while the expression of the de-biasing term
$c_{l}$ (cf. (3.12)) is fully data-driven and preferable in practice, we
remark that the Marchenko-Pastur law allows us to approximate the de-biasing
term $c_{l}$ as follows (as $n$ grows)

$c_{l}\leavevmode\nobreak\ \approx\leavevmode\nobreak\
\begin{dcases}\frac{\lambda_{l}}{1+\int\frac{\lambda}{\lambda_{l}-\lambda}\mu(\mathrm{d}\lambda)}\int\frac{\lambda}{(\lambda_{l}-\lambda)^{2}}\mu(\mathrm{d}\lambda),&\text{if
}n\geq p,\\\
\frac{\frac{\sigma^{2}p}{n}}{\lambda_{l}-\frac{\sigma^{2}p}{n}}+\frac{\lambda_{l}}{\lambda_{l}-\frac{\sigma^{2}p}{n}}\frac{\lambda_{l}}{1+\int\frac{\lambda}{\lambda_{l}-\lambda}\mu(\mathrm{d}\lambda)}\int\frac{\lambda-\frac{\sigma^{2}p}{n}}{(\lambda_{l}-\lambda)^{2}}\mu(\mathrm{d}\lambda),\qquad&\text{if
}n<p,\end{dcases}$ (3.16)

where

$\displaystyle\mu(\mathrm{d}\lambda)=\frac{n\sqrt{(\lambda_{+}-\lambda)(\lambda-\lambda_{-})}}{2\pi\sigma^{2}p\lambda}\mathds{1}\\{\lambda_{-}\leq\lambda\leq\lambda_{+}\\}\mathrm{d}\lambda\quad\text{with}\quad\lambda_{\pm}=\sigma^{2}(1\pm\sqrt{p/n})^{2}.$
(3.17)

##### Implications.

In short, Theorem 3 characterizes the statistical accuracy of both the plug-in
estimator and the modified de-biased estimator, the latter of which enjoys
improved statistical guarantees. In the sequel, we single out a few
implications of this result.

  * •

_Estimation guarantees._ Let us first assess the statistical error bound of
the de-biased estimator (namely, $E_{\mathsf{PCA},l}$ in (3.15)). For
simplicity of presentation, we shall focus on the case with $r,\kappa\asymp
1$, where the error term $E_{\mathsf{PCA},l}$ admits the following simpler
expression

$\displaystyle E_{\mathsf{PCA},l}$
$\displaystyle=\widetilde{\Theta}\bigg{(}\frac{(\lambda_{l}^{\star}+\sigma^{2})^{2}}{(\Delta_{l}^{\star})^{2}n}\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}+(\lambda_{l}^{\star}+\sigma^{2})\max_{k:k\neq
l}\frac{\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|}{\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|\sqrt{n}}+\frac{\sigma}{\lambda_{l}^{\star}\sqrt{n}}\sqrt{\lambda_{l}^{\star}+\sigma^{2}}\bigg{)}.$
(3.18)

In particular, the first term on the right-hand side of (3.18) quantifies the
role of the ground truth $\bm{a}^{\top}\bm{u}_{l}^{\star}$ on the estimation
error, which scales inverse quadratically in the eigen-gap
$\Delta_{l}^{\star}$; the second term on the right-hand side of (3.18) can be
understood as the additional interference resulting from the linear form of
other eigenvectors (namely, $\bm{a}^{\top}\bm{u}_{k}^{\star}$ for $k\neq l$),
which is inversely proportional to the corresponding eigen-gap
$\left|\lambda_{l}^{\star}-\lambda_{k}^{\star}\right|$.

  * •

_Relaxed eigen-gap condition_. To simplify discussions, let us again focus on
the case with $r,\kappa\asymp 1$ and omit logarithmic factors. Classical
matrix perturbation theory (e.g., the Davis-Kahan $\sin\bm{\Theta}$ theorem
(Davis and Kahan, 1970)) requires the eigen-gap to exceed the size of
perturbation, namely,

$\Delta_{l}^{\star}\gtrsim\Big{\|}\frac{1}{n}\bm{S}\bm{S}^{\top}-\bm{\Sigma}\Big{\|}.$

As it turns out, the eigen-gap requirement above leads to the following
condition (by invoking the high-probability bound to be presented shortly in
Lemma 7)

$\Delta_{l}^{\star}\gtrsim\frac{\lambda_{l}^{\star}}{\sqrt{n}}+\sqrt{\frac{\lambda_{l}^{\star}\sigma^{2}p}{n}}+\sigma^{2}\bigg{(}\sqrt{\frac{p}{n}}+\frac{p}{n}\bigg{)}=:\mathsf{gap}_{\mathsf{DK}}.$

In comparison, the eigen-gap condition (3.13b) in Theorem 3 reads

$\Delta_{l}^{\star}\gtrsim\frac{\lambda_{l}^{\star}+\sigma^{2}}{\sqrt{n}}=:\mathsf{gap}.$

To better understand and compare these two eigen-gap requirements, we shall
discuss them for a couple of distinct scenarios.

    * –

If
$\sigma^{2}\big{(}\sqrt{\frac{p}{n}}+\frac{p}{n}\big{)}\lesssim\lambda_{l}^{\star}\lesssim\sigma^{2}$
(the sample size needs to satisfy $n\geq p$ by the assumption (3.13a)), the
eigen-gap conditions above simplify to

$\mathsf{gap}\asymp\frac{\sigma^{2}}{\sqrt{n}}\qquad\text{and}\qquad\mathsf{gap}_{\mathsf{DK}}\asymp\sigma^{2}\sqrt{\frac{p}{n}}.$
$\Longrightarrow\qquad\frac{\mathsf{gap}_{\mathsf{DK}}}{\mathsf{gap}}\asymp\sqrt{p}.$

    * –

If $\sigma^{2}\lesssim\lambda_{l}^{\star}\lesssim\sigma^{2}p$, then one has

$\mathsf{gap}\asymp\frac{\lambda_{l}^{\star}}{\sqrt{n}}\qquad\text{and}\qquad\mathsf{gap}_{\mathsf{DK}}\asymp\sqrt{\frac{\lambda_{l}^{\star}\sigma^{2}p}{n}}+\frac{\sigma^{2}p}{n}.$

Comparing these two terms reveals that

$\frac{\mathsf{gap}_{\mathsf{DK}}}{\mathsf{gap}}\asymp\sqrt{\frac{\sigma^{2}p}{\lambda_{l}^{\star}}}\bigg{(}1+\sqrt{\frac{\sigma^{2}p}{\lambda_{l}^{\star}n}}\bigg{)}\overset{(\mathrm{i})}{\asymp}\sqrt{\frac{\sigma^{2}p}{\lambda_{l}^{\star}}}\overset{(\mathrm{ii})}{\gtrsim}1,$

where (i) holds due to the assumption (3.13a) and (ii) follows from the
condition $\lambda_{l}^{\star}\lesssim\sigma^{2}p$.

    * –

If $\lambda_{l}^{\star}\gtrsim\sigma^{2}p$, then it is straightforward to see
that

$\mathsf{gap}\asymp\mathsf{gap}_{\mathsf{DK}}\asymp\frac{\lambda_{l}^{\star}}{\sqrt{n}}.$

To sum up, our eigen-gap requirement (3.13b) is

$\Omega\left(\sqrt{p\Big{(}1\wedge\frac{\sigma^{2}}{\lambda_{l}^{\star}}\Big{)}}\vee
1\right)$

times less stringent than the one demanded in classical matrix perturbation
theory, thereby justifying the improvement of our results upon prior art. In
addition, we note that (Bao et al., 2022) also considered statistical
inference for principal components of spike covariance matrices; when
$\sigma=1$, the eigen-gap therein needs to satisfy $\Delta_{l}^{\star}\gtrsim
n^{-1/2+\epsilon}$ for an arbitrary small fixed constant $\epsilon>0$, thereby
leading to a more stringent condition than ours.

  * •

_Bias reduction_. Similar to the matrix denoising case, the plug-in estimator
$\bm{a}^{\top}\bm{u}_{l}$ suffers from the following extra “bias” term in
comparison to the de-biased estimator (3.14b):

$E_{\mathsf{pca},l}^{\mathsf{bias}}:=\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}p}{\lambda_{l}^{\star
2}n}\left|\bm{a}^{\top}\bm{u}_{l}^{\star}\right|.$ (3.19)

If $\bm{a}$ and $\bm{u}_{l}^{\star}$ are fairly correlated, then this
additional term becomes non-negligible and might affect the estimation
accuracy negatively. To see this, let us consider the following simple case.

    * –

_Example_. Assume that $r=2$, $\lambda_{1}^{\star}=2\lambda_{2}^{\star}>0$,
$|\bm{a}^{\top}\bm{u}_{1}^{\star}|\asymp 1$,
$\sigma^{2}\asymp\lambda_{1}^{\star}$ and $p\asymp n$. As can be
straightforwardly verified, the error terms (3.15) and (3.19) in this case
become

$\displaystyle E_{\mathsf{pca},1}$
$\displaystyle=\widetilde{O}\bigg{(}\frac{1}{n}\left|\bm{a}^{\top}\bm{u}_{1}^{\star}\right|+\frac{1}{\sqrt{n}}\left|\bm{a}^{\top}\bm{u}_{2}^{\star}\right|+\frac{1}{\sqrt{n}}\bigg{)}=\widetilde{O}\Big{(}\frac{1}{\sqrt{n}}\Big{)};$
$\displaystyle E_{\mathsf{pca},1}^{\mathsf{bias}}$
$\displaystyle\asymp\frac{p}{n}\left|\bm{a}^{\top}\bm{u}_{1}^{\star}\right|\asymp
1.$

In other words, the bias term $E_{\mathsf{pca},1}^{\mathsf{bias}}$ could be
$\sqrt{n}$ times larger than the error term
$E_{\mathsf{pca},1}^{\mathsf{bias}}$ (up to some logarithmic factor).

As a takeaway message from the above example, it is crucial to reduce the bias
incurred by $E_{\mathsf{pca},1}^{\mathsf{bias}}$. The proposed de-biased
estimator $u_{\bm{a}}^{\mathsf{debiased}}$ achieves bias reduction by
enlarging the plug-in estimator by a factor of $\sqrt{1+c_{l}}$, where $c_{l}$
is computable in a data-driven manner. It is worth noting that the factor
$c_{l}$ (cf. (3.12)) takes two different forms, depending on the relative
ratio between the sample size $n$ and the dimension $p$.

##### Minimax lower bounds and optimality.

In order to evaluate the tightness of our statistical guarantees, we develop
minimax lower bounds for PCA. Here and below, we denote by
$\bm{u}_{l}(\bm{\Sigma})\in\mathbb{R}^{p}$ the eigenvector associated with the
$l$-th largest eigenvalue of a matrix $\bm{\Sigma}$, and we define two sets of
covariance matrices as follows:

$\displaystyle\mathcal{M}_{1}(\bm{\Sigma}^{\star})$
$\displaystyle:=\left\\{\bm{\Sigma}\in\mathbb{R}^{p\times
p}\,\colon\,\mathsf{rank}(\bm{\Sigma})=r,\,\lambda_{i}(\bm{\Sigma})=\lambda_{i}^{\star}\,(1\leq
i\leq r),\,\|\bm{\Sigma}-\bm{\Sigma}^{\star}\|_{\mathrm{F}}\leq\max_{k:\,k\neq
l}\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})(\lambda_{k}^{\star}+\sigma^{2})}{n}}\right\\}.$
$\displaystyle\mathcal{M}_{2}(\bm{\Sigma}^{\star})$
$\displaystyle:=\left\\{\bm{\Sigma}\in\mathbb{R}^{p\times
p}\,\colon\,\mathsf{rank}(\bm{\Sigma})=r,\,\lambda_{i}(\bm{\Sigma})=\lambda_{i}^{\star}\,(1\leq
i\leq
r),\,\|\bm{u}_{l}(\bm{\Sigma})-\bm{u}_{l}^{\star}\|_{\mathrm{2}}\leq\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}\right\\}.$

######  Theorem 4.

Consider any fixed vector $\bm{a}\in\mathbb{R}^{p}$. For any given
$\bm{\Sigma}$, let $\\{\bm{s}_{i}\\}_{i=1}^{n}$ be independent samples
satisfying
$\bm{s}_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(\bm{0},\bm{\Sigma}+\sigma^{2}\bm{I}_{p})$.
Assume that the sample size obeys

$n\geq\left\\{\max_{k:\,k\neq
l}\frac{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|^{2}}\right\\}\vee\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}}.$ (3.20)

Then one has

$\displaystyle\inf_{u_{\bm{a},l}}\sup_{\bm{\Sigma}\in\mathcal{M}_{1}(\bm{\Sigma}^{\star})}\mathbb{E}\Big{[}\min\big{|}u_{\bm{a},l}\pm\bm{a}^{\top}\bm{u}_{l}(\bm{\Sigma})\big{|}\Big{]}$
$\displaystyle\qquad\gtrsim\max_{k:\,k\neq l,\,1\leq k\leq
r}\frac{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|^{2}\,n}\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}+\max_{k:\,k\neq
l,\,1\leq k\leq
r}\frac{\sqrt{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|\sqrt{n}}\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}\eqqcolon
E_{\mathsf{lb}1,l};$
$\displaystyle\inf_{u_{\bm{a},l}}\sup_{\bm{\Sigma}\in\mathcal{M}_{2}(\bm{\Sigma}^{\star})}\mathbb{E}\Big{[}\min\big{|}u_{\bm{a},l}\pm\bm{a}^{\top}\bm{u}_{l}(\bm{\Sigma})\big{|}\Big{]}$
$\displaystyle\qquad\gtrsim\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}\|\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\|_{2}\eqqcolon E_{\mathsf{lb}2,l}.$

Here, the infimum is taken over all estimator $u_{\bm{a},l}$ for the linear
form of the $l$-th eigenvector.

The proof of this theorem can be found in Appendix E. To interpret this lower
bound, let us consider, for simplicity, the scenario where

$r,\kappa\asymp
1\qquad\text{and}\qquad|\bm{a}^{\top}\bm{u}_{l}^{\star}|\leq(1-\epsilon)\|\bm{a}\|_{2}$
(3.22)

for some arbitrarily small constant $\epsilon>0$. In this scenario, the
statistical error bound (3.14b) derived in Theorem 3 matches the preceding
minimax lower bounds in the sense that

$E_{\mathsf{PCA},l}\asymp E_{\mathsf{lb}1,l}+E_{\mathsf{lb}2,l}.$

To verify this relation under the conditions (3.22), it is sufficient to see
that

$\displaystyle\max_{k:k\neq
l}\frac{\sqrt{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|\sqrt{n}}\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}+\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}\|\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\|_{2}$
$\displaystyle\qquad\asymp\sum_{k:\,k\neq
l}\frac{\sqrt{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|\sqrt{n}}\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}+\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}\|\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\|_{2}$
$\displaystyle\qquad\overset{(\mathrm{i})}{\asymp}\sum_{k:\,k\neq
l}\frac{\sqrt{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|\sqrt{n}}\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}+\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}\bigg{(}\sum_{k:\,k\neq
l}\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}+\|\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\|_{2}\bigg{)}$
$\displaystyle\qquad\overset{(\mathrm{ii})}{\asymp}\sum_{k:\,k\neq
l}\frac{\sqrt{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|\sqrt{n}}\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}+\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}\|\bm{a}\|_{2},$

where (i) holds true since $\max_{k:k\neq
l}\frac{\sqrt{(\lambda_{k}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|\sqrt{n}}\gtrsim\sqrt{\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}}{\lambda_{l}^{\star
2}n}}$, and (ii) holds true as long as
$|\bm{a}^{\top}\bm{u}_{l}^{\star}|\leq(1-\epsilon)\|\bm{a}\|_{2}$ for some
constant $\epsilon>0$. In conclusion, the above calculation unveils the
statistical optimality of the proposed de-biased estimator for the scenario
specified in (3.22).

##### Comparison with past works.

Estimation for linear forms of eigenvectors in the context of PCA has been
investigated in several recent works (Koltchinskii et al., 2016, 2017, 2020),
with the bias issue of plug-in estimators first recognized in Koltchinskii et
al. (2016). Among these works, the state-of-the-art result was due to
Koltchinskii et al. (2020), which proposed an efficient de-biased estimator
and established its asymptotic normality. To better understand our
contributions, it is helpful to compare Theorem 3 with the theoretical
guarantees in Koltchinskii et al. (2020) under the spiked covariance model
with $\bm{\Sigma}=\bm{\Sigma}^{\star}+\sigma^{2}\bm{I}_{p}$. The theoretical
guarantees developed in Koltchinskii et al. (2020, Theorem 3.3) operate under
the following conditions (when translated to our setting using our notation)

$\displaystyle\Delta_{l}^{\star}=\Omega(\lambda_{\max}^{\star}+\sigma^{2}),\quad\sigma^{2}=o(\lambda_{\min}^{\star}),\quad
r,\kappa\asymp 1,\quad\sum_{k:\,k\neq
l}\left|\bm{a}^{\top}\bm{u}_{k}^{\star}\right|^{2}+\frac{\sigma^{2}}{\lambda_{l}^{\star}}\|\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\|_{2}^{2}\asymp\|\bm{a}\|_{2}^{2}.$
(3.23)

In comparison, our results make improvements in the following aspects:

  * •

_Eigen-gap requirement_ : our eigen-gap requirement (3.13b) is
$\widetilde{O}(\sqrt{r/n})$ times less stringent than the one in (3.23);

  * •

_Requirement on noise variance_ : our result (i.e., Theorem 3) allows the
noise variance $\sigma^{2}$ to be larger than $\lambda_{\min}^{\star}$;

  * •

_Requirement on condition number and rank:_ our theory permits both $\kappa$
and $r$ to grow with the dimension.

It is worth noting that Koltchinskii et al. (2020) accommodates a more general
class of covariance matrices than the aforementioned spiked covariance. The
main purpose of our discussion above is to make clear the inadequacy of prior
theories when the eigen-gap is small.

##  4 Related works

Spectral methods have served as an effective paradigm for a variety of
statistical data science problems, examples including matrix completion
(Keshavan et al., 2010a, b; Sun and Luo, 2016; Ma et al., 2020), tensor
completion (Xia et al., 2021; Montanari and Sun, 2018; Cai et al., 2022,
2020), community detection (Lei, 2019; Abbe et al., 2020b), ranking from
pairwise comparisons (Negahban et al., 2017; Chen and Suh, 2015), and so on.
The mainstream analysis framework for spectral methods is largely built upon
classical matrix perturbation theory (Stewart and Sun, 1990; Chen et al.,
2021b). This set of classical theory typically focuses on deriving $\ell_{2}$
eigenspace or singular subspace perturbation bounds (e.g., the Davis-Kahan
theorem (Davis and Kahan, 1970) and the Wedin theorem (Wedin, 1972)), which
has been derived for general purposes without incorporating statistical
properties of the specific problems of interest. Several useful extensions
have been developed tailored to high-dimensional statistical applications,
particularly when the perturbation matrix of interest enjoys certain random
structure (Vu, 2011; Wang, 2015; Yu et al., 2015; Xia, 2019; Cai and Zhang,
2018; O’Rourke et al., 2018). In particular, the $\ell_{2}$ perturbation
bounds for the eigenvector (or eigenspace) of the sample covariance matrix has
been extensively studied in the PCA literature, e.g., (Nadler, 2008; Johnstone
and Lu, 2009; Vu and Lei, 2012; Lounici, 2013, 2014; Zhang et al., 2022; Zhu
et al., 2019; Xia, 2021). Another line of works (Vu, 2011; O’Rourke et al.,
2018) improved Davis-Kahan’s and Wedin’s theorems in the matrix denoising
setting with small eigen-gaps, which, however, is not tight unless the
spectral norm $\|\bm{H}\|$ of the noise matrix is extremely small.

Moving beyond $\ell_{2}$ perturbation theory, more fine-grained eigenvector
perturbation bounds — particularly entrywise eigenvector perturbation or
$\ell_{2,\infty}$ eigenspace perturbation — has garnered growing attention
over the past few years (Abbe et al., 2020b; Ma et al., 2020; Cape et al.,
2019; Cai et al., 2021; Chen et al., 2020b, 2021a; Cai et al., 2022; Lei,
2019; Fan et al., 2018; Zhong and Boumal, 2018; Abbe et al., 2020a). Among
these $\ell_{\infty}$ or $\ell_{2,\infty}$ theoretical guarantees, the results
in Abbe et al. (2020b); Ma et al. (2020); Cai et al. (2022, 2021); Chen et al.
(2019a, 2020b, b, 2020a) were established via a powerful leave-one-out
analysis framework, while the works (Eldridge et al., 2018; Chen et al.,
2021a) invoked a Neumann expansion trick paired with proper control of
moments.

In contrast to the rich literature on $\ell_{2}$, $\ell_{\infty}$ and/or
$\ell_{2,\infty}$ perturbation theory, estimation theory concerning linear
functionals of eigenvectors (or singular vectors) are rather scarce and under-
explored. While entrywise perturbation can be regarded as a special type of
linear functionals of eigenvectors, the analysis techniques mentioned above
are typically incapable of analyzing an arbitrary linear form. Only until
recently, progress has been made towards addressing this problem. In the
matrix denoising setting, effective concentration bounds have been established
in Koltchinskii and Xia (2016) for estimating linear forms of singular vectors
under i.i.d. Gaussian noise, while Bao et al. (2021) established the limiting
distributions of the angle between the singular vectors of the noisy matrix
and the corresponding ground-truth singular vectors. In Koltchinskii et al.
(2016, 2017, 2020), several bias reduction procedures were developed for the
problem of PCA and covariance estimation, which established the asymptotic
normality and statistical efficiency of the proposed estimator. The eigen-gap
conditions required therein, however, are considerably more stringent than the
ones required in our theory. Another line of recent works has studied linear
form of eigenvectors was Chen et al. (2021a); Cheng et al. (2021), which,
however, tackled a different setting of the matrix denoising problem.
Specifically, Chen et al. (2021a); Cheng et al. (2021) focused on the case
where the noise matrix $\bm{H}$ is asymmetric and contains independent entries
(so that $H_{i,j}$ and $H_{j,i}$ are two independent copies of noise); in this
case, a carefully de-biased estimator proposed based on the eigenvector of the
asymmetric data matrix $\bm{M}$ is shown to be minimax-optimal. Additionally,
Fan et al. (2020) pinned down the asymptotic distribution for bilinear forms
of eigenvectors for large spiked random matrices, while Xia and Yuan (2021)
proposed a de-biasing method to estimate linear forms of the matrix for noisy
matrix completion. These are beyond the reach of the current paper.

##  5 Analysis

In this section, we discuss the analysis ideas for establishing Theorem 1 and
Theorem 3. One of the main tools lies in the master theorems stated below,
which characterize the principal angle between the perturbed eigenvector and
an arbitrary subspace of interest. We shall see momentarily the effectiveness
of these master theorems when applied to matrix denoising and PCA.

###  5.1 Master theorems

For any matrix $\bm{Q}\in\mathbb{R}^{n\times k}$ obeying
$\bm{Q}^{\top}\bm{Q}=\bm{I}_{k}$ ($1\leq k\leq n$), let
$\bm{Q}^{\perp}\in\mathbb{R}^{n\times(n-k)}$ be an arbitrary matrix whose
columns form an orthonormal basis of the complement to the subspace spanned by
the columns of $\bm{Q}$, namely

$\big{[}\bm{Q},\bm{Q}^{\perp}\big{]}^{\top}\big{[}\bm{Q},\bm{Q}^{\perp}\big{]}=\bm{I}_{n}.$
(5.1)

Our results concern the decomposition of an eigenvector $\bm{u}_{l}$ of matrix
$\bm{M}$ taking the following form:

$\bm{u}_{l}=\bm{u}_{l,\|}\cos\theta+\bm{u}_{l,\perp}\sin\theta.$ (5.2)

Here, $\theta$ denotes the principal angle between $\bm{u}_{l}$ and the
subspace spanned by $\bm{Q}$, whereas $\bm{u}_{l,\|}$ and $\bm{u}_{l,\perp}$
are two unit vectors (i.e. $\|\bm{u}_{l,\|}\|_{2}=\|\bm{u}_{l,\perp}\|_{2}=1$)
such that

  * •

$\bm{u}_{l,\|}$ lies in the subspace spanned by $\bm{Q}$; this means that
$\bm{Q}\bm{Q}^{\top}\bm{u}_{l,\|}=\bm{u}_{l,\|}$, where $\bm{Q}\bm{Q}^{\top}$
is the projection matrix onto the subspace spanned by $\bm{Q}$;

  * •

$\bm{u}_{l,\perp}$ is perpendicular to the subspace spanned by $\bm{Q}$, so
that $\bm{Q}^{\perp}(\bm{Q}^{\perp})^{\top}\bm{u}_{l,\perp}=\bm{u}_{l,\perp}$.

##### When $\bm{Q}$ is a unit vector.

We shall begin with the case when $\bm{Q}$ is a unit vector. For notational
simplicity, let us write $\bm{q}$ for $\bm{Q}$ in this case to emphasize that
this is a vector, and let $\bm{q}^{\perp}\in\mathbb{R}^{n\times(n-1)}$
indicate $\bm{Q}^{\perp}$. In this case, we can take $\bm{u}_{l,\|}$ to be
equal to $\bm{q}$. Our result is this:

######  Theorem 5.

Consider any vector $\bm{q}\in\mathbb{R}^{n}$ with $\|\bm{q}\|_{2}=1$. Write

$\bm{u}_{l}=\bm{q}\cos\theta+\bm{u}_{l,\perp}\sin\theta$ (5.3)

for some $\theta$ as well as some vector $\bm{u}_{l,\perp}$ obeying
$\|\bm{u}_{l,\perp}\|_{2}=1$ and $\bm{q}^{\top}\bm{u}_{l,\perp}=0$. Suppose
that $\lambda_{l}\bm{I}_{n-1}-(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}^{\perp}$ is
invertible. Then one has

$\displaystyle\cos^{2}\theta$
$\displaystyle=\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}^{\perp}\big{)}^{-1}(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}\big{\|}_{2}^{2}},$
(5.4a) $\displaystyle\lambda_{l}$
$\displaystyle=\bm{q}^{\top}\bm{M}\bm{q}+\bm{q}^{\top}\bm{M}\bm{q}^{\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}^{\perp}\big{)}^{-1}(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}.$
(5.4b) In addition, when $\sin\theta\neq 0$, the vector $\bm{u}_{l,\perp}$
satisfies
$\bm{u}_{l,\perp}=\pm\frac{\bm{q}^{\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}^{\perp}\big{)}^{-1}(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}}{\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}^{\perp}\big{)}^{-1}(\bm{q}^{\perp})^{\top}\bm{M}\bm{q}\big{\|}_{2}}.$
(5.4c)

###### Proof.

See Appendix A.1.∎

In words, Theorem 5 derives closed-form expressions for both $\cos\theta$ and
$\bm{u}_{l,\perp}$ (up to global signs), in terms of simple and direct
manipulation of the data matrix $\bm{M}$ as well as the associated eigenvalue
$\lambda_{l}$. While the identities (5.4a) and (5.4c) might seem somewhat
complicated at first glance, they often allow for convenient decomposition of
the noise into independent components, thus streamlining the analysis.
Similarly, while the relation (5.4b) takes the form of a nonlinear equation
about $\lambda_{l}$, it often enables convenient decoupling of complicated
statistical dependency, as we shall demonstrate momentarily.

##### When $\bm{Q}$ is a more general orthonormal matrix.

The next theorem extends the relation (5.4b) to the case when $\bm{Q}$ is a
general orthonormal matrix (beyond the vector case), which proves useful in
eigenvalue analysis for more general low-rank problems.

######  Theorem 6.

Assume that $k<n$. Consider the corresponding decomposition (5.2) for any
matrix $\bm{Q}\in\mathbb{R}^{n\times k}$ obeying
$\bm{Q}^{\top}\bm{Q}=\bm{I}_{k}$. Suppose that
$\lambda_{l}\bm{\bm{I}}_{n-k}-(\bm{Q}^{\perp})^{\top}\bm{M}\bm{Q}^{\perp}$ and
$\lambda_{l}\bm{I}_{k}-\bm{{Q}}^{\top}\bm{M}\bm{{Q}}$ are both invertible.
Then one has

$\displaystyle\cos^{2}\theta$
$\displaystyle=\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{\bm{I}}_{n-k}-(\bm{Q}^{\perp})^{\top}\bm{M}\bm{Q}^{\perp}\big{)}^{-1}(\bm{Q}^{\perp})^{\top}\bm{M}\bm{u}_{l,\|}\big{\|}_{2}^{2}},$
(5.5a)
$\displaystyle\big{(}\lambda_{l}\bm{I}_{k}-\bm{Q}^{\top}\bm{M}\bm{Q}\big{)}\bm{Q}^{\top}\bm{u}_{l,\|}$
$\displaystyle=\bm{Q}^{\top}\bm{M}\bm{Q}^{\perp}\big{(}\lambda_{l}\bm{\bm{I}}_{n-k}-(\bm{Q}^{\perp})^{\top}\bm{M}\bm{Q}^{\perp}\big{)}^{-1}(\bm{Q}^{\perp})^{\top}\bm{M}\bm{u}_{l,\|}.$
(5.5b)

###### Proof.

See Appendix A.2.∎

###  5.2 Analysis for matrix denoising

Armed with the preceding master theorems, we are now positioned to develop
consequences for matrix denoising. As a crucial first step of the analysis, we
need to establish an eigenvalue perturbation theory that is tightly connected
to the eigenvector perturbation bounds. Recalling that $\lambda_{l}$ is the
$l$-th largest eigenvalue (in magnitude) of $\bm{M}$, we present a theorem
that reveals the proximity of $\lambda_{l}$ and the ground truth
$\lambda_{l}^{\star}$.

######  Theorem 7 (Eigenvalue perturbation for matrix denoising).

Consider the model in Section 2.1. Fix any $1\leq l\leq r$, and instate the
assumptions of Theorem 1. With probability at least $1-O(n^{-10}),$ one has

$|\lambda_{l}-\gamma(\lambda_{l})-\lambda_{l}^{\star}|\leq
C_{1}\sigma\sqrt{r}\log n$ (5.6)

for some sufficiently large constant $C_{1}>0$, where $\gamma(\cdot)$ is
defined as

$\gamma(\lambda)\coloneqq\sigma^{2}\mathsf{tr}\Big{[}\Big{(}\lambda\bm{I}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\Big{)}^{-1}\Big{]}.$
(5.7)

######  Remark 5.

Here, we recall that the columns of
$\bm{U}^{\star\perp}\in\mathbb{R}^{n\times(n-r)}$ form an orthonormal basis of
the complement to the subspace spanned by $\bm{U}^{\star}$.

######  Remark 6.

The error bound (5.6) concerning the empirical eigenvalue $\lambda_{l}$
contains a systematic non-negligible term $\gamma(\lambda_{l})$. This makes
clear the presence of a bias effect, which needs to be properly subtracted if
one desires a near-optimal estimate of $\lambda_{l}^{\star}$. It is also worth
noting that the importance of bias correction in eigenvalue estimation has
been recognized in prior literature as well (e.g. (Paul, 2007)).

####  5.2.1 Proof of eigenvalue perturbation theory (Theorem 7)

We start by demonstrating how to prove the eigenvalue perturbation bound in
Theorem 7. Let us fix an arbitrary $1\leq l\leq r$. The key ingredient of the
analysis is to invoke our master theorem (namely, Theorem 6).

Before proceeding, we first verify a few useful facts. It is well known that
if $\sigma\sqrt{n}\leq c_{0}\lambda_{\min}^{\star}$ for some sufficiently
small constant $c_{0}>0$, then with probability exceeding $1-O(n^{-20})$ one
has (see, e.g., Chen et al. (2021b, Theorem 3.1.4))

$\|\bm{H}\|\leq\lambda_{\min}^{\star}/3.$ (5.8)

Recall that

$(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}=(\bm{U}^{\star\perp})^{\top}\bm{M}^{\star}\bm{U}^{\star\perp}+(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}=(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp},$

which together with (5.8) implies that

$\big{\|}(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}\big{\|}=\big{\|}(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\big{\|}\leq\|\bm{H}\|\leq\lambda_{\min}^{\star}/3$
(5.9)

with probability exceeding $1-O(n^{-20})$. This means that with high
probability: (i) the Weyl inequality yields

$|\lambda_{l}|\geq|\lambda_{l}^{\star}|-\|\bm{H}\|\geq
2\,|\lambda_{l}^{\star}|/3\qquad\text{and}\qquad|\lambda_{l}|\leq|\lambda_{l}^{\star}|+\|\bm{H}\|\leq
4\,|\lambda_{l}^{\star}|/3;$ (5.10)

(2) it holds true that
$\lambda_{\min}^{\star}/3\geq\|\bm{H}\|\geq\|(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}\|$,
and hence

$\lambda\bm{I}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}\quad\text{is
invertible}$

for any $\lambda\in\mathbb{R}$ obeying $|\lambda|\geq
2\lambda_{\min}^{\star}/3$.

With the above two observations in mind, take $\bm{Q}=\bm{U}^{\star}$ in
Theorem 6 to show that

$\displaystyle\big{(}\lambda_{l}\bm{I}_{r}-\bm{U}^{\star\top}\bm{M}\bm{U}^{\star}\big{)}\bm{U}^{\star\top}\bm{u}_{l,\|}$
$\displaystyle=\bm{G}(\lambda_{l})\bm{U}^{\star\top}\bm{u}_{l,\|}$ (5.11)

with probability exceeding $1-O(n^{-20})$, where for any given $\lambda$ with
$2\lambda_{\min}^{\star}/3\leq|\lambda|\leq 4\lambda_{\max}^{\star}/3$, we
define

$\bm{G}(\lambda)\coloneqq\bm{U}^{\star\top}\bm{M}\bm{U}^{\star\perp}\Big{(}\lambda\bm{I}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}\Big{)}^{-1}(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star}.$
(5.12)

Note that $\bm{U}^{\star\top}$ and $\bm{u}_{l}^{\star\perp}$ are not uniquely
defined. To avoid ambiguity, here and throughout, we let
$\bm{U}^{\star\perp}\in\mathbb{R}^{n\times(n-r)}$ denote an arbitrary matrix
whose columns form an orthonormal basis of the complement to the subspace
spanned by $\bm{U}^{\star}$, and define

$\bm{u}_{l}^{\star\perp}=[\bm{u}_{1}^{\star},\bm{u}_{2}^{\star},\ldots,\bm{u}_{l-1}^{\star},\bm{u}_{l+1}^{\star},\ldots,\bm{u}_{r}^{\star},\bm{U}^{\star\perp}]\in\mathbb{R}^{n\times(n-1)}$
(5.13)

for each $1\leq l\leq r$.

Recognizing that
$\bm{U}^{\star\top}\bm{M}^{\star}\bm{U}^{\star}=\bm{\Lambda}^{\star}$,
$\bm{M}^{\star}\bm{U}^{\star\perp}=\bm{0}$ and
$(\bm{U}^{\star\perp})^{\top}\bm{M}^{\star}=\bm{0}$, we can rewrite (5.11) as

$\displaystyle\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}^{\star}-\bm{U}^{\star\top}\bm{H}\bm{U}^{\star}\big{)}\bm{U}^{\star\top}\bm{u}_{l,\|}$
$\displaystyle=\bm{G}(\lambda_{l})\bm{U}^{\star\top}\bm{u}_{l,\|}$ (5.14a)
$\text{with}\quad\bm{G}(\lambda)=\bm{U}^{\star\top}\bm{H}\bm{U}^{\star\perp}\Big{(}\lambda\bm{I}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\Big{)}^{-1}(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star}.$
(5.14b)

Rearranging terms further gives

$\displaystyle\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}^{\star}-\bm{G}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\|}$
$\displaystyle=\bm{U}^{\star\top}\bm{H}\bm{U}^{\star}\bm{U}^{\star\top}\bm{u}_{l,\|}+\big{(}\bm{G}(\lambda_{l})-\bm{G}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\|},$
(5.15)

where we define

$\bm{G}^{\perp}(\lambda)\coloneqq\mathbb{E}\left[\bm{G}(\lambda)\mid(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\right],$
(5.16)

with the (conditional) expectation taken assuming that $\lambda$ is
independent of $\bm{H}$. Here, we single out the component
$\bm{G}^{\perp}(\lambda)$ since — as will be seen momentarily — it often
contains some non-negligible bias term. Combining (5.15) with the triangle
inequality and the fact $\|\bm{U}^{\star\top}\bm{u}_{l,\|}\|_{2}=1$ then
yields

$\displaystyle\left\|\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}^{\star}-\bm{G}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\|}\right\|_{2}$
$\displaystyle\leq\left\|\bm{U}^{\star\top}\bm{H}\bm{U}^{\star}\right\|+\left\|\bm{G}(\lambda_{l})-\bm{G}^{\perp}(\lambda_{l})\right\|$
(5.17)
$\displaystyle\leq\big{\|}\bm{U}^{\star\top}\bm{H}\bm{U}^{\star}\big{\|}+\sup_{\lambda:\,|\lambda|\in\big{[}2|\lambda_{l}^{\star}|/3,\,4|\lambda_{l}^{\star}|/3\big{]}}\big{\|}\bm{G}(\lambda)-\bm{G}^{\perp}(\lambda)\big{\|}$
(5.18)

with probability at least $1-O(n^{-20})$, where the last line arises from
(5.10).

In order to justify that
$\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}^{\star}-\bm{G}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\|}\approx\bm{0}$,
it remains to show that the two terms on the right-hand side of (5.18) are
both fairly small, which we accomplish through the following lemma.

######  Lemma 1.

Assume that $\bm{H}\in\mathbb{R}^{n\times n}$ is a symmetric matrix with
$H_{ij}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\sigma^{2}),i\geq j$ and
$\sigma\sqrt{n}\leq c_{0}\lambda_{\min}^{\star}$ for some sufficiently small
constant $c_{0}>0$. Then for any $1\leq l\leq r$, with probability at least
$1-O(n^{-11}),$ one has

$\displaystyle\big{\|}\bm{U}^{\star\top}\bm{H}\bm{U}^{\star}\big{\|}$
$\displaystyle\lesssim\sigma\big{(}\sqrt{r}+\sqrt{\log n}\big{)},$
$\displaystyle\sup_{\lambda:\,|\lambda|\in\big{[}2|\lambda_{l}^{\star}|/3,\,4|\lambda_{l}^{\star}|/3\big{]}}\big{\|}\bm{G}(\lambda)-\bm{G}^{\perp}(\lambda)\big{\|}$
$\displaystyle\lesssim\frac{\sigma^{2}}{\lambda_{\min}^{\star}}\big{(}\sqrt{rn\log
n}+r\log n\big{)}.$ (5.19)

In addition, one has

$\bm{G}^{\perp}(\lambda)=\Big{\\{}\sigma^{2}\mathsf{tr}\Big{[}\big{(}\lambda\bm{I}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\big{)}^{-1}\Big{]}\Big{\\}}\bm{I}_{r}.$
(5.20)

###### Proof.

See Appendix B.1.∎

With the above lemma in place, by introducing

$\displaystyle\bm{M}_{\lambda}$
$\displaystyle:=\bm{\Lambda}^{\star}+\bm{G}^{\perp}(\lambda)=\bm{\Lambda}^{\star}+\gamma(\lambda)\bm{I}_{r}$
(5.21a) $\displaystyle\gamma(\lambda)$
$\displaystyle:=\sigma^{2}\mathsf{tr}\Big{[}\big{(}\lambda\bm{I}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\big{)}^{-1}\Big{]}$
(5.21b)

for any $\lambda$ with $2\lambda_{\min}^{\star}/3\leq|\lambda|\leq
4\lambda_{\max}^{\star}/3$, we can invoke the union bound to show that with
probability at least $1-O(n^{-10})$,

$\displaystyle\big{\|}(\lambda_{l}\bm{I}_{r}-\bm{M}_{\lambda_{l}})\bm{U}^{\star\top}\bm{u}_{l,\|}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\bm{U}^{\star\top}\bm{H}\bm{U}^{\star}\big{\|}+\sup_{\lambda:\,|\lambda|\in\big{[}2|\lambda_{l}^{\star}|/3,\,4|\lambda_{l}^{\star}|/3\big{]}}\big{\|}\bm{G}(\lambda)-\bm{G}^{\perp}(\lambda)\big{\|}$
$\displaystyle\lesssim\sigma\big{(}\sqrt{r}+\sqrt{\log
n}\big{)}+\frac{\sigma^{2}}{\lambda_{\min}^{\star}}\big{(}\sqrt{rn\log
n}+r\log n\big{)}$ $\displaystyle\leq C_{1}\sigma\sqrt{r}\log
n=:\mathcal{E}_{\mathsf{MD}}$ (5.22)

holds for all $1\leq l\leq r$, where $C_{1}>0$ is some sufficiently large
constant. Intuitively, this means that
$(\lambda_{l}\bm{I}_{r}-\bm{M}_{\lambda_{l}})\bm{U}^{\star\top}\bm{u}_{l,\|}\approx\bm{0}$,
and hence $\lambda_{l}$ is expected to be close to an eigenvalue of
$\bm{M}_{\lambda_{l}}$ — which is $\lambda_{i}^{\star}+\gamma(\lambda_{l})$
for some $1\leq i\leq r$.

With the above bound in place, the only possible range of $\lambda_{l}$ is
characterized by the following lemma, which in turn establishes Theorem 7.

######  Lemma 2.

Under the condition (5.22) and the eigen-gap assumption (3.3), with
probability at least $1-O(n^{-10})$ one has

$\big{|}\lambda_{l}-\lambda_{l}^{\star}-\gamma(\lambda_{l})\big{|}\leq\mathcal{E}_{\mathsf{MD}},\qquad
1\leq l\leq r.$ (5.23)

###### Proof.

See Appendix B.2.∎

####  5.2.2 Proof of eigenvector perturbation theory (Theorem 1)

Let us begin by decomposing $\bm{u}_{l}$ along the ground-truth direction
$\bm{u}_{l}^{\star}$ and its complement subspace as follows

$\bm{u}_{l}=\bm{u}_{l}^{\star}\cos\theta+\bm{u}_{l,\perp}\sin\theta,$ (5.24)

where the vector $\bm{u}_{l,\perp}$ obeys $\|\bm{u}_{l,\perp}\|_{2}=1$ and
$\bm{u}_{l,\perp}^{\top}\bm{u}_{l}^{\star}=0$. Writing
$\bm{a}=\bm{P}_{\bm{U}^{\star}}\bm{a}+\bm{P}_{\bm{U}^{\star\perp}}\bm{a}$ with
$\bm{P}_{\bm{U}^{\star}}=\sum_{1\leq k\leq
r}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}$ and
$\bm{P}_{\bm{U}^{\star\perp}}=\bm{I}-\bm{P}_{\bm{U}^{\star}}$, we obtain

$\displaystyle\bm{a}^{\top}\bm{u}_{l}=$
$\displaystyle(\bm{P}_{\bm{U}^{\star}}\bm{a})^{\top}\bm{u}_{l}+(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}\bm{u}_{l}$
$\displaystyle=$
$\displaystyle(\bm{P}_{\bm{U}^{\star}}\bm{a})^{\top}(\bm{u}_{l}^{\star}\cos\theta+\bm{u}_{l,\perp}\sin\theta)+\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{u}_{l}\rangle$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{r}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}(\bm{u}_{l}^{\star}\cos\theta+\bm{u}_{l,\perp}\sin\theta)+\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle$
$\displaystyle=$
$\displaystyle\bm{a}^{\top}\bm{u}_{l}^{\star}\cos\theta+\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta+\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle,$

where the third line relies on the fact
$\bm{P}_{\bm{U}^{\star\perp}}\bm{P}_{\bm{U}^{\star\perp}}=\bm{P}_{\bm{U}^{\star\perp}}$.
It then follows that

$\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}=\bm{a}^{\top}\bm{u}_{l}^{\star}(\cos\theta\pm
1)+\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta+\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle,$

allowing us to deduce that

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\leq$
$\displaystyle\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}(1-|\cos\theta|)+\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}+\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}$
$\displaystyle\leq$
$\displaystyle\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}(1-\cos^{2}\theta)+\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}+\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}.$
(5.25)

and

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\sqrt{1+b_{l}}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\leq\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\cdot\big{|}1-\sqrt{1+b_{l}}|\cos\theta|\big{|}+\sqrt{1+b_{l}}\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}$
$\displaystyle\quad+\sqrt{1+b_{l}}\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}.$
(5.26)

As a result, it boils down to bounding the terms

$1-\cos^{2}\theta,\quad
1-\sqrt{1+b_{l}}|\cos\theta|,\quad\sqrt{1+b_{l}},\quad\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta,\quad\text{and}\quad\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle.$

We claim that
$\lambda_{l}\bm{I}_{n-1}-(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star\perp}$
is invertible. This can be seen from (5.33) stated in Lemma 3 directly, whose
validation is independent with this claim. The invertibility taken together
with Theorem 5 reveals that $\cos\theta\neq 0$. If $\sin\theta=0$, then we
have $\bm{u}_{l}=\pm\bm{u}_{l}^{\star}$ and the conclusion is obvious since
$\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}=0$.
Therefore, we shall assume $\cos\theta\neq 0$ and $\sin\theta\neq 0$ in the
remainder of the proof. Invoking Theorem 5 yields

$\displaystyle\cos^{2}\theta$
$\displaystyle=\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star\perp}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}},$
(5.27a) $\displaystyle\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}$
$\displaystyle=\frac{\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star\perp}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star}}{\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star\perp}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star}\big{\|}_{2}}.$
(5.27b)

Recognizing that
$\bm{M}^{\star}\bm{u}_{l}^{\star}=\lambda_{l}^{\star}\bm{u}_{l}^{\star}$, we
can alternatively write (5.27) as follows

$\displaystyle\cos^{2}\theta$
$\displaystyle=\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}},$
(5.28a) $\displaystyle\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}$
$\displaystyle=\frac{\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}}{\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}}.$
(5.28b)

Here, we define

$\displaystyle\bm{M}^{(l)}$
$\displaystyle\coloneqq(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}\bm{u}_{l}^{\star\perp}=(\bm{u}_{l}^{\star\perp})^{\top}\bm{M}^{\star}\bm{u}_{l}^{\star\perp}+(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star\perp}.$
(5.29)

With the above relations in mind, we can demonstrate that

$\displaystyle\big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\big{|}=\big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\big{|}\sqrt{1-\cos^{2}\theta}$
$\displaystyle=\frac{\big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{|}}{\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}}\cdot\sqrt{\frac{\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}}}$
$\displaystyle\leq\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\Big{|},$

where the last inequality comes from the fact
$\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}=\big{\|}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}$
(since the columns of $\bm{u}_{l}^{\star\perp}$ are orthonormal). Substituting
this into (5.25) and (5.26) yields

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\leq\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\cdot(1-\cos^{2}\theta)+\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}$
$\displaystyle\quad+\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\cdot\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\Big{|};$
(5.30)

and

$\displaystyle\min\big{|}\sqrt{1+b_{l}}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\leq\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\cdot\big{|}1-\sqrt{1+b_{l}}|\cos\theta|\big{|}+\sqrt{1+b_{l}}\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}$
$\displaystyle\quad+\sqrt{1+b_{l}}\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\cdot\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\Big{|}.$
(5.31)

In what follows, we shall control these quantities separately.

##### 1\. Controlling the spectrum of $\bm{M}^{(l)}$.

Before proceeding, we find it helpful to first study the spectrum of
$\bm{M}^{(l)}$. Let $\\{\lambda_{i}^{(l)}\\}_{i=1}^{n-1}$ denote the
eigenvalues of $\bm{M}^{(l)}$ with
$|\lambda_{1}^{(l)}|\geq|\lambda_{2}^{(l)}|\geq\cdots\geq|\lambda_{n-1}^{(l)}|$
with associate eigenvectors $\\{\bm{u}_{i}^{(l)}\\}_{i=1}^{n-1}$. In addition,
we define several matrices as follows

$\displaystyle\bm{U}_{\smallsetminus l}^{\star}$
$\displaystyle\coloneqq[\bm{u}_{1}^{\star},\cdots,\bm{u}_{l-1}^{\star},\bm{u}_{l+1}^{\star},\cdots,\bm{u}_{r}^{\star}]\in\mathbb{R}^{n\times(r-1)},$
(5.32a) $\displaystyle\bm{U}^{\star(l)}$
$\displaystyle\coloneqq(\bm{u}_{l}^{\star\perp})^{\top}\bm{U}_{\smallsetminus
l}^{\star}=\begin{bmatrix}\bm{I}_{r-1}\\\
\bm{0}\end{bmatrix}\in\mathbb{R}^{(n-1)\times(r-1)},$ (5.32b)
$\displaystyle\bm{U}^{\star(l)\perp}$
$\displaystyle\coloneqq(\bm{u}_{l}^{\star\perp})^{\top}\bm{U}^{\star\perp}=\begin{bmatrix}\bm{0}\\\
\bm{I}_{n-r}\end{bmatrix}\in\mathbb{R}^{(n-1)\times(n-r)},$ (5.32c)
$\displaystyle\bm{\Lambda}^{\star(l)}$
$\displaystyle\coloneqq\mathsf{diag}\big{(}\\{\lambda_{i}^{\star}\\}_{i\neq
l}\big{)}\in\mathbb{R}^{(r-1)\times(r-1)},$ (5.32d)

and define

$\bm{u}_{k,\parallel}^{(l)}\coloneqq\frac{1}{\|\bm{P}_{\bm{U}^{\star(l)}}\bm{u}_{k}^{(l)}\|_{2}}\bm{P}_{\bm{U}^{\star(l)}}\bm{u}_{k}^{(l)}$

for each $k\neq l$.

Armed with this set of notation, we are ready to present Lemma 3, which
studies the eigenvalues of $\bm{M}^{(l)}$.

######  Lemma 3.

Instate the assumptions of Theorem 1, and recall the definition of
$\mathcal{E}_{\mathsf{MD}}$ in Lemma 2. With probability at least
$1-O(n^{-10})$, the following holds:

  1. 1.

For each $1\leq k<r$, one has
$\lambda_{k}^{(l)}-\gamma(\lambda_{k}^{(l)})\in\mathcal{B}_{\mathcal{E}_{\mathsf{MD}}}(\lambda_{i}^{\star})$
for some $i\neq l$, and

$\big{\|}\big{(}\lambda_{k}^{(l)}\bm{I}_{r-1}-\gamma(\lambda_{k}^{(l)})\bm{I}_{r-1}-\bm{\Lambda}^{\star(l)}\big{)}\bm{U}^{\star(l)\top}\bm{u}_{k,\parallel}^{(l)}\big{\|}_{2}\lesssim\sigma\sqrt{r}\log
n;$

  2. 2.

For each $k\geq r$, one has $|\lambda_{k}^{(l)}|\lesssim\sigma\sqrt{n}$;

  3. 3.

Moreover, one has

$\big{|}\lambda-\lambda_{l}\big{|}\gtrsim\begin{cases}\Delta_{l}^{\star},&\text{if}\
\lambda-\gamma(\lambda)\in\mathcal{B}_{\mathcal{E}_{\mathsf{MD}}}(\lambda_{k}^{\star})\,\text{\text{for
some }}k\neq l\text{ and }1\leq k\leq r;\\\
|\lambda_{l}^{\star}|,&\text{\text{if}}\
|\lambda|\lesssim\sigma\sqrt{n}.\end{cases}$

In particular, we have

$\big{|}\lambda_{k}^{(l)}-\lambda_{l}\big{|}\gtrsim\begin{cases}\Delta_{l}^{\star},&1\leq
k<r;\\\ |\lambda_{l}^{\star}|,&k\geq r.\end{cases}$ (5.33)

###### Proof.

See Appendix C.1.∎

In words, this lemma tells us that:

  * •

For any $1\leq k\leq r$, the properly corrected $\lambda_{k}^{(l)}$ (namely,
$\lambda_{k}^{(l)}-\gamma(\lambda_{k}^{(l)})$) stays very close to one of the
true non-zero eigenvalues excluding $\lambda_{l}^{\star}$;

  * •

For any $k\geq r$, the eigenvalue $\lambda_{k}^{(l)}$ is reasonably small;

  * •

Any eigenvalue of $\bm{M}^{(l)}$ is sufficiently separated from the $l$-th
eigenvalue $\lambda_{l}$ of $\bm{M}$, where the separation is lower bounded by
the order of the associated eigen-gap.

##### 2\. Controlling $\cos^{2}\theta$.

We now turn to bounding $\cos^{2}\theta$. In view of the expression of
$\cos^{2}\theta$ in (5.28a), it suffices to look at
$\big{\|}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}$.
A simple yet crucial observation is that: the matrix
$(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star\perp}$ is independent
of $(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}$ (which follows
from the same argument as in the proof of Lemma 1 in Appendix B.1).
Consequently, $\bm{M}^{(l)}$ (defined in (5.29)) is independent of
$(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\sim\mathcal{N}(\bm{0},\sigma^{2}\bm{I}_{n-1})$,
which is a Gaussian random vector in $\mathbb{R}^{n-1}$. In light of this
observation, we can bound
$\big{\|}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}$
as follows.

######  Lemma 4.

Instate the assumptions of Theorem 1. The following holds with probability at
least $1-O(n^{-10})$:

$\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}=\sum_{k:\,r<k\leq
n}\frac{\sigma^{2}}{(\lambda_{l}-\lambda_{k})^{2}}+O\bigg{(}\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}+\frac{\sigma^{2}\sqrt{n\log
n}}{\lambda_{l}^{\star 2}}\bigg{)},$ (5.34)

which further indicates that

$\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}\asymp\frac{\sigma^{2}n}{\lambda_{l}^{\star
2}}+O\bigg{(}\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}\bigg{)}\ll 1.$ (5.35)

###### Proof.

See Appendix C.2.∎

Combining this lemma with (5.28a), we reach

$1-\cos^{2}\theta=1-\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}}\asymp\frac{\sigma^{2}n}{\lambda_{l}^{\star
2}}+O\bigg{(}\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}\bigg{)}\ll 1,$ (5.36)

where the last step arises from the assumption (3.3). In addition, recalling
the de-bias parameter $b_{l}$

$b_{l}=\sum_{k:\,r<k\leq n}\frac{\sigma^{2}}{(\lambda_{l}-\lambda_{k})^{2}},$

one arrives at

$\displaystyle\big{|}(1+b_{l})\cos^{2}\theta-1\big{|}$
$\displaystyle=\Bigg{|}\frac{1+b_{l}}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}}-1\Bigg{|}$
$\displaystyle=\frac{\Big{|}b_{l}-\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}\Big{|}}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}}$
$\displaystyle\leq\Big{|}b_{l}-\big{\|}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}\Big{|}$
$\displaystyle\overset{(\mathrm{i})}{\lesssim}\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}+\frac{\sigma^{2}\sqrt{n\log
n}}{\lambda_{l}^{\star 2}}\overset{(\mathrm{ii})}{\ll}1,$ (5.37)

where (i) follows from (5.34) and (ii) is due to the assumption (3.3).
Combined with (5.36), this further allows us to obtain $1+b_{l}\lesssim 1$ and

$\big{|}1-\sqrt{1+b_{l}}|\cos\theta|\big{|}=\bigg{|}\frac{1-(1+b_{l})\cos^{2}\theta}{1+\sqrt{1+b_{l}}|\cos\theta|}\bigg{|}\lesssim\big{|}1-(1+b_{l})\cos^{2}\theta\big{|}\lesssim\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}+\frac{\sigma^{2}\sqrt{n\log
n}}{\lambda_{l}^{\star 2}}.$ (5.38)

##### 3\. Controlling $\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\cdot\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}$.

The key observation is that
$(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\sim\mathcal{N}(\bm{0},\bm{I}_{n-1})$
is independent of $\bm{M}^{(l)}$ (but dependent of $\lambda_{l}$). This term
can be bounded via the following lemma, which will be established in Appendix
C.3.

######  Lemma 5.

Instate the assumptions of Theorem 1. With probability at least
$1-O(n^{-10})$, one has

$\displaystyle\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\cdot\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{n-1}-\bm{M}^{(l)}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\bm{H}\bm{u}_{l}^{\star}\Big{|}$
$\displaystyle\qquad\qquad\lesssim\frac{\sigma}{|\lambda_{l}^{\star}|}\sqrt{\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}+\sigma\sqrt{r\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}\sum_{k:k\neq
l}\frac{\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|}.$
(5.39)

##### 4\. Controlling
$\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle$.

When it comes to the last term
$\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle$,
one can take advantage of the rotational invariance of
$\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}$ in the subspace spanned by
$\bm{U}^{\star\perp}$ to upper bound it. This is formalized in Lemma 6, with
the proof postponed to Appendix C.4.

######  Lemma 6.

Instate the assumptions of Theorem 1. With probability at least
$1-O(n^{-10})$,

$\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}\lesssim\sqrt{\frac{\log
n}{n}}\,\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\big{\|}_{2}\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\big{\|}_{2}.$
(5.40)

Consequently, it remains to upper bound
$\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\big{\|}_{2}$. Recall
$\bm{u}_{l,\parallel}\coloneqq\bm{P}_{\bm{U}^{\star}}(\bm{u})/\|\bm{P}_{\bm{U}^{\star}}(\bm{u})\|_{2}$
defined in in Section 5.1. By virtue of Theorem 6, one has

$\displaystyle\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\big{\|}_{2}^{2}$
$\displaystyle=1-\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{\bm{I}}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}\big{)}^{-1}(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{u}_{l,\parallel}\big{\|}_{2}^{2}}$
$\displaystyle\leq\big{\|}\big{(}\lambda_{l}\bm{\bm{I}}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{U}^{\star\perp}\big{)}^{-1}(\bm{U}^{\star\perp})^{\top}\bm{M}\bm{u}_{l,\parallel}\big{\|}_{2}^{2}$
$\displaystyle\leq\big{\|}\big{(}\lambda_{l}\bm{\bm{I}}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\big{)}^{-1}\big{\|}^{2}\|(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{u}_{l,\parallel}\|_{2}^{2},$
(5.41)

where the last inequality makes use of the fact that

$(\bm{U}^{\star\perp})^{\top}\bm{M}=(\bm{U}^{\star\perp})^{\top}\bm{M}^{\star}+(\bm{U}^{\star\perp})^{\top}\bm{H}=(\bm{U}^{\star\perp})^{\top}\bm{H}.$

Additionally, it is easily seen that

$\displaystyle\|\lambda_{l}\bm{\bm{I}}_{n-r}-(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\|$
$\displaystyle\geq|\lambda_{l}|-\|(\bm{U}^{\star\perp})^{\top}\bm{H}\bm{U}^{\star\perp}\|\gtrsim|\lambda_{l}^{\star}|$
$\displaystyle\|\bm{U}^{\star\perp\top}\bm{H}\bm{u}_{l,\parallel}\|_{2}$
$\displaystyle\leq\|\bm{H}\|\lesssim\sigma\sqrt{n}$

with high probability. These combined with (5.41) lead to

$\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\big{\|}_{2}\lesssim\frac{\sigma\sqrt{n}}{|\lambda_{l}^{\star}|}.$
(5.42)

Substitution into (5.40) reveals that

$\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}\lesssim\sqrt{\frac{\log
n}{n}}\,\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\big{\|}_{2}\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\big{\|}_{2}\lesssim\frac{\sigma\sqrt{\log
n}}{|\lambda_{l}^{\star}|}\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\big{\|}_{2}.$
(5.43)

##### 5\. Combining bounds.

In view of (5.30), the bounds (5.36), (5.39) and (5.43) taken collectively
lead to our advertised result

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\lesssim\bigg{(}\frac{\sigma^{2}n}{\lambda_{l}^{\star
2}}+\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}\bigg{)}\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}+\frac{\sigma\sqrt{\log
n}}{|\lambda_{l}^{\star}|}\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\big{\|}_{2}$
$\displaystyle\quad+\sigma\sqrt{r\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}\sum_{k:k\neq
l}\frac{\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|}+\frac{\sigma}{|\lambda_{l}^{\star}|}\sqrt{\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}.$

Regarding the analysis for the de-biased estimate, one can substitute (5.38),
(5.39) and (5.43) into (5.31) to obtain

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\sqrt{1+b_{l}}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\lesssim\bigg{(}\frac{\sigma^{2}\sqrt{n\log
n}}{\lambda_{l}^{\star 2}}+\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}\bigg{)}\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}+\frac{\sigma\sqrt{\log
n}}{|\lambda_{l}^{\star}|}\big{\|}\bm{P}_{\bm{U}^{\star\perp}}\bm{a}\big{\|}_{2}$
$\displaystyle\quad+\sigma\sqrt{r\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}\sum_{k:k\neq
l}\frac{\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|}+\frac{\sigma}{|\lambda_{l}^{\star}|}\sqrt{\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}$
$\displaystyle\lesssim\frac{\sigma^{2}r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}}\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}+\sigma\sqrt{r\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}\sum_{k:k\neq
l}\frac{\big{|}\bm{a}^{\top}\bm{u}_{k}^{\star}\big{|}}{|\lambda_{l}^{\star}-\lambda_{k}^{\star}|}+\frac{\sigma}{|\lambda_{l}^{\star}|}\sqrt{\log\bigg{(}\frac{n\kappa\lambda_{\max}}{\Delta_{l}^{\star}}\bigg{)}}$

where the last step holds since $\sigma\sqrt{n}\lesssim\lambda_{\min}^{\star}$
and
$\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\leq\|\bm{a}\|_{2}\|\bm{u}_{l}^{\star}\|_{2}=1.$
This concludes the proof.

###  5.3 Analysis for principal component analysis

Akin to the matrix denoising counterpart, the first step towards establishing
the desired eigenvector perturbation bounds lies in the development of a fine-
grained eigenvalue perturbation theory. Here and throughout, we let
$\bm{U}^{\star\perp}\in\mathbb{R}^{p\times(p-r)}$ represent a matrix
consisting of orthonormal columns perpendicular to the subspace spanned by
$\bm{U}^{\star}$.

######  Theorem 8 (Eigenvalue perturbation for PCA).

Consider the model in Section 2.2. Fix any $1\leq l\leq r$, and instate the
assumptions of Theorem 3. Then with probability at least $1-O(n^{-10}),$ one
has

$\bigg{|}\frac{\lambda_{l}}{1+\beta(\lambda_{l})}-\lambda_{l}^{\star}-\sigma^{2}\bigg{|}\leq
C_{2}(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r}{n}}\log n$ (5.44)

for some sufficiently large constant $C_{2}>0$, where we define

$\beta(\lambda):=\frac{1}{n}\mathsf{tr}\Big{[}\frac{1}{n}\bm{S}_{\perp}^{\top}\big{(}\lambda\bm{I}_{p-r}-\frac{1}{n}\bm{S}_{\perp}\bm{S}_{\perp}^{\top}\big{)}^{-1}\bm{S}_{\perp}\Big{]}\qquad\text{with
}\bm{S}_{\perp}\coloneqq(\bm{U}^{\star\perp})^{\top}\bm{S}.$ (5.45)

######  Remark 7.

As asserted by Theorem 8, the empirical eigenvalue $\lambda_{l}$ exhibits a
form of “inflation” in comparison to the corresponding ground-truth value
$\lambda_{l}^{\star}+\sigma^{2}$. As a result, it is advisable to properly
shrink $\lambda_{l}$ when estimating $\lambda_{l}^{\star}+\sigma^{2}$.

In what follows, we shall first outline the proof for Theorem 8 (which is very
similar to the analysis for Theorem 7), followed by a proof sketch for the
eigenvector perturbation theory in Theorem 3.

####  5.3.1 Proof of eigenvalue perturbation theory (Theorem 8)

Before embarking on the proof, we shall define

$\bm{S}_{\parallel}:=\bm{U}^{\star\top}\bm{S}\in\mathbb{R}^{r\times
n},\quad\bm{S}_{\perp}:=(\bm{U}^{\star\perp})^{\top}\bm{S}\in\mathbb{R}^{(p-r)\times
n}\quad\text{and}\quad\bm{\Lambda}:=\bm{U}^{\star\top}\bm{\Sigma}\bm{U}^{\star}=\bm{\Lambda}^{\star}+\sigma^{2}\bm{I}_{r}$
(5.46)

for notional convenience, allowing one to express

$\displaystyle(\bm{U}^{\star\perp})^{\top}\bm{S}\bm{S}^{\top}\bm{U}^{\star\perp}$
$\displaystyle=\bm{S}_{\perp}\bm{S}_{\perp}^{\top},$ (5.47a)
$\displaystyle(\bm{U}^{\star\perp})^{\top}\bm{S}\bm{S}^{\top}\bm{U}^{\star}$
$\displaystyle=\bm{S}_{\perp}\bm{S}_{\parallel}^{\top},$ (5.47b)
$\displaystyle\bm{U}^{\star\top}\bm{S}\bm{S}^{\top}\bm{U}^{\star}$
$\displaystyle=\bm{S}_{\parallel}\bm{S}_{\parallel}^{\top}.$ (5.47c)

As can be straightforwardly verified:

  * •

The columns of $\bm{S}_{\parallel}$ are independent zero-mean Gaussian random
vectors with covariance matrix $\bm{\Lambda}$;

  * •

The columns of $\bm{S}_{\perp}$ are i.i.d. zero-mean Gaussian random vectors
with covariance matrix $\sigma^{2}\bm{I}_{p-r}$;

  * •

$\bm{S}_{\parallel}$ is statistically independent of $\bm{S}_{\perp}$ (from
standard properties for Gaussian random vectors).

In addition, the following lemma controls the distance between
$\frac{1}{n}\bm{S}\bm{S}^{\top}$ and $\bm{\Sigma}$ when measured by the
spectral norm.

######  Lemma 7.

Assume that $n\geq r$. Then with probability at least $1-O(n^{-10})$, one has

$\Big{\|}\frac{1}{n}\bm{S}\bm{S}^{\top}-\bm{\Sigma}\Big{\|}\lesssim\lambda_{\max}^{\star}\sqrt{\frac{r\log
n}{n}}+\sqrt{(\lambda_{\max}^{\star}+\sigma^{2})\sigma^{2}\frac{p}{n}}\,\log
n+\sigma^{2}\bigg{(}\sqrt{\frac{p}{n}}+\frac{p}{n}+\sqrt{\frac{\log
n}{n}}\bigg{)}.$ (5.48)

###### Proof.

See Appendix D.1.∎

######  Remark 8.

In particular, under the noise assumption (3.13a), Lemma 7 tells us that
$\big{\|}\frac{1}{n}\bm{S}\bm{S}^{\top}-\bm{\Sigma}\big{\|}\ll\lambda_{\min}^{\star}$
with probability at least $1-O(n^{-10})$, which together with Weyl’s
inequality gives

$2\lambda_{l}^{\star}/3\leq\lambda_{l}\leq 4\lambda_{l}^{\star}/3,\qquad 1\leq
l\leq r.$ (5.49)

We now move on to present the proof of Theorem 8. The key ingredient
underlying the analysis is, once again, to invoke our master theorem (namely,
Theorem 6), by treating $\frac{1}{n}\bm{S}\bm{S}^{\top}$,
$\bm{\Sigma}^{\star}$ and $\bm{U}^{\star}$ as $\bm{M}$, $\bm{M}^{\star}$ and
$\bm{Q}$, respectively. Recalling the definition of

$\bm{u}_{l,\parallel}\coloneqq\frac{1}{\|\bm{P}_{\bm{U}^{\star}}(\bm{u})\|_{2}}\bm{P}_{\bm{U}^{\star}}(\bm{u})$
(5.50)

as in Section 5.1 (so that
$\bm{U}^{\star}\bm{U}^{\star\top}\bm{u}_{l,\parallel}=\bm{u}_{l,\parallel}$),
one can invoke (5.5b) in Theorem 6 to derive

$\Big{(}\lambda_{l}\bm{I}_{r}-\frac{1}{n}\bm{S}_{\parallel}\bm{S}_{\parallel}^{\top}\Big{)}\bm{U}^{\star\top}\bm{u}_{l,\parallel}=\bm{K}(\lambda_{l})\,\bm{U}^{\star\top}\bm{u}_{l,\parallel},$
(5.51)

where we recall the definitions of $\bm{S}_{\parallel}$ and $\bm{S}_{\perp}$
in (5.46), and $\bm{K}(\lambda)$ is given by

$\bm{K}(\lambda)\coloneqq\frac{1}{n}\bm{S}_{\parallel}\cdot\underbrace{\frac{1}{n}\bm{S}_{\perp}^{\top}\Big{(}\lambda\bm{I}_{p-r}-\frac{1}{n}\bm{S}_{\perp}\bm{S}_{\perp}^{\top}\Big{)}^{-1}\bm{S}_{\perp}}_{=:\,\bm{C}(\lambda)}\cdot\,\bm{S}_{\parallel}^{\top}.$
(5.52)

It is also helpful to define

$\bm{K}^{\perp}(\lambda)\coloneqq\mathbb{E}\big{[}\bm{K}(\lambda)\mid\bm{C}(\lambda)\big{]},$
(5.53)

with $\lambda$ regarded as a deterministic quantity independent of the data
samples. Then rearranging terms in (5.51) yields

$\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}-\bm{K}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\parallel}=\Big{(}\frac{1}{n}\bm{S}_{\parallel}\bm{S}_{\parallel}^{\top}-\bm{\Lambda}+\bm{K}(\lambda_{l})-\bm{K}^{\perp}(\lambda_{l})\Big{)}\bm{U}^{\star\top}\bm{u}_{l,\parallel},$

which together with (5.49) results in the following bound:

$\big{\|}\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}-\bm{K}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\parallel}\big{\|}_{2}\leq\Big{\|}\frac{1}{n}\bm{S}_{\parallel}\bm{S}_{\parallel}^{\top}-\bm{\Lambda}\Big{\|}+\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\big{\|}\bm{K}(\lambda)-\bm{K}^{\perp}(\lambda)\big{\|},$
(5.54)

Akin to the proof of Theorem 7 in Section, our goal is to show
$\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}-\bm{K}^{\perp}(\lambda_{l})\big{)}\bm{U}^{\star\top}\bm{u}_{l,\parallel}\approx\bm{0}$,
which would then imply that $\lambda_{l}$ is sufficiently close to some
eigenvalue of $\bm{\Lambda}+\bm{K}^{\perp}(\lambda_{l})$. In light of this, we
intend to upper bound the two terms on the right-hand side of (5.54) in the
sequel.

  * •

Let us first look at the first term on the right-hand side of (5.54). Since
the columns of $\bm{S}_{\parallel}=\bm{U}^{\star\top}\bm{S}$ are independent
Gaussian random vectors with distribution $\mathcal{N}(\bm{0},\bm{\Lambda})$,
we can rewrite

$\bm{S}_{\parallel}=\bm{\Lambda}^{1/2}\bm{Z},$ (5.55)

where $\bm{Z}=[Z_{i,j}]\in\mathbb{R}^{r\times n}$ is a Gaussian random matrix
with i.i.d. entries $Z_{i,j}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,1)$.
Applying standard Gaussian concentration inequalities reveals that: with
probability at least $1-O(n^{-10})$,

$\displaystyle\Big{\|}\frac{1}{n}\bm{S}_{\parallel}\bm{S}_{\parallel}^{\top}-\bm{\Lambda}\Big{\|}\leq\|\bm{\Lambda}\|\cdot\Big{\|}\frac{1}{n}\bm{Z}\bm{Z}^{\top}-\bm{I}_{r}\Big{\|}$
$\displaystyle\lesssim(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r\log
n}{n}}.$ (5.56)

  * •

As for the second term on the right-hand side of (5.54), we claim for the
moment that

$\displaystyle\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\big{\|}\bm{K}(\lambda)-\bm{K}^{\perp}(\lambda)\big{\|}$
$\displaystyle\ll(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r}{n}}\log n,$
(5.57)
$\displaystyle\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\|\bm{C}(\lambda)\|$
$\displaystyle\lesssim\frac{\sigma^{2}}{\lambda_{l}^{\star}}\bigg{(}1+\frac{p}{n}\bigg{)},$
(5.58)

where $\bm{C}(\lambda)$ is defined in (5.52). The proof of this claim is
postponed to the end of the section.

Substituting (5.56) and (5.57) into (5.54) reveals that with probability
exceeding $1-O(n^{-10})$,

$\big{\|}\big{(}\lambda_{l}\bm{I}_{r}-\bm{\Lambda}-\bm{K}^{\perp}(\lambda_{l})\big{)}\bm{u}_{l,\parallel}\big{\|}_{2}\lesssim(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r}{n}}\log
n=:\mathcal{E}_{\mathsf{PCA}}.$ (5.59)

With the preceding inequality in place, we are ready to study the eigenvalues
of $\bm{\Lambda}+\bm{K}^{\perp}(\lambda_{l})$. Similar to the analysis in the
proof of Lemma 1 in Appendix B.1, it is straightforward to verify that

$\displaystyle\bm{K}^{\perp}(\lambda)$
$\displaystyle=\beta(\lambda)\bm{\Lambda},$ (5.60)

where $\beta(\lambda)=\frac{1}{n}\mathsf{tr}\big{(}\bm{C}(\lambda)\big{)}$ has
been defined in (5.45). This immediately demonstrates that the $l$-th
eigenvalue of $\bm{\Lambda}+\bm{K}^{\perp}(\lambda_{l})$ is equal to

$\big{(}1+\beta(\lambda_{l})\big{)}(\lambda_{l}^{\star}+\sigma^{2}).$

Moreover, it is readily seen from (5.58) that $\beta(\lambda)$ satisfies

$\displaystyle\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\beta(\lambda)$
$\displaystyle\leq\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\frac{n\wedge
p}{n}\|\bm{C}(\lambda)\|\lesssim\frac{n\wedge
p}{n}\cdot\frac{\sigma^{2}}{\lambda_{l}^{\star}}\bigg{(}1+\frac{p}{n}\bigg{)}\asymp\frac{\sigma^{2}p}{\lambda_{l}^{\star}n}=o(1)$
(5.61)

as long as the noise level obeys $\sigma^{2}p/n\ll\lambda_{\min}^{\star}/\log
n$. Finally, combining (5.60) with (5.46) and (5.59), we can repeat the same
argument as in the proof for Lemma 2 in Section B.2 to reach

$\big{|}\lambda_{l}-(\lambda_{l}^{\star}+\sigma^{2})\big{(}1+\beta(\lambda_{l})\big{)}\big{|}\lesssim(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r}{n}}\log
n;$

for conciseness, we omit the details of proof. This inequality establishes the
proximity of $\lambda_{l}$ and
$(\lambda_{l}^{\star}+\sigma^{2})\big{(}1+\beta(\lambda_{l})\big{)}$. Taking
this collectively with (5.61) (i.e., $1+\beta(\lambda_{l})\asymp 1$), we
establish the advertised bound (5.44).

##### Proof of the inequality (5.57)

Recall the definitions of $\bm{K}(\lambda)$, $\bm{C}(\lambda)$ as well as
$\bm{K}^{\perp}(\lambda)$ in (5.52) and (5.53). Recognizing that one can
express $\bm{S}_{\parallel}=\bm{\Lambda}^{1/2}\bm{Z}$ with
$\bm{Z}\in\mathbb{R}^{r\times n}$ being an i.i.d. standard Gaussian matrix
(see (5.55)), we can define

$\displaystyle\overline{\bm{K}}(\lambda)$
$\displaystyle:=\frac{1}{n}\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}\qquad\text{and}\qquad\overline{\bm{K}}^{\perp}(\lambda):=\mathbb{E}\big{[}\,\overline{\bm{K}}(\lambda)\mid\bm{C}(\lambda)\big{]},$

which allow us to express

$\displaystyle\bm{K}(\lambda)$
$\displaystyle\coloneqq\frac{1}{n}\bm{S}_{\parallel}\bm{C}(\lambda)\bm{S}_{\parallel}^{\top}=\frac{1}{n}\bm{\Lambda}^{1/2}\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}\bm{\Lambda}^{1/2}=\bm{\Lambda}^{1/2}\overline{\bm{K}}(\lambda)\bm{\Lambda}^{1/2},$
$\displaystyle\bm{K}^{\perp}(\lambda)$
$\displaystyle\coloneqq\mathbb{E}\big{[}\bm{K}(\lambda)\mid\bm{C}(\lambda)\big{]}=\bm{\Lambda}^{1/2}\mathbb{E}\big{[}\,\overline{\bm{K}}(\lambda)\mid\bm{C}(\lambda)\big{]}\bm{\Lambda}^{1/2}=\bm{\Lambda}^{1/2}\overline{\bm{K}}^{\perp}(\lambda)\bm{\Lambda}^{1/2}.$

One can then develop the following upper bound

$\displaystyle\big{\|}\bm{K}(\lambda)-\bm{K}^{\perp}(\lambda)\big{\|}$
$\displaystyle=\big{\|}\bm{\Lambda}^{1/2}\big{(}\overline{\bm{K}}(\lambda)-\overline{\bm{K}}^{\perp}(\lambda)\big{)}\bm{\Lambda}^{1/2}\big{\|}\leq\|\bm{\Lambda}\|\big{\|}\overline{\bm{K}}(\lambda)-\overline{\bm{K}}^{\perp}(\lambda)\big{\|}$
$\displaystyle=(\lambda_{\max}^{\star}+\sigma^{2})\frac{1}{n}\big{\|}\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}-\mathbb{E}[\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}\mid\bm{C}(\lambda)]\big{\|}.$
(5.62)

By construction, $\bm{S}_{\parallel}\coloneqq\bm{U}^{\star\top}\bm{S}$ and
$\bm{S}_{\perp}:=(\bm{U}^{\star\perp})^{\top}\bm{S}$ are mutually
statistically independent, thus implying that $\bm{Z}$ is also independent of
$\bm{C}(\lambda)$ with $\lambda$ treated as a deterministic quantity.

The remainder of the proof thus comes down to controlling

$\big{\|}\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}-\mathbb{E}[\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}\mid\bm{C}(\lambda)]\big{\|}.$

By virtue of the rotational invariance of Gaussian random matrices, we can
replace $\bm{C}(\lambda)$ in the quantity above by a diagonal matrix comprised
of the eigenvalues of $\bm{C}(\lambda)$. To see this, we denote by
$\bm{V}\bm{D}\bm{V}^{\top}$ the eigen-decomposition of $\bm{C}(\lambda)$ and
find that

$\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}=\bm{Z}\bm{V}\bm{D}\bm{V}^{\top}\bm{Z}^{\top}\overset{\mathrm{d}}{=}\bm{Z}\bm{D}\bm{Z}^{\top},$

where the last step arises from the rotational invariance of the Gaussian
random matrix, namely $\bm{Z}\bm{V}\overset{\mathrm{d}}{=}\bm{Z}$. In view of
Lemma 18, it suffices to control the eigenvalues of $\bm{C}(\lambda)$.

As can be straightforwardly verified, the rank of $\bm{C}(\lambda)$ is upper
bounded by $(p-r)\wedge n$ and the $i$-th largest eigenvalue of
$\bm{C}(\lambda)$ (cf. (5.52)) satisfies

$\displaystyle\lambda_{i}\big{(}\bm{C}(\lambda)\big{)}$
$\displaystyle=\lambda_{i}\Big{(}\frac{1}{n}\bm{S}_{\perp}^{\top}\Big{(}\lambda\bm{I}_{p-r}-\frac{1}{n}\bm{S}_{\perp}\bm{S}_{\perp}^{\top}\Big{)}^{-1}\bm{S}_{\perp}\Big{)}=\frac{\lambda_{i}(\frac{1}{n}\bm{S}_{\perp}\bm{S}_{\perp}^{\top})}{\lambda-\lambda_{i}(\frac{1}{n}\bm{S}_{\perp}\bm{S}_{\perp}^{\top})},\qquad
1\leq i\leq(p-r)\wedge n.$

In addition, (D.4) demonstrates that with probability at least $1-O(n^{-10})$,

$0\leq\lambda_{i}\Big{(}\frac{1}{n}\bm{S}_{\perp}\bm{S}_{\perp}^{\top}\Big{)}\lesssim\sigma^{2}\bigg{(}1+\sqrt{\frac{p}{n}}+\frac{p}{n}+\sqrt{\frac{\log
n}{n}}\bigg{)}\ll\lambda_{\min}^{\star},\qquad 1\leq i\leq(p-r)\wedge n,$

where the last step holds due to the noise assumption (3.13a). Combining these
two observations establishes the claim bound (5.58):

$\displaystyle\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\|\bm{C}(\lambda)\|$
$\displaystyle\lesssim\frac{\sigma^{2}}{\lambda_{l}^{\star}}\bigg{(}1+\sqrt{\frac{p}{n}}+\frac{p}{n}+\sqrt{\frac{\log
n}{n}}\bigg{)}\asymp\frac{\sigma^{2}}{\lambda_{l}^{\star}}\bigg{(}1+\frac{p}{n}\bigg{)},$

where the last step arises from the Cauchy-Schwarz inequality. Consequently,
one can invoke Lemma 18 and apply the standard epsilon-net argument (similar
to the proof of Lemma 1 in Appendix B.1 and hence omitted here) to demonstrate
that

$\displaystyle\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\frac{1}{n}\big{\|}\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}-\mathbb{E}[\bm{Z}\bm{C}(\lambda)\bm{Z}^{\top}\mid\bm{C}(\lambda)]\big{\|}$
$\displaystyle\qquad\lesssim\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\frac{1}{n}\|\bm{C}(\lambda)\|_{\mathrm{F}}\sqrt{r\log
n}+\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\frac{1}{n}\|\bm{C}(\lambda)\|\big{(}r\log
n+\log^{2}n\big{)}$
$\displaystyle\qquad\lesssim\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\frac{1}{n}\|\bm{C}(\lambda)\|\sqrt{r(n\wedge
p)}\,\log^{2}n$
$\displaystyle\qquad\lesssim\frac{\sigma^{2}}{\lambda_{l}^{\star}}\bigg{(}\frac{p}{n}+\sqrt{\frac{p}{n}}\bigg{)}\sqrt{\frac{r}{n}}\,\log^{2}n\ll\sqrt{\frac{r}{n}}\log
n$

with probability at least $1-O(n^{-10})$. Here, the last line follows from
(5.58) and the noise assumption that
$\sigma^{2}(p/n+\sqrt{p/n})\ll\lambda_{\min}^{\star}/\log n$. Combining this
with (5.62), we arrive at

$\sup_{\lambda:\,\lambda\in[2\lambda_{l}^{\star}/3,4\lambda_{l}^{\star}/3]}\big{\|}\bm{K}(\lambda)-\bm{K}^{\perp}(\lambda)\big{\|}\ll(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r}{n}}\log
n$

as claimed.

####  5.3.2 Proof of eigenvector perturbation theory (Theorem 3)

We now turn to our eigenvector perturbation theory. As before, we find it
convenient to decompose the $l$-th eigenvector $\bm{u}_{l}$ of
$\frac{1}{n}\bm{S}\bm{S}^{\top}$ as follows

$\bm{u}_{l}=\bm{u}_{l}^{\star}\cos\theta+\bm{u}_{l,\perp}\sin\theta,$ (5.63)

where the vector $\bm{u}_{l,\perp}$ obeys $\|\bm{u}_{l,\perp}\|_{2}=1$ and
$\bm{u}_{l,\perp}^{\top}\bm{u}_{l}^{\star}=0$. We shall employ this
decomposition to identify several key quantities that we’d like to control.
Specifically, armed with this decomposition, we can derive

$\displaystyle\bm{a}^{\top}\bm{u}_{l}=$
$\displaystyle(\bm{P}_{\bm{U}^{\star}}\bm{a})^{\top}\bm{u}_{l}+(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}\bm{u}_{l}$
$\displaystyle=$
$\displaystyle(\bm{P}_{\bm{U}^{\star}}\bm{a})^{\top}(\bm{u}_{l}^{\star}\cos\theta+\bm{u}_{l,\perp}\sin\theta)+(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}\bm{u}_{l}$
$\displaystyle=$ $\displaystyle\sum_{1\leq k\leq
r}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}(\bm{u}_{l}^{\star}\cos\theta+\bm{u}_{l,\perp}\sin\theta)+(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}(\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l})$
$\displaystyle=$
$\displaystyle\bm{a}^{\top}\bm{u}_{l}^{\star}\cos\theta+\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta+(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}(\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}),$

where we use the fact that
$\bm{a}=\bm{P}_{\bm{U}^{\star}}\bm{a}+\bm{P}_{\bm{U}^{\star\perp}}\bm{a}$ with

$\bm{P}_{\bm{U}^{\star}}=\Sigma_{1\leq k\leq
r}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\qquad\text{and}\qquad\bm{P}_{\bm{U}^{\star\perp}}=\bm{I}-\bm{P}_{\bm{U}^{\star}}.$

As a result, we arrive at

$\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}=\bm{a}^{\top}\bm{u}_{l}^{\star}(\cos\theta\pm
1)+\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta+(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}(\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}),$

which further implies

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\leq$
$\displaystyle\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}(1-|\cos\theta|)+\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}+\big{|}(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}(\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l})\big{|}$
$\displaystyle\leq$
$\displaystyle\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}(1-\cos^{2}\theta)+\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}+\big{|}(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}(\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l})\big{|}.$
(5.64)

and

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\sqrt{1+c_{l}}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\leq\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\cdot\big{|}1-\sqrt{1+c_{l}}|\cos\theta|\big{|}+\sqrt{1+c_{l}}\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}$
$\displaystyle\quad+\sqrt{1+c_{l}}\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}.$
(5.65)

Thus, it comes down to bounding the following terms

$1-\cos^{2}\theta,\quad
1-\sqrt{1+c_{l}}|\cos\theta|,\quad\sqrt{1+c_{l}},\quad\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta,\quad\text{and}\quad\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle.$

separately, which forms the main content of the remainder of the proof.

We claim that
$\lambda_{l}\bm{I}_{p-1}-(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star\perp}$
is invertible. This will be seen from (5.75) stated in Lemma 8 directly. The
invertibility taken together with Theorem 5 reveals that $\cos\theta\neq 0$.
If $\sin\theta=0$, then we have $\bm{u}_{l}=\pm\bm{u}_{l}^{\star}$ and the
conclusion is obvious since
$\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}=0$.
Therefore, it suffices to focus on the case where $\cos\theta\neq 0$ and
$\sin\theta\neq 0$ in the sequel.

##### 1\. Identifying several key quantities.

Invoke Theorem 5 to show that

$\displaystyle\cos^{2}\theta$
$\displaystyle=\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{p-1}-(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star\perp}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star}\big{\|}_{2}^{2}},$
(5.66a) $\displaystyle\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}$
$\displaystyle=\frac{\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star\perp}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star}}{\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star\perp}\big{)}^{-1}(\bm{u}_{l}^{\star\perp})^{\top}\frac{1}{n}\bm{S}\bm{S}^{\top}\bm{u}_{l}^{\star}\big{\|}_{2}}.$
(5.66b)

For notational convenience, we shall define

$\displaystyle\bm{s}_{l,\parallel}$
$\displaystyle:=\bm{u}_{l}^{\star\top}\bm{S}\in\mathbb{R}^{1\times
n}\qquad\text{and}\qquad\bm{S}_{l,\perp}:=(\bm{u}_{l}^{\star\perp})^{\top}\bm{S}\in\mathbb{R}^{(p-1)\times
n},$ (5.67)

allowing us to write (5.66) more succinctly as follows

$\displaystyle\cos^{2}\theta$
$\displaystyle=\frac{1}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}},$
(5.68a) $\displaystyle\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}$
$\displaystyle=\frac{\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}}{\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}}.$
(5.68b)

With the above relations in mind, we can demonstrate that

$\displaystyle\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\sin\theta\Big{|}=\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l,\perp}\Big{|}\sqrt{1-\cos^{2}\theta}$
$\displaystyle\quad=\frac{\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{|}}{\big{\|}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}}\cdot\sqrt{\frac{\big{\|}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}{1+\big{\|}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}}$
$\displaystyle\quad\leq\left|\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\right|,$

where the last step follows since the columns of $\bm{u}_{l}^{\star\perp}$ are
orthonormal. Substitution into (5.64) then yields

$\displaystyle\min\big{|}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\leq\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\cdot(1-\cos^{2}\theta)+\big{|}(\bm{P}_{\bm{U}^{\star\perp}}\bm{a})^{\top}(\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l})\big{|}$
$\displaystyle\quad+\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{|};$
(5.69)

and

$\displaystyle\min\big{|}\sqrt{1+c_{l}}\bm{a}^{\top}\bm{u}_{l}\pm\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}$
$\displaystyle\leq\big{|}\bm{a}^{\top}\bm{u}_{l}^{\star}\big{|}\cdot\big{|}1-\sqrt{1+c_{l}}|\cos\theta|\big{|}+\sqrt{1+c_{l}}\big{|}\langle\bm{P}_{\bm{U}^{\star\perp}}\bm{a},\,\bm{P}_{\bm{U}^{\star\perp}}\bm{u}_{l}\rangle\big{|}$
$\displaystyle\quad+\sqrt{1+c_{l}}\Big{|}\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{|}.$
(5.70)

In what follows, we shall control these quantities separately.

##### 2\. Controlling the spectrum of
$\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}$.

Before moving forward to bound the terms mentioned above, we take a moment to
first look at the eigenvalues of
$\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}$. We first introduce some
useful notation as follows:

  * •

Let $\\{\gamma_{i}^{(l)}\\}_{i=1}^{p-1}$ denote the eigenvalues of
$\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}$ (see the definition of
$\bm{S}_{l,\perp}$ in (5.67)), and we assume that

$\gamma_{1}^{(l)}\geq\cdots\geq\gamma_{p-1}^{(l)}.$ (5.71)

  * •

Let $\bm{u}_{i}^{(l)}$ be the eigenvector of
$\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}$ associated with the
eigenvalue $\gamma_{i}^{(l)}$.

Similar to (5.32), we find it helpful to introduce the following matrices

$\displaystyle\bm{U}_{\smallsetminus l}^{\star}$
$\displaystyle:=[\bm{u}_{1}^{\star},\cdots,\bm{u}_{l-1}^{\star},\bm{u}_{l+1}^{\star},\cdots,\bm{u}_{r}^{\star}]\in\mathbb{R}^{p\times(r-1)};$
(5.72a) $\displaystyle\bm{U}^{\star(l)}$
$\displaystyle:=(\bm{u}_{l}^{\star\perp})^{\top}\bm{U}_{\smallsetminus
l}^{\star}=\begin{bmatrix}\bm{I}_{r-1}\\\
\bm{0}\end{bmatrix}\in\mathbb{R}^{(p-1)\times(r-1)};$ (5.72b)
$\displaystyle\bm{U}^{\star(l)\perp}$
$\displaystyle:=(\bm{u}_{l}^{\star\perp})^{\top}\bm{U}^{\star\perp}=\begin{bmatrix}\bm{0}\\\
\bm{I}_{p-r}\end{bmatrix}\in\mathbb{R}^{(p-1)\times(p-r)};$ (5.72c)
$\displaystyle\bm{\Lambda}^{\star(l)}$
$\displaystyle:=\mathsf{diag}\big{(}\\{\lambda_{i}^{\star}\\}_{i:i\neq
l}\big{)}\in\mathbb{R}^{(r-1)\times(r-1)}.$ (5.72d) In addition, we define
$\bm{u}_{i,\parallel}^{(l)}:=\frac{1}{\big{\|}\bm{P}_{\bm{U}^{\star(l)}}\bm{u}_{i}^{(l)}\big{\|}_{2}}\bm{P}_{\bm{U}^{\star(l)}}\bm{u}_{i}^{(l)},\qquad
i\neq l,$ (5.72e)

where
$\bm{P}_{\bm{U}^{\star(l)}}=\bm{U}^{\star(l)}\big{(}\bm{U}^{\star(l)}\big{)}^{\top}$.
Equipped with this set of notation, we are ready to present a lemma that
characterizes the eigenvalues of the matrix
$\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}$.

######  Lemma 8.

Instate the assumptions of Theorem 3, and recall the definition of
$\beta(\cdot)$ in (5.45). With probability at least $1-O(n^{-10})$, the
eigenvalues $\\{\gamma_{i}^{(l)}\\}_{i=1}^{p-1}$ of
$\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}$ (see (5.71)) satisfy the
following properties.

  1. 1.

For each $1\leq i<r$, one has

$\frac{\gamma_{i}^{(l)}}{1+\beta(\gamma_{i}^{(l)})}\in\mathcal{B}_{\mathcal{E}_{\mathsf{PCA}}}(\lambda_{k}^{\star}+\sigma^{2})\qquad\text{for
some }k\neq l\text{ and }1\leq k\leq r$

and

$\Big{\|}\Big{(}\gamma_{i}^{(l)}\bm{I}_{r-1}-\big{(}1+\beta(\gamma_{i}^{(l)})\big{)}\big{(}\bm{\Lambda}^{\star(l)}+\sigma^{2}\bm{I}_{r-1}\big{)}\Big{)}\bm{U}^{\star(l)\top}\bm{u}_{i,\parallel}^{(l)}\Big{\|}_{2}\lesssim\mathcal{E}_{\mathsf{PCA}},$

where $\mathcal{E}_{\mathsf{PCA}}$ is defined in (5.59).

  2. 2.

For each $r\leq i\leq n\wedge(p-1)$, one has

$\left|\gamma_{i}^{(l)}-\sigma^{2}\frac{p\vee
n}{n}\right|\lesssim\sigma^{2}\sqrt{\frac{p+\log n}{n}}.$ (5.73)

  3. 3.

For each $n\wedge(p-1)<i\leq p-1$, we have $\gamma_{i}^{(l)}=0$.

  4. 4.

Furthermore, one has

$|\lambda-\lambda_{l}|\gtrsim\begin{cases}\Delta_{l}^{\star},&\text{if}\
\frac{\lambda}{1+\beta(\lambda)}\in\mathcal{B}_{\mathcal{E}_{\mathsf{PCA}}}(\lambda_{i}^{\star}+\sigma^{2})\quad\text{\text{for
some }}i\neq l\text{ and }1\leq i\leq r;\\\ \lambda_{l}^{\star},&\text{if}\
\big{|}\lambda-\sigma^{2}\frac{p\vee
n}{n}\big{|}\lesssim\sigma^{2}\sqrt{\frac{p+\log n}{n}}.\end{cases}$ (5.74)

In particular, one has

$\big{|}\gamma_{i}^{(l)}-\lambda_{l}\big{|}\gtrsim\begin{cases}\Delta_{l}^{\star},&1\leq
i<r;\\\ \lambda_{l}^{\star},&i\geq r.\end{cases}$ (5.75)

###### Proof.

See Appendix D.2.∎

##### 3\. Controlling $\cos^{2}\theta$.

In view of the expression of $\cos^{2}\theta$ in (5.68a), it suffices to
control
$\|(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\|_{2}^{2}$,
which is accomplished in the following lemma.

######  Lemma 9.

Consider any $1\leq l\leq r$. Instate the assumptions of Theorem 3, and recall
the definition of $c_{l}$ in (3.12). The following holds with probability at
least $1-O(n^{-10})$:

$\Big{\|}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{\|}_{2}^{2}\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}p\log^{2}n}{\lambda_{l}^{\star
2}n}\ll 1.$ (5.76)

Moreover, for the case with $n\geq p$, one has

$\displaystyle\bigg{|}\Big{\|}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{\|}_{2}^{2}-c_{l}\bigg{|}$
$\displaystyle\qquad\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{\sigma^{2}p}{\lambda_{l}^{\star
2}n}\bigg{(}(\lambda_{l}^{\star}+\sigma^{2})\sqrt{\frac{\log
n}{p}}+(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r\log n}{n}}\bigg{)},$
(5.77)

and for the case with $p>n$, we have

$\bigg{|}\Big{\|}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{\|}_{2}^{2}-c_{l}\bigg{|}\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{\sigma^{2}\kappa\sqrt{pr\log
n}}{\lambda_{l}^{\star}n}.$ (5.78)

###### Proof.

See Appendix D.3.∎

This lemma taken collectively with (5.68a) leads to

$\displaystyle|\cos^{2}\theta-1|$
$\displaystyle=\Bigg{|}\frac{1}{1+\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}-1\Bigg{|}$
$\displaystyle=\frac{\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}{1+\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}$
$\displaystyle\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{(\lambda_{l}^{\star}+\sigma^{2})\sigma^{2}p\log^{2}n}{\lambda_{l}^{\star
2}n}\ll 1.$ (5.79)

where the last step follows from the assumptions (3.13a) and (3.13b). In
addition, when $n\geq p$, one can combine (5.68a) and (5.77) to demonstrate
that

$\displaystyle\big{|}(1+c_{l})\cos^{2}\theta-1\big{|}=\Bigg{|}\frac{1+c_{l}}{1+\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}-1\Bigg{|}$
$\displaystyle\qquad=\frac{\Big{|}c_{l}-\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}\Big{|}}{1+\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}$
$\displaystyle\qquad\leq\Big{|}c_{l}-\Big{\|}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{\|}_{2}^{2}\Big{|}$
$\displaystyle\qquad\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{\sigma^{2}p}{\lambda_{l}^{\star
2}n}\bigg{(}(\lambda_{\max}^{\star}+\sigma^{2})\sqrt{\frac{r\log
n}{n}}+(\lambda_{l}^{\star}+\sigma^{2})\frac{\log^{2}n}{\sqrt{p}}\bigg{)},$
(5.80)

where the first line comes from the definition of $\cos^{2}\theta$ in (5.68a),
and the last inequality holds due to (5.77). Moreover, if $p>n$, putting
(5.68a) and (5.78) together reveals that

$\displaystyle\big{|}(1+c_{l})\cos^{2}\theta-1\big{|}$
$\displaystyle=\Bigg{|}\frac{1+c_{l}}{1+\big{\|}(\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top})^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\big{\|}_{2}^{2}}-1\Bigg{|}$
$\displaystyle\leq\Big{|}c_{l}-\Big{\|}\Big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\Big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}\Big{\|}_{2}^{2}\Big{|}$
$\displaystyle\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{\sigma^{2}\kappa\sqrt{pr\log
n}}{\lambda_{l}^{\star}n}\ll 1,$ (5.81)

where the last inequality holds due to the conditions (3.13a) and (3.13b).
Taken collectively with (5.79), this leads to $1+c_{l}\lesssim 1$ and

$\displaystyle\big{|}1-\sqrt{1+c_{l}}|\cos\theta|\big{|}$
$\displaystyle=\bigg{|}\frac{1-(1+c_{l})\cos^{2}\theta}{1+\sqrt{1+c_{l}}|\cos\theta|}\bigg{|}\lesssim\big{|}1-(1+c_{l})\cos^{2}\theta\big{|}$
$\displaystyle\lesssim\frac{(\lambda_{\max}^{\star}+\sigma^{2})(\lambda_{l}^{\star}+\sigma^{2})r\log
n}{\big{(}\Delta_{l}^{\star}\big{)}^{2}n}+\frac{\sigma^{2}\kappa\sqrt{pr\log
n}}{\lambda_{l}^{\star}n}.$ (5.82)

##### 4\. Controlling $\sum_{k:k\neq
l}\bm{a}^{\top}\bm{u}_{k}^{\star}\bm{u}_{k}^{\star\top}\bm{u}_{l}^{\star\perp}\big{(}\lambda_{l}\bm{I}_{p-1}-\frac{1}{n}\bm{S}_{l,\perp}\bm{S}_{l,\perp}^{\top}\big{)}^{-1}\frac{1}{n}\bm{S}_{l,\perp}\bm{s}_{l,\parallel}^{\top}$.

Recognizing that the vector $\bm{s}_{l,\parallel}$ (see (5.67)) obeys

$\bm{s}_{l,\parallel}\sim\mathcal{N}\big{(}\bm{0},(\lambda_{l}^{\star}+\sigma^{2})\bm{I}_{n}\big{)}$

and is independent of $\bm{S}_{l,\perp}$ (see (5.67)), we can control this
quantity through the lemma below.

######  Lemma 10.