arXiv:1708.07642v1 [math.ST] 25 Aug 2017

arXiv: arXiv:0000.0000

Efficient Estimation of Linear
Functionals of Principal Components
Vladimir Koltchinskii1 , Matthias Löffler2,* , and Richard Nickl2,**
1 School

of Mathematics Georgia Institute of Technology Atlanta, GA 30332-0160, United
States of America. e-mail: vlad@math.gatech.edu

2 Statistical

Laboratory, Centre for Mathematical Sciences, University of Cambridge,
Wilberforce Road, CB3 0WB Cambridge, United Kingdom. e-mail:
* m.loffler@statslab.cam.ac.uk; ** r.nickl@statslab.cam.ac.uk

Abstract: We study principal component analysis (PCA) for mean zero
i.i.d. Gaussian observations X1 , . . . , Xn in a separable Hilbert space H with
unknown covariance operator Σ. The complexity of the problem is charactr(Σ)
terized by its effective rank r(Σ) := kΣk , where tr(Σ) denotes the trace of
Σ and kΣk denotes its operator norm. This framework includes, in particular, high-dimensional spiked covariance models as well as some models in
functional PCA and kernel PCA in machine learning.
We develop a method of bias reduction in the problem of estimation of
linear functionals of eigenvectors of Σ. Under the assumption that r(Σ) =
o(n), we establish the asymptotic normality and asymptotic properties of
the risk of the resulting estimators and prove matching minimax lower
bounds, showing their semi-parametric optimality.
Keywords and phrases: principal component analysis, spectral projections, asymptotic normality, semi-parametric efficiency.

1. Introduction
Principal Component Analysis (PCA) is commonly used as a dimension reduction technique for high-dimensional data sets. Assuming a general framework
where the data lies in a Hilbert space H, PCA can be applied to a wide range
of problems such as functional data analysis [24, 19] or machine learning [4].
The parametric setting has been well understood since the 1960’s (e.g. [1]
and [7]) and the asymptotic distribution of sample eigenvalues and sample
eigenvectors is well known. For high-dimensional data, where the dimension
p = p(n) → ∞ with the sample size n, the spiked covariance model introduced
by Johnstone in [14] has been the most common framework to study the asymptotic properties of principal components. In this model, it is assumed that the
covariance matrix is given by a ’spike’ and a noise part, that is
Σ=

l
X
j=1

1 Supported
2 Supported

si (θi ⊗ θi ) + σ 2 Ip ,

in part by NSF Grants DMS-1509739 and CCF-1523768
in part by ERC Grant UQMSI/647813
1

/Efficient estimation in PCA

2

Pl
where
j=1 si (θi ⊗ θi ) is a low rank covariance matrix involving several orthonormal components (’spikes’) θi and σ 2 Ip is the covariance of the noise. Error bounds in this model, based on perturbation analysis, were studied in [20].
Moreover, if np → c ∈ (0, 1] the asymptotic distribution of sample eigenvectors
was derived in [23] and in more general asymptotic regimes in [33]. Assuming sparsity of the eigenvectors (sparse PCA), inference is possible even when
p
n → ∞. This model has recently received a lot of attention, e.g. [6, 2, 31, 32, 9].
More recently, a so-called ’effective rank’ setting for PCA has been considered, for example, in [15, 16, 17, 30, 25, 21]. In this dimension-free setting, it is
assumed that the covariance Σ is an operator acting in a Hilbert space H, no
structural assumptions are made about Σ and its ’complexity’ is characterized
by the effective rank r(Σ) := tr(Σ)/kΣk, tr(Σ) denoting the trace and kΣk denoting the operator (spectral) norm of Σ. In a series of papers [16, 15, 17, 18],
Koltchinskii and Lounici derived sharp bounds on the spectral norm loss of estimation of Σ by the sample covariance Σ̂ that provide complete characterization
of the size of kΣ̂ − Σk in terms of kΣk and r(Σ), and obtained error bounds and
limiting results for empirical spectral projection operators and eigenvectors of
Σ̂ under the assumption that r(Σ) = o(n) as n → ∞. In a recent paper [21],
Naumov et. al. constructed bootstrap confidence sets for spectral projections
in a lower dimensional regime where r(Σ) = o(n1/3 ). In [25], Reiss and Wahl
considered the reconstruction error for spectral projections.
In this paper, we further develop the results of [15] and [17] in the direction of
semi-parametric statistics. In particular, we develop a bias reduction method in
the problem of estimation of linear functionals of principal components (eigenvectors of Σ) and show asymptotic normality of the resulting de-biased estimators under the assumption that r(Σ) = o(n). We prove a non-asymptotic risk
lower bound that asymptotically exactly matches our upper bounds, thus establishing rigorously the semi-parametric optimality of our estimator in a general
dimension-free setting
√ (as long as r(Σ) = o(n)).
The problem of n-consistent estimation of low-dimensional functionals of
high-dimensional parameters has received increased attention in recent years,
and in various models semi-parametric efficiency of regularisation-based estimators has been studied, see for instance [27, 12, 26, 22]. While formal calculations
of the Fisher information in such models indicate optimality of these procedures, a rigorous interpretation of such efficiency claims requires some care:
the standard asymptotic setting for semi-parametric efficiency [28] can not be
straightforwardly applied because parameters in high-dimensional models are
not fixed but vary with sample size n, so that establishing LAN expansions
to apply Le Cam theory is not always possible or even desirable. In [12] some
non-asymptotic techniques have been suggested under conditions that ensure
asymptotic negligibility of the bias of candidate estimators. We take here a
different approach, based on using van Trees’ inequality [10] to construct nonasymptotic lower bounds for the minimax risk in our estimation problem that
match the upper bound exactly in the large sample limit.

/Efficient estimation in PCA

3

2. Preliminaries
2.1. Some notations and conventions.
Let H be a separable Hilbert space. In what follows, h·, ·i denotes the inner
product of H and also, with a little abuse of notation, the Hilbert–Schmidt
inner product between Hilbert–Schmidt operators acting on H. Similarly, the
notation k · k is used both for the norm of vectors in H and for the operator
(spectral) norm of bounded linear operators in H. For a nuclear operator A,
tr(A) denotes its trace. We use the notation k · kp , 1 ≤ p ≤ ∞ √
for the Schatten
p-norms of operators in H : kAkp := (tr(|A|p ))1/p , where |A| = A∗ A, A∗ being
the adjoint operator of A. For p = 1, kAk1 is the nuclear norm; for p = 2, kAk2
is the Hilbert–Schmidt norm; for p = ∞, kAk∞ = kAk is the operator norm.
Given vectors u, v ∈ H, u ⊗ v denotes the tensor product of u and v :
(u ⊗ v) : H 7→ H, (u ⊗ v)w := hv, wiu.
Given bounded linear operators A, B : H 7→ H, A ⊗ B denotes their tensor
product:
(A ⊗ B)(u ⊗ v) = Au ⊗ Bv, u, v ∈ H.

Note that A ⊗ B can be extended (by linearity and continuity) to a bounded
operator in the Hilbert space H ⊗ H, which could be identified with the space
of Hilbert–Schmidt operators in H. It is easy to see that, for a Hilbert–Schmidt
operator C, we have (A ⊗ B)C = ACB ∗ (in the finite-dimensional case, this
defines the so called Kronecker product of matrices). On a couple of occasions,
we might need to use the tensor product of Hilbert–Schmidt operators A, B,
viewed as vectors in the space of Hilbert–Schmidt operators. For this tensor
product, we use the notation A ⊗v B.
Throughout the paper, the following notations will be used: for nonnegative
a, b, a . b means that there exists a numerical constant c > 0 such that a ≤
cb; a & b is equivalent to b . a; finally, a ≍ b is equivalent to a . b and
b . a. Sometimes, constant c in the above relationships could depend on some
parameter γ. In this case, we provide signs ., & and ≍ with subscript γ. For
instance, a .γ b means that there exists a constant cγ > 0 such that a ≤ cγ b.
In many places in the proofs, we use exponential bounds for some random
variables, say, ξ of the following form: for all t ≥ 1 with probability at least
1 − e−t , ξ ≤ Ct. In some cases, it would follow from our arguments that the
inequality holds with a slightly different probability, say, at least 1 − 3e−t . In
such cases, it is easy to rewrite the bound again as 1−e−t by adjusting the value
of constant C. Indeed, for t ≥ 1 with probability at least 1−e−t = 1−3e−t−log(3) ,
we have ξ ≤ C(t + log(3)) ≤ 2 log(3)Ct. We will use such an adjustment of the
constants in many proofs, often, without further notice.
2.2. Bounds on sample covariance.
Let X be a Gaussian vector in H with mean EX = 0 and covariance operator
Σ := E(X ⊗ X). Given i.i.d. observations X1 , . . . , Xn of X, let Σ̂ = Σ̂n be the

/Efficient estimation in PCA

4

sample (empirical) covariance operator defined as follows:
Σ̂ := n−1

n
X
j=1

Xj ⊗ Xj .

Definition 2.1. The effective rank of the covariance operator Σ is defined as
r(Σ) :=

tr(Σ)
.
kΣk

The role of the effective rank as a complexity parameter in covariance estimation is clear from the following result proved in [16].
Theorem 2.1. Let X be a mean zero Gaussian random vector in H with covariance operator Σ and let Σ̂ be the sample covariance based on i.i.d. observations
X1 , . . . , Xn of X. Then

r
r(Σ) _ r(Σ)
.
(2.1)
EkΣ̂ − Σk ≍ kΣk
n
n
This result shows that the size of the properly rescaled operator norm deviΣ̂−Σk
ation of Σ̂ from Σ, EkkΣk
, is characterized up to numerical constants by the

ratio r(Σ)
n . In particular, the condition r(Σ) = o(n) is necessary and sufficient
for operator norm consistency of Σ̂ as an estimator of Σ. In addition to this, the
following concentration inequality for kΣ̂ − Σk around its expectation was also
proved in [16].
Theorem 2.2. Under the conditions of the previous theorem, for all t ≥ 1 with
probability at least 1 − e−t
r _ 
r
t
r(Σ) _
t
.
(2.2)
1
kΣ̂ − Σk − EkΣ̂ − Σk . kΣk
n
n
n
It immediately follows from the bounds (2.1) and (2.2) that, for all t ≥ 1
with probability at least 1 − e−t
r
r

r(Σ) _ r(Σ) _ t _ t
kΣ̂ − Σk . kΣk
(2.3)
n
n
n
n

and, for all p ∈ [1, ∞),

1/p

E

p

kΣ̂ − Σk .p kΣk

r


r(Σ) _ r(Σ)
.
n
n

(2.4)

2.3. Perturbation theory and empirical spectral projections.
The covariance operator Σ is self-adjoint, positively semidefinite and nuclear. It
has spectral decomposition
X
Σ=
µr Pr ,
r≥1

/Efficient estimation in PCA

5

where µr are distinct strictly positive eigenvalues of Σ arranged in decreasing
order and Pr are the corresponding spectral projection operators. For r ≥ 1,
Pr is an orthogonal projection on the eigenspace of the eigenvalue µr . The
dimension of this eigenspace is finite and will be denoted by mr . The eigenspaces
corresponding to different eigenvalues µr are mutually orthogonal. Denote by
σ(Σ) the spectrum of operator Σ and let λj = λj (Σ), j ≥ 1 be the eigenvalues
of Σ arranged in a non-increasing order and repeated with their multiplicities.
Denote ∆r := {j : λj = µr }, r ≥ 1. Then card(∆r ) = mr . The r-th spectral gap
is defined as
gr = gr (Σ) := dist(µr ; σ(Σ) \ {µr }).

Let ḡr = ḡr (Σ) := min1≤s≤r gs .
We turn now to the definition of empirical spectral projections of sample
covariance Σ̂ that could be viewed as estimators of the true spectral projections
Pr , r ≥ 1. In [15], the following definition was used: let P̂r be the orthogonal
projection on the direct sum of eigenspaces of Σ̂ corresponding to its eigenvalues
{λj (Σ̂) : j ∈ ∆r }. This is not a perfect definition of a statistical estimator since
the set ∆r is unknown and it has to be recovered from the spectrum σ(Σ̂) of Σ̂.
When Σ̂ is close to Σ in the operator norm, the spectrum σ(Σ̂) of Σ̂ is a
small perturbation of the spectrum σ(Σ) of Σ. This could be quantified by the
following inequality that goes back to H. Weyl:
sup |λj (Σ̂) − λj (Σ)| ≤ kΣ̂ − Σk.

(2.5)

j≥1

It easily follows from this inequality that, if kΣ̂ − Σk is sufficiently small, then
the eigenvalues λj (Σ̂) of Σ̂ form well separated clusters around the eigenvalues µ1 , µ2 , . . . of Σ. To make the last claim more precise, consider a finite or
countable bounded set A ⊂ R+ such that 0 ∈ Anand 0 is the only limit point
o
(if any) of A. Given δ > 0, define λδ (A) := max λ ∈ A : (λ − δ, λ) ∩ A = ∅
and let Tδ (A) := A \ [0, λδ (A)). The set Tδ (A) will be called the top δ-cluster
of A. Let A1 := Tδ (A), A2 := Tδ (A \ A1 ), A3 := Tδ (A \ (A1 ∪ A2 )), . . . and
ν = νδ := min{j : Aj+1 = ∅}. Obviously, ν < ∞. We will call the sets A1 , . . . , Aν
the δ-clusters of A. They provide a partition of A into sets separated by the gaps
of length at least δ and such that the gaps between the points inside each of the
clusters are smaller than δ.
The next lemma easily follows from inequality (2.5).
Lemma 2.1. Let δ > 0 be such that, for some r ≥ 1,
kΣ̂ − Σk < δ/2 and δ <

ḡr
.
2

Let Âδ1 , . . . , Âδν be the δ-clusters of the set σ(Σ̂). Then ν ≥ r and, for all 1 ≤
s≤r
Âδs ⊂ (µs − δ/2, µs + δ/2) and {j : λj (Σ̂) ∈ Âδs } = ∆s .

Given δ > 0 and δ-clusters Âδ1 , . . . , Âδν of σ(Σ̂), define, for 1 ≤ s ≤ ν, the
empirical spectral projection P̂sδ as the orthogonal projection on the direct sum

/Efficient estimation in PCA

6

of eigenspaces of Σ̂ corresponding to its eigenvalues from the cluster Âδs . It
immediately follows from Lemma 2.1 that, under its assumptions on δ, P̂sδ =
P̂s , s = 1, . . . , r.
In the following sections, we will be interested in the problem of estimation
of spectral projections in the case when the true covariance Σ belongs to certain
subsets of the following class of covariance operators:


kΣk
(r)
≤a ,
S (r; a) := Σ : r(Σ) ≤ r,
ḡr (Σ)
where a > 1, r > 1. We will allow the effective rank to be large, r = rn → ∞,
but not too large such that rn = o(n) as n → ∞. For Σ ∈ S (r) (r; a), we take
δ := τ kΣ̂k for a sufficiently small value of the constant τ > 0 in the definition
of spectral projections P̂sδ .
The following lemma is an easy consequence of the exponential bound (2.3).


1 V
Lemma 2.2. Suppose a > 1 and rn = o(n) as n → ∞. Take τ ∈ 0, 4a 2
and δ := τ kΣ̂k. Then, there exists a numerical constant β > 0 such that, for all
large enough n,
sup
Σ∈S (r) (r;a)

PΣ {∃s = 1, . . . , r : P̂sδ 6= P̂s } ≤ e−βτ

2

n

.

Proof. By (2.3) with t := βτ 2 n, we obtain that

r _ r 2 
2
rn
βτ n
≤ e−βτ n ,
sup
PΣ kΣ̂ − Σk ≥ CkΣk
n
n
Σ∈S (r) (r;a)
where C > 0 is a numerical constant. Take β =
p
enough n, C rnn ≤ τ /4 to obtain that
sup

Σ∈S (r) (r;a)

1
16C 2

and note that, for all large

PΣ {kΣ̂ − Σk ≥ (τ /4)kΣk} ≤ e−βτ

2

n

,

Since τ /4 ≤ 1/2, we easily obtain that, for all Σ ∈ S (r) (r; a) and for all n large
2
enough with probability at least 1 − e−βτ n , (1/2)kΣk ≤ kΣ̂k ≤ 2kΣk. This
implies that with the same probability (and on the same event)
kΣ̂ − Σk < (τ /4)kΣk ≤ (τ /2)kΣ̂k = δ/2.
On the other hand, for all Σ ∈ S (r) (r; a),
δ = τ kΣ̂k ≤ 2τ kΣk <

1
ḡr (Σ)
kΣk ≤
.
2a
2

It remains to use Lemma 2.1 to complete the proof.
In the proofs of the main results of the paper, we deal for the most part with
spectral projections P̂r that were studied in detail in [15]. We use Lemma 2.2
to reduce the results for P̂rδ to the results for P̂r .

/Efficient estimation in PCA

7

3. Main Results
Our main goal is to develop an efficient estimator of the linear functional hθr , ui,
where u ∈ H is a given vector and θr = θr (Σ) is a unit eigenvector of the unknown covariance operator Σ corresponding to its r–th eigenvalue µr , which
is assumed to be simple (that is, of multiplicity mr = 1). The corresponding
spectral projection Pr is one-dimensional: Pr = θr ⊗ θr . A “naive” plug-in estimator of Pr is the empirical spectral projection P̂rδ with δ = τ kΣ̂k for a suitable
choice of a small constant τ, as described in Lemma 2.2. According to this
lemma and under its assumptions, P̂rδ coincides with a high probability with
the one-dimensional empirical spectral projection P̂r := θ̂r ⊗ θ̂r , where θ̂r is the
corresponding unit eigenvector of Σ̂. As an estimator of θr , we can use an arbitrary unit vector θ̂rδ from the eigenspace Im(P̂rδ ), which with a high-probability
coincides with ±θ̂r (under conditions of Lemma 2.2). In case r = 1, when the
top eigenvalue µ1 = kΣk of Σ is simple and the goal is to estimate a linear
functional of the top principal component θ1 , there is no need to use δ-clusters
to define an estimator of θ1 since θ̂1 (a unit eigenvector in the eigenspace of the
top eigenvalue kΣ̂k of Σ̂) is already a legitimate estimator.
Note that both θr and −θr are unit eigenvectors of Σ, so, strictly speaking,
hθr , ui can be estimated only up to its sign. In what follows, we assume that θ̂rδ
and θr (or, whenever is needed, θ̂r and θr ) are properly aligned in the sense that
hθ̂rδ , θr i ≥ 0 (which is always the case either for θr , or for −θr ). This allows us
to view hθ̂rδ , ui as an estimator of hθr , ui.
It was shown in [15] that “naive” plug-in estimators of the functional hθr , ui,
such as hθ̂rδ , ui or hθ̂r , ui, are biased with the bias becoming substantial enough
to affect the efficiency of the estimator or even its convergence rates as soon as
the effective rank is large enough, namely, r(Σ) & n1/2 . Moreover, it was shown
that the quantity
br = br (Σ) := EΣ hθ̂r , θr i2 − 1 ∈ [−1, 0]
plays the role of a bias parameter. In particular, the results of [15] imply that
√
the random variable hθ̂r , ui concentrates around 1 + br hθr , ui (rather than
around hθr , ui) with the size of the deviations of order O(n−1/2 ) provided that
r(Σ) = o(n) as n → ∞. Thus, the bias of hθ̂r , ui as an estimator of hθr , ui is of the
√
order ( 1 + br −1)hθr , ui ≍ br hθr , ui. It was shown in [15] that |br | . r(Σ)
n and it
will be proved below in this paper that, in fact, |br | ≍ r(Σ)
(see
Lemma
4.9 and
n
bounds (4.32), (4.33)). This fact implies that, indeed, the bias of hθ̂r , ui (and of
hθ̂rδ , ui) is not negligible and affects the convergence rate as soon as nr(Σ)
1/2 → ∞.
This resembles the situation in sparse regression (see e.g. [13, 27, 34]). If p
denotes the dimension of the model and s its sparsity and if s log(p) = o(n1/2 ),
the bias of a de-sparsified LASSO estimator for the regressor β is negligible,
which makes it possible to prove asymptotic normality of linear forms of β.
On the other hand, if s log(p) ≫ n1/2 , Cai and Guo [5] proved that adaptive
confidence sets for linear forms do not exist. This implies that any attempt

/Efficient estimation in PCA

8

to further de-bias the de-sparsified LASSO or any other estimator to prove
asymptotic normality is deemed to fail. Contrary to this, in our case estimation
of the bias parameter br is possible (as will be shown below).
We will state a uniform (and somewhat stronger) version of some of the
results of [15] on asymptotic normality of linear forms
p
√
n(hθ̂rδ , ui − 1 + br (Σ)hθr (Σ), ui), u ∈ H

under the assumption that r(Σ) = o(n). To this end, define the following operator
X
1
Cr :=
Ps ,
µr − µs
s6=r

which is bounded with kCr k =

1
gr .

Denote

σr2 (Σ; u) := hΣθr , θr ihΣCr u, Cr ui = µr hΣCr u, Cr ui.
Clearly,
σr2 (Σ; u) ≤

kΣk2
kuk2 .
gr2

(3.1)

Note that, if H is finite-dimensional (with a fixed dimension) and Σ is nonsingular, then the Fisher information for the model X ∼ N (0; Σ) is I(Σ) =
1
−1
⊗ Σ−1 ) (see, e.g., [8]). The maximum likelihood estimator Σ̂ based on n
2 (Σ
i.i.d. observations
of X (the sample covariance) is then asymptotically normal
√
with n-rate and limit covariance I(Σ)−1 = 2(Σ ⊗ Σ). An application of the
Delta Method to the smooth function g(Σ) := hθ
Dr (Σ), ui shows thatEg(Σ̂) is
also asymptotically normal with limiting variance (I(Σ)−1 g ′ (Σ), g ′ (Σ) , which

turns out to be equal to σr2 (Σ; u).
For u ∈ H, r > 1, a > 1 and σ0 > 0, consider the following class of covariance
operators in H :
o
n
kΣk
S (r) (r, a, σ0 , u) := Σ : r(Σ) ≤ r,
≤ a, σr2 (Σ; u) ≥ σ02 .
ḡr (Σ)
We emphasize here that we regard a and σ0 as fixed constants, but r, kΣk and ḡr
may all possibly depend on n. For example, this allows that kΣk → ∞ as long
as ḡr → ∞ at the same rate as it is the case in factor models as considered in
[33]. Note that some additional conditions on r, a, σ0 , u are needed for the class
S (r) (r, a, σ0 , u) to be nonempty. Say, bound (3.1) implies that it is necessary
for this that σ02 ≤ a2 kuk2 . It is also obvious that there should be a > r (since
kΣk ≥ rgr (Σ)).
We will also need the following assumption on the loss function ℓ.
Assumption 3.1. Let ℓ : R 7→ R+ be a loss function satisfying the following
conditions: ℓ(0) = 0, ℓ(u) = ℓ(−u), u ∈ R, ℓ is nondecreasing and convex on R+
and, for some constants c1 , c2 > 0
ℓ(u) ≤ c1 ec2 u , u ≥ 0.

/Efficient estimation in PCA

9

The proofs to all our theorems are in fact non-asymptotic and often can be
expressed with Berry-Essen type bounds. However, for a more concise presentation we present the asymptotic statements.
In what follows, Z denotes a standard Gaussian random variable and Φ denotes its distribution function.
Theorem 3.1. Let u ∈ H, a > 1 and σ0> 0. Suppose
 that rn > 1 and rn = o(n)
1 V
as n → ∞. Let δ = τ kΣ̂k for some τ ∈ 0, 4a 2 . Then
supΣ∈S (r) (rn ,a,σ0 ,u) supx∈R PΣ

√

n(hθ̂rδ ,ui−

√

1+br (Σ)hθr (Σ),ui)
σr (Σ;u)


≤ x − Φ(x) → 0 as n → ∞.

Moreover, under Assumption 3.1,
p
√

n(hθ̂rδ , ui − 1 + br (Σ)hθr (Σ), ui)
EΣ ℓ
sup
−Eℓ(Z) → 0 as n → ∞.
σr (Σ; u)
Σ∈S (r) (rn ,a,σ0 ,u)
The proof of this theorem will be given in Section 4 that also includes a
number of auxiliary statements used in the proofs of our main results on efficient
estimation of linear functionals.
Corollary 3.1. Let u ∈ H, a > 1 and σ0 > 0.Suppose 
that rn > 1 and
V
√
1
rn = o( n) as n → ∞. Let δ = τ kΣ̂k for some τ ∈ 0, 4a
2 . Then
supΣ∈S (r) (rn ,a,σ0 ,u) supx∈R PΣ

√

n(hθ̂rδ ,ui−hθr (Σ),ui)
σr (Σ;u)


≤ x − Φ(x) → 0 as n → ∞.

Moreover, under Assumption 3.1,

√
n(hθ̂rδ , ui − hθr (Σ), ui)
− Eℓ(Z) → 0 as n → ∞.
EΣ ℓ
sup
σr (Σ; u)
Σ∈S (r) (rn ,a,σ0 ,u)
Our next goal is to provide a minimax lower bound on the risk of an arbitrary
estimator of the linear functional hθr (Σ), ui in the case of quadratic loss ℓ(t) =
t2 , t ∈ R. The proof is based on van Trees’ inequality and will be given in Section
7. Let
o
n
kΣk
< a, σr2 (Σ; u) > σ02 , r > 1, a > 1, σ02 > 0.
S̊ (r) (r, a, σ0 , u) := Σ : r(Σ) < r,
ḡr (Σ)
Theorem 3.2. Let r > 1, a > 1 and σ0 > 0. Suppose S̊ (r) (r, a, σ0 , u) 6= ∅. Then,
for all statistics Tn (X1 , . . . , Xn ),
lim inf inf
n→∞ Tn

nEΣ (Tn (X1 , ..., Xn ) − hθr (Σ), ui)2
≥ 1.
σr2 (Σ; u)
Σ∈S̊ (r) (r,a,σ0 ,u)
sup

Moreover, for any Σ0 ∈ S̊ (r) (r, a, σ0 , u)
lim lim inf inf

ε→0 n→∞ Tn

nEΣ (Tn (X1 , ..., Xn ) − hθr (Σ), ui)2
≥ 1.
σr2 (Σ; u)
Σ∈S̊ (r) (r,a,σ0 ,u),kΣ−Σ0 k1 ≤ε
sup

/Efficient estimation in PCA

10

It follows from Corollary 3.1 and Theorem 3.2 that the estimator hθ̂rδ , ui is
efficient in a semi-parametric sense for quadratic loss under the assumption
rn
that rn = o(n1/2 ). It turns
√ out, however, that if n1/2 → ∞, then not only the
efficiency, but even the n–convergence rate of this estimator fails in the class
of covariance operators S (r) (rn , a, σ0 , u).

Proposition 3.1. Let a > r and let σ02 be sufficiently small, say,


1
a2
a
2
σ0 ≤
.
−
2 (r − 1)2
r−1
Let rn = o(n) and
c(r; a; σ0 ) > 0

rn
n1/2

→ ∞ as n → ∞. Then, for some constant c =



rn
= 1.
PΣ |hθ̂rδ , ui − hθr (Σ), ui| ≥ ckuk
n→∞ Σ∈S (r) (r ,a,σ ,u)
n
n
0
lim

sup

√
The reason for the loss of the n–convergence rate of plug-in estimators of
linear functionals of principal components is their large bias in the case when
n
the complexity of the problem is even moderately high (that is, nr1/2
→ ∞).
√In
[15], a method of bias reduction in this problem was suggested that led to nconsistent estimation of linear functionals. This approach is based on concentration properties of linear functionals hθ̂rδ , ui. To describe it, it is of importance
to emphasize the dependence of the bias parameter br on the sample size. To
(n)
this end, we will write br = br (Σ) = br (Σ). The idea is to split the sample into
two equal parts and to construct an estimator of the bias parameter that can
be used to de-bias plug-in estimators. Assume, for simplicity, that n is even and
let n′ := n/2. The sample X1 , . . . , Xn is divided into two parts, X1 , . . . , Xn′ and
Xn′ +1 , . . . , Xn , of size n′ each. Let Σ̂(1) , Σ̂(2) be the sample covariance operators
based on these two samples and denote by θ̂rδ,1 , θ̂rδ,2 the corresponding empirical
eigenvectors (estimators
of θr ). Since for any u ∈ H, hθ̂rδ,1 , ui and hθ̂rδ,2 , ui conq
centrate around

(n′ )

1 + br

(Σ)hθr (Σ), ui and the random vectors θ̂rδ,1 , θ̂rδ,2 are

independent, it is natural to expect that hθ̂rδ,1 , θ̂rδ,2 i concentrates around
q
E
Dq
′
(n′ )
(n′ )
1 + br (Σ)θr (Σ), 1 + br (Σ)θr (Σ) = 1 + br(n ) (Σ)
(n′ )

(n′ )

and to use b̂r := hθ̂rδ,1 , θ̂rδ,2 i−1 as an estimator of br (Σ). It was proved in [15]
(n′ )
(n′ )
that, under the assumption r(Σ) = o(n), the error b̂r − br (Σ) = o(n−1/2 )
which allows one to define a new estimator of the linear functional hθr (Σ), ui
with reduced bias as √ 1 (n′ ) hθ̂rδ,1 , ui. It was shown in [15] that this estimator
1+b̂r
√
is n-consistent and asymptotically normal. It is, however, not efficient: due to
a very straightforward sample split, the limiting variance of this estimator is
twice as large as the optimal variance.
We describe below a more subtle construction that yields an asymptotically
normal estimator of hθr (Σ), ui with optimal variance in the class of covariance

/Efficient estimation in PCA

11

operators S (r) (rn , a, σ0 , u) with rn = o(n). The idea is to use only a small portion
of the data (of size o(n)) to estimate the bias parameters and to use most of the
data for the estimator of the target eigenvector. The main difficulty is that the
bias parameters themselves depend on the sample size.
Let m = mn = o(n) as n → ∞. Assuming that m < n/3, we split the sample
X1 , . . . , Xn into three disjoint subsamples, one of size n′ = n′n := n − 2m > n/3
and two others of size m each. Clearly, n′ = (1 + o(1))n as n → ∞. Denote
by Σ̂(1) , Σ̂(2) , Σ̂(3) the sample covariances based on these three subsamples and
δ ,j
let θ̂rj , j = 1, 2, 3 be the corresponding empirical eigenvectors with parameters
δj = τ kΣ̂(j) k for a proper choice of τ (see Lemma 2.2). Let
dˇr :=

hθ̂rδ1 ,1 , θ̂rδ2 ,2 i

hθ̂rδ2 ,2 , θ̂rδ3 ,3 i1/2

and
θ̌r :=

θ̂rδ1 ,1
.
dˇr ∨ (1/2)

Our main goal is to prove the following result showing the efficiency of the
estimator hθ̌r , ui of the linear functional hθr (Σ), ui. Its proof will be given in
Section 5.
Theorem 3.3. Let u ∈ H, a > 1 and σ0 > 0. Suppose that rn > 1 and rn = o(n)
as n → ∞. Take m = mn such that mn = o(n) and nrn = o(m2n ) as n → ∞.
Then
√

n(hθ̌r , ui − hθr (Σ), ui)
sup
sup PΣ
≤ x − Φ(x) → 0 as n → ∞.
σr (Σ; u)
Σ∈S (r) (rn ,a,σ0 ,u) x∈R
(3.2)
Moreover, under Assumption 3.1 on the loss ℓ,
√

n(hθ̌r , ui − hθr (Σ), ui)
EΣ ℓ
sup
− Eℓ(Z) → 0 as n → ∞.
σr (Σ; u)
Σ∈S (r) (rn ,a,σ0 ,u)
Finally, we show that σr (Σ; u) can be consistently estimated by σr (Σ̂; u),
which allows us to replace the standard deviation σr (Σ; u) in the normal approximation (3.2) by its empirical version. This yields the following result that
can be used for constructing ℓ∞ -type confidence sets for θr and for hypotheses
testing of linear functionals of θr . See Section 6 for its proof.
Corollary 3.2. Under the conditions of Theorem 3.3,
√

n(hθ̌r ,ui−hθr (Σ),ui)
supΣ∈S (r) (rn ,a,σ0 ,u) supx∈R PΣ
≤
x
− Φ(x) → 0 as n → ∞.
σ (Σ̂;u)
r

/Efficient estimation in PCA

12

4. Proof of Theorem 3.1
We will prove the result for empirical eigenvectors θ̂r rather than for θ̂rδ . The
reduction to this case is based on Lemma 2.2 which immediately implies that
sup
Σ∈S (r) (rn ,a,σ0 ,u)

PΣ {θ̂rδ 6= θ̂r } ≤ e−βτ

2

n

.

Therefore, denoting
p
√
n(hθ̂rδ , ui − 1 + br (Σ)hθr (Σ), ui)
ξn (Σ) :=
σr (Σ; u)
and

p
√
n(hθ̂r, ui − 1 + br (Σ)hθr (Σ), ui)
,
ηn (Σ) :=
σr (Σ; u)

we obtain
sup

sup |PΣ {ξn (Σ) ≤ x} − PΣ {ηn (Σ) ≤ x}| ≤ e−βτ

Σ∈S (r) (rn ,a,σ0 ,u) x∈R

Also, since ξn (Σ) ≤

√
2 nkuk
σr (Σ;u)

and ηn (Σ) ≤

sup
Σ∈S (r) (rn ,a,σ0 ,u)

≤

sup
Σ∈S (r) (rn ,a,σ0 ,u)

√
2 nkuk
σr (Σ;u) ,

2

n

→ 0 as n → ∞.

we obtain that

|EΣ ℓ(ξn (Σ)) − EΣ ℓ(ηn (Σ))|

EΣ |ℓ(ξn (Σ))−ℓ(ηn (Σ))|I(θ̂rδ 6= θ̂r ) ≤ 2ℓ


 √
2 nkuk −βτ 2 n
e
→ 0,
σ0

under Assumption 3.1.
We will prove more explicit bounds for the estimator θ̂r stated below in
Lemma 4.8 that immediately implies the result.
Our starting point is the first order perturbation expansion of the empirical
spectral projection operator P̂r :
P̂r = Pr + Lr (E) + Sr (E)

(4.1)

with a linear term Lr (E) = Pr ECr + Cr EPr and a remainder Sr (E), where
E := Σ̂ − Σ. It was proved in [15] that, under the assumption
EkΣ̂ − Σk ≤

(1 − γ)gr
2

(4.2)

for some γ ∈ (0, 1), the bilinear form of the remainder Sr (E) satisfies the following concentration inequality: for all u, v ∈ H and for all t ≥ 1 with probability
at least 1 − e−t
r
r
r
kΣk2
r(Σ) _ t _ t
t
kukkvk. (4.3)
h(Sr (E) − ESr (E))u, vi .γ
2
gr
n
n
n
n

/Efficient estimation in PCA

13

Under the same assumption, it was also proved in [15] that the following representation holds for the bias EP̂r − Pr of empirical spectral projections P̂r :
EP̂r − Pr = Pr (EP̂r − Pr )Pr + Tr ,

(4.4)

where the main term Pr (EP̂r − Pr )Pr is aligned with the spectral projection Pr
and is of order
kΣk2 r(Σ)
(4.5)
kPr (EP̂r − Pr )Pr k .
gr2
n
and the remainder Tr satisfies the bound
mr kΣk2
kTr k .γ
gr2

r

r(Σ) 1
√ .
n
n

(4.6)

Representation (4.4) is especially simple in the case when Pr is of rank 1 (mr =
1), which also implies that P̂r is of rank 1. In this case, Pr = θr ⊗θr , P̂r = θ̂r ⊗ θ̂r
for unit eigenvectors θr , θ̂r of covariance operators Σ, Σ̂, respectively, and
Pr (EP̂r − Pr )Pr = br Pr
for a “bias parameter” br = br (Σ) :
br = Ehθ̂r , θr i2 − 1 ∈ [−1, 0].
Thus, it follows from (4.4) that
EP̂r = (1 + br )Pr + Tr .

(4.7)

We obtain from (4.1) and (4.7) that
P̂r − (1 + br )Pr = Lr (E) + Sr (E) − ESr (E) + Tr .

(4.8)

Denote
ρr (u) := h(P̂r − (1 + br )Pr )θr , ui, u ∈ H.
As in [15], the function ρr (u), u ∈ H will be used in what follows to control the
√
linear forms hθ̂r − 1 + br θr , ui, u ∈ H. First, we need to derive some bounds
on ρr (u).
The following lemma is an immediate consequence of (4.8), (4.3) and (4.6).
Lemma 4.1. Suppose condition (4.2) holds for some γ ∈ (0, 1). Then, for all
u ∈ H and for all t ≥ 1 with probability at least 1 − e−t
r
r
r
r(Σ) _ t _ t
t
kΣk2
kuk.
(4.9)
|ρr (u) − hLr (E)θr , ui| .γ
gr2
n
n
n
n

We will need simple concentration and normal approximation bounds for
hLr (E)θr , ui given in the next lemma.

/Efficient estimation in PCA

Lemma 4.2. For all t ≥ 1 with probability at least 1 − e−t
r _ 
t
t
.
|hLr (E)θr , ui| . σr (Σ; u)
n
n

Moreover, if σr (Σ; u) > 0, then
√

nhLr (E)θr , ui
1
sup P
≤ x − Φ(x) . √ ,
σ
(Σ;
u)
n
r
x∈R

14

(4.10)

(4.11)

where Φ is the distribution function of standard normal r.v.
Proof. Without loss of generality, assume that the space H is finite-dimensional
(the general case follows by a simple approximation argument). Since Lr (E) =
Pr ECr + Cr EPr and Cr θr = 0, we have
hLr (E)θr , ui = hCr EPr θr , ui = hEθr , Cr ui = hE, θr ⊗ Cr ui.
Since E is self-adjoint, we obtain that
hLr (E)θr , ui =

1
hE, θr ⊗ Cr u + Cr u ⊗ θr i.
2

Let Z, Z1 , . . . , Zn be i.i.d. standard normal vectors in H such that Xj = Σ1/2 Zj .
Then


n
X
−1
1/2
Zj ⊗ Zj − E(Z ⊗ Z) Σ1/2 .
n
E=Σ
j=1

Defining
D :=


1 1/2
1  1/2
Σ θr ⊗Σ1/2 Cr u+Σ1/2 Cr u⊗Σ1/2 θr ,
Σ (θr ⊗Cr u+Cr u⊗θr )Σ1/2 =
2
2

we obtain that



n
X
−1
Zj ⊗ Zj − E(Z ⊗ Z), D
hLr (E)θr , ui = n
j=1

= n−1

n
X
j=1

Clearly,

(hDZj , Zj i − EhDZ, Zi).
d

hDZ, Zi =

X

λk gk2 ,

k

where {λk } are the eigenvalues of D and {gk } are i.i.d. standard normal r.v. It
easily follows that
EhDZ, Zi = tr(D) = 0
and
Var(hDZ, Zi) = 2

X
k

λ2k = 2kDk22 = σr2 (Σ; u).

/Efficient estimation in PCA

15

We can now represent hLr (E)θr , ui as follows:
d

hLr (E)θr , ui = n−1

n X
X
j=1

k

2
λk (gk,j
− 1),

where {gk,j } are i.i.d. standard normal r.v. Using standard exponential bounds
for sums of independent ψ1 r.v. (see, e.g., [30], Proposition 5.16 or Theorem
3.1.9 in [11]), we obtain that with probability at least 1 − e−t
n

−1

n X
X
j=1

2
λk (gk,j

k

− 1) .

X

λ2k

k

which implies that with the same probability
r
|hLr (E)θr , ui| . kDk2

1/2 r

t
t _
sup |λk | ,
n
n
k

t
t _
kDk .
n
n

Since kDk ≤ kDk2 = 12 σr2 (Σ; u), bound (4.10) follows.
To prove (4.11), we use the Berry-Esseen bound that implies
P
 Pn P

2
|λk |3 1
j=1
k λk (gk,j − 1)
P 2 1/2
√
sup P
≤ x − Φ(x) . P k 2 3/2 √ ,
n
n(2 k λk )
( k λk )
x∈R

and therefore
√

kDk 1
1
nhLr (E)θr , ui
kDk33 1
√ .
√ .√ .
sup P
≤ x − Φ(x) .
3
σ
(Σ;
u)
kDk
kDk
n
n
n
r
2
x∈R
2
The following bounds on ρr (u) immediately follow from (4.9) and (4.10).

Lemma 4.3. Suppose condition (4.2) holds for some γ ∈ (0, 1). Then, for all
u ∈ H and for all t ≥ 1 with probability at least 1 − e−t
q

q
q q
Wt
kΣk2
r(Σ) W
t
t
t
+
|ρr (u)| .γ σr (Σ; u)
n
n
g2
n
n
n kuk. (4.12)
r

Moreover, with the same probability
|ρr (u)| .γ

kΣk
gr

q

t
n kuk

+

kΣk2
gr2

q

r(Σ)
n

and, for u = θr ,
kΣk2
|ρr (θr )| .γ
gr2

r

r(Σ) _
n


Wqt qt
n

r r
t
t
.
n
n

n kuk.

(4.13)

(4.14)

/Efficient estimation in PCA

16

Note that we dropped the term nt in some of the expressions on the right
hand
q side of the above bounds (compare with (4.9)). This term is dominated
by

t
n

for t ≤ n. Moreover, it follows from the definition of ρr (u) that it is

upper bounded by 2kuk. Since kΣk
gr ≥ 1, this easily implies that, for t ≥ n, the
right hand side of bound (4.13) (with a proper constant) is larger than |ρr (u)|.
Bound (4.14) follows from (4.9) since hLr (E)θr , θr i = 0.
To study concentration and normal approximation of the linear form
p
hθ̂r − 1 + br θr , ui, u ∈ H,
it remains to prove that it can be approximated by hLr (E)θr , ui.

Lemma 4.4. Suppose that for some γ ∈ (0, 1) condition (4.2) holds and, in
addition,
1 + br ≥ γ.
(4.15)

Then, for all u ∈ H and for all t ≥ 1, with probability at least 1 − e−t
r
r
r
p
r(Σ) _ t _ t
t
kΣk2
|hθ̂r − 1 + br θr , ui − hLr (E)θr , ui| .γ
kuk.
gr2
n
n
n
n
(4.16)
Proof. We use the following representation obtained in [15] (see (6.7) in [15]),
which holds provided that θ̂r and θr are properly aligned so that hθ̂r , θr i ≥ 0 :
√
hθ̂r − 1 + br θr , ui = √ ρr (u)
(4.17)
1+br +ρr (θr )

√

√ 1+br
ρr (θr )hθr , ui
−√
√
1+br +ρr (θr )( 1+br +ρr (θr )+ 1+br )
(it is clear from the proof given in [15] that 1 + br + ρr (θr ) ≥ 0). Denote
νr :=

ρr (θr )
.
1 + br

Then, it is easy to see that
√
hθ̂r − 1 + br θr , ui = ρr (u) −

br /(1+br )+νr
1+νr +

√

√

(1+νr )/(1+br )

ρr (u)

(4.18)

νr 1+b
√ r hθr , ui.
− 1+ν
+ 1+ν
r

r

Recall that (4.2) and (4.15) hold for some γ ∈ (0, 1). If |νr | ≤ 1/2, then (4.18)
easily implies that
|hθ̂r −

p
1
1 + br θr , ui − ρr (u)| ≤ (|br | + |νr |)|ρr (u)| + |νr ||hθr , ui|.
γ

It also follows from (4.14) that, under condition (4.15),
r r
r
kΣk2
r(Σ) _ t
t
|νr | .γ
2
gr
n
n
n

(4.19)

(4.20)

/Efficient estimation in PCA

17

with probability at least 1 − e−t . On the other hand, bound (4.5) implies that
|br | .

kΣk2 r(Σ)
.
gr2
n

(4.21)

It follows from (4.20) that for the condition |νr | ≤ 1/2 to hold with probability
at least 1 − e−t , it is enough to have
r r
r
r(Σ) _ t
t
kΣk2
≤ cγ
(4.22)
2
gr
n
n
n

for a small enough constant cγ > 0. Assume that (4.22) holds. Note also
q that it
r(Σ)
kΣk
implies that t . n and condition (4.2) and Theorem 2.1 imply that gr
n .
1. It follows from (4.19), (4.13), (4.20) and (4.21) that with probability at least
1 − 3e−t :
√
|hθ̂r − 1 + br θr , ui − ρr (u)|
q



q q 
kΣk2
r(Σ) W
kΣk2 r(Σ)
t
t
∧ 1/2
.γ g 2 n +
gr2
n
n
n
r




q
q q
q
kΣk
kΣk2
r(Σ) W
t
t
t
× gr
n kuk + gr2
n
n
n kuk
q

q q
2
r(Σ) W
t
t
(4.23)
+ kΣk
2
g
n
n
n kuk.
r

Using the facts that

kΣk
kΣk2 r(Σ)
.
gr2
n
gr
that

r

kΣk2 t
kΣk
.
gr2 n
gr

r(Σ)
. 1,
n

r

t
.1
n

and that
kΣk2
gr2

r

r(Σ)
n

r

r 
1/4  1/4

r
t
kΣk
kΣk r(Σ)
t
r(Σ) _ t
≤
.
n
gr
n
n
gr
n
n

(that follow from condition (4.22)), it is easy to conclude that the last term
r r
r
r(Σ) _ t
t
kΣk2
kuk
2
gr
n
n
n

in the right hand side of bound (4.23) is dominant. Hence, with probability at
least 1 − e−t
r r
r
p
r(Σ) _ t
t
kΣk2
kuk
(4.24)
|hθ̂r − 1 + br θr , ui − ρr (u)| .γ
2
gr
n
n
n

/Efficient estimation in PCA

18

provided that condition (4.22) holds. On the other hand, if
r r
r
r(Σ) _ t
t
kΣk2
> cγ ,
2
gr
n
n
n

then

p
p
1 + br θr , ui − ρr (u)| ≤ |hθ̂r − 1 + br θr , ui| + |ρr (u)|
p
≤ (kθ̂r k + 1 + br kθr k)kuk + (kP̂r k + (1 + br )kPr k)kθr kkuk ≤ 4kuk
r r
r
r(Σ) _ t
t
kΣk2
kuk.
.γ
gr2
n
n
n
|hθ̂r −

Thus, we proved that with probability at least 1 − e−t
r r
r
p
r(Σ) _ t
t
kΣk2
kuk.
|hθ̂r − 1 + br θr , ui − ρr (u)| .γ
2
gr
n
n
n

(4.25)

It remains to combine this with the bound (4.9) to complete the proof.
The following result is a slightly improved version of Theorem 6 in [15].
Lemma 4.5. Under conditions (4.2) and (4.15) for some γ ∈ (0, 1), the following bounds hold for all t ≥ 1 with probability at least 1 − e−t :
r
p
kΣk t
|hθ̂r − 1 + br θr , ui| .γ
kuk
(4.26)
gr
n
and

r r
r
p
r(Σ) _ t
t
kΣk2
.
|hθ̂r − 1 + br θr , θr i| .γ
2
gr
n
n
n

(4.27)

Proof. Indeed, it follows from (4.16) and (4.10) that, for some constants C, Cγ >
0 with probability at least 1 − e−t
r r
r _ 
r
p
t
r(Σ) _ t
t
kΣk2
t
|hθ̂r − 1 + br θr , ui| ≤ Cσr (Σ; u)
+Cγ 2
kuk.
n
n
gr
n
n
n
Since σr (Σ; u) .

kΣk
gr kuk,

with the same probability

p
kΣk
|hθ̂r − 1 + br θr , ui| ≤ C
gr

r

t
kΣk2
kuk + Cγ 2
n
gr

r

r(Σ) _
n

r r
t
t
kuk.
n
n

We dropped the term nt present in bounds (4.16) and (4.10) since for t ≥ n
(the only case when it is needed), the right hand side already dominates the left
hand side (which is q
smaller than 2kuk). Note that condition (4.2) and Theorem
2.1 imply that

kΣk
gr

r(Σ)
n

≤ cγ for some constant cγ > 0. Assuming that also

/Efficient estimation in PCA
kΣk
gr

q

t
n

19

≤ cγ , which implies that t . n, we obtain that for some constant

Cγ > q
0 with probability at least 1 − e−t bound (4.26) holds. On the other hand,
t
if kΣk
gr
n > cγ , then
p
p
kΣk
|hθ̂r − 1 + br θr , ui| ≤ (kθ̂r k + 1 + br kθr k)kuk ≤ 2kuk .γ
gr

r

t
kuk,
n

implying again (4.26). For u = θr , hLr (E)θr , ui = 0 and bound (4.16) implies
that with probability at least 1 − e−t (4.27) holds.
The following √two lemmas will be used to derive normal approximation
bounds for hθ̂r − 1 + br θr , ui from the corresponding bounds for hLr (E)θr , ui
as well as to control the risk for loss functions satisfying Assumption 3.1. We
state them without proofs (which are elementary).
Lemma 4.6. For random variables ξ, η, denote
∆(ξ; η) := sup |P{ξ ≤ x} − P{η ≤ x}|
x∈R

and
δ(ξ; η) := inf{δ > 0 : P{|ξ − η| ≥ δ} + δ}.

Then, for a standard normal r.v. Z,

∆(ξ; Z) ≤ ∆(η; Z) + δ(ξ; η).
Under Assumption 3.1, for all A > 0
|Eℓ(ξ) − Eℓ(η)| ≤ 4ℓ(A)∆(ξ; η) + Eℓ(ξ)I(|ξ| ≥ A) + Eℓ(η)I(|η| ≥ A).
Lemma 4.7. Let ξ be a random variable such that for some τ1 ≥ 0 and τ2 ≥ 0
and for all t ≥ 1 with probability at least 1 − e−t
√
|ξ| ≤ τ1 t ∨ τ2 t.
Let ℓ be a loss function satisfying Assumption 3.1. If 2c2 τ2 < 1, then
√
2 2
Eℓ2 (ξ) ≤ 2e 2πc21 e2c2 τ1 +

ec21
.
1 − 2c2 τ2

(4.28)

√ Next we prove the normal approximation bounds for linear forms hθ̂r −
1 + br θr , ui.
Lemma 4.8. Suppose that conditions (4.2) and (4.15) hold for some γ ∈ (0, 1)
and also that n ≥ 2r(Σ). Assume that, for some u ∈ H, σr (Σ; u) > 0. Let α ≥ 1.
Then the following bound holds: for some constants C, Cγ,α > 0,

√
√
nhθ̂r − 1+br θr ,ui
≤ x − Φ(x)
supx∈R P
σr (Σ;u)
q
α


n
W log r(Σ)
Cγ,α kΣk2
r(Σ)
r(Σ)
n
−1/2
√
≤ Cn
+ σr (Σ;u) g2
.(4.29)
kuk +
n log r(Σ)
n
n
r

/Efficient estimation in PCA

20

Moreover, under Assumption 3.1 on the loss ℓ, there exist constants C, Cγ , Cγ,α >
0 such that
√

√
nhθ̂r − 1 + br θr , ui
− Eℓ(Z)
Eℓ
σr (Σ; u)
α 
s


n 
n _ log r(Σ)
Cγ,α kΣk2
r(Σ)
r(Σ)
−1/2
c2 A
√
log
kuk
+
Cn
+
≤ c1 e
σr (Σ; u) gr2
n
r(Σ)
n
n
2 2

+ 2e3/2 (2π)1/4 c1 ec2 τ e−A

2

/2τ 2

2

+ c1 ec2 e−A

2

/4

,

(4.30)

where

kΣkkuk
.
gr σr (Σ; u)
Proof. We will use the first claim of Lemma 4.6 with
√
√
√
nhθ̂r − 1 + br θr , ui
nhLr (E)θr , ui
ξ :=
and η :=
.
σr (Σ; u)
σr (Σ; u)
τ := Cγ

It follows from bound (4.16) that, under conditions (4.2) and (4.15), for some
Cγ > 0
r

r


Cγ kΣk2
r(Σ) _ t _ t √
−t
δ(ξ; η) ≤ inf
.
tkuk + e
t≥1 σr (Σ; u) gr2
n
n
n
n
r(Σ)

with some α ≥ 1 easily yields an upper bound
α
s

n 
n _ log r(Σ)
Cγ,α kΣk2
r(Σ)
r(Σ)
√
.
log
kuk +
δ(ξ; η) ≤
σr (Σ; u) gr2
n
r(Σ)
n
n

Taking t := α log

Using bound (4.11) to control ∆(η; Z), we obtain from Lemma 4.6 that bound
(4.29) holds with some constants C, Cγ,α > 0. To prove the second statement,
√

√

1+br θr ,ui
we use the second bound of Lemma 4.6 with r.v. ξ := nhθ̂rσ−r (Σ;u)
and
η = Z. The following exponential bound on ξ is an easy corollary of bound
(4.26): for some constant Cγ > 0 and for all t ≥ 1 with probability at least
1 − e−t
√
kΣk √
|ξ| ≤ Cγ
tkuk = τ t.
(4.31)
gr σr (Σ; u)
Using bound (4.28) with τ1 = τ and τ2 = 0, we obtain
√
√
2 2
2 2
Eℓ2 (ξ) ≤ 2e 2πc21 e2c2 τ1 + ec21 ≤ 4e 2πc21 e2c2 τ1

Therefore,
2 2

Eℓ(ξ)I(|ξ| ≥ A) ≤ E1/2 ℓ2 (ξ)P1/2 {|ξ| ≥ A} ≤ 2e3/2 (2π)1/4 c1 ec2 τ e−A
We also have

2

Eℓ(Z)I(|Z| ≥ A) ≤ c1 ec2 e−A

2

/4

2

/2τ 2

.

.

Using bound (4.29), we can now deduce bound (4.30) from the second statement
of Lemma 4.6.

/Efficient estimation in PCA

21

Lemma 4.8 immediately implies Theorem 3.1 (by passing to the limit as
n → ∞ in (4.29) and as n → ∞ and then A → ∞ in (4.30)).
4.1. Proof of Proposition 3.1
Denote
Ar (Σ) := 2 tr(Pr ΣPr ) tr(Cr ΣCr ) = 2

X µr µs m s
.
(µr − µs )2
s6=r

It was shown in [17] that
EkLr (E)k22 =

Ar (Σ)
,
n

where E = Σ̂ − Σ. Note that

and

Ar (Σ)
µr
kΣk2
≤ 2 (tr(Σ) − µr ) ≤
r(Σ)
2
gr
gr2

(4.32)

µ1 µr
Ar (Σ)
(r(Σ) − 1).
≥
2
(µ1 − µr )2 ∨ µ2r

(4.33)

Lemma 4.9. The following representation holds:
br (Σ) = −
where

kΣk3
|βr | .
gr3

1 Ar (Σ)
+ βr ,
2 n

r

r(Σ) _ r(Σ)
n
n

3

.

Proof. Recall representation (4.4) and bound (4.6). Note that
br = tr(Pr (EP̂r − Pr )Pr )
and
EP̂r − Pr = ESr (E).
We will use the following representation for Sr (E) (based on perturbation series
for P̂r ) that easily follows from Lemma 4 in [18]:
Sr (E) = Pr ECr ECr + Cr EPr ECr + Cr ECr EPr
−Pr ECr Pr ECr2 − Pr ECr2 EPr − Cr2 EPr EPr + Sr(3) (E),
where
kSr(3) (E)k .

kEk3
.
gr3

Since Pr Cr = Cr Pr = 0 this implies
Pr Sr (E)Pr = −Pr ECr2 EPr + Pr Sr(3) (E)Pr .

/Efficient estimation in PCA

22

Therefore we obtain
br = E tr(Pr Sr (E)Pr ) = −E tr(Pr ECr2 EPr ) + E tr(Pr Sr(3) (E)Pr )

1
= −EkPr ECr k22 +E tr(Pr Sr(3) (E)Pr ) = − EkPr ECr +Cr EPr k22 +E tr(Pr Sr(3) (E)Pr )
2
1 Ar (Σ)
1
+ E tr(Pr Sr(3) (E)Pr ).
− EkLr (E)k22 + E tr(Pr Sr(3) (E)Pr ) = −
2
2 n
(3)

Thus, βr = E tr(Pr Sr (E)Pr ) and, using bound (2.4), we get
|βr | ≤ EkSr(3) (E)kkPr k1 ≤ EkSr(3) (E)k .
kΣk3
.
gr3
which completes the proof.

r

r(Σ) _ r(Σ)
n
n

3

EkEk3
gr3

,

It follows from the lower bound (4.33) on Ar2(Σ) and the bound of Lemma 4.9
that, under the assumption r(Σ) ≤ n, with some constant C > 0
3/2

r(Σ) − 1
kΣk3 r(Σ)
µ1 µr
.
(4.34)
−C 3
|br | ≥
(µ1 − µr )2 ∨ µ2r
n
gr
n
Next note that
p
p
|hθ̂r − θr , ui| ≥ | 1 + br − 1|hθr , ui| − |hθ̂r − 1 + br θr , ui|

p
|br |
√
|hθr , ui| − |hθ̂r − 1 + br θr , ui|
1 + 1 + br
p
|br |
|hθr , ui| − |hθ̂r − 1 + br θr , ui|.
≥
2
Using bounds (4.26) and (4.34), we obtain that for all t ≥ 1 with probability at
least 1 − e−t
r
3/2 


1
kΣk t
r(Σ) − 1
kΣk3 r(Σ)
µ1 µr
|hθ̂r −θr , ui| ≥ |hθr , ui|
−Cγ
−C 3
kuk.
2
(µ1 − µr )2 ∨ µ2r
n
gr
n
gr
n
(4.35)
We will show that there exists a covariance Σ0 ∈ S (r) (rn , a, σ0 , u) such that
|hθr (Σ0 ), ui| ≥ kuk
2 ,
≥

µ1 (Σ0 )µr (Σ0 )
≥ c1
(µ1 (Σ0 ) − µr (Σ0 ))2 ∨ µ2r (Σ0 )
for some constant c1 > 0 that might depend on r, a, σ0 and r(Σ0 ) − 1 ≥ rn /2.
r2
Assuming that such a Σ0 exists, we choose tn → ∞, tn = o( nn ) and applying
bound (4.35) to Σ = Σ0 , we immediately obtain that
r 



 3/2
tn
c1 rn C 3 rn
sup
PΣ |hθ̂r − θr (Σ), ui| ≥
kuk
− Cγ a
− a
8 n
4
n
n
Σ∈S (r) (rn ,a,σ0 ,u)

/Efficient estimation in PCA

23

≥ 1 − e−tn → 1.

Since


r 
 3/2
c
r
C 3 rn
tn
c1 rn
1
n
kuk =
− a
− Cγ a
+ o(1)
kuk,
8 n
4
n
n
8
n

this implies the claim of Proposition 3.1.
It remains to define a Σ0 with the desired properties. Let
Σ0 =

r+1
X

µs Ps ,

s=1

where Ps = θs ⊗ θs , s = 1, . . . r, θ1 , . . . , θr being arbitrary orthonormal vectors
in H and Pr+1 is an orthogonal projection
on
 a d-dimensional subspace of H

s−1
orthogonal to θ1 , . . . , θr . Let µs := µ1 1 − a , s = 1, . . . , r + 1. Then ḡr (Σ0 ) =
0k
and the condition ḡkΣ
≤ a is satisfied. For simplicity, assume that kuk = 1.
r (Σ0 )
Moreover, since θ1 , . . . , θr are arbitrary orthonormal vectors, we can assume
without loss of generality that, for r > 1, u := √12 θ1 + √12 θr . Then hθr (Σ0 ), ui =
√1 > 1 kuk and, by a simple computation,
2
2


X
a2
1 µ1 µr
1
a
µr µs
2
2
.
kPs uk =
=
−
σr (Σ0 ; u) =
(µr − µs )2
2 (µ1 − µr )2
2 (r − 1)2
r−1

µ1
a

s6=r

Assuming that σ02 ≤

1
2



a
a2
(r−1)2 − r−1



, we conclude that the condition σr2 (Σ0 ; u) ≥

σ02 is satisfied. For r = 1, we can assume that u := √12 θ1 + √12 θ2 with a slight
modification of the argument. Finally, we take dimension d = dn so that
r
r 
X
X
µs
µr+1
s − 1 
r
r(Σ0 ) =
+
dn =
1−
+ 1−
dn ∈ (rn /2 + 1, rn ].
µ
µ1
a
a
s=1 1
s=1

Then Σ0 ∈ S (r) (rn , a, σ0 , u). This completes the proof.
5. Proof of Theorem 3.3

δ ,j

Recall that the estimator θ̌r is based on empirical eigenvectors θ̂rj , j = 1, 2, 3
with parameters δj = τ kΣ̂(j) k and with a proper choice of τ (as in Lemma 2.2).
These eigenvectors are in turn defined in terms of empirical spectral projections
δ ,j
P̂r j of sample covariances Σ̂(j) (based on δj -clusters of its spectrum σ(Σ̂(j) )).
We will, however, replace θ̌r by the estimator θ̃r defined in terms of empirical
(j)
(j)
spectral projections P̂r , j = 1, 2, 3, P̂r being the orthogonal projection onto
(j)
direct sum of eigenspaces of Σ̂ corresponding to its eigenvalues λk (Σ̂(j) ), k ∈
(j)
(j)
(j)
∆r . Since card(∆r ) = mr = 1, P̂r = θ̂r ⊗ θ̂r and we can define
(1)

dˆr :=

(2)

hθ̂r , θ̂r i
(2)

(3)

hθ̂r , θ̂r i1/2

/Efficient estimation in PCA

and

24

(1)

θ̃r :=

θ̂r

dˆr ∨ (1/2)

.
δ ,j

(j)

The reduction to this case is based on Lemma 2.2 (implying that P̂r j = P̂r
with a high probability) and is straightforward (as in the proof of Theorem 3.1).
The rest of the proof is based on several lemmas stated and proved below.
Lemma 5.1. Suppose that for some γ ∈ (0, 1) condition (4.2) holds for the
sample covariance Σ̂(2) based on m observations:
EkΣ̂(2) − Σk ≤

(1 − γ)gr
2

(5.1)

Then, for all t ≥ 1 with probability at least 1 − e−t
q
q
q
q q
(n′ )
(m)
(1) (2)
kΣk2
r(Σ) W
t
t
1 + br
.γ g 2
hθ̂r , θ̂r i − 1 + br
m
m
m . (5.2)
r

and with the same probability
(2)

(3)

(m)

hθ̂r , θ̂r i − (1 + br

) .γ

kΣk2
gr2

q

r(Σ)
m

Wq

t
m

q

t
m.

(5.3)

Proof. Obviously, condition (5.1) holds also for the sample covariance Σ̂(2)
(which is based on a sample of the same size m). Moreover, it also holds for
the sample covariance Σ̂(1) based on n′ ≥ m observations since the sequence
n 7→ EkΣ̂n − Σk is non-increasing (see, e.g., Lemma 2.4.5 in [29]).
The following representation is obvious:
q
q
(n′ )
(m)
(1) (2)
hθ̂r , θ̂r i = 1 + br
1 + br hθr , θr i
q
q
(m) (1)
(n′ )
+ 1 + br hθ̂r − 1 + br θr , θr i
q
q
(n′ ) (2)
(m)
+ 1 + br hθ̂r − 1 + br θr , θr i
q
q
(1)
(n′ )
(2)
(m)
hθ̂r − 1 + br θr , θ̂r − 1 + br θr i.
(5.4)

By bound (4.27), with probability at least 1 − e−t
q
q
q q
(n′ )
(1)
kΣk2
r(Σ) W
t
t
|hθ̂r − 1 + br θr , θr i| .γ g2
n′
n′
n′
r

Similarly, with probability at least 1 − e−t
q
q
q q
(m)
(2)
kΣk2
r(Σ) W
t
t
|hθ̂r − 1 + br θr , θr i| .γ g2
m
m
m.
r

(5.5)

(5.6)

/Efficient estimation in PCA

25

To bound the last term in the right hand side of (5.4), we apply bound (4.26)
(1)
to θ̂r conditionally on the second sample (similarly to the proof of Theorem 6
in [15]). This yields that with probability at least 1 − e−t
r
q
q
q
kΣk t (2)
(n′ )
(m)
(m)
(2)
(1)
1 + br θr k.
k
θ̂
−
|hθ̂r − 1 + br θr , θ̂r − 1 + br θr i| .γ
gr
n′ r
(5.7)
On the other hand, under the assumption that hθ̂r , θr i ≥ 0,
q
q
(2)
(m)
(m)
(2)
1 + br − 1
kθ̂r − 1 + br θr k ≤ kθ̂r − θr k +
q
q
(m)
(2)
|b(m) |
(2)
= 2 − 2hθ̂r , θr i + √ r (m) ≤ 2 − 2hθ̂r , θr i2 + |br |
1+br +1
q
(2)
(m)
(2)
(m)
= 2 − 2hP̂r , Pr i + |br | = kP̂r − Pr k2 + |br |.
√
(2)
(m)
≤ 2kP̂r − Pr k + |br |.
By a standard perturbation bound (see, e.g., [15]),
kP̂r(2) − Pr k ≤ 4
Thus,
kθ̂r(2)

kΣ̂(2) − Σk
.
gr

q
√ kΣ̂(2) − Σk
(m)
− 1 + b r θr k ≤ 4 2
+ |b(m)
r |.
gr

(5.8)

Using the exponential bound (2.3) on kΣ̂(2) − Σk and bound (4.21), we obtain
that with probability at least 1 − e−t
r

r
q
kΣk2 r(Σ)
r(Σ) _ r(Σ) _
t _ t
kΣk
(m)
(2)
+ 2
.
θ̂r − 1 + br θr .
gr
m
m
m
m
gr m
(5.9)
q
2

kΣk r(Σ)
r(Σ)
Under assumption (5.1), we have kΣk
gr
m . 1, which implies
gr2
m .
q
kΣk
r(Σ)
gr
m . Thus, the first term in the right hand side of bound (5.9) is dominant.

Moreover, we can drop the term r(Σ)
m and, for t ≤ m, we can also drop the term
kΣk t
Since the left hand side of (5.9) is not larger than
gr m in the right hand side.
q
kΣk
t
2, for t > m, the term gr
m is larger (up to a constant) than the left hand

t
side. Thus, the term kΣk
gr m can be dropped for all the values of t and the bound
(5.9) simplifies as follows
r 
q
r
kΣk
r(Σ) _
t
(m)
(2)
(5.10)
θ̂r − 1 + br θr .
gr
m
m

/Efficient estimation in PCA

26

and it still holds with probability at least 1 − e−t . It follows from bound (5.7)
and (5.10) that for all t ≥ 1 with probability at least 1 − 2e−t
r r
q
q
r
kΣk2
r(Σ) _
t
t
(n′ )
(m)
(2)
(1)
.
|hθ̂r − 1 + br θr , θ̂r − 1 + br θr i| .γ
gr2
m
m
n′
(5.11)
Taking into account that n′ ≥ m, it easily follows from representation (5.4)
and bounds (5.5), (5.6) and (5.11) that with probability at least 1 − e−t
q
q
q
q q
2
(1) (2)
(n′ )
(m)
r(Σ) W
t
t
hθ̂r , θ̂r i − 1 + br
.γ kΣk
1 + br
g2
m
m
m,
r

which proves (5.2). The proof of bound (5.3) is similar.
Define

(1)

(2)

(2)

(3)

hθ̂r , θ̂r i
q
−1
∆1 := q
(n′ )
(m)
1 + br
1 + br

and

∆2 :=

hθ̂r , θ̂r i
(m)

1 + br

− 1.

Assuming that
′

1 + br(n ) ≥ (3/4)2 and 1 + b(m)
≥ (3/4)2 ,
r

(5.12)

we obtain that, for some constant Cγ > 0 and for t ≥ 1 on an event E of
probability at least 1 − e−t
r r
r
kΣk2
r(Σ) _
t
t
.
(5.13)
|∆1 | ∨ |∆2 | ≤ Cγ 2
gr
m
m
m

Next we have

(1)

dˆr =

(2)

hθ̂r , θ̂r i

(1)

(n′ ) 1/2

(2)

hθ̂r , θ̂r i/((1 + br

)

(m) 1/2

(1 + br

)

)

q
(n′ )
1 + br

=
(2) (3)
(2) (3)
(m)
hθ̂r , θ̂r i1/2
hθ̂r , θ̂r i1/2 /(1 + br )1/2
√
q
q
q
1 + ∆1 − 1 + ∆2
1 + ∆1
(n′ )
(n′ )
(n′ )
√
√
1 + br = 1 + br +
1 + br ,
=
1 + ∆2
1 + ∆2
which implies
dˆr −

q
q
(1+∆1 )2 −(1+∆2 )
(n′ )
(n′ )
≤ 1 + br √1+∆ (1+∆ +√1+∆
1 + br
2

≤

1

2|∆1 |+∆21 +|∆2 |
√
√
.
1+∆2 (1+∆1 + 1+∆2 )

2)

(5.14)

Under the assumption that
kΣk2
gr2

r

r(Σ) _
m

r

t
m

r

t
≤ cγ
m

(5.15)

/Efficient estimation in PCA

27

for a sufficiently small constant cγ > 0, bounds (5.14) and (5.13) imply that on
the event E
r r
r
r(Σ) _
t
t
kΣk2
dˆr
q
− 1 .γ
.
(5.16)
gr2
m
m
m
(n′ )
1 + br

Moreover, on the same event E,
q
(n′ )
dˆr ≥ 1 + br −
≥

3
4

−

√

√

2|∆1 |+∆21 +|∆2 |
√
1+∆2 (1+∆1 + 1+∆2 )

2|∆1 |+∆21 +|∆2 |
√
1+∆2 (1+∆1 + 1+∆2 )

≥ 21 ,

(5.17)

q
r r
r
(n′ )
1 + br
kΣk2
r(Σ) _
t
t
− 1 .γ
2
gr
m
m
m
dˆr

and also, using bound (4.21), we obtain that
q
(n′ )
2|∆1 |+∆21 +|∆2 |
√
|dˆr − 1| ≤ | 1 + br − 1| + √1+∆ (1+∆
+ 1+∆
2

≤

(n′ )
|br |

2
r(Σ)
.γ kΣk
gr2
n′

and

+

+

1

(5.18)

2)

2|∆1 |+∆21 +|∆2 |
√
√
1+∆2 (1+∆1 + 1+∆2 )

kΣk2
gr2

q

kΣk2 r(Σ) kΣk2
1
+ 2
− 1 .γ
gr2 n′
gr
dˆr

r(Σ)
m

r

Wq

t
m

r(Σ) _
m

q

r

t
m

t
m.

r

(5.19)

t
.
m

(5.20)

The key ingredient of the proof of Theorem 3.3 is the following lemma.
Lemma 5.2. Suppose that, for some γ ∈ (0, 1), conditions (5.1) and (5.12)
hold. Then, for all t ≥ 1 with probability at least 1 − e−t
hθ̃r − θr , ui − hLr (Σ̂(1) − Σ)θr , ui
q
q W q
2
r(Σ) W
t
t
t
.γ kΣk
g2
m
m
m
m kuk.
r

Proof. We use the following simple representation:
q
(n′ )
(1)
hθ̃r − θr , ui = hθ̂r − 1 + br θr , ui


√

q
(n′ )
(1)
(n′ )
1+br
+ d̂1 − 1 hθ̂r − 1 + br θr , ui +
−
1
hθr , ui
d¯r
r

(5.21)

(5.22)

that holds on the event E (where dˆr ≥ 1/2). Using bounds (5.18) and (5.20)
that both hold under assumption (5.15) on the event E as well as bound (4.26)

/Efficient estimation in PCA

28

(1)

with n = n′ ), we obtain that with probability at least 1 − 2e−t
q
(n′ )
(1)
hθ̃r − θr , ui − hθ̂r − 1 + br θr , ui
q
q q
q
q
2
kΣk2
r(Σ) kΣk
r(Σ) W
t
t
t kΣk
t
.γ kΣk
kuk
+
gr2
n′ gr
n′
gr2
m
m
m gr
n′ kuk
q
q q
2
r(Σ) W
t
t
+ kΣk
g2
m
m
m kuk.

(applied to θ̂r

r

It is easy to check that the last term in the right hand side is dominant yielding
the simpler bound
q
(n′ )
(1)
hθ̃r − θr , ui − hθ̂r − 1 + br θr , ui
q
q q
2
r(Σ) W
t
t
.γ kΣk
(5.23)
2
g
m
m
m kuk
r

that holds under assumption (5.15) with probability at least 1 − e−t . Since the
left hand side is bounded by 5kuk, bound (5.23) also holds trivially when
r r
r
r(Σ) _
t
t
kΣk2
> cγ .
2
gr
m
m
m
(1)

It remains to combine (5.23) with the bound (4.16) (applied to θ̂r ) to complete
the proof.
The following statement is an immediate consequence of Lemma 5.2 and
t
from the bounds since the
Lemma 4.2. As always, we dropped the terms nt′ , m
′
left-hand side is smaller that 3kuk and, for t ≥ n or t ≥ m (the only cases
q when
q

these terms might be needed), it is dominated by the expression with
only.

t
n′ ,

t
m

Corollary 5.1. Suppose that, for some γ ∈ (0, 1), conditions (5.1) and (5.12)
hold. Then, for all t ≥ 1 with probability at least 1 − e−t
q
q
q q
r(Σ) W
kΣk
kΣk2
t
t
t
hθ̃r − θr , ui .γ gr
n′ kuk + g2
m
m
m kuk.
r

Lemma 5.2 implies the following statement. This, in turn, implies Theorem
3.3.
Lemma 5.3. Suppose that m2 ≥ 2nr(Σ) and conditions (5.1) and (5.12) hold
for some γ ∈ (0, 1). For a given u ∈ H, suppose that σr (Σ; u) > 0. Let α ≥ 1.

/Efficient estimation in PCA

29

Then the following bounds holds: for some constants C, Cγ,α > 0,

√
nhθ̃r − θr , ui
≤ x − Φ(x)
sup P
σr (Σ; u)
x∈R
s
s

α
m2 
2
2 _
n log2 nr(Σ)
nr(Σ)
kΣk
m
nr(Σ)
C
γ,α
′ −1/2
kuk
+
log
.
≤ C(n )
+
σr (Σ; u) gr2
m2
nr(Σ)
m2
m2
(5.24)
Moreover, denote
τ1 := Cγ
and



kΣk _ kΣk2
gr
gr2

kΣk2
τ2 := Cγ 2
gr

r

r


nr(Σ)
kuk
m2

n
kuk.
m2

Suppose that Assumptions 3.1 on the loss ℓ holds and c2 τ2 ≤ 1/4. There exist
constants C, Cγ , Cγ,α > 0 such that
√

nhθ̃r −θr ,ui
Eℓ
− Eℓ(Z)
σr (Σ;u)
r


α 
q

m2
2
W
n log2 nr(Σ)
2
C
nr(Σ)
kΣk
nr(Σ)
γ,α
m
c2 A
′ −1/2
kuk +
≤ c1 e
C(n )
+ σr (Σ;u) g2
m2 log nr(Σ)
m2
m2
r

2

2

+2e3/2 (2π)1/4 c1 ec2 τ1 (e−A

2

/2τ12

2

∨ e−A/2τ2 ) + c1 ec2 e−A

2

/4

.

Proof. The proof is similar to that of Lemma 4.8. To prove (5.24), we apply the
first bound of Lemma 4.6 to the random variables
√
nhθ̃r − θr , ui
hLr (Σ̂(1) − Σ)θr , ui
ξ :=
, η :=
.
σr (Σ; u)
σr (Σ; u)


m2
to control δ(ξ, η).
and use the bound of Lemma 5.2 with t = α log nr(Σ)

To prove the bound (5.25), observe that, by bound (5.24), for all t ≥ 1 with
probability at least 1 − e−t
√
|ξ| ≤ τ1 t ∨ τ2 t.
Under assumption c2 τ2 ≤ 1/4, bound (4.28) implies that
√
2 2
Eℓ2 (ξ) ≤ 2e 2πc21 e2c2 τ1 +

Therefore,

√
2 2
ec21
≤ 4e 2πc21 e2c2 τ1 .
1 − 2c2 τ2
2 2

Eℓ(ξ)I(|ξ| ≥ A) ≤ E1/2 ℓ2 (ξ)P1/2 {|ξ| ≥ A} ≤ 2e3/2 (2π)1/4 c1 ec2 τ1 (e−A

2

/2τ12

∨e−A/2τ2 ).

It remains to repeat the rest of the proof of the second statement of Lemma
4.8.

(5.25)

/Efficient estimation in PCA

30

6. Proof of Corollary 3.2
The proof is based on a deterministic bound on |σr2 (Σ̃; u) − σr2 (Σ; u)| for a small
perturbation Σ̃ of Σ provided by the following lemma.
Lemma 6.1. Let mr = 1. Denote E := Σ̃ − Σ and suppose that kEk ≤ gr /4.
Then
kΣk2 kEk
kuk2 .
(6.1)
|σr2 (Σ̃; u) − σr2 (Σ; u)| .
gr2 gr
and

kΣk2 kEk
1
σr (Σ̃; u)
kuk2 .
−1 . 2
σr (Σ; u)
σr (Σ; u) gr2 gr

(6.2)

Proof. We use the Riesz representation of the spectral projector Pr (Σ̃)
I
1
Pr (Σ̃) = −
R (η)dη,
2πi γr Σ̃
where RB (η) = (B − ηI)−1 denotes the resolvent of operator B and γr is the
circle in C with center µr and radius gr /2 (and with counterclockwise orientation). Since kẼk ≤ g4r and mr = 1, it is easy to see that there is only one
eigenvalue µr (Σ̃) of Σ̃ inside γr and that dist(η; σ(Σ̃)) ≥ g4r , η ∈ γr . Note also
that, for all η ∈ γr ,
4
2
(6.3)
kRΣ (η)k ≤ , kRΣ̃ (η)k ≤
gr
gr
and
RΣ̃ (η) − RΣ (η) = (Σ − ηI + E)−1 − (Σ − ηI)−1
h
i
−1
= (I + RΣ (η)E) − I RΣ (η).

(6.4)

It follows that, for all η ∈ γr ,
kRΣ̃ (η) − RΣ (η)k ≤

∞
2
8kEk
2 X
−1
kRΣ (η)Ekk ≤
k (I + RΣ (η)E) − Ik ≤
.
gr
gr
gr2
k=1

(6.5)

Denote A(Σ) := θr (Σ)⊗u+u⊗θr(Σ), B(Σ) := Pr (Σ)⊗Cr (Σ)+Cr (Σ)⊗Pr (Σ)
and
D(Σ) := B(Σ)A(Σ) = θr (Σ) ⊗ Cr (Σ)u + Cr (Σ)u ⊗ θr (Σ).
We have
I
I
∞
X
1
1
dη
RΣ (η) ⊗ RΣ (η)dη =
Ps ⊗ Ps′
2πi γr
2πi
(µ
−
η)(µ
s
s′ − η)
γr
′
s,s =1

=

X
s6=r

1
(Pr ⊗ Ps + Ps ⊗ Pr )
µr − µs

= Pr (Σ) ⊗ Cr (Σ) + Cr (Σ) ⊗ Pr (Σ) = B(Σ). (6.6)

/Efficient estimation in PCA

31

Hence, using (6.3) and (6.5), we derive the following bound for any bounded
operator H :
(B(Σ̃) − B(Σ))H
I
1
[R (η)HRΣ̃ (η) − RΣ (η)HRΣ (η)] dη
=
2πi γr Σ̃
I
1
[(RΣ̃ (η) − RΣ (η))HRΣ̃ (η) + RΣ (η)H(RΣ̃ (η) − RΣ (η))] dη
=
2πi γr


gr 8kEk
24kEkkHk
2
4
≤
≤
+
kHk
.
(6.7)
2 gr2
gr
gr
gr2
Note also that
kA(Σ̃)k ≤ 2kuk,
and, using the bound kCr (Σ)k ≤

(6.8)

1
gr ,

kB(Σ)Hk ≤ kPr (Σ)HCr (Σ)k + kCr (Σ)HPr (Σ)k ≤

2
kHk.
gr

(6.9)

Finally, observe that, by standard perturbation bounds,
kA(Σ̃) − A(Σ)k ≤ 2kθr (Σ̃) − θr (Σ)kkuk
√
≤ 2kPr (Σ̃) − Pr (Σ)k2 kuk ≤ 2 2kPr (Σ̃) − Pr (Σ)k2 kuk
√
8 2kEkkuk
≤
.
gr

(6.10)

It follows from bounds (6.7), (6.8), (6.9) and (6.10) that
kD(Σ̃) − D(Σ)k ≤ k(B(Σ̃) − B(Σ))A(Σ̃)k + kB(Σ)(A(Σ̃) − A(Σ))k
√
48kEkkuk
2
2 8 2kEkkuk
24kEkkA(Σ̃)k
+ kA(Σ̃) − A(Σ)k ≤
+
≤
gr2
gr
gr2
gr
gr
80kEkkuk
≤
.
(6.11)
gr2
Now, recall that
σr2 (Σ; u) = hΣθr (Σ), θr (Σ)ihΣCr (Σ)u, Cr (Σ)ui
2
1 1/2
=
Σ (θr (Σ) ⊗ Cr (Σ)u + Cr (Σ)u ⊗ θr )Σ1/2
2
2
1
1 1/2
= kΣ D(Σ)Σ1/2 k22 = tr(Σ1/2 D(Σ)Σ1/2 Σ1/2 D(Σ)Σ1/2 )
2
2
1
= tr(ΣD(Σ)ΣD(Σ)).
2

(6.12)

/Efficient estimation in PCA

32

Hence, by the duality between operator and nuclear norms and since rank(D(Σ)) ≤
2, rank(D(Σ̃)) ≤ 2, we have that
|σr2 (Σ̃; u) − σr2 (Σ; u)| =
=

tr(Σ̃D(Σ̃)Σ̃D(Σ̃)) − tr(ΣD(Σ)ΣD(Σ))
2
1
tr((Σ̃ − Σ)D(Σ̃)Σ̃D(Σ̃)) + tr(Σ(D(Σ̃) − D(Σ))Σ̃D(Σ̃))
2
+ tr(ΣD(Σ)(Σ̃ − Σ)D(Σ̃)) + tr(ΣD(Σ)Σ(D(Σ̃) − D(Σ)))


1
kΣ̃ − Σk kD(Σ̃)Σ̃D(Σ̃)k1 + kD(Σ̃)ΣD(Σ)k1
2


1
+ kD(Σ̃) − Dk kΣ̃D(Σ̃)Σk1 + kΣD(Σ)Σk1
2


≤

≤ kΣ̃ − Σk kD(Σ̃)Σ̃D(Σ̃)k + kD(Σ̃)ΣD(Σ)k


+ kD(Σ̃) − Dk kΣ̃D(Σ̃)Σk + kΣD(Σ)Σk .

It remains to observe that kCr (Σ)k ≤

1
gr ,

kCr (Σ̃)k ≤

2
gr

and that

kD(Σ)k ≤ 2k(θr (Σ) ⊗ Cr (Σ)u)k ≤ 2kCr (Σ)kkuk ≤

2kuk
,
gr

kD(Σ̃)k ≤ 2k(θr (Σ̃) ⊗ Cr (Σ̃)u)k ≤ 2kCr (Σ̃)kkuk ≤

4kuk
gr

and
kΣ̃k ≤ kΣk + kEk ≤ kΣk +

(6.13)

gr
≤ 2kΣk,
4

implying the bounds
32kΣkkuk2
8kΣkkuk2
, kD(Σ̃)ΣD(Σ)k ≤
,
2
gr
gr2
2kΣk2 kuk
8kΣk2kuk
and kΣD(Σ)Σk ≤
.
kΣ̃D(Σ̃)Σk ≤
gr
gr

kD(Σ̃)Σ̃D(Σ̃)k ≤

(6.14)

Bound (6.1) now follows from (6.13), (6.11) and (6.14). Bound (6.2) follows from
(6.1).
It remains to apply this lemma to Σ̃ = Σ̂ and to use standard bounds on
kΣ̂ − Σk to obtain the following inequalities.
Proposition 6.1. Suppose that condition (4.2) holds for some γ ∈ (0, 1). Then,
there exists a constant cγ > 0 such that for all t ∈ [1, cγ n] with probability at
least 1 − e−t
r 
r
r(Σ) _ t
kΣk3
2
2
kuk2
(6.15)
|σr (Σ̂; u) − σr (Σ; u)| .
gr3
n
n

/Efficient estimation in PCA

and

kΣk3
1
σr (Σ̂; u)
−1 . 2
σr (Σ; u)
σr (Σ; u) gr3

r

r(Σ) _
n

33

r 
t
kuk2 .
n

(6.16)

The consistency of estimator σr (Σ̂; u) immediately follows:
Proposition 6.2. Suppose rn > 1, rn = o(n) as n → ∞. For any sequence
δn → 0 such that rnn = o(δn2 ) as n → ∞,


(Σ̂;u)
supΣ∈S (r) (rn ,a,σ0 ,u) PΣ σσrr (Σ;u)
− 1 ≥ δn → 0 as n → ∞.
Corollary 3.2 can be easily proved using the first statement of Theorem 3.3,
Proposition 6.2 and Lemma 4.6.
7. Proof of Theorem 3.2
Note that the set S̊ (r) (r, a, σ0 , u) is open in nuclear norm topology. This easily
follows from the continuity of functions Σ 7→ kΣk, Σ 7→ ḡr (Σ) and Σ 7→ σr2 (Σ; u)
with respect to the operator norm (for the last function, see Lemma 6.1) and, as
a consequence, with respect to the nuclear norm, and of the functions Σ 7→ tr(Σ)
and Σ 7→ r(Σ)
respect to the nuclear norm.
Pwith
∞
(r)
Let Σ =
µ
(r, a, σ0 , u). Without loss of generality, assume
s=1 s Ps ∈ S̊
PN
that Σ is of finite rank. Otherwise, consider ΣN := s=1 µs Ps . Clearly,
r(ΣN ) ≤ r(Σ) < r

and, for all N > r,
kΣk
kΣN k
=
< a.
ḡr (ΣN )
ḡr (Σ)
Moreover, since kΣN − Σk → 0 as N → ∞, we also have that σr2 (ΣN ; u) →
σr2 (Σ; u) as N → ∞, implying that σr2 (ΣN ; u) > σ02 for all large enough N.
Thus, ΣN ∈ S̊ (r) (r, a, σ0 , u) for a sufficiently large N and we can replace Σ by
ΣN . Assuming that rank(Σ) < ∞, let L := Im(Σ). We can now restrict Σ to
an operator acting from L to L, which is non-singular. In what follows, all the
covariance operators from the class S̊ (r) (r, a, σ0 , u) that are of interest to us will
have L as an image and could be viewed as operators from L to L. For simplicity,
we just assume that H = L is a finite-dimensional space. For a fixed Σ, consider
the following parametric family of perturbations of Σ :
tH
Σt := Σ + √ , |t| ≤ c,
n
where H is a self-adjoint operator and c > 0 is a constant. Denote
SΣ,c := {Σt : t ∈ [−c, c]}.

/Efficient estimation in PCA

34

Since the set S̊ (r) (r, a, σ0 , u) is open in nuclear norm topology, there exists δ > 0
such that the condition
ckHk1
√
< δ,
(7.1)
n
implies that SΣ,c ⊂ S̊ (r) (r, a, σ0 , u). Moreover, we will assume that
δ < kΣ−1 k−1

(7.2)

and

1
ḡr (Σ).
(7.3)
4
Under these assumptions and condition (7.1), Σt is a small enough perturbation
of Σ so that Σt is non-singular and we can define in a standard way the onedimensional spectral projection operator Pt := Pr (Σt ) = θt ⊗ θt , where θt =
θr (Σt ) is the corresponding unit eigenvector as well as operators Ct := Cr (Σt )
and
Lt (H) := Lr (Σt )(H) = Pt HCt + Ct HPt .
δ<

It is easy to see that (for a given c > 0 and large enough n so that the perturbation is small) one can choose t 7→ θt in such a way that hθt , θt′ i ≥ 0, t, t′ ∈ [−c, c].
Based on these definitions, we also define the functions g(t) := hθt , ui and
σ 2 (t) := σr2 (Σt ; u). Concerning the function g, we need the following lemma.
Lemma 7.1. The function g is continuously differentiable in the interval [−c, c]
and the following statements hold:
i)
ii)

√1 hLt (H)θt , ui, t ∈ [−c, c].
n
2
− g ′ (0)| . |t|kHk
gr2 n kuk, t ∈ [−c, c].

g ′ (t) =
|g ′ (t)

Proof. Let δ ∈ (−1, 1). Similarly to (4.17) (see also (6.6) in [15]),
g(t + δ) − g(t) = hθt+δ − θt , ui

p
h(Pt+δ − Pt )θt , ui − ( 1 + h(Pt+δ − Pt )θt , θt i − 1)hθt , ui
p
.
=
1 + h(Pt+δ − Pt )θt , θt i
(7.4)

Applying the first order perturbation expansion (similar to (4.1)) to the spectral
projections Pt , Pt+δ , we obtain that
√
√
Pt+δ − Pt = Lt (δH/ n) + St (δH/ n)
(7.5)
with the remainder term satisfying the bound
√
δ 2 kHk2
= O(δ 2 ).
kSt (δH/ n)k .
gr2 n

(7.6)

Moreover, since Ct θt = 0,
√
1
hLt (δH/ n)θt , θt i = √ h(Pt HCt + Ct HPt )θt , θt i = 0
n

(7.7)

/Efficient estimation in PCA

35

and therefore we have that
|h(Pt+δ − Pt )θt , θt i| .

δ 2 kHk2
= O(δ 2 ).
gr2 n

(7.8)

Hence, using again (7.4), (7.6) and (7.8), we have that
1 hLt (H)θt , ui
g(t + δ) − g(t)
=√
+ O(δ).
δ
n 1 + O(δ)

(7.9)

Passing to the limit as δ → 0 implies the first assertion.
We now prove the second claim. First note that
√
√
|g ′ (t) − g ′ (0)| = |hLt (H/ n)θt − L0 (H/ n)θ0 , ui|
√
√
√
≤ |h(Lt (H/ n) − L0 (H/ n))θt , ui| + |hL0 (H/ n)(θt − θ0 ), ui|
√
√
√
≤ kLt (H/ n) − L0 (H/ n)kkuk + kL0 (H/ n)kkθt − θ0 kkuk.
(7.10)
Also,

√
1
Lt (H/ n) = −
2πi

I

H
RΣt (η) √ RΣt (η)dη,
n
γr

(7.11)

where γr is the circle of radius gr /2 with the center at µr and with counterclockwise orientation. Therefore, by a standard argument already used in the
proof of Lemma 6.1,
√
√
kHk
gr
sup kRΣt (η) − RΣ (η)k(kRΣ (η)k + kRΣt (η)k) √ .
kLt (H/ n) − L0 (H/ n)k ≤
2 η∈γr
n
(7.12)
By (6.3) and (6.5), we have
kRΣ (η)k ≤

2
4
, kRΣt (η)k ≤
gr
gr

and
kRΣt (η) − RΣ (η)k ≤

8 |t|kHk
√ .
gr2
n

Therefore, it follows from (7.12) that
√
√
24|t|kHk2
.
kLt (H/ n) − L0 (H/ n)k ≤
gr2 n
It remains to observe that
kL0 (H)k = kPr HCr + Cr HPr k ≤

2kHk
gr

(7.13)

/Efficient estimation in PCA

and

36

√
4 2|t|kHk
√
kθt − θ0 k ≤ kPt − P0 k2 ≤
gr n

(where we also used the fact that rank(Pt − P0 ) ≤ 2 and kPt − P0 k2 ≤
P0 k). This implies the bound
√
√
8 2|t|kHk2
kL0 (H/ n)kkθt − θ0 kkuk ≤
kuk.
gr2 n

√
2kPt −
(7.14)

The second assertion follows from the bounds (7.10), (7.13) and (7.14).
′
The continuity of the derivative
√ g (t) easily follows from the continuity of the
functions t 7→ θt and t 7→ Lt (H/ n) (which could be proved using representation (7.11)).
We will study the following estimation problem. Let Σ be fixed and let
X1 , . . . , Xn be i.i.d. random variables in H sampled from N (0; Σt ), |t| ≤ c, t being an unknown parameter. The goal is to estimate the function g(t) based on the
observations X1 , . . . , Xn . We will use van Trees inequality to obtain a minimax
lower bound on the risk of estimation of g(t) with respect to quadratic loss. To
this end, let π be a smooth probability density on [−1, 1], satisfying the boundR 1 ′ (s)2
ds < +∞.
ary conditions π(−1) = π(1) = 0 as well the condition Jπ := −1 ππ(s)
 
1
t
Let πc (t) := c π c , t ∈ [−c, c] be a prior on [−c, c]. Then (see e.g. [10]), for any
estimator Tn = Tn (X1 , . . . , Xn ) of g(t) the following bound holds
Z c
sup nEt (Tn − g(t))2 ≥ n
Et (Tn − g(t))2 πc (t)dt
|t|≤c

−c

R

n
≥ Rc

2
c
′
g
(t)π
(t)dt
c
−c

−c In (t)πc (t)dt

+ Jπ c

,

(7.15)

where In (t) = nI(t) denotes the Fisher information for the model
i.i.d.

X1 , . . . , Xn ∼ N (0, Σt ),
t ∈ [−c, c]. Let I(t) := I1 (t). It is well known that the Fisher information for the
model X ∼ N (0; Σ) with non-singular covariance matrix Σ is I(Σ) = 12 (Σ−1 ⊗
Σ−1 ) (see, e.g., [8]). Thus,




dΣt dΣt
n
H
−1
−1 H
In (t) = nI(t) = n I(Σ)
=
(Σt ⊗ Σt ) √ , √
,
dt dt
2
n
n
1
1 −1
−1
−1
hΣt HΣ−1
t , Hi = tr(Σt HΣt H).
2
2
We will now bound the numerator of the expression in the right hand side of
inequality (7.15) from below and its denominator from above.
=

/Efficient estimation in PCA

37

Bound on the numerator. We use Lemma 7.1 to obtain that for some constant
B1 > 0
Z c
2 Z c
2
′
′
′
′
g (t)πc (t)dt =
[g (0) + (g (t) − g (0))]π(t/c)dt/c
−c
−c
Z c
′
2
′
≥ g (0) + 2g (0)
(g ′ (t) − g ′ (0))π(t/c)dt/c
−c
Z c
′
2
′
|g ′ (t) − g ′ (0)|π(t/c)dt/c
≥ g (0) − 2|g (0)|
−c

≥ g ′ (0)2 − B1 c|g ′ (0)|
= g ′ (0)2 − B1 c|g ′ (0)|
=

Z

1

−1

|t|π(t)dt

kHk2
kuk
gr2 n

kHk2
kuk
gr2 n

hLr (H)θr , ui2
B1 ckHk2
− |hLr (H)θr , ui| 2 3/2 kuk.
n
gr n

(7.16)

Bound on the denominator. First note that, by a simple computation,
Jπc = Jπ /c2 .

(7.17)

−1
1
−1
HΣ−1 H).
Then, we need to bound In (t) = 12 tr(Σ−1
t HΣt H) in terms of In (0) = 2 tr(Σ
Assume that
ckΣ−1 Hk
1
√
(7.18)
≤ .
2
n

Arguing as in the proof of Lemma 6.1, we easily get that
"
#
−1
tΣ−1 H
−1
−1
Σt = Σ +
I+ √
− I Σ−1 ,
n
{z
}
|

(7.19)

=:D

where

kDk ≤ 2|t|

kΣ−1 Hk
√
≤ 1.
n

Furthermore, note that

−1
−1
tr Σ−1
HΣ−1 H)+2 tr(DΣ−1 HΣ−1 H)+tr(DΣ−1 HDΣ−1 H).
t HΣt H = tr(Σ

and thus we have that

kDΣ−1 Hk2 kHΣ−1 Dk2
In (t) ≤ In (0) + kDkkΣ−1 HΣ−1 Hk1 +
2


2
|t|kΣ−1 Hk32
kDk
√
kΣ−1 Hk22 ≤ In (0) + 3
.
≤ In (0) + kDk +
2
n

(7.20)

/Efficient estimation in PCA

38

Using (7.20), we obtain the following bound:
Z c
Z
kΣ−1 Hk32 c
In (t)πc (t)dt ≤ In (0) + 3 √
|t|π(t/c)dt/c
n
−c
−c
≤ In (0) +

3ckΣ−1 Hk32
√
.
n

(7.21)

Substituting (7.16), (7.21) and (7.17) into van Trees inequality (7.15) and
taking into account that
In (0) =

1
1
tr(Σ−1 HΣ−1 H) = kΣ−1/2 HΣ−1/2 k22
2
2

and
hLr (H)θr , ui = h(Pr HCr + Cr HPr )θr , ui = hHθr , Cr ui

=

1
hH, θr ⊗ Cr u + Cr u ⊗ θr i = hΣ−1/2 HΣ−1/2 , Σ−1/2 BΣ−1/2 i,
2

where
B :=

1
(Σθr ⊗ ΣCr u + ΣCr u ⊗ Σθr ),
2

we obtain that
sup nEt (Tn − g(t))2

|t|≤c

≥

2

√
hΣ−1/2 HΣ−1/2 , Σ−1/2 BΣ−1/2 i2 − |hΣ−1/2 HΣ−1/2 , Σ−1/2 BΣ−1/2 i| B1gckHk
kuk
2 n
r

1
−1/2 HΣ−1/2 k2
2
2 kΣ

+

3ckΣ−1 Hk32
√
n

+ Jπ /c2

.

(7.22)

In what follows, we set H := B. Note that with this choice of H
1 1/2
kΣ θr ⊗ Σ1/2 Cr u + Σ1/2 Cr u ⊗ Σ1/2 θr k22
2

1  1/2
kΣ θr ⊗Σ1/2 Cr uk22 +kΣ1/2 Cr u⊗Σ1/2 θr k22 = kΣ1/2 θr k2 kΣ1/2 Cr uk2 = σr2 (Σ; u).
=
2
Also, by a simple computation (using that rank(B) = 2), we have that
2kΣ−1/2 BΣ−1/2 k22 =

kΣk2
1 kΣk2
kuk, kBk1 ≤
kuk
kBk ≤ kBk2 ≤ √
gr
2 gr
and that

(7.23)

1 kΣk
kΣ−1 Bk ≤ kΣ−1 Bk2 ≤ √
kuk.
(7.24)
2 gr
These bounds imply that, for any given c > 0 and for all n large enough, H = B
satisfies condition (7.1) for a small enough δ such that SΣ,c ⊂ S̊ (r) (r, a, σ0 , u)
and conditions (7.2), (7.3) hold. Also, H = B satisfies condition (7.18) (for any
given c > 0 and all large enough n).

/Efficient estimation in PCA

39

For H = B, inequality (7.22) becomes
sup nEt (Tn − g(t))2

|t|≤c

≥
≥

2

√
kΣ−1/2 BΣ−1/2 k42 − kΣ−1/2 BΣ−1/2 k22 B1gckBk
2 n kuk
r

1
−1/2 BΣ−1/2 k2
2
2 kΣ


1−

σr2 (Σ; u)

+

B1 ckBk2
√ kuk
2gr2 n
1 2
4 σr (Σ; u)

3ckΣ−1 Bk32
√
n

+ Jπ /c2

3ckΣ−1 Bk32
√
+ Jπ /c2 
n
.
3ckΣ−1 Bk32
2
√
+
J
/c
π
n

+

+

(7.25)

It remains to replace σr2 (Σ; u) with σ 2 (t) = σr2 (Σt ; u). To this end, we use the
bound (6.1) to obtain that for some constant D1 > 0
D1 kΣk2 ckBk
σ 2 (t)
√ kuk2 .
≤
1
+
2
σr2 (Σ; u) gr3
n
t∈[−c,c] σr (Σ; u)
sup

(7.26)

It follows from (7.25) that
nEt (Tn − g(t))2
σ 2 (t)
sup
≥1−
sup
2
σ 2 (t)
t∈[−c,c] σr (Σ; u) |t|≤c

B1 ckBk2
√ kuk
2gr2 n
1 2
4 σr (Σ; u)

3ckΣ−1 Bk32
√
+ Jπ /c2
n
.
3ckΣ−1 Bk32
2
√
+
J
/c
π
n

+

+

(7.27)
Suppose

kΣk4 c
√ kuk3 ≤ 1,
(7.28)
gr4
n
which holds for any given c > 0 and all large enough n and which, in view of
bounds (7.23), implies that
D1
σr2 (Σ; u)

D1 kΣk2 ckBk
√ kuk2 ≤ 1.
σr2 (Σ; u) gr3
n
Under condition (7.28), bounds (7.27) and (7.26) (and also bounds (7.23) and
(7.24)) imply that
EΣ (Tn − hθr (Σ), ui)2
nEt (Tn − g(t))2
≥
sup
σr2 (Σ; u)
σ 2 (t)
|t|≤c
Σ∈S̊ (r) (r,a,σ0 ,u)
sup


≥ 1−
≥


1−

3ckΣ−1 Bk32
√
+ Jπ /c2 
n
1−
3ckΣ−1 Bk32
1 2
2
√
σ
(Σ;
u)
+
+
J
/c
π
r
4
n
B1 a4 kuk3 √cn + 3a3 kuk3 √cn + Jπ /c2 
1
σ02
3 kuk3 √c + J /c2
+
3a
π
4
n
B1 ckBk2
√ kuk
2gr2 n

+

D1 kΣk2 ckBk
√ kuk2
2
σr (Σ; u) gr3
n
−


D1 4
3 c
√
.
a
kuk
σ02
n



(7.29)

It remains to pass to the limit in inequality (7.29) first as n → ∞ and then as
c → ∞ to complete the proof.
A local version of the theorem easily follows from the above arguments since,
for all ε > 0, c > 0 and for all large enough n, SΣ0 ,c ⊂ {Σ : kΣ − Σ0 k1 ≤ ε}.

/Efficient estimation in PCA

40

References
[1] T. W. Anderson. (1963). Asymptotic theory for principal component analysis. Ann. Math. Statist., 34 122148 MR0145620
[2] Q. Berthet and P. Rigollet. (2013). Optimal detection of sparse principal
components in high dimension. Ann. Statist. 41(4), 1780-1815. MR3127849
[3] F. Benaych-Georges and R. R. Nadakuditi. (2011). The eigenvalues and
eigenvectors of finite, low rank perturbations of large random matrices. Adv.
Math., 227(1), 494-521 MR2782201
[4] G. Blanchard, O. Bousquet, and L. Zwald. (2007). Statistical properties of
kernel principal component analysis. Machine Learning, 66(2-3), 259-294.
[5] T.T. Cai and Z. Guo. Confidence Intervals for High-Dimensional Linear
Regression: Minimax Rates and Adaptivity. Ann. Statist., 45(2), 615-646
MR3650395
[6] T. Cai, Z. Ma, and Y. Wu. (2013). Sparse PCA: optimal rates and adaptive
estimation. Ann. Statist., 41(6), 3074-3110 MR3161458
[7] J. Dauxois, A. Pousse, and Y. Romain. (1982). Asymptotic theory for the
principal component analysis of a vector random function: some applications
to statistical inference. J. Multivariate Anal., 12(1), 136-154. MR0650934
[8] M.L. Eaton. (1983). Multivariate Statistics: A Vector Space Approach John
Wiley & Sons, Inc., New York MR0716321
[9] C. Gao and H. Zhou. (2015). Rate-optimal posterior contraction for sparse
PCA. Ann. Statist. 43(2), 785-818 MR3325710
[10] R.D. Gill and B.Y. Levit. (1995). Applications of the van Trees inequality:
a Bayesian Cramér-Rao bound Bernoulli., 1(1-2), 59-79 MR1354456
[11] E. Giné and R. Nickl. (2016). Mathematical foundations of infinitedimensional statistical models. Cambridge University Press, New York.
MR3588285
[12] J. Janková and S. van de Geer. (2016). Semi-parametric efficiency bounds
for high-dimensional models Ann. Statist., to appear
[13] A. Javanmard and A. Montanari. (2014). Confidence intervals and hypothesis testing for high-dimensional regression. J. Mach. Learn. Res. 15,
2869-2909. MR3277152
[14] I. M. Johnstone. (2001). On the distribution of the largest eigenvalue in
principal components analysis. Ann. Statist., 29(2), 295-327 MR1863961
[15] V. Koltchinskii and K. Lounici. (2016). Asymptotics and concentration
bounds for bilinear forms of spectral projectors of sample covariance. Ann.
Inst. Henri Poincaré Probab. Stat. 52(4), 1976-2013. MR3573302
[16] V. Koltchinskii and K. Lounici. (2017). Concentration inequalities and
moment bounds for sample covariance operators. Bernoulli 23(1), 110-133.
MR3556768
[17] V. Koltchinskii and K. Lounici (2017). Normal approximation and concentration of spectral projectors of sample covariance Ann. Statist. 45(1),
121-157. MR3611488
[18] V. Koltchinskii and K. Lounici (2016). New asymptotic results in principal
component analysis. Available at https://arxiv.org/abs/1601.01457

/Efficient estimation in PCA

41

[19] E. Lila, J.A.D Aston, and L.M. Sangalli. (2016). Smooth Principal Component Analysis over two-dimensional manifolds with an application to Neuroimaging. Ann. Appl. Stat. 10(4), 1854-1879. MR3592040
[20] B. Nadler. (2008). Finite sample approximation results for principal component analysis: a matrix perturbation approach. Ann. Statist., 36(6), 27912817. MR2485013
[21] A. Naumov, V. Spokoiny and V. Ulyanov. (2017). Bootstrap confidence sets for spectral projectors of sample covariance. Available at:
https://arxiv.org/pdf/1703.00871.pdf
[22] Y. Ning and H. Liu. (2017). A general theory of hypothesis tests and confidence regions for sparse high dimensional models. Ann. Statist. 45(1),
158-195. MR3611489
[23] D. Paul. (2007). Asymptotics of Sample Eigenstructure for a Large Dimensional Spiked Covariance Model. Statistica Sinica. 17(4), 1617-1642.
MR2399865
[24] J.O. Ramsay and B.W. Silverman. (2005). Functional Data Analysis.
Springer Series in Statistics. Springer, New York. MR2168993
[25] M. Reiss and M. Wahl. (2016). Non-asymptotic upper bounds for the reconstruction error of PCA. Available at https://arxiv.org/abs/1609.03779
[26] Z. Ren, T. Sun, C.H. Zhang, H.H. Zhou. (2015) Asymptotic normality and
optimalities in estimation of large Gaussian graphical models. Ann. Statist.,
43(3), 991-1026. MR3346695
[27] S. van de Geer, P. Bühlmann, Y. Ritov and R. Dezeure. (2014). On asymptotically optimal confidence regions and tests for high-dimensional models.
Ann. of Statist., 42(3), 1166-1202. MR3224285
[28] A.W. van de Vaart. (1998). Asymptotic statistics. Cambridge Series in
Statistical and Probabilistic Mathematics, 3. Cambridge University Press,
Cambridge. MR1652247
[29] A. W. van der Vaart and J. A. Wellner (1996). Weak Convergence and
Empirical Processes. Springer MR1385671
[30] Vershynin, R. (2012) Introduction to the non-asymptotic analysis of random matrices. In: Compressed Sensing, Theory and Applications. Edited by
Y. Eldar and G. Kutyniok, Chapter 5, pp. 210-268, Cambridge University
Press. MR2963170
[31] V. Vu and J. Lei. (2013). Minimax sparse principal subspace estimation in
high dimensions. Ann. Statist., 41(6), 2905-2947. MR161452
[32] T. Wang, Q. Berthet and R.J Samworth. (2016). Statistical and Computational Trade-offs in estimation of sparse principal components. Ann. Statist.,
44(5), 1896-1930. MR3546438
[33] W. Wang and J. Fan. (2017). Asymptotics of empirical eigenstructure
for high dimensional spiked covariance. Ann. Statist., 45(3), 1342-1374.
MR3662457
[34] C.-H. Zhang and S. S. Zhang. (2014). Confidence intervals for low dimensional parameters in high dimensional linear models. J. R. Stat. Soc. Ser.
B. Stat. Methodol., 76(1), 217-242. MR3153940

